libstdc++-v3/include/bits/std_bitset.h

   1 // <bitset> -*- C++ -*-
   2
   3 // Copyright (C) 2001 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  * Copyright (c) 1998
  32  * Silicon Graphics Computer Systems, Inc.
  33  *
  34  * Permission to use, copy, modify, distribute and sell this software
  35  * and its documentation for any purpose is hereby granted without fee,
  36  * provided that the above copyright notice appear in all copies and
  37  * that both that copyright notice and this permission notice appear
  38  * in supporting documentation.  Silicon Graphics makes no
  39  * representations about the suitability of this software for any
  40  * purpose.  It is provided "as is" without express or implied warranty.
  41  */
  42
  43 /** @file std_bitset.h
  44  *  This is an internal header file, included by other library headers.
  45  *  You should not attempt to use it directly.
  46  */
  47
  48 #ifndef __GLIBCPP_BITSET
  49 #define __GLIBCPP_BITSET
  50
  51 #pragma GCC system_header
  52
  53 // A bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused
  54 // bits.  (They are the high- order bits in the highest word.)  It is
  55 // a class invariant of class bitset<> that those unused bits are
  56 // always zero.
  57
  58 // Most of the actual code isn't contained in bitset<> itself, but in the
  59 // base class _Base_bitset.  The base class works with whole words, not with
  60 // individual bits.  This allows us to specialize _Base_bitset for the
  61 // important special case where the bitset is only a single word.
  62
  63
  64 #include <bits/std_cstddef.h>     // for size_t
  65 #include <bits/std_cstring.h>     // for memset
  66 #include <bits/std_string.h>
  67 #include <bits/std_stdexcept.h>
  68 #include <bits/functexcept.h>   // for invalid_argument, out_of_range,
  69                                  // overflow_error
  70 #include <bits/std_ostream.h>     // for ostream (operator<<)
  71 #include <bits/std_istream.h>     // for istream (operator>>)
  72
  73 #define _GLIBCPP_BITSET_BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long))
  74 #define __BITSET_WORDS(__n) \
  75  ((__n) < 1 ? 1 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD)
  76
  77 namespace std
  78 {
  79
  80 // structure to aid in counting bits
  81 template<bool __dummy>
  82 struct _Bit_count {
  83   static unsigned char _S_bit_count[256];
  84 };
  85
  86 // Mapping from 8 bit unsigned integers to the index of the first one
  87 // bit:
  88 template<bool __dummy>
  89 struct _First_one {
  90   static unsigned char _S_first_one[256];
  91 };
  92
  93 //
  94 // Base class: general case.
  95 //
  96
  97 template<size_t _Nw>
  98 struct _Base_bitset {
  99   typedef unsigned long _WordT;
 100
 101   _WordT _M_w[_Nw];                // 0 is the least significant word.
 102
 103   _Base_bitset( void ) { _M_do_reset(); }
 104   _Base_bitset(unsigned long __val) {
 105     _M_do_reset();
 106     _M_w[0] = __val;
 107   }
 108
 109   static size_t _S_whichword( size_t __pos )
 110     { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
 111   static size_t _S_whichbyte( size_t __pos )
 112     { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }
 113   static size_t _S_whichbit( size_t __pos )
 114     { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
 115   static _WordT _S_maskbit( size_t __pos )
 116     { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 117
 118   _WordT& _M_getword(size_t __pos)       { return _M_w[_S_whichword(__pos)]; }
 119   _WordT  _M_getword(size_t __pos) const { return _M_w[_S_whichword(__pos)]; }
 120
 121   _WordT& _M_hiword()       { return _M_w[_Nw - 1]; }
 122   _WordT  _M_hiword() const { return _M_w[_Nw - 1]; }
 123
 124   void _M_do_and(const _Base_bitset<_Nw>& __x) {
 125     for ( size_t __i = 0; __i < _Nw; __i++ ) {
 126       _M_w[__i] &= __x._M_w[__i];
 127     }
 128   }
 129
 130   void _M_do_or(const _Base_bitset<_Nw>& __x) {
 131     for ( size_t __i = 0; __i < _Nw; __i++ ) {
 132       _M_w[__i] |= __x._M_w[__i];
 133     }
 134   }
 135
 136   void _M_do_xor(const _Base_bitset<_Nw>& __x) {
 137     for ( size_t __i = 0; __i < _Nw; __i++ ) {
 138       _M_w[__i] ^= __x._M_w[__i];
 139     }
 140   }
 141
 142   void _M_do_left_shift(size_t __shift);
 143   void _M_do_right_shift(size_t __shift);
 144
 145   void _M_do_flip() {
 146     for ( size_t __i = 0; __i < _Nw; __i++ ) {
 147       _M_w[__i] = ~_M_w[__i];
 148     }
 149   }
 150
 151   void _M_do_set() {
 152     for ( size_t __i = 0; __i < _Nw; __i++ ) {
 153       _M_w[__i] = ~static_cast<_WordT>(0);
 154     }
 155   }
 156
 157   void _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); }
 158
 159   bool _M_is_equal(const _Base_bitset<_Nw>& __x) const {
 160     for (size_t __i = 0; __i < _Nw; ++__i) {
 161       if (_M_w[__i] != __x._M_w[__i])
 162         return false;
 163     }
 164     return true;
 165   }
 166
 167   bool _M_is_any() const {
 168     for ( size_t __i = 0; __i < _Nw; __i++ ) {
 169       if ( _M_w[__i] != static_cast<_WordT>(0) )
 170         return true;
 171     }
 172     return false;
 173   }
 174
 175   size_t _M_do_count() const {
 176     size_t __result = 0;
 177     const unsigned char* __byte_ptr = (const unsigned char*)_M_w;
 178     const unsigned char* __end_ptr = (const unsigned char*)(_M_w+_Nw);
 179
 180     while ( __byte_ptr < __end_ptr ) {
 181       __result += _Bit_count<true>::_S_bit_count[*__byte_ptr];
 182       __byte_ptr++;
 183     }
 184     return __result;
 185   }
 186
 187   unsigned long _M_do_to_ulong() const;
 188
 189   // find first "on" bit
 190   size_t _M_do_find_first(size_t __not_found) const;
 191
 192   // find the next "on" bit that follows "prev"
 193   size_t _M_do_find_next(size_t __prev, size_t __not_found) const;
 194 };
 195
 196 //
 197 // Definitions of non-inline functions from _Base_bitset.
 198 //
 199
 200 template<size_t _Nw>
 201 void _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
 202 {
 203   if (__shift != 0) {
 204     const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
 205     const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
 206
 207     if (__offset == 0)
 208       for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
 209         _M_w[__n] = _M_w[__n - __wshift];
 210
 211     else {
 212       const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
 213       for (size_t __n = _Nw - 1; __n > __wshift; --__n)
 214         _M_w[__n] = (_M_w[__n - __wshift] << __offset) |
 215                     (_M_w[__n - __wshift - 1] >> __sub_offset);
 216       _M_w[__wshift] = _M_w[0] << __offset;
 217     }
 218
 219     fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
 220   }
 221 }
 222
 223 template<size_t _Nw>
 224 void _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
 225 {
 226   if (__shift != 0) {
 227     const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
 228     const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
 229     const size_t __limit = _Nw - __wshift - 1;
 230
 231     if (__offset == 0)
 232       for (size_t __n = 0; __n <= __limit; ++__n)
 233         _M_w[__n] = _M_w[__n + __wshift];
 234
 235     else {
 236       const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
 237       for (size_t __n = 0; __n < __limit; ++__n)
 238         _M_w[__n] = (_M_w[__n + __wshift] >> __offset) |
 239                     (_M_w[__n + __wshift + 1] << __sub_offset);
 240       _M_w[__limit] = _M_w[_Nw-1] >> __offset;
 241     }
 242
 243     fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
 244   }
 245 }
 246
 247 template<size_t _Nw>
 248 unsigned long _Base_bitset<_Nw>::_M_do_to_ulong() const
 249 {
 250   for (size_t __i = 1; __i < _Nw; ++__i)
 251     if (_M_w[__i])
 252       __throw_overflow_error("bitset");
 253
 254   return _M_w[0];
 255 }
 256
 257 template<size_t _Nw>
 258 size_t _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
 259 {
 260   for ( size_t __i = 0; __i < _Nw; __i++ ) {
 261     _WordT __thisword = _M_w[__i];
 262     if ( __thisword != static_cast<_WordT>(0) ) {
 263       // find byte within word
 264       for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
 265         unsigned char __this_byte
 266           = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
 267         if ( __this_byte )
 268           return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
 269             _First_one<true>::_S_first_one[__this_byte];
 270
 271         __thisword >>= CHAR_BIT;
 272       }
 273     }
 274   }
 275   // not found, so return an indication of failure.
 276   return __not_found;
 277 }
 278
 279 template<size_t _Nw>
 280 size_t
 281 _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
 282 {
 283   // make bound inclusive
 284   ++__prev;
 285
 286   // check out of bounds
 287   if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD )
 288     return __not_found;
 289
 290     // search first word
 291   size_t __i = _S_whichword(__prev);
 292   _WordT __thisword = _M_w[__i];
 293
 294     // mask off bits below bound
 295   __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
 296
 297   if ( __thisword != static_cast<_WordT>(0) ) {
 298     // find byte within word
 299     // get first byte into place
 300     __thisword >>= _S_whichbyte(__prev) * CHAR_BIT;
 301     for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) {
 302       unsigned char __this_byte
 303         = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
 304       if ( __this_byte )
 305         return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
 306           _First_one<true>::_S_first_one[__this_byte];
 307
 308       __thisword >>= CHAR_BIT;
 309     }
 310   }
 311
 312   // check subsequent words
 313   __i++;
 314   for ( ; __i < _Nw; __i++ ) {
 315     __thisword = _M_w[__i];
 316     if ( __thisword != static_cast<_WordT>(0) ) {
 317       // find byte within word
 318       for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
 319         unsigned char __this_byte
 320           = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
 321         if ( __this_byte )
 322           return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
 323             _First_one<true>::_S_first_one[__this_byte];
 324
 325         __thisword >>= CHAR_BIT;
 326       }
 327     }
 328   }
 329
 330   // not found, so return an indication of failure.
 331   return __not_found;
 332 } // end _M_do_find_next
 333
 334
 335 // ------------------------------------------------------------
 336
 337 //
 338 // Base class: specialization for a single word.
 339 //
 340
 341 template<> struct _Base_bitset<1> {
 342   typedef unsigned long _WordT;
 343   _WordT _M_w;
 344
 345   _Base_bitset( void ) : _M_w(0) {}
 346   _Base_bitset(unsigned long __val) : _M_w(__val) {}
 347
 348   static size_t _S_whichword( size_t __pos )
 349     { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
 350   static size_t _S_whichbyte( size_t __pos )
 351     { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }
 352   static size_t _S_whichbit( size_t __pos )
 353     {  return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
 354   static _WordT _S_maskbit( size_t __pos )
 355     { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 356
 357   _WordT& _M_getword(size_t)       { return _M_w; }
 358   _WordT  _M_getword(size_t) const { return _M_w; }
 359
 360   _WordT& _M_hiword()       { return _M_w; }
 361   _WordT  _M_hiword() const { return _M_w; }
 362
 363   void _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; }
 364   void _M_do_or(const _Base_bitset<1>& __x)  { _M_w |= __x._M_w; }
 365   void _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; }
 366   void _M_do_left_shift(size_t __shift)     { _M_w <<= __shift; }
 367   void _M_do_right_shift(size_t __shift)    { _M_w >>= __shift; }
 368   void _M_do_flip()                       { _M_w = ~_M_w; }
 369   void _M_do_set()                        { _M_w = ~static_cast<_WordT>(0); }
 370   void _M_do_reset()                      { _M_w = 0; }
 371
 372   bool _M_is_equal(const _Base_bitset<1>& __x) const
 373     { return _M_w == __x._M_w; }
 374   bool _M_is_any() const
 375     { return _M_w != 0; }
 376
 377   size_t _M_do_count() const {
 378     size_t __result = 0;
 379     const unsigned char* __byte_ptr = (const unsigned char*)&_M_w;
 380     const unsigned char* __end_ptr
 381       = ((const unsigned char*)&_M_w)+sizeof(_M_w);
 382     while ( __byte_ptr < __end_ptr ) {
 383       __result += _Bit_count<true>::_S_bit_count[*__byte_ptr];
 384       __byte_ptr++;
 385     }
 386     return __result;
 387   }
 388
 389   unsigned long _M_do_to_ulong() const { return _M_w; }
 390
 391   size_t _M_do_find_first(size_t __not_found) const;
 392
 393   // find the next "on" bit that follows "prev"
 394   size_t _M_do_find_next(size_t __prev, size_t __not_found) const;
 395
 396 };
 397
 398
 399 // ------------------------------------------------------------
 400 // Helper class to zero out the unused high-order bits in the highest word.
 401
 402 template <size_t _Extrabits> struct _Sanitize {
 403   static void _M_do_sanitize(unsigned long& __val)
 404     { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
 405 };
 406
 407 template<> struct _Sanitize<0> {
 408   static void _M_do_sanitize(unsigned long) {}
 409 };
 410
 411
 412
 413 // ------------------------------------------------------------
 414 // Class bitset.
 415 //   _Nb may be any nonzero number of type size_t.
 416
 417 template<size_t _Nb>
 418 class bitset : private _Base_bitset<__BITSET_WORDS(_Nb)>
 419 {
 420 private:
 421   typedef _Base_bitset<__BITSET_WORDS(_Nb)> _Base;
 422   typedef unsigned long _WordT;
 423
 424 private:
 425   void _M_do_sanitize() {
 426     _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>::_M_do_sanitize(this->_M_hiword());
 427   }
 428
 429 public:
 430
 431   // bit reference:
 432   class reference;
 433   friend class reference;
 434
 435   class reference {
 436     friend class bitset;
 437
 438     _WordT *_M_wp;
 439     size_t _M_bpos;
 440
 441     // left undefined
 442     reference();
 443
 444   public:
 445     reference( bitset& __b, size_t __pos ) {
 446       _M_wp = &__b._M_getword(__pos);
 447       _M_bpos = _Base::_S_whichbit(__pos);
 448     }
 449
 450     ~reference() {}
 451
 452     // for b[i] = __x;
 453     reference& operator=(bool __x) {
 454       if ( __x )
 455         *_M_wp |= _Base::_S_maskbit(_M_bpos);
 456       else
 457         *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 458
 459       return *this;
 460     }
 461
 462     // for b[i] = b[__j];
 463     reference& operator=(const reference& __j) {
 464       if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) )
 465         *_M_wp |= _Base::_S_maskbit(_M_bpos);
 466       else
 467         *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 468
 469       return *this;
 470     }
 471
 472     // flips the bit
 473     bool operator~() const
 474       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
 475
 476     // for __x = b[i];
 477     operator bool() const
 478       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
 479
 480     // for b[i].flip();
 481     reference& flip() {
 482       *_M_wp ^= _Base::_S_maskbit(_M_bpos);
 483       return *this;
 484     }
 485   };
 486
 487   // 23.3.5.1 constructors:
 488   bitset() {}
 489   bitset(unsigned long __val) : _Base_bitset<__BITSET_WORDS(_Nb)>(__val)
 490     { _M_do_sanitize(); }
 491
 492   template<class _CharT, class _Traits, class _Alloc>
 493   explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
 494                   size_t __pos = 0)
 495     : _Base()
 496   {
 497     if (__pos > __s.size())
 498       __throw_out_of_range("bitset");
 499     _M_copy_from_string(__s, __pos,
 500                         basic_string<_CharT, _Traits, _Alloc>::npos);
 501   }
 502   template<class _CharT, class _Traits, class _Alloc>
 503   bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
 504          size_t __pos,
 505          size_t __n)
 506     : _Base()
 507   {
 508     if (__pos > __s.size())
 509       __throw_out_of_range("bitset");
 510     _M_copy_from_string(__s, __pos, __n);
 511   }
 512
 513   // 23.3.5.2 bitset operations:
 514   bitset<_Nb>& operator&=(const bitset<_Nb>& __rhs) {
 515     this->_M_do_and(__rhs);
 516     return *this;
 517   }
 518
 519   bitset<_Nb>& operator|=(const bitset<_Nb>& __rhs) {
 520     this->_M_do_or(__rhs);
 521     return *this;
 522   }
 523
 524   bitset<_Nb>& operator^=(const bitset<_Nb>& __rhs) {
 525     this->_M_do_xor(__rhs);
 526     return *this;
 527   }
 528
 529   bitset<_Nb>& operator<<=(size_t __pos) {
 530     this->_M_do_left_shift(__pos);
 531     this->_M_do_sanitize();
 532     return *this;
 533   }
 534
 535   bitset<_Nb>& operator>>=(size_t __pos) {
 536     this->_M_do_right_shift(__pos);
 537     this->_M_do_sanitize();
 538     return *this;
 539   }
 540
 541   //
 542   // Extension:
 543   // Versions of single-bit set, reset, flip, test with no range checking.
 544   //
 545
 546   bitset<_Nb>& _Unchecked_set(size_t __pos) {
 547     this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 548     return *this;
 549   }
 550
 551   bitset<_Nb>& _Unchecked_set(size_t __pos, int __val) {
 552     if (__val)
 553       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 554     else
 555       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 556
 557     return *this;
 558   }
 559
 560   bitset<_Nb>& _Unchecked_reset(size_t __pos) {
 561     this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 562     return *this;
 563   }
 564
 565   bitset<_Nb>& _Unchecked_flip(size_t __pos) {
 566     this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
 567     return *this;
 568   }
 569
 570   bool _Unchecked_test(size_t __pos) const {
 571     return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
 572       != static_cast<_WordT>(0);
 573   }
 574
 575   // Set, reset, and flip.
 576
 577   bitset<_Nb>& set() {
 578     this->_M_do_set();
 579     this->_M_do_sanitize();
 580     return *this;
 581   }
 582
 583   bitset<_Nb>& set(size_t __pos, bool __val = true) {
 584     if (__pos >= _Nb)
 585       __throw_out_of_range("bitset");
 586
 587     return _Unchecked_set(__pos, __val);
 588   }
 589
 590   bitset<_Nb>& reset() {
 591     this->_M_do_reset();
 592     return *this;
 593   }
 594
 595   bitset<_Nb>& reset(size_t __pos) {
 596     if (__pos >= _Nb)
 597       __throw_out_of_range("bitset");
 598
 599     return _Unchecked_reset(__pos);
 600   }
 601
 602   bitset<_Nb>& flip() {
 603     this->_M_do_flip();
 604     this->_M_do_sanitize();
 605     return *this;
 606   }
 607
 608   bitset<_Nb>& flip(size_t __pos) {
 609     if (__pos >= _Nb)
 610       __throw_out_of_range("bitset");
 611
 612     return _Unchecked_flip(__pos);
 613   }
 614
 615   bitset<_Nb> operator~() const {
 616     return bitset<_Nb>(*this).flip();
 617   }
 618
 619   // element access:
 620   //for b[i];
 621   // _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already
 622   // resolves DR 11 (items 1 and 2), but does not do the range-checking
 623   // required by that DR's resolution.  -pme
 624   reference operator[](size_t __pos) { return reference(*this,__pos); }
 625   bool operator[](size_t __pos) const { return _Unchecked_test(__pos); }
 626
 627   unsigned long to_ulong() const { return this->_M_do_to_ulong(); }
 628
 629   template <class _CharT, class _Traits, class _Alloc>
 630   basic_string<_CharT, _Traits, _Alloc> to_string() const {
 631     basic_string<_CharT, _Traits, _Alloc> __result;
 632     _M_copy_to_string(__result);
 633     return __result;
 634   }
 635
 636   // Helper functions for string operations.
 637   template<class _CharT, class _Traits, class _Alloc>
 638   void _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s,
 639                           size_t,
 640                           size_t);
 641
 642   template<class _CharT, class _Traits, class _Alloc>
 643   void _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const;
 644
 645   size_t count() const { return this->_M_do_count(); }
 646
 647   size_t size() const { return _Nb; }
 648
 649   bool operator==(const bitset<_Nb>& __rhs) const {
 650     return this->_M_is_equal(__rhs);
 651   }
 652   bool operator!=(const bitset<_Nb>& __rhs) const {
 653     return !this->_M_is_equal(__rhs);
 654   }
 655
 656   bool test(size_t __pos) const {
 657     if (__pos >= _Nb)
 658       __throw_out_of_range("bitset");
 659
 660     return _Unchecked_test(__pos);
 661   }
 662
 663   bool any() const { return this->_M_is_any(); }
 664   bool none() const { return !this->_M_is_any(); }
 665
 666   bitset<_Nb> operator<<(size_t __pos) const
 667     { return bitset<_Nb>(*this) <<= __pos; }
 668   bitset<_Nb> operator>>(size_t __pos) const
 669     { return bitset<_Nb>(*this) >>= __pos; }
 670
 671   //
 672   // EXTENSIONS: bit-find operations.  These operations are
 673   // experimental, and are subject to change or removal in future
 674   // versions.
 675   //
 676
 677   // find the index of the first "on" bit
 678   size_t _Find_first() const
 679     { return this->_M_do_find_first(_Nb); }
 680
 681   // find the index of the next "on" bit after prev
 682   size_t _Find_next( size_t __prev ) const
 683     { return this->_M_do_find_next(__prev, _Nb); }
 684
 685 };
 686
 687 //
 688 // Definitions of non-inline member functions.
 689 //
 690
 691 template <size_t _Nb>
 692 template<class _CharT, class _Traits, class _Alloc>
 693 void bitset<_Nb>
 694   ::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s,
 695                         size_t __pos,
 696                         size_t __n)
 697 {
 698   reset();
 699   const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos));
 700   for (size_t __i = 0; __i < __nbits; ++__i) {
 701     switch(__s[__pos + __nbits - __i - 1]) {
 702     case '0':
 703       break;
 704     case '1':
 705       set(__i);
 706       break;
 707     default:
 708       __throw_invalid_argument("bitset");
 709     }
 710   }
 711 }
 712
 713 template <size_t _Nb>
 714 template <class _CharT, class _Traits, class _Alloc>
 715 void bitset<_Nb>
 716   ::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const
 717 {
 718   __s.assign(_Nb, '0');
 719
 720   for (size_t __i = 0; __i < _Nb; ++__i)
 721     if (_Unchecked_test(__i))
 722       __s[_Nb - 1 - __i] = '1';
 723 }
 724
 725 // ------------------------------------------------------------
 726
 727 //
 728 // 23.3.5.3 bitset operations:
 729 //
 730
 731 template <size_t _Nb>
 732 inline bitset<_Nb> operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) {
 733   bitset<_Nb> __result(__x);
 734   __result &= __y;
 735   return __result;
 736 }
 737
 738
 739 template <size_t _Nb>
 740 inline bitset<_Nb> operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) {
 741   bitset<_Nb> __result(__x);
 742   __result |= __y;
 743   return __result;
 744 }
 745
 746 template <size_t _Nb>
 747 inline bitset<_Nb> operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) {
 748   bitset<_Nb> __result(__x);
 749   __result ^= __y;
 750   return __result;
 751 }
 752
 753 template <class _CharT, class _Traits, size_t _Nb>
 754 basic_istream<_CharT, _Traits>&
 755 operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
 756 {
 757   typedef typename _Traits::char_type char_type;
 758   basic_string<_CharT, _Traits> __tmp;
 759   __tmp.reserve(_Nb);
 760
 761   // Skip whitespace
 762   typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
 763   if (__sentry) {
 764     basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
 765     for (size_t __i = 0; __i < _Nb; ++__i) {
 766       static typename _Traits::int_type __eof = _Traits::eof();
 767
 768       typename _Traits::int_type __c1 = __buf->sbumpc();
 769       if (_Traits::eq_int_type(__c1, __eof)) {
 770         __is.setstate(ios_base::eofbit);
 771         break;
 772       }
 773       else {
 774         char_type __c2 = _Traits::to_char_type(__c1);
 775         char_type __c  = __is.narrow(__c2, '*');
 776
 777         if (__c == '0' || __c == '1')
 778           __tmp.push_back(__c);
 779         else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof)) {
 780           __is.setstate(ios_base::failbit);
 781           break;
 782         }
 783       }
 784     }
 785
 786     if (__tmp.empty())
 787       __is.setstate(ios_base::failbit);
 788     else
 789       __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
 790   }
 791
 792   return __is;
 793 }
 794
 795 template <class _CharT, class _Traits, size_t _Nb>
 796 basic_ostream<_CharT, _Traits>&
 797 operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x)
 798 {
 799   basic_string<_CharT, _Traits> __tmp;
 800   __x._M_copy_to_string(__tmp);
 801   return __os << __tmp;
 802 }
 803
 804 } // namespace std
 805
 806 #undef __BITSET_WORDS
 807
 808 #endif /* __GLIBCPP_BITSET */
 809
 810
 811 // Local Variables:
 812 // mode:C++
 813 // End:
 814