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
00045
00046
00047
00048
#ifndef _GLIBCXX_BITSET
00049
#define _GLIBCXX_BITSET 1
00050
00051
#pragma GCC system_header
00052
00053
#include <cstddef>
00054
#include <cstring>
00055
#include <limits>
00056
#include <string>
00057
#include <bits/functexcept.h>
00058
00059
#include <ostream>
00060
#include <istream>
00061
00062
#define _GLIBCXX_BITSET_BITS_PER_WORD numeric_limits<unsigned long>::digits
00063
#define _GLIBCXX_BITSET_WORDS(__n) \
00064
((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
00065
/ _GLIBCXX_BITSET_BITS_PER_WORD)
00066
00067
namespace _GLIBCXX_STD
00068 {
00069
00070
00071
00072
00073
00074
00075
00076
00077
template<size_t _Nw>
00078
struct _Base_bitset
00079 {
00080
typedef unsigned long _WordT;
00081
00082
00083 _WordT _M_w[_Nw];
00084
00085 _Base_bitset()
00086 { _M_do_reset(); }
00087
00088 _Base_bitset(
unsigned long __val)
00089 {
00090 _M_do_reset();
00091 _M_w[0] = __val;
00092 }
00093
00094
static size_t
00095 _S_whichword(size_t __pos )
00096 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00097
00098
static size_t
00099 _S_whichbyte(size_t __pos )
00100 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00101
00102
static size_t
00103 _S_whichbit(size_t __pos )
00104 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00105
00106
static _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 _WordT&
00119 _M_hiword()
00120 {
return _M_w[_Nw - 1]; }
00121
00122 _WordT
00123 _M_hiword()
const
00124
{
return _M_w[_Nw - 1]; }
00125
00126
void
00127 _M_do_and(
const _Base_bitset<_Nw>& __x)
00128 {
00129
for (size_t __i = 0; __i < _Nw; __i++)
00130 _M_w[__i] &= __x._M_w[__i];
00131 }
00132
00133
void
00134 _M_do_or(
const _Base_bitset<_Nw>& __x)
00135 {
00136
for (size_t __i = 0; __i < _Nw; __i++)
00137 _M_w[__i] |= __x._M_w[__i];
00138 }
00139
00140
void
00141 _M_do_xor(
const _Base_bitset<_Nw>& __x)
00142 {
00143
for (size_t __i = 0; __i < _Nw; __i++)
00144 _M_w[__i] ^= __x._M_w[__i];
00145 }
00146
00147
void
00148 _M_do_left_shift(size_t __shift);
00149
00150
void
00151 _M_do_right_shift(size_t __shift);
00152
00153
void
00154 _M_do_flip()
00155 {
00156
for (size_t __i = 0; __i < _Nw; __i++)
00157 _M_w[__i] = ~_M_w[__i];
00158 }
00159
00160
void
00161 _M_do_set()
00162 {
00163
for (size_t __i = 0; __i < _Nw; __i++)
00164 _M_w[__i] = ~static_cast<_WordT>(0);
00165 }
00166
00167
void
00168 _M_do_reset()
00169 { std::memset(_M_w, 0, _Nw *
sizeof(_WordT)); }
00170
00171
bool
00172 _M_is_equal(
const _Base_bitset<_Nw>& __x)
const
00173
{
00174
for (size_t __i = 0; __i < _Nw; ++__i)
00175 {
00176
if (_M_w[__i] != __x._M_w[__i])
00177
return false;
00178 }
00179
return true;
00180 }
00181
00182
bool
00183 _M_is_any()
const
00184
{
00185
for (size_t __i = 0; __i < _Nw; __i++)
00186 {
00187
if (_M_w[__i] != static_cast<_WordT>(0))
00188
return true;
00189 }
00190
return false;
00191 }
00192
00193 size_t
00194 _M_do_count()
const
00195
{
00196 size_t __result = 0;
00197
for (size_t __i = 0; __i < _Nw; __i++)
00198 __result += __builtin_popcountl(_M_w[__i]);
00199
return __result;
00200 }
00201
00202
unsigned long
00203 _M_do_to_ulong() const;
00204
00205
00206 size_t
00207 _M_do_find_first(size_t __not_found) const;
00208
00209
00210 size_t
00211 _M_do_find_next(size_t __prev, size_t __not_found) const;
00212 };
00213
00214
00215 template<size_t _Nw>
00216
void
00217 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
00218 {
00219
if (__builtin_expect(__shift != 0, 1))
00220 {
00221
const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
00222
const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
00223
00224
if (__offset == 0)
00225
for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
00226 _M_w[__n] = _M_w[__n - __wshift];
00227
else
00228 {
00229
const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
00230 - __offset);
00231
for (size_t __n = _Nw - 1; __n > __wshift; --__n)
00232 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
00233 | (_M_w[__n - __wshift - 1] >> __sub_offset));
00234 _M_w[__wshift] = _M_w[0] << __offset;
00235 }
00236
00237
std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
00238 }
00239 }
00240
00241
template<size_t _Nw>
00242
void
00243 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
00244 {
00245
if (__builtin_expect(__shift != 0, 1))
00246 {
00247
const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
00248
const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
00249
const size_t __limit = _Nw - __wshift - 1;
00250
00251
if (__offset == 0)
00252
for (size_t __n = 0; __n <= __limit; ++__n)
00253 _M_w[__n] = _M_w[__n + __wshift];
00254
else
00255 {
00256
const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
00257 - __offset);
00258
for (size_t __n = 0; __n < __limit; ++__n)
00259 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
00260 | (_M_w[__n + __wshift + 1] << __sub_offset));
00261 _M_w[__limit] = _M_w[_Nw-1] >> __offset;
00262 }
00263
00264
std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
00265 }
00266 }
00267
00268
template<size_t _Nw>
00269
unsigned long
00270 _Base_bitset<_Nw>::_M_do_to_ulong()
const
00271
{
00272
for (size_t __i = 1; __i < _Nw; ++__i)
00273
if (_M_w[__i])
00274 __throw_overflow_error(__N(
"_Base_bitset::_M_do_to_ulong"));
00275
return _M_w[0];
00276 }
00277
00278
template<size_t _Nw>
00279 size_t
00280 _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found)
const
00281
{
00282
for (size_t __i = 0; __i < _Nw; __i++)
00283 {
00284 _WordT __thisword = _M_w[__i];
00285
if (__thisword != static_cast<_WordT>(0))
00286
return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00287 + __builtin_ctzl(__thisword));
00288 }
00289
00290
return __not_found;
00291 }
00292
00293
template<size_t _Nw>
00294 size_t
00295 _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found)
const
00296
{
00297
00298 ++__prev;
00299
00300
00301
if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
00302
return __not_found;
00303
00304
00305 size_t __i = _S_whichword(__prev);
00306 _WordT __thisword = _M_w[__i];
00307
00308
00309 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
00310
00311
if (__thisword != static_cast<_WordT>(0))
00312
return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00313 + __builtin_ctzl(__thisword));
00314
00315
00316 __i++;
00317
for (; __i < _Nw; __i++)
00318 {
00319 __thisword = _M_w[__i];
00320
if (__thisword != static_cast<_WordT>(0))
00321
return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00322 + __builtin_ctzl(__thisword));
00323 }
00324
00325
return __not_found;
00326 }
00327
00328
00329
00330
00331
00332
00333
00334
00335
template<>
00336
struct _Base_bitset<1>
00337 {
00338
typedef unsigned long _WordT;
00339 _WordT _M_w;
00340
00341 _Base_bitset(
void)
00342 : _M_w(0)
00343 { }
00344
00345 _Base_bitset(
unsigned long __val)
00346 : _M_w(__val)
00347 { }
00348
00349
static size_t
00350 _S_whichword(size_t __pos )
00351 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00352
00353
static size_t
00354 _S_whichbyte(size_t __pos )
00355 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00356
00357
static size_t
00358 _S_whichbit(size_t __pos )
00359 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00360
00361
static _WordT
00362 _S_maskbit(size_t __pos )
00363 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00364
00365 _WordT&
00366 _M_getword(size_t)
00367 {
return _M_w; }
00368
00369 _WordT
00370 _M_getword(size_t)
const
00371
{
return _M_w; }
00372
00373 _WordT&
00374 _M_hiword()
00375 {
return _M_w; }
00376
00377 _WordT
00378 _M_hiword()
const
00379
{
return _M_w; }
00380
00381
void
00382 _M_do_and(
const _Base_bitset<1>& __x)
00383 { _M_w &= __x._M_w; }
00384
00385
void
00386 _M_do_or(
const _Base_bitset<1>& __x)
00387 { _M_w |= __x._M_w; }
00388
00389
void
00390 _M_do_xor(
const _Base_bitset<1>& __x)
00391 { _M_w ^= __x._M_w; }
00392
00393
void
00394 _M_do_left_shift(size_t __shift)
00395 { _M_w <<= __shift; }
00396
00397
void
00398 _M_do_right_shift(size_t __shift)
00399 { _M_w >>= __shift; }
00400
00401
void
00402 _M_do_flip()
00403 { _M_w = ~_M_w; }
00404
00405
void
00406 _M_do_set()
00407 { _M_w = ~static_cast<_WordT>(0); }
00408
00409
void
00410 _M_do_reset()
00411 { _M_w = 0; }
00412
00413
bool
00414 _M_is_equal(
const _Base_bitset<1>& __x)
const
00415
{
return _M_w == __x._M_w; }
00416
00417
bool
00418 _M_is_any()
const
00419
{
return _M_w != 0; }
00420
00421 size_t
00422 _M_do_count()
const
00423
{
return __builtin_popcountl(_M_w); }
00424
00425
unsigned long
00426 _M_do_to_ulong()
const
00427
{
return _M_w; }
00428
00429 size_t
00430 _M_do_find_first(size_t __not_found)
const
00431
{
00432
if (_M_w != 0)
00433
return __builtin_ctzl(_M_w);
00434
else
00435
return __not_found;
00436 }
00437
00438
00439 size_t
00440 _M_do_find_next(size_t __prev, size_t __not_found)
const
00441
{
00442 ++__prev;
00443
if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
00444
return __not_found;
00445
00446 _WordT __x = _M_w >> __prev;
00447
if (__x != 0)
00448
return __builtin_ctzl(__x) + __prev;
00449
else
00450
return __not_found;
00451 }
00452 };
00453
00454
00455
00456
00457
00458
00459
00460
00461
template<>
00462
struct _Base_bitset<0>
00463 {
00464
typedef unsigned long _WordT;
00465
00466 _Base_bitset()
00467 { }
00468
00469 _Base_bitset(
unsigned long)
00470 { }
00471
00472
static size_t
00473 _S_whichword(size_t __pos )
00474 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00475
00476
static size_t
00477 _S_whichbyte(size_t __pos )
00478 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00479
00480
static size_t
00481 _S_whichbit(size_t __pos )
00482 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00483
00484
static _WordT
00485 _S_maskbit(size_t __pos )
00486 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00487
00488
00489
00490
00491
00492
00493
00494
00495 _WordT&
00496 _M_getword(size_t)
const
00497
{
00498 __throw_out_of_range(__N(
"_Base_bitset::_M_getword"));
00499
return *
new _WordT;
00500 }
00501
00502 _WordT
00503 _M_hiword()
const
00504
{
return 0; }
00505
00506
void
00507 _M_do_and(
const _Base_bitset<0>&)
00508 { }
00509
00510
void
00511 _M_do_or(
const _Base_bitset<0>&)
00512 { }
00513
00514
void
00515 _M_do_xor(
const _Base_bitset<0>&)
00516 { }
00517
00518
void
00519 _M_do_left_shift(size_t)
00520 { }
00521
00522
void
00523 _M_do_right_shift(size_t)
00524 { }
00525
00526
void
00527 _M_do_flip()
00528 { }
00529
00530
void
00531 _M_do_set()
00532 { }
00533
00534
void
00535 _M_do_reset()
00536 { }
00537
00538
00539
00540
00541
bool
00542 _M_is_equal(
const _Base_bitset<0>&)
const
00543
{
return true; }
00544
00545
bool
00546 _M_is_any()
const
00547
{
return false; }
00548
00549 size_t
00550 _M_do_count()
const
00551
{
return 0; }
00552
00553
unsigned long
00554 _M_do_to_ulong()
const
00555
{
return 0; }
00556
00557
00558
00559 size_t
00560 _M_do_find_first(size_t)
const
00561
{
return 0; }
00562
00563 size_t
00564 _M_do_find_next(size_t, size_t)
const
00565
{
return 0; }
00566 };
00567
00568
00569
00570
template<size_t _Extrabits>
00571
struct _Sanitize
00572 {
00573
static void _S_do_sanitize(
unsigned long& __val)
00574 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
00575 };
00576
00577
template<>
00578
struct _Sanitize<0>
00579 {
static void _S_do_sanitize(
unsigned long) {} };
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
template<size_t _Nb>
00646 class bitset
00647 :
private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
00648 {
00649
private:
00650
typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
00651
typedef unsigned long _WordT;
00652
00653
void
00654 _M_do_sanitize()
00655 {
00656 _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
00657 _S_do_sanitize(this->_M_hiword());
00658 }
00659
00660
public:
00661
00662
00663
00664
00665
00666
00667
00668
00669
00670
00671
00672
00673 class reference
00674 {
00675
friend class bitset;
00676
00677 _WordT *_M_wp;
00678 size_t _M_bpos;
00679
00680
00681
reference();
00682
00683
public:
00684
reference(
bitset& __b, size_t __pos)
00685 {
00686 _M_wp = &__b._M_getword(__pos);
00687 _M_bpos = _Base::_S_whichbit(__pos);
00688 }
00689
00690 ~
reference()
00691 { }
00692
00693
00694
reference&
00695 operator=(
bool __x)
00696 {
00697
if (__x)
00698 *_M_wp |= _Base::_S_maskbit(_M_bpos);
00699
else
00700 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00701
return *
this;
00702 }
00703
00704
00705
reference&
00706 operator=(
const reference& __j)
00707 {
00708
if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
00709 *_M_wp |= _Base::_S_maskbit(_M_bpos);
00710
else
00711 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00712
return *
this;
00713 }
00714
00715
00716
bool
00717
operator~()
const
00718
{
return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
00719
00720
00721 operator bool()
const
00722
{
return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
00723
00724
00725
reference&
00726
flip()
00727 {
00728 *_M_wp ^= _Base::_S_maskbit(_M_bpos);
00729
return *
this;
00730 }
00731 };
00732
friend class reference;
00733
00734
00735
00736 bitset()
00737 { }
00738
00739
00740 bitset(
unsigned long __val)
00741 : _Base(__val)
00742 { _M_do_sanitize(); }
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
template<
class _CharT,
class _Traits,
class _Alloc>
00754
explicit
00755 bitset(
const basic_string<_CharT, _Traits, _Alloc>& __s,
00756 size_t __position = 0)
00757 : _Base()
00758 {
00759
if (__position > __s.
size())
00760 __throw_out_of_range(__N(
"bitset::bitset initial position "
00761
"not valid"));
00762 _M_copy_from_string(__s, __position,
00763
basic_string<_CharT, _Traits, _Alloc>::npos);
00764 }
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
template<
class _CharT,
class _Traits,
class _Alloc>
00776 bitset(
const basic_string<_CharT, _Traits, _Alloc>& __s,
00777 size_t __position, size_t __n)
00778 : _Base()
00779 {
00780
if (__position > __s.
size())
00781 __throw_out_of_range(__N(
"bitset::bitset initial position "
00782
"not valid"));
00783 _M_copy_from_string(__s, __position, __n);
00784 }
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794
bitset<_Nb>&
00795 operator&=(
const bitset<_Nb>& __rhs)
00796 {
00797 this->_M_do_and(__rhs);
00798
return *
this;
00799 }
00800
00801
bitset<_Nb>&
00802 operator|=(
const bitset<_Nb>& __rhs)
00803 {
00804 this->_M_do_or(__rhs);
00805
return *
this;
00806 }
00807
00808
bitset<_Nb>&
00809 operator^=(
const bitset<_Nb>& __rhs)
00810 {
00811 this->_M_do_xor(__rhs);
00812
return *
this;
00813 }
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
bitset<_Nb>&
00824 operator<<=(size_t __position)
00825 {
00826
if (__builtin_expect(__position < _Nb, 1))
00827 {
00828 this->_M_do_left_shift(__position);
00829 this->_M_do_sanitize();
00830 }
00831
else
00832 this->_M_do_reset();
00833
return *
this;
00834 }
00835
00836
bitset<_Nb>&
00837 operator>>=(size_t __position)
00838 {
00839
if (__builtin_expect(__position < _Nb, 1))
00840 {
00841 this->_M_do_right_shift(__position);
00842 this->_M_do_sanitize();
00843 }
00844
else
00845 this->_M_do_reset();
00846
return *
this;
00847 }
00848
00849
00850
00851
00852
00853
00854
00855
00856
bitset<_Nb>&
00857 _Unchecked_set(size_t __pos)
00858 {
00859 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00860
return *
this;
00861 }
00862
00863
bitset<_Nb>&
00864 _Unchecked_set(size_t __pos,
int __val)
00865 {
00866
if (__val)
00867 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00868
else
00869 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00870
return *
this;
00871 }
00872
00873
bitset<_Nb>&
00874 _Unchecked_reset(size_t __pos)
00875 {
00876 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00877
return *
this;
00878 }
00879
00880
bitset<_Nb>&
00881 _Unchecked_flip(size_t __pos)
00882 {
00883 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
00884
return *
this;
00885 }
00886
00887
bool
00888 _Unchecked_test(size_t __pos)
const
00889
{
return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
00890 != static_cast<_WordT>(0)); }
00891
00892
00893
00894
00895
00896
00897
bitset<_Nb>&
00898 set()
00899 {
00900 this->_M_do_set();
00901 this->_M_do_sanitize();
00902
return *
this;
00903 }
00904
00905
00906
00907
00908
00909
00910
00911
bitset<_Nb>&
00912 set(size_t __position,
bool __val =
true)
00913 {
00914
if (__position >= _Nb)
00915 __throw_out_of_range(__N(
"bitset::set"));
00916
return _Unchecked_set(__position, __val);
00917 }
00918
00919
00920
00921
00922
bitset<_Nb>&
00923 reset()
00924 {
00925 this->_M_do_reset();
00926
return *
this;
00927 }
00928
00929
00930
00931
00932
00933
00934
00935
00936
bitset<_Nb>&
00937 reset(size_t __position)
00938 {
00939
if (__position >= _Nb)
00940 __throw_out_of_range(__N(
"bitset::reset"));
00941
return _Unchecked_reset(__position);
00942 }
00943
00944
00945
00946
00947
bitset<_Nb>&
00948 flip()
00949 {
00950 this->_M_do_flip();
00951 this->_M_do_sanitize();
00952
return *
this;
00953 }
00954
00955
00956
00957
00958
00959
00960
bitset<_Nb>&
00961 flip(size_t __position)
00962 {
00963
if (__position >= _Nb)
00964 __throw_out_of_range(__N(
"bitset::flip"));
00965
return _Unchecked_flip(__position);
00966 }
00967
00968
00969
bitset<_Nb>
00970 operator~()
const
00971
{
return bitset<_Nb>(*this).flip(); }
00972
00973
00974
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00986
00987
00988
00989
00990 reference
00991 operator[](size_t __position)
00992 {
return reference(*
this,__position); }
00993
00994
bool
00995 operator[](size_t __position)
const
00996
{
return _Unchecked_test(__position); }
00997
00998
00999
01000
01001
01002
01003
01004
01005
unsigned long
01006 to_ulong()
const
01007
{
return this->_M_do_to_ulong(); }
01008
01009
01010
01011
01012
01013
01014
01015
01016
01017
01018
01019
01020
01021
01022
01023
template<
class _CharT,
class _Traits,
class _Alloc>
01024
basic_string<_CharT, _Traits, _Alloc>
01025 to_string()
const
01026
{
01027
basic_string<_CharT, _Traits, _Alloc> __result;
01028 _M_copy_to_string(__result);
01029
return __result;
01030 }
01031
01032
01033
template<
class _CharT,
class _Traits,
class _Alloc>
01034
void
01035 _M_copy_from_string(
const basic_string<_CharT, _Traits, _Alloc>& __s,
01036 size_t, size_t);
01037
01038
template<
class _CharT,
class _Traits,
class _Alloc>
01039
void
01040 _M_copy_to_string(
basic_string<_CharT, _Traits, _Alloc>&) const;
01041
01042
01043 size_t
01044 count()
const
01045
{
return this->_M_do_count(); }
01046
01047
01048 size_t
01049 size()
const
01050
{
return _Nb; }
01051
01052
01053
01054
bool
01055 operator==(
const bitset<_Nb>& __rhs)
const
01056
{
return this->_M_is_equal(__rhs); }
01057
01058
bool
01059 operator!=(
const bitset<_Nb>& __rhs)
const
01060
{
return !this->_M_is_equal(__rhs); }
01061
01062
01063
01064
01065
01066
01067
01068
01069
bool
01070 test(size_t __position)
const
01071
{
01072
if (__position >= _Nb)
01073 __throw_out_of_range(__N(
"bitset::test"));
01074
return _Unchecked_test(__position);
01075 }
01076
01077
01078
01079
01080
01081
bool
01082 any()
const
01083
{
return this->_M_is_any(); }
01084
01085
01086
01087
01088
01089
bool
01090 none()
const
01091
{
return !this->_M_is_any(); }
01092
01093
01094
01095
bitset<_Nb>
01096 operator<<(size_t __position)
const
01097
{
return bitset<_Nb>(*this) <<= __position; }
01098
01099
bitset<_Nb>
01100 operator>>(size_t __position)
const
01101
{
return bitset<_Nb>(*this) >>= __position; }
01102
01103
01104
01105
01106
01107
01108
01109
01110 size_t
01111 _Find_first()
const
01112
{
return this->_M_do_find_first(_Nb); }
01113
01114
01115
01116
01117
01118
01119
01120
01121 size_t
01122 _Find_next(size_t __prev )
const
01123
{
return this->_M_do_find_next(__prev, _Nb); }
01124 };
01125
01126
01127
template<size_t _Nb>
01128
template<
class _CharT,
class _Traits,
class _Alloc>
01129
void
01130 bitset<_Nb>::_M_copy_from_string(
const basic_string<_CharT, _Traits,
01131 _Alloc>& __s, size_t __pos, size_t __n)
01132 {
01133
reset();
01134
const size_t __nbits =
std::min(_Nb, std::min(__n, __s.size() - __pos));
01135
for (size_t __i = 0; __i < __nbits; ++__i)
01136 {
01137
switch(__s[__pos + __nbits - __i - 1])
01138 {
01139
case '0':
01140
break;
01141
case '1':
01142
set(__i);
01143
break;
01144
default:
01145 __throw_invalid_argument(__N(
"bitset::_M_copy_from_string"));
01146 }
01147 }
01148 }
01149
01150
template<size_t _Nb>
01151
template<
class _CharT,
class _Traits,
class _Alloc>
01152
void
01153 bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits,
01154 _Alloc>& __s)
const
01155
{
01156 __s.assign(_Nb,
'0');
01157
for (size_t __i = 0; __i < _Nb; ++__i)
01158
if (_Unchecked_test(__i))
01159 __s[_Nb - 1 - __i] =
'1';
01160 }
01161
01162
01163
01164
01165
01166
01167
01168
01169
01170
01171
01172
template<size_t _Nb>
01173
inline bitset<_Nb>
01174 operator&(
const bitset<_Nb>& __x,
const bitset<_Nb>& __y)
01175 {
01176
bitset<_Nb> __result(__x);
01177 __result &= __y;
01178
return __result;
01179 }
01180
01181
template<size_t _Nb>
01182
inline bitset<_Nb>
01183 operator|(
const bitset<_Nb>& __x,
const bitset<_Nb>& __y)
01184 {
01185
bitset<_Nb> __result(__x);
01186 __result |= __y;
01187
return __result;
01188 }
01189
01190
template <size_t _Nb>
01191
inline bitset<_Nb>
01192 operator^(
const bitset<_Nb>& __x,
const bitset<_Nb>& __y)
01193 {
01194
bitset<_Nb> __result(__x);
01195 __result ^= __y;
01196
return __result;
01197 }
01198
01199
01200
01201
01202
01203
01204
01205
01206
01207
01208
01209
template<
class _CharT,
class _Traits, size_t _Nb>
01210 basic_istream<_CharT, _Traits>&
01211 operator>>(
basic_istream<_CharT, _Traits>& __is,
bitset<_Nb>& __x)
01212 {
01213
typedef typename _Traits::char_type char_type;
01214
basic_string<_CharT, _Traits> __tmp;
01215 __tmp.
reserve(_Nb);
01216
01217
ios_base::iostate __state = ios_base::goodbit;
01218
typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
01219
if (__sentry)
01220 {
01221
try
01222 {
01223
basic_streambuf<_CharT, _Traits>* __buf = __is.
rdbuf();
01224
01225
01226
const char_type __zero = __is.
widen(
'0');
01227
const char_type __one = __is.
widen(
'1');
01228
for (size_t __i = 0; __i < _Nb; ++__i)
01229 {
01230
static typename _Traits::int_type __eof = _Traits::eof();
01231
01232
typename _Traits::int_type __c1 = __buf->
sbumpc();
01233
if (_Traits::eq_int_type(__c1, __eof))
01234 {
01235 __state |= ios_base::eofbit;
01236
break;
01237 }
01238
else
01239 {
01240
const char_type __c2 = _Traits::to_char_type(__c1);
01241
if (__c2 == __zero)
01242 __tmp.
push_back(
'0');
01243
else if (__c2 == __one)
01244 __tmp.
push_back(
'1');
01245
else if (_Traits::eq_int_type(__buf->
sputbackc(__c2),
01246 __eof))
01247 {
01248 __state |= ios_base::failbit;
01249
break;
01250 }
01251 }
01252 }
01253 }
01254
catch(...)
01255 { __is._M_setstate(ios_base::badbit); }
01256 }
01257
01258
if (__tmp.
empty() && _Nb)
01259 __state |= ios_base::failbit;
01260
else
01261 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
01262
if (__state)
01263 __is.
setstate(__state);
01264
return __is;
01265 }
01266
01267
template <
class _CharT,
class _Traits, size_t _Nb>
01268 basic_ostream<_CharT, _Traits>&
01269 operator<<(basic_ostream<_CharT, _Traits>& __os,
const bitset<_Nb>& __x)
01270 {
01271
basic_string<_CharT, _Traits> __tmp;
01272 __x._M_copy_to_string(__tmp);
01273
return __os << __tmp;
01274 }
01275
01276 }
01277
01278
#undef _GLIBCXX_BITSET_WORDS
01279
#undef _GLIBCXX_BITSET_BITS_PER_WORD
01280
01281
#ifdef _GLIBCXX_DEBUG
01282
# include <debug/bitset>
01283
#endif
01284
01285
#endif