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

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