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