00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043 #ifndef _GLIBCXX_BITSET
00044 #define _GLIBCXX_BITSET 1
00045
00046 #pragma GCC system_header
00047
00048 #include <cstddef>
00049 #include <string>
00050 #include <bits/functexcept.h>
00051
00052 #include <iosfwd>
00053 #include <cxxabi-forced.h>
00054
00055 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * sizeof(unsigned long))
00056 #define _GLIBCXX_BITSET_WORDS(__n) \
00057 ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
00058 / _GLIBCXX_BITSET_BITS_PER_WORD)
00059
00060 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00061
00062
00063
00064
00065
00066
00067
00068 template<size_t _Nw>
00069 struct _Base_bitset
00070 {
00071 typedef unsigned long _WordT;
00072
00073
00074 _WordT _M_w[_Nw];
00075
00076 _Base_bitset()
00077 { _M_do_reset(); }
00078
00079 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00080 _Base_bitset(unsigned long long __val)
00081 #else
00082 _Base_bitset(unsigned long __val)
00083 #endif
00084 {
00085 _M_do_reset();
00086 _M_w[0] = __val;
00087 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00088 if (sizeof(unsigned long long) > sizeof(unsigned long))
00089 _M_w[1] = __val >> _GLIBCXX_BITSET_BITS_PER_WORD;
00090 #endif
00091 }
00092
00093 static size_t
00094 _S_whichword(size_t __pos )
00095 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00096
00097 static size_t
00098 _S_whichbyte(size_t __pos )
00099 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00100
00101 static size_t
00102 _S_whichbit(size_t __pos )
00103 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00104
00105 static _WordT
00106 _S_maskbit(size_t __pos )
00107 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00108
00109 _WordT&
00110 _M_getword(size_t __pos)
00111 { return _M_w[_S_whichword(__pos)]; }
00112
00113 _WordT
00114 _M_getword(size_t __pos) const
00115 { return _M_w[_S_whichword(__pos)]; }
00116
00117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00118 const _WordT*
00119 _M_getdata() const
00120 { return _M_w; }
00121 #endif
00122
00123 _WordT&
00124 _M_hiword()
00125 { return _M_w[_Nw - 1]; }
00126
00127 _WordT
00128 _M_hiword() const
00129 { return _M_w[_Nw - 1]; }
00130
00131 void
00132 _M_do_and(const _Base_bitset<_Nw>& __x)
00133 {
00134 for (size_t __i = 0; __i < _Nw; __i++)
00135 _M_w[__i] &= __x._M_w[__i];
00136 }
00137
00138 void
00139 _M_do_or(const _Base_bitset<_Nw>& __x)
00140 {
00141 for (size_t __i = 0; __i < _Nw; __i++)
00142 _M_w[__i] |= __x._M_w[__i];
00143 }
00144
00145 void
00146 _M_do_xor(const _Base_bitset<_Nw>& __x)
00147 {
00148 for (size_t __i = 0; __i < _Nw; __i++)
00149 _M_w[__i] ^= __x._M_w[__i];
00150 }
00151
00152 void
00153 _M_do_left_shift(size_t __shift);
00154
00155 void
00156 _M_do_right_shift(size_t __shift);
00157
00158 void
00159 _M_do_flip()
00160 {
00161 for (size_t __i = 0; __i < _Nw; __i++)
00162 _M_w[__i] = ~_M_w[__i];
00163 }
00164
00165 void
00166 _M_do_set()
00167 {
00168 for (size_t __i = 0; __i < _Nw; __i++)
00169 _M_w[__i] = ~static_cast<_WordT>(0);
00170 }
00171
00172 void
00173 _M_do_reset()
00174 { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); }
00175
00176 bool
00177 _M_is_equal(const _Base_bitset<_Nw>& __x) const
00178 {
00179 for (size_t __i = 0; __i < _Nw; ++__i)
00180 if (_M_w[__i] != __x._M_w[__i])
00181 return false;
00182 return true;
00183 }
00184
00185 size_t
00186 _M_are_all_aux() const
00187 {
00188 for (size_t __i = 0; __i < _Nw - 1; __i++)
00189 if (_M_w[__i] != ~static_cast<_WordT>(0))
00190 return 0;
00191 return ((_Nw - 1) * _GLIBCXX_BITSET_BITS_PER_WORD
00192 + __builtin_popcountl(_M_hiword()));
00193 }
00194
00195 bool
00196 _M_is_any() const
00197 {
00198 for (size_t __i = 0; __i < _Nw; __i++)
00199 if (_M_w[__i] != static_cast<_WordT>(0))
00200 return true;
00201 return false;
00202 }
00203
00204 size_t
00205 _M_do_count() const
00206 {
00207 size_t __result = 0;
00208 for (size_t __i = 0; __i < _Nw; __i++)
00209 __result += __builtin_popcountl(_M_w[__i]);
00210 return __result;
00211 }
00212
00213 unsigned long
00214 _M_do_to_ulong() const;
00215
00216 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00217 unsigned long long
00218 _M_do_to_ullong() const;
00219 #endif
00220
00221
00222 size_t
00223 _M_do_find_first(size_t __not_found) const;
00224
00225
00226 size_t
00227 _M_do_find_next(size_t __prev, size_t __not_found) const;
00228 };
00229
00230
00231 template<size_t _Nw>
00232 void
00233 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
00234 {
00235 if (__builtin_expect(__shift != 0, 1))
00236 {
00237 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
00238 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
00239
00240 if (__offset == 0)
00241 for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
00242 _M_w[__n] = _M_w[__n - __wshift];
00243 else
00244 {
00245 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
00246 - __offset);
00247 for (size_t __n = _Nw - 1; __n > __wshift; --__n)
00248 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
00249 | (_M_w[__n - __wshift - 1] >> __sub_offset));
00250 _M_w[__wshift] = _M_w[0] << __offset;
00251 }
00252
00253 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
00254 }
00255 }
00256
00257 template<size_t _Nw>
00258 void
00259 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
00260 {
00261 if (__builtin_expect(__shift != 0, 1))
00262 {
00263 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
00264 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
00265 const size_t __limit = _Nw - __wshift - 1;
00266
00267 if (__offset == 0)
00268 for (size_t __n = 0; __n <= __limit; ++__n)
00269 _M_w[__n] = _M_w[__n + __wshift];
00270 else
00271 {
00272 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
00273 - __offset);
00274 for (size_t __n = 0; __n < __limit; ++__n)
00275 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
00276 | (_M_w[__n + __wshift + 1] << __sub_offset));
00277 _M_w[__limit] = _M_w[_Nw-1] >> __offset;
00278 }
00279
00280 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
00281 }
00282 }
00283
00284 template<size_t _Nw>
00285 unsigned long
00286 _Base_bitset<_Nw>::_M_do_to_ulong() const
00287 {
00288 for (size_t __i = 1; __i < _Nw; ++__i)
00289 if (_M_w[__i])
00290 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
00291 return _M_w[0];
00292 }
00293
00294 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00295 template<size_t _Nw>
00296 unsigned long long
00297 _Base_bitset<_Nw>::_M_do_to_ullong() const
00298 {
00299 const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long);
00300 for (size_t __i = 1 + __dw; __i < _Nw; ++__i)
00301 if (_M_w[__i])
00302 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong"));
00303
00304 if (__dw)
00305 return _M_w[0] + (static_cast<unsigned long long>(_M_w[1])
00306 << _GLIBCXX_BITSET_BITS_PER_WORD);
00307 return _M_w[0];
00308 }
00309 #endif
00310
00311 template<size_t _Nw>
00312 size_t
00313 _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
00314 {
00315 for (size_t __i = 0; __i < _Nw; __i++)
00316 {
00317 _WordT __thisword = _M_w[__i];
00318 if (__thisword != static_cast<_WordT>(0))
00319 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00320 + __builtin_ctzl(__thisword));
00321 }
00322
00323 return __not_found;
00324 }
00325
00326 template<size_t _Nw>
00327 size_t
00328 _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
00329 {
00330
00331 ++__prev;
00332
00333
00334 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
00335 return __not_found;
00336
00337
00338 size_t __i = _S_whichword(__prev);
00339 _WordT __thisword = _M_w[__i];
00340
00341
00342 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
00343
00344 if (__thisword != static_cast<_WordT>(0))
00345 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00346 + __builtin_ctzl(__thisword));
00347
00348
00349 __i++;
00350 for (; __i < _Nw; __i++)
00351 {
00352 __thisword = _M_w[__i];
00353 if (__thisword != static_cast<_WordT>(0))
00354 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00355 + __builtin_ctzl(__thisword));
00356 }
00357
00358 return __not_found;
00359 }
00360
00361
00362
00363
00364
00365
00366 template<>
00367 struct _Base_bitset<1>
00368 {
00369 typedef unsigned long _WordT;
00370 _WordT _M_w;
00371
00372 _Base_bitset(void)
00373 : _M_w(0)
00374 { }
00375
00376 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00377 _Base_bitset(unsigned long long __val)
00378 #else
00379 _Base_bitset(unsigned long __val)
00380 #endif
00381 : _M_w(__val)
00382 { }
00383
00384 static size_t
00385 _S_whichword(size_t __pos )
00386 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00387
00388 static size_t
00389 _S_whichbyte(size_t __pos )
00390 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00391
00392 static size_t
00393 _S_whichbit(size_t __pos )
00394 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00395
00396 static _WordT
00397 _S_maskbit(size_t __pos )
00398 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00399
00400 _WordT&
00401 _M_getword(size_t)
00402 { return _M_w; }
00403
00404 _WordT
00405 _M_getword(size_t) const
00406 { return _M_w; }
00407
00408 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00409 const _WordT*
00410 _M_getdata() const
00411 { return &_M_w; }
00412 #endif
00413
00414 _WordT&
00415 _M_hiword()
00416 { return _M_w; }
00417
00418 _WordT
00419 _M_hiword() const
00420 { return _M_w; }
00421
00422 void
00423 _M_do_and(const _Base_bitset<1>& __x)
00424 { _M_w &= __x._M_w; }
00425
00426 void
00427 _M_do_or(const _Base_bitset<1>& __x)
00428 { _M_w |= __x._M_w; }
00429
00430 void
00431 _M_do_xor(const _Base_bitset<1>& __x)
00432 { _M_w ^= __x._M_w; }
00433
00434 void
00435 _M_do_left_shift(size_t __shift)
00436 { _M_w <<= __shift; }
00437
00438 void
00439 _M_do_right_shift(size_t __shift)
00440 { _M_w >>= __shift; }
00441
00442 void
00443 _M_do_flip()
00444 { _M_w = ~_M_w; }
00445
00446 void
00447 _M_do_set()
00448 { _M_w = ~static_cast<_WordT>(0); }
00449
00450 void
00451 _M_do_reset()
00452 { _M_w = 0; }
00453
00454 bool
00455 _M_is_equal(const _Base_bitset<1>& __x) const
00456 { return _M_w == __x._M_w; }
00457
00458 size_t
00459 _M_are_all_aux() const
00460 { return __builtin_popcountl(_M_w); }
00461
00462 bool
00463 _M_is_any() const
00464 { return _M_w != 0; }
00465
00466 size_t
00467 _M_do_count() const
00468 { return __builtin_popcountl(_M_w); }
00469
00470 unsigned long
00471 _M_do_to_ulong() const
00472 { return _M_w; }
00473
00474 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00475 unsigned long long
00476 _M_do_to_ullong() const
00477 { return _M_w; }
00478 #endif
00479
00480 size_t
00481 _M_do_find_first(size_t __not_found) const
00482 {
00483 if (_M_w != 0)
00484 return __builtin_ctzl(_M_w);
00485 else
00486 return __not_found;
00487 }
00488
00489
00490 size_t
00491 _M_do_find_next(size_t __prev, size_t __not_found) const
00492 {
00493 ++__prev;
00494 if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
00495 return __not_found;
00496
00497 _WordT __x = _M_w >> __prev;
00498 if (__x != 0)
00499 return __builtin_ctzl(__x) + __prev;
00500 else
00501 return __not_found;
00502 }
00503 };
00504
00505
00506
00507
00508
00509
00510 template<>
00511 struct _Base_bitset<0>
00512 {
00513 typedef unsigned long _WordT;
00514
00515 _Base_bitset()
00516 { }
00517
00518 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00519 _Base_bitset(unsigned long long)
00520 #else
00521 _Base_bitset(unsigned long)
00522 #endif
00523 { }
00524
00525 static size_t
00526 _S_whichword(size_t __pos )
00527 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00528
00529 static size_t
00530 _S_whichbyte(size_t __pos )
00531 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00532
00533 static size_t
00534 _S_whichbit(size_t __pos )
00535 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00536
00537 static _WordT
00538 _S_maskbit(size_t __pos )
00539 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00540
00541
00542
00543
00544
00545
00546
00547
00548 _WordT&
00549 _M_getword(size_t) const
00550 {
00551 __throw_out_of_range(__N("_Base_bitset::_M_getword"));
00552 return *new _WordT;
00553 }
00554
00555 _WordT
00556 _M_hiword() const
00557 { return 0; }
00558
00559 void
00560 _M_do_and(const _Base_bitset<0>&)
00561 { }
00562
00563 void
00564 _M_do_or(const _Base_bitset<0>&)
00565 { }
00566
00567 void
00568 _M_do_xor(const _Base_bitset<0>&)
00569 { }
00570
00571 void
00572 _M_do_left_shift(size_t)
00573 { }
00574
00575 void
00576 _M_do_right_shift(size_t)
00577 { }
00578
00579 void
00580 _M_do_flip()
00581 { }
00582
00583 void
00584 _M_do_set()
00585 { }
00586
00587 void
00588 _M_do_reset()
00589 { }
00590
00591
00592
00593
00594 bool
00595 _M_is_equal(const _Base_bitset<0>&) const
00596 { return true; }
00597
00598 size_t
00599 _M_are_all_aux() const
00600 { return 0; }
00601
00602 bool
00603 _M_is_any() const
00604 { return false; }
00605
00606 size_t
00607 _M_do_count() const
00608 { return 0; }
00609
00610 unsigned long
00611 _M_do_to_ulong() const
00612 { return 0; }
00613
00614 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00615 unsigned long long
00616 _M_do_to_ullong() const
00617 { return 0; }
00618 #endif
00619
00620
00621
00622 size_t
00623 _M_do_find_first(size_t) const
00624 { return 0; }
00625
00626 size_t
00627 _M_do_find_next(size_t, size_t) const
00628 { return 0; }
00629 };
00630
00631
00632
00633 template<size_t _Extrabits>
00634 struct _Sanitize
00635 {
00636 static void _S_do_sanitize(unsigned long& __val)
00637 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
00638 };
00639
00640 template<>
00641 struct _Sanitize<0>
00642 { static void _S_do_sanitize(unsigned long) {} };
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660
00661
00662
00663
00664
00665
00666
00667
00668
00669
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707
00708 template<size_t _Nb>
00709 class bitset
00710 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
00711 {
00712 private:
00713 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
00714 typedef unsigned long _WordT;
00715
00716 void
00717 _M_do_sanitize()
00718 {
00719 _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
00720 _S_do_sanitize(this->_M_hiword());
00721 }
00722
00723 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00724 template<typename> friend class hash;
00725 #endif
00726
00727 public:
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740 class reference
00741 {
00742 friend class bitset;
00743
00744 _WordT *_M_wp;
00745 size_t _M_bpos;
00746
00747
00748 reference();
00749
00750 public:
00751 reference(bitset& __b, size_t __pos)
00752 {
00753 _M_wp = &__b._M_getword(__pos);
00754 _M_bpos = _Base::_S_whichbit(__pos);
00755 }
00756
00757 ~reference()
00758 { }
00759
00760
00761 reference&
00762 operator=(bool __x)
00763 {
00764 if (__x)
00765 *_M_wp |= _Base::_S_maskbit(_M_bpos);
00766 else
00767 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00768 return *this;
00769 }
00770
00771
00772 reference&
00773 operator=(const reference& __j)
00774 {
00775 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
00776 *_M_wp |= _Base::_S_maskbit(_M_bpos);
00777 else
00778 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00779 return *this;
00780 }
00781
00782
00783 bool
00784 operator~() const
00785 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
00786
00787
00788 operator bool() const
00789 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
00790
00791
00792 reference&
00793 flip()
00794 {
00795 *_M_wp ^= _Base::_S_maskbit(_M_bpos);
00796 return *this;
00797 }
00798 };
00799 friend class reference;
00800
00801
00802
00803 bitset()
00804 { }
00805
00806
00807 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00808 bitset(unsigned long long __val)
00809 #else
00810 bitset(unsigned long __val)
00811 #endif
00812 : _Base(__val)
00813 { _M_do_sanitize(); }
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824 template<class _CharT, class _Traits, class _Alloc>
00825 explicit
00826 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
00827 size_t __position = 0)
00828 : _Base()
00829 {
00830 if (__position > __s.size())
00831 __throw_out_of_range(__N("bitset::bitset initial position "
00832 "not valid"));
00833 _M_copy_from_string(__s, __position,
00834 std::basic_string<_CharT, _Traits, _Alloc>::npos,
00835 _CharT('0'), _CharT('1'));
00836 }
00837
00838
00839
00840
00841
00842
00843
00844
00845
00846
00847 template<class _CharT, class _Traits, class _Alloc>
00848 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
00849 size_t __position, size_t __n)
00850 : _Base()
00851 {
00852 if (__position > __s.size())
00853 __throw_out_of_range(__N("bitset::bitset initial position "
00854 "not valid"));
00855 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
00856 }
00857
00858
00859
00860 template<class _CharT, class _Traits, class _Alloc>
00861 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
00862 size_t __position, size_t __n,
00863 _CharT __zero, _CharT __one = _CharT('1'))
00864 : _Base()
00865 {
00866 if (__position > __s.size())
00867 __throw_out_of_range(__N("bitset::bitset initial position "
00868 "not valid"));
00869 _M_copy_from_string(__s, __position, __n, __zero, __one);
00870 }
00871
00872 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00873
00874
00875
00876
00877
00878
00879 explicit
00880 bitset(const char* __str)
00881 : _Base()
00882 {
00883 if (!__str)
00884 __throw_logic_error(__N("bitset::bitset(const char*)"));
00885
00886 const size_t __len = __builtin_strlen(__str);
00887 _M_copy_from_ptr<char, std::char_traits<char>>(__str, __len, 0,
00888 __len, '0', '1');
00889 }
00890 #endif
00891
00892
00893
00894
00895
00896
00897
00898
00899
00900 bitset<_Nb>&
00901 operator&=(const bitset<_Nb>& __rhs)
00902 {
00903 this->_M_do_and(__rhs);
00904 return *this;
00905 }
00906
00907 bitset<_Nb>&
00908 operator|=(const bitset<_Nb>& __rhs)
00909 {
00910 this->_M_do_or(__rhs);
00911 return *this;
00912 }
00913
00914 bitset<_Nb>&
00915 operator^=(const bitset<_Nb>& __rhs)
00916 {
00917 this->_M_do_xor(__rhs);
00918 return *this;
00919 }
00920
00921
00922
00923
00924
00925
00926
00927
00928
00929 bitset<_Nb>&
00930 operator<<=(size_t __position)
00931 {
00932 if (__builtin_expect(__position < _Nb, 1))
00933 {
00934 this->_M_do_left_shift(__position);
00935 this->_M_do_sanitize();
00936 }
00937 else
00938 this->_M_do_reset();
00939 return *this;
00940 }
00941
00942 bitset<_Nb>&
00943 operator>>=(size_t __position)
00944 {
00945 if (__builtin_expect(__position < _Nb, 1))
00946 {
00947 this->_M_do_right_shift(__position);
00948 this->_M_do_sanitize();
00949 }
00950 else
00951 this->_M_do_reset();
00952 return *this;
00953 }
00954
00955
00956
00957
00958
00959
00960
00961
00962 bitset<_Nb>&
00963 _Unchecked_set(size_t __pos)
00964 {
00965 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00966 return *this;
00967 }
00968
00969 bitset<_Nb>&
00970 _Unchecked_set(size_t __pos, int __val)
00971 {
00972 if (__val)
00973 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00974 else
00975 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00976 return *this;
00977 }
00978
00979 bitset<_Nb>&
00980 _Unchecked_reset(size_t __pos)
00981 {
00982 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00983 return *this;
00984 }
00985
00986 bitset<_Nb>&
00987 _Unchecked_flip(size_t __pos)
00988 {
00989 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
00990 return *this;
00991 }
00992
00993 bool
00994 _Unchecked_test(size_t __pos) const
00995 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
00996 != static_cast<_WordT>(0)); }
00997
00998
00999
01000
01001
01002
01003 bitset<_Nb>&
01004 set()
01005 {
01006 this->_M_do_set();
01007 this->_M_do_sanitize();
01008 return *this;
01009 }
01010
01011
01012
01013
01014
01015
01016
01017 bitset<_Nb>&
01018 set(size_t __position, bool __val = true)
01019 {
01020 if (__position >= _Nb)
01021 __throw_out_of_range(__N("bitset::set"));
01022 return _Unchecked_set(__position, __val);
01023 }
01024
01025
01026
01027
01028 bitset<_Nb>&
01029 reset()
01030 {
01031 this->_M_do_reset();
01032 return *this;
01033 }
01034
01035
01036
01037
01038
01039
01040
01041
01042 bitset<_Nb>&
01043 reset(size_t __position)
01044 {
01045 if (__position >= _Nb)
01046 __throw_out_of_range(__N("bitset::reset"));
01047 return _Unchecked_reset(__position);
01048 }
01049
01050
01051
01052
01053 bitset<_Nb>&
01054 flip()
01055 {
01056 this->_M_do_flip();
01057 this->_M_do_sanitize();
01058 return *this;
01059 }
01060
01061
01062
01063
01064
01065
01066 bitset<_Nb>&
01067 flip(size_t __position)
01068 {
01069 if (__position >= _Nb)
01070 __throw_out_of_range(__N("bitset::flip"));
01071 return _Unchecked_flip(__position);
01072 }
01073
01074
01075 bitset<_Nb>
01076 operator~() const
01077 { return bitset<_Nb>(*this).flip(); }
01078
01079
01080
01081
01082
01083
01084
01085
01086
01087
01088
01089
01090
01091
01092
01093
01094 reference
01095 operator[](size_t __position)
01096 { return reference(*this,__position); }
01097
01098 bool
01099 operator[](size_t __position) const
01100 { return _Unchecked_test(__position); }
01101
01102
01103
01104
01105
01106
01107
01108
01109 unsigned long
01110 to_ulong() const
01111 { return this->_M_do_to_ulong(); }
01112
01113 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01114 unsigned long long
01115 to_ullong() const
01116 { return this->_M_do_to_ullong(); }
01117 #endif
01118
01119
01120
01121
01122
01123
01124
01125
01126
01127 template<class _CharT, class _Traits, class _Alloc>
01128 std::basic_string<_CharT, _Traits, _Alloc>
01129 to_string() const
01130 {
01131 std::basic_string<_CharT, _Traits, _Alloc> __result;
01132 _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
01133 return __result;
01134 }
01135
01136
01137
01138 template<class _CharT, class _Traits, class _Alloc>
01139 std::basic_string<_CharT, _Traits, _Alloc>
01140 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
01141 {
01142 std::basic_string<_CharT, _Traits, _Alloc> __result;
01143 _M_copy_to_string(__result, __zero, __one);
01144 return __result;
01145 }
01146
01147
01148
01149 template<class _CharT, class _Traits>
01150 std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
01151 to_string() const
01152 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
01153
01154
01155
01156 template<class _CharT, class _Traits>
01157 std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
01158 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
01159 { return to_string<_CharT, _Traits,
01160 std::allocator<_CharT> >(__zero, __one); }
01161
01162 template<class _CharT>
01163 std::basic_string<_CharT, std::char_traits<_CharT>,
01164 std::allocator<_CharT> >
01165 to_string() const
01166 {
01167 return to_string<_CharT, std::char_traits<_CharT>,
01168 std::allocator<_CharT> >();
01169 }
01170
01171 template<class _CharT>
01172 std::basic_string<_CharT, std::char_traits<_CharT>,
01173 std::allocator<_CharT> >
01174 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
01175 {
01176 return to_string<_CharT, std::char_traits<_CharT>,
01177 std::allocator<_CharT> >(__zero, __one);
01178 }
01179
01180 std::basic_string<char, std::char_traits<char>, std::allocator<char> >
01181 to_string() const
01182 {
01183 return to_string<char, std::char_traits<char>,
01184 std::allocator<char> >();
01185 }
01186
01187 std::basic_string<char, std::char_traits<char>, std::allocator<char> >
01188 to_string(char __zero, char __one = '1') const
01189 {
01190 return to_string<char, std::char_traits<char>,
01191 std::allocator<char> >(__zero, __one);
01192 }
01193
01194
01195 template<class _CharT, class _Traits>
01196 void
01197 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
01198 _CharT, _CharT);
01199
01200 template<class _CharT, class _Traits, class _Alloc>
01201 void
01202 _M_copy_from_string(const std::basic_string<_CharT,
01203 _Traits, _Alloc>& __s, size_t __pos, size_t __n,
01204 _CharT __zero, _CharT __one)
01205 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
01206 __zero, __one); }
01207
01208 template<class _CharT, class _Traits, class _Alloc>
01209 void
01210 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
01211 _CharT, _CharT) const;
01212
01213
01214 template<class _CharT, class _Traits, class _Alloc>
01215 void
01216 _M_copy_from_string(const std::basic_string<_CharT,
01217 _Traits, _Alloc>& __s, size_t __pos, size_t __n)
01218 { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); }
01219
01220 template<class _CharT, class _Traits, class _Alloc>
01221 void
01222 _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const
01223 { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); }
01224
01225
01226 size_t
01227 count() const
01228 { return this->_M_do_count(); }
01229
01230
01231 size_t
01232 size() const
01233 { return _Nb; }
01234
01235
01236
01237 bool
01238 operator==(const bitset<_Nb>& __rhs) const
01239 { return this->_M_is_equal(__rhs); }
01240
01241 bool
01242 operator!=(const bitset<_Nb>& __rhs) const
01243 { return !this->_M_is_equal(__rhs); }
01244
01245
01246
01247
01248
01249
01250
01251
01252 bool
01253 test(size_t __position) const
01254 {
01255 if (__position >= _Nb)
01256 __throw_out_of_range(__N("bitset::test"));
01257 return _Unchecked_test(__position);
01258 }
01259
01260
01261
01262
01263
01264
01265
01266 bool
01267 all() const
01268 { return this->_M_are_all_aux() == _Nb; }
01269
01270
01271
01272
01273
01274 bool
01275 any() const
01276 { return this->_M_is_any(); }
01277
01278
01279
01280
01281
01282 bool
01283 none() const
01284 { return !this->_M_is_any(); }
01285
01286
01287
01288 bitset<_Nb>
01289 operator<<(size_t __position) const
01290 { return bitset<_Nb>(*this) <<= __position; }
01291
01292 bitset<_Nb>
01293 operator>>(size_t __position) const
01294 { return bitset<_Nb>(*this) >>= __position; }
01295
01296
01297
01298
01299
01300
01301
01302
01303 size_t
01304 _Find_first() const
01305 { return this->_M_do_find_first(_Nb); }
01306
01307
01308
01309
01310
01311
01312
01313
01314 size_t
01315 _Find_next(size_t __prev ) const
01316 { return this->_M_do_find_next(__prev, _Nb); }
01317 };
01318
01319
01320 template<size_t _Nb>
01321 template<class _CharT, class _Traits>
01322 void
01323 bitset<_Nb>::
01324 _M_copy_from_ptr(const _CharT* __s, size_t __len,
01325 size_t __pos, size_t __n, _CharT __zero, _CharT __one)
01326 {
01327 reset();
01328 const size_t __nbits = std::min(_Nb, std::min(__n, __len - __pos));
01329 for (size_t __i = __nbits; __i > 0; --__i)
01330 {
01331 const _CharT __c = __s[__pos + __nbits - __i];
01332 if (_Traits::eq(__c, __zero))
01333 ;
01334 else if (_Traits::eq(__c, __one))
01335 _Unchecked_set(__i - 1);
01336 else
01337 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
01338 }
01339 }
01340
01341 template<size_t _Nb>
01342 template<class _CharT, class _Traits, class _Alloc>
01343 void
01344 bitset<_Nb>::
01345 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
01346 _CharT __zero, _CharT __one) const
01347 {
01348 __s.assign(_Nb, __zero);
01349 for (size_t __i = _Nb; __i > 0; --__i)
01350 if (_Unchecked_test(__i - 1))
01351 _Traits::assign(__s[_Nb - __i], __one);
01352 }
01353
01354
01355
01356
01357
01358
01359
01360
01361
01362
01363
01364 template<size_t _Nb>
01365 inline bitset<_Nb>
01366 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01367 {
01368 bitset<_Nb> __result(__x);
01369 __result &= __y;
01370 return __result;
01371 }
01372
01373 template<size_t _Nb>
01374 inline bitset<_Nb>
01375 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01376 {
01377 bitset<_Nb> __result(__x);
01378 __result |= __y;
01379 return __result;
01380 }
01381
01382 template <size_t _Nb>
01383 inline bitset<_Nb>
01384 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01385 {
01386 bitset<_Nb> __result(__x);
01387 __result ^= __y;
01388 return __result;
01389 }
01390
01391
01392
01393
01394
01395
01396
01397
01398
01399
01400
01401 template<class _CharT, class _Traits, size_t _Nb>
01402 std::basic_istream<_CharT, _Traits>&
01403 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
01404 {
01405 typedef typename _Traits::char_type char_type;
01406 typedef std::basic_istream<_CharT, _Traits> __istream_type;
01407 typedef typename __istream_type::ios_base __ios_base;
01408
01409 std::basic_string<_CharT, _Traits> __tmp;
01410 __tmp.reserve(_Nb);
01411
01412
01413
01414 const char_type __zero = __is.widen('0');
01415 const char_type __one = __is.widen('1');
01416
01417 typename __ios_base::iostate __state = __ios_base::goodbit;
01418 typename __istream_type::sentry __sentry(__is);
01419 if (__sentry)
01420 {
01421 __try
01422 {
01423 for (size_t __i = _Nb; __i > 0; --__i)
01424 {
01425 static typename _Traits::int_type __eof = _Traits::eof();
01426
01427 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
01428 if (_Traits::eq_int_type(__c1, __eof))
01429 {
01430 __state |= __ios_base::eofbit;
01431 break;
01432 }
01433 else
01434 {
01435 const char_type __c2 = _Traits::to_char_type(__c1);
01436 if (_Traits::eq(__c2, __zero))
01437 __tmp.push_back(__zero);
01438 else if (_Traits::eq(__c2, __one))
01439 __tmp.push_back(__one);
01440 else if (_Traits::
01441 eq_int_type(__is.rdbuf()->sputbackc(__c2),
01442 __eof))
01443 {
01444 __state |= __ios_base::failbit;
01445 break;
01446 }
01447 }
01448 }
01449 }
01450 __catch(__cxxabiv1::__forced_unwind&)
01451 {
01452 __is._M_setstate(__ios_base::badbit);
01453 __throw_exception_again;
01454 }
01455 __catch(...)
01456 { __is._M_setstate(__ios_base::badbit); }
01457 }
01458
01459 if (__tmp.empty() && _Nb)
01460 __state |= __ios_base::failbit;
01461 else
01462 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
01463 __zero, __one);
01464 if (__state)
01465 __is.setstate(__state);
01466 return __is;
01467 }
01468
01469 template <class _CharT, class _Traits, size_t _Nb>
01470 std::basic_ostream<_CharT, _Traits>&
01471 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01472 const bitset<_Nb>& __x)
01473 {
01474 std::basic_string<_CharT, _Traits> __tmp;
01475
01476
01477
01478 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
01479 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
01480 return __os << __tmp;
01481 }
01482
01483
01484 _GLIBCXX_END_NESTED_NAMESPACE
01485
01486 #undef _GLIBCXX_BITSET_WORDS
01487 #undef _GLIBCXX_BITSET_BITS_PER_WORD
01488
01489 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01490
01491 #include <bits/functional_hash.h>
01492
01493 _GLIBCXX_BEGIN_NAMESPACE(std)
01494
01495
01496
01497 template<size_t _Nb>
01498 struct hash<_GLIBCXX_STD_D::bitset<_Nb>>
01499 : public std::unary_function<_GLIBCXX_STD_D::bitset<_Nb>, size_t>
01500 {
01501 size_t
01502 operator()(const _GLIBCXX_STD_D::bitset<_Nb>& __b) const
01503 {
01504 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
01505 return std::_Fnv_hash::hash(__b._M_getdata(), __clength);
01506 }
01507 };
01508
01509 template<>
01510 struct hash<_GLIBCXX_STD_D::bitset<0>>
01511 : public std::unary_function<_GLIBCXX_STD_D::bitset<0>, size_t>
01512 {
01513 size_t
01514 operator()(const _GLIBCXX_STD_D::bitset<0>&) const
01515 { return 0; }
01516 };
01517
01518 _GLIBCXX_END_NAMESPACE
01519
01520 #endif // __GXX_EXPERIMENTAL_CXX0X__
01521
01522 #ifdef _GLIBCXX_DEBUG
01523 # include <debug/bitset>
01524 #endif
01525
01526 #ifdef _GLIBCXX_PROFILE
01527 # include <profile/bitset>
01528 #endif
01529
01530 #endif