contrib/gcc-4.1/libstdc++-v3/include/std/std_bitset.h

   1 // <bitset> -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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 bitset
  44  *  This is a Standard C++ Library header.
  45  */
  46
  47 #ifndef _GLIBCXX_BITSET
  48 #define _GLIBCXX_BITSET 1
  49
  50 #pragma GCC system_header
  51
  52 #include <cstddef>     // For size_t
  53 #include <cstring>     // For memset
  54 #include <limits>      // For numeric_limits
  55 #include <string>
  56 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
  57                                 // overflow_error
  58 #include <ostream>     // For ostream (operator<<)
  59 #include <istream>     // For istream (operator>>)
  60
  61 #define _GLIBCXX_BITSET_BITS_PER_WORD  numeric_limits<unsigned long>::digits
  62 #define _GLIBCXX_BITSET_WORDS(__n) \
  63  ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
  64                   / _GLIBCXX_BITSET_BITS_PER_WORD)
  65
  66 namespace _GLIBCXX_STD
  67 {
  68   /**
  69    *  @if maint
  70    *  Base class, general case.  It is a class inveriant that _Nw will be
  71    *  nonnegative.
  72    *
  73    *  See documentation for bitset.
  74    *  @endif
  75   */
  76   template<size_t _Nw>
  77     struct _Base_bitset
  78     {
  79       typedef unsigned long _WordT;
  80
  81       /// 0 is the least significant word.
  82       _WordT            _M_w[_Nw];
  83
  84       _Base_bitset()
  85       { _M_do_reset(); }
  86
  87       _Base_bitset(unsigned long __val)
  88       {
  89         _M_do_reset();
  90         _M_w[0] = __val;
  91       }
  92
  93       static size_t
  94       _S_whichword(size_t __pos )
  95       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
  96
  97       static size_t
  98       _S_whichbyte(size_t __pos )
  99       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
 100
 101       static size_t
 102       _S_whichbit(size_t __pos )
 103       { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
 104
 105       static _WordT
 106       _S_maskbit(size_t __pos )
 107       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 108
 109       _WordT&
 110       _M_getword(size_t __pos)
 111       { return _M_w[_S_whichword(__pos)]; }
 112
 113       _WordT
 114       _M_getword(size_t __pos) const
 115       { return _M_w[_S_whichword(__pos)]; }
 116
 117       _WordT&
 118       _M_hiword()
 119       { return _M_w[_Nw - 1]; }
 120
 121       _WordT
 122       _M_hiword() const
 123       { return _M_w[_Nw - 1]; }
 124
 125       void
 126       _M_do_and(const _Base_bitset<_Nw>& __x)
 127       {
 128         for (size_t __i = 0; __i < _Nw; __i++)
 129           _M_w[__i] &= __x._M_w[__i];
 130       }
 131
 132       void
 133       _M_do_or(const _Base_bitset<_Nw>& __x)
 134       {
 135         for (size_t __i = 0; __i < _Nw; __i++)
 136           _M_w[__i] |= __x._M_w[__i];
 137       }
 138
 139       void
 140       _M_do_xor(const _Base_bitset<_Nw>& __x)
 141       {
 142         for (size_t __i = 0; __i < _Nw; __i++)
 143           _M_w[__i] ^= __x._M_w[__i];
 144       }
 145
 146       void
 147       _M_do_left_shift(size_t __shift);
 148
 149       void
 150       _M_do_right_shift(size_t __shift);
 151
 152       void
 153       _M_do_flip()
 154       {
 155         for (size_t __i = 0; __i < _Nw; __i++)
 156           _M_w[__i] = ~_M_w[__i];
 157       }
 158
 159       void
 160       _M_do_set()
 161       {
 162         for (size_t __i = 0; __i < _Nw; __i++)
 163           _M_w[__i] = ~static_cast<_WordT>(0);
 164       }
 165
 166       void
 167       _M_do_reset()
 168       { std::memset(_M_w, 0, _Nw * sizeof(_WordT)); }
 169
 170       bool
 171       _M_is_equal(const _Base_bitset<_Nw>& __x) const
 172       {
 173         for (size_t __i = 0; __i < _Nw; ++__i)
 174           {
 175             if (_M_w[__i] != __x._M_w[__i])
 176               return false;
 177           }
 178         return true;
 179       }
 180
 181       bool
 182       _M_is_any() const
 183       {
 184         for (size_t __i = 0; __i < _Nw; __i++)
 185           {
 186             if (_M_w[__i] != static_cast<_WordT>(0))
 187               return true;
 188           }
 189         return false;
 190       }
 191
 192       size_t
 193       _M_do_count() const
 194       {
 195         size_t __result = 0;
 196         for (size_t __i = 0; __i < _Nw; __i++)
 197           __result += __builtin_popcountl(_M_w[__i]);
 198         return __result;
 199       }
 200
 201       unsigned long
 202       _M_do_to_ulong() const;
 203
 204       // find first "on" bit
 205       size_t
 206       _M_do_find_first(size_t __not_found) const;
 207
 208       // find the next "on" bit that follows "prev"
 209       size_t
 210       _M_do_find_next(size_t __prev, size_t __not_found) const;
 211     };
 212
 213   // Definitions of non-inline functions from _Base_bitset.
 214   template<size_t _Nw>
 215     void
 216     _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
 217     {
 218       if (__builtin_expect(__shift != 0, 1))
 219         {
 220           const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
 221           const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
 222
 223           if (__offset == 0)
 224             for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
 225               _M_w[__n] = _M_w[__n - __wshift];
 226           else
 227             {
 228               const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
 229                                            - __offset);
 230               for (size_t __n = _Nw - 1; __n > __wshift; --__n)
 231                 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
 232                              | (_M_w[__n - __wshift - 1] >> __sub_offset));
 233               _M_w[__wshift] = _M_w[0] << __offset;
 234             }
 235
 236           std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
 237         }
 238     }
 239
 240   template<size_t _Nw>
 241     void
 242     _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
 243     {
 244       if (__builtin_expect(__shift != 0, 1))
 245         {
 246           const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
 247           const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
 248           const size_t __limit = _Nw - __wshift - 1;
 249
 250           if (__offset == 0)
 251             for (size_t __n = 0; __n <= __limit; ++__n)
 252               _M_w[__n] = _M_w[__n + __wshift];
 253           else
 254             {
 255               const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
 256                                            - __offset);
 257               for (size_t __n = 0; __n < __limit; ++__n)
 258                 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
 259                              | (_M_w[__n + __wshift + 1] << __sub_offset));
 260               _M_w[__limit] = _M_w[_Nw-1] >> __offset;
 261             }
 262
 263           std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
 264         }
 265     }
 266
 267   template<size_t _Nw>
 268     unsigned long
 269     _Base_bitset<_Nw>::_M_do_to_ulong() const
 270     {
 271       for (size_t __i = 1; __i < _Nw; ++__i)
 272         if (_M_w[__i])
 273           __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
 274       return _M_w[0];
 275     }
 276
 277   template<size_t _Nw>
 278     size_t
 279     _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
 280     {
 281       for (size_t __i = 0; __i < _Nw; __i++)
 282         {
 283           _WordT __thisword = _M_w[__i];
 284           if (__thisword != static_cast<_WordT>(0))
 285             return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
 286                     + __builtin_ctzl(__thisword));
 287         }
 288       // not found, so return an indication of failure.
 289       return __not_found;
 290     }
 291
 292   template<size_t _Nw>
 293     size_t
 294     _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
 295     {
 296       // make bound inclusive
 297       ++__prev;
 298
 299       // check out of bounds
 300       if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
 301         return __not_found;
 302
 303       // search first word
 304       size_t __i = _S_whichword(__prev);
 305       _WordT __thisword = _M_w[__i];
 306
 307       // mask off bits below bound
 308       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
 309
 310       if (__thisword != static_cast<_WordT>(0))
 311         return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
 312                 + __builtin_ctzl(__thisword));
 313
 314       // check subsequent words
 315       __i++;
 316       for (; __i < _Nw; __i++)
 317         {
 318           __thisword = _M_w[__i];
 319           if (__thisword != static_cast<_WordT>(0))
 320             return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
 321                     + __builtin_ctzl(__thisword));
 322         }
 323       // not found, so return an indication of failure.
 324       return __not_found;
 325     } // end _M_do_find_next
 326
 327   /**
 328    *  @if maint
 329    *  Base class, specialization for a single word.
 330    *
 331    *  See documentation for bitset.
 332    *  @endif
 333   */
 334   template<>
 335     struct _Base_bitset<1>
 336     {
 337       typedef unsigned long _WordT;
 338       _WordT _M_w;
 339
 340       _Base_bitset(void)
 341       : _M_w(0)
 342       { }
 343
 344       _Base_bitset(unsigned long __val)
 345       : _M_w(__val)
 346       { }
 347
 348       static size_t
 349       _S_whichword(size_t __pos )
 350       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
 351
 352       static size_t
 353       _S_whichbyte(size_t __pos )
 354       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
 355
 356       static size_t
 357       _S_whichbit(size_t __pos )
 358       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
 359
 360       static _WordT
 361       _S_maskbit(size_t __pos )
 362       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 363
 364       _WordT&
 365       _M_getword(size_t)
 366       { return _M_w; }
 367
 368       _WordT
 369       _M_getword(size_t) const
 370       { return _M_w; }
 371
 372       _WordT&
 373       _M_hiword()
 374       { return _M_w; }
 375
 376       _WordT
 377       _M_hiword() const
 378       { return _M_w; }
 379
 380       void
 381       _M_do_and(const _Base_bitset<1>& __x)
 382       { _M_w &= __x._M_w; }
 383
 384       void
 385       _M_do_or(const _Base_bitset<1>& __x)
 386       { _M_w |= __x._M_w; }
 387
 388       void
 389       _M_do_xor(const _Base_bitset<1>& __x)
 390       { _M_w ^= __x._M_w; }
 391
 392       void
 393       _M_do_left_shift(size_t __shift)
 394       { _M_w <<= __shift; }
 395
 396       void
 397       _M_do_right_shift(size_t __shift)
 398       { _M_w >>= __shift; }
 399
 400       void
 401       _M_do_flip()
 402       { _M_w = ~_M_w; }
 403
 404       void
 405       _M_do_set()
 406       { _M_w = ~static_cast<_WordT>(0); }
 407
 408       void
 409       _M_do_reset()
 410       { _M_w = 0; }
 411
 412       bool
 413       _M_is_equal(const _Base_bitset<1>& __x) const
 414       { return _M_w == __x._M_w; }
 415
 416       bool
 417       _M_is_any() const
 418       { return _M_w != 0; }
 419
 420       size_t
 421       _M_do_count() const
 422       { return __builtin_popcountl(_M_w); }
 423
 424       unsigned long
 425       _M_do_to_ulong() const
 426       { return _M_w; }
 427
 428       size_t
 429       _M_do_find_first(size_t __not_found) const
 430       {
 431         if (_M_w != 0)
 432           return __builtin_ctzl(_M_w);
 433         else
 434           return __not_found;
 435       }
 436
 437       // find the next "on" bit that follows "prev"
 438       size_t
 439       _M_do_find_next(size_t __prev, size_t __not_found) const
 440       {
 441         ++__prev;
 442         if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
 443           return __not_found;
 444
 445         _WordT __x = _M_w >> __prev;
 446         if (__x != 0)
 447           return __builtin_ctzl(__x) + __prev;
 448         else
 449           return __not_found;
 450       }
 451     };
 452
 453   /**
 454    *  @if maint
 455    *  Base class, specialization for no storage (zero-length %bitset).
 456    *
 457    *  See documentation for bitset.
 458    *  @endif
 459   */
 460   template<>
 461     struct _Base_bitset<0>
 462     {
 463       typedef unsigned long _WordT;
 464
 465       _Base_bitset()
 466       { }
 467
 468       _Base_bitset(unsigned long)
 469       { }
 470
 471       static size_t
 472       _S_whichword(size_t __pos )
 473       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
 474
 475       static size_t
 476       _S_whichbyte(size_t __pos )
 477       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
 478
 479       static size_t
 480       _S_whichbit(size_t __pos )
 481       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
 482
 483       static _WordT
 484       _S_maskbit(size_t __pos )
 485       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 486
 487       // This would normally give access to the data.  The bounds-checking
 488       // in the bitset class will prevent the user from getting this far,
 489       // but (1) it must still return an lvalue to compile, and (2) the
 490       // user might call _Unchecked_set directly, in which case this /needs/
 491       // to fail.  Let's not penalize zero-length users unless they actually
 492       // make an unchecked call; all the memory ugliness is therefore
 493       // localized to this single should-never-get-this-far function.
 494       _WordT&
 495       _M_getword(size_t) const
 496       {
 497         __throw_out_of_range(__N("_Base_bitset::_M_getword"));
 498         return *new _WordT;
 499       }
 500
 501       _WordT
 502       _M_hiword() const
 503       { return 0; }
 504
 505       void
 506       _M_do_and(const _Base_bitset<0>&)
 507       { }
 508
 509       void
 510       _M_do_or(const _Base_bitset<0>&)
 511       { }
 512
 513       void
 514       _M_do_xor(const _Base_bitset<0>&)
 515       { }
 516
 517       void
 518       _M_do_left_shift(size_t)
 519       { }
 520
 521       void
 522       _M_do_right_shift(size_t)
 523       { }
 524
 525       void
 526       _M_do_flip()
 527       { }
 528
 529       void
 530       _M_do_set()
 531       { }
 532
 533       void
 534       _M_do_reset()
 535       { }
 536
 537       // Are all empty bitsets equal to each other?  Are they equal to
 538       // themselves?  How to compare a thing which has no state?  What is
 539       // the sound of one zero-length bitset clapping?
 540       bool
 541       _M_is_equal(const _Base_bitset<0>&) const
 542       { return true; }
 543
 544       bool
 545       _M_is_any() const
 546       { return false; }
 547
 548       size_t
 549       _M_do_count() const
 550       { return 0; }
 551
 552       unsigned long
 553       _M_do_to_ulong() const
 554       { return 0; }
 555
 556       // Normally "not found" is the size, but that could also be
 557       // misinterpreted as an index in this corner case.  Oh well.
 558       size_t
 559       _M_do_find_first(size_t) const
 560       { return 0; }
 561
 562       size_t
 563       _M_do_find_next(size_t, size_t) const
 564       { return 0; }
 565     };
 566
 567
 568   // Helper class to zero out the unused high-order bits in the highest word.
 569   template<size_t _Extrabits>
 570     struct _Sanitize
 571     {
 572       static void _S_do_sanitize(unsigned long& __val)
 573       { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
 574     };
 575
 576   template<>
 577     struct _Sanitize<0>
 578     { static void _S_do_sanitize(unsigned long) {} };
 579
 580   /**
 581    *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
 582    *
 583    *  @ingroup Containers
 584    *
 585    *  (Note that %bitset does @e not meet the formal requirements of a
 586    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
 587    *
 588    *  The template argument, @a Nb, may be any non-negative number,
 589    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
 590    *
 591    *  In the general unoptimized case, storage is allocated in word-sized
 592    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
 593    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
 594    *  the high-order bits in the highest word.)  It is a class invariant
 595    *  that those unused bits are always zero.
 596    *
 597    *  If you think of %bitset as "a simple array of bits," be aware that
 598    *  your mental picture is reversed:  a %bitset behaves the same way as
 599    *  bits in integers do, with the bit at index 0 in the "least significant
 600    *  / right-hand" position, and the bit at index Nb-1 in the "most
 601    *  significant / left-hand" position.  Thus, unlike other containers, a
 602    *  %bitset's index "counts from right to left," to put it very loosely.
 603    *
 604    *  This behavior is preserved when translating to and from strings.  For
 605    *  example, the first line of the following program probably prints
 606    *  "b('a') is 0001100001" on a modern ASCII system.
 607    *
 608    *  @code
 609    *     #include <bitset>
 610    *     #include <iostream>
 611    *     #include <sstream>
 612    *
 613    *     using namespace std;
 614    *
 615    *     int main()
 616    *     {
 617    *         long         a = 'a';
 618    *         bitset<10>   b(a);
 619    *
 620    *         cout << "b('a') is " << b << endl;
 621    *
 622    *         ostringstream s;
 623    *         s << b;
 624    *         string  str = s.str();
 625    *         cout << "index 3 in the string is " << str[3] << " but\n"
 626    *              << "index 3 in the bitset is " << b[3] << endl;
 627    *     }
 628    *  @endcode
 629    *
 630    *  Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
 631    *  for a description of extensions.
 632    *
 633    *  @if maint
 634    *  Most of the actual code isn't contained in %bitset<> itself, but in the
 635    *  base class _Base_bitset.  The base class works with whole words, not with
 636    *  individual bits.  This allows us to specialize _Base_bitset for the
 637    *  important special case where the %bitset is only a single word.
 638    *
 639    *  Extra confusion can result due to the fact that the storage for
 640    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
 641    *  carefully encapsulated.
 642    *  @endif
 643   */
 644   template<size_t _Nb>
 645     class bitset
 646     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
 647     {
 648     private:
 649       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
 650       typedef unsigned long _WordT;
 651
 652       void
 653         _M_do_sanitize()
 654         {
 655           _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
 656             _S_do_sanitize(this->_M_hiword());
 657         }
 658
 659     public:
 660       /**
 661        *  This encapsulates the concept of a single bit.  An instance of this
 662        *  class is a proxy for an actual bit; this way the individual bit
 663        *  operations are done as faster word-size bitwise instructions.
 664        *
 665        *  Most users will never need to use this class directly; conversions
 666        *  to and from bool are automatic and should be transparent.  Overloaded
 667        *  operators help to preserve the illusion.
 668        *
 669        *  (On a typical system, this "bit %reference" is 64 times the size of
 670        *  an actual bit.  Ha.)
 671        */
 672       class reference
 673       {
 674         friend class bitset;
 675
 676         _WordT *_M_wp;
 677         size_t _M_bpos;
 678
 679         // left undefined
 680         reference();
 681
 682       public:
 683         reference(bitset& __b, size_t __pos)
 684         {
 685           _M_wp = &__b._M_getword(__pos);
 686           _M_bpos = _Base::_S_whichbit(__pos);
 687         }
 688
 689         ~reference()
 690         { }
 691
 692         // For b[i] = __x;
 693         reference&
 694         operator=(bool __x)
 695         {
 696           if (__x)
 697             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 698           else
 699             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 700           return *this;
 701         }
 702
 703         // For b[i] = b[__j];
 704         reference&
 705         operator=(const reference& __j)
 706         {
 707           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
 708             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 709           else
 710             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 711           return *this;
 712         }
 713
 714         // Flips the bit
 715         bool
 716         operator~() const
 717         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
 718
 719         // For __x = b[i];
 720         operator bool() const
 721         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
 722
 723         // For b[i].flip();
 724         reference&
 725         flip()
 726         {
 727           *_M_wp ^= _Base::_S_maskbit(_M_bpos);
 728           return *this;
 729         }
 730       };
 731       friend class reference;
 732
 733       // 23.3.5.1 constructors:
 734       /// All bits set to zero.
 735       bitset()
 736       { }
 737
 738       /// Initial bits bitwise-copied from a single word (others set to zero).
 739       bitset(unsigned long __val)
 740       : _Base(__val)
 741       { _M_do_sanitize(); }
 742
 743       /**
 744        *  @brief  Use a subset of a string.
 745        *  @param  s  A string of '0' and '1' characters.
 746        *  @param  position  Index of the first character in @a s to use;
 747        *                    defaults to zero.
 748        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
 749        *  @throw  std::invalid_argument  If a character appears in the string
 750        *                                 which is neither '0' nor '1'.
 751        */
 752       template<class _CharT, class _Traits, class _Alloc>
 753         explicit
 754         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 755                size_t __position = 0)
 756         : _Base()
 757         {
 758           if (__position > __s.size())
 759             __throw_out_of_range(__N("bitset::bitset initial position "
 760                                      "not valid"));
 761           _M_copy_from_string(__s, __position,
 762                               std::basic_string<_CharT, _Traits, _Alloc>::npos);
 763         }
 764
 765       /**
 766        *  @brief  Use a subset of a string.
 767        *  @param  s  A string of '0' and '1' characters.
 768        *  @param  position  Index of the first character in @a s to use.
 769        *  @param  n    The number of characters to copy.
 770        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
 771        *  @throw  std::invalid_argument  If a character appears in the string
 772        *                                 which is neither '0' nor '1'.
 773        */
 774       template<class _CharT, class _Traits, class _Alloc>
 775         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 776                size_t __position, size_t __n)
 777         : _Base()
 778         {
 779           if (__position > __s.size())
 780             __throw_out_of_range(__N("bitset::bitset initial position "
 781                                      "not valid"));
 782           _M_copy_from_string(__s, __position, __n);
 783         }
 784
 785       // 23.3.5.2 bitset operations:
 786       //@{
 787       /**
 788        *  @brief  Operations on bitsets.
 789        *  @param  rhs  A same-sized bitset.
 790        *
 791        *  These should be self-explanatory.
 792        */
 793       bitset<_Nb>&
 794       operator&=(const bitset<_Nb>& __rhs)
 795       {
 796         this->_M_do_and(__rhs);
 797         return *this;
 798       }
 799
 800       bitset<_Nb>&
 801       operator|=(const bitset<_Nb>& __rhs)
 802       {
 803         this->_M_do_or(__rhs);
 804         return *this;
 805       }
 806
 807       bitset<_Nb>&
 808       operator^=(const bitset<_Nb>& __rhs)
 809       {
 810         this->_M_do_xor(__rhs);
 811         return *this;
 812       }
 813       //@}
 814
 815       //@{
 816       /**
 817        *  @brief  Operations on bitsets.
 818        *  @param  position  The number of places to shift.
 819        *
 820        *  These should be self-explanatory.
 821        */
 822       bitset<_Nb>&
 823       operator<<=(size_t __position)
 824       {
 825         if (__builtin_expect(__position < _Nb, 1))
 826           {
 827             this->_M_do_left_shift(__position);
 828             this->_M_do_sanitize();
 829           }
 830         else
 831           this->_M_do_reset();
 832         return *this;
 833       }
 834
 835       bitset<_Nb>&
 836       operator>>=(size_t __position)
 837       {
 838         if (__builtin_expect(__position < _Nb, 1))
 839           {
 840             this->_M_do_right_shift(__position);
 841             this->_M_do_sanitize();
 842           }
 843         else
 844           this->_M_do_reset();
 845         return *this;
 846       }
 847       //@}
 848
 849       //@{
 850       /**
 851        *  These versions of single-bit set, reset, flip, and test are
 852        *  extensions from the SGI version.  They do no range checking.
 853        *  @ingroup SGIextensions
 854        */
 855       bitset<_Nb>&
 856       _Unchecked_set(size_t __pos)
 857       {
 858         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 859         return *this;
 860       }
 861
 862       bitset<_Nb>&
 863       _Unchecked_set(size_t __pos, int __val)
 864       {
 865         if (__val)
 866           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 867         else
 868           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 869         return *this;
 870       }
 871
 872       bitset<_Nb>&
 873       _Unchecked_reset(size_t __pos)
 874       {
 875         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 876         return *this;
 877       }
 878
 879       bitset<_Nb>&
 880       _Unchecked_flip(size_t __pos)
 881       {
 882         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
 883         return *this;
 884       }
 885
 886       bool
 887       _Unchecked_test(size_t __pos) const
 888       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
 889                 != static_cast<_WordT>(0)); }
 890       //@}
 891
 892       // Set, reset, and flip.
 893       /**
 894        *  @brief Sets every bit to true.
 895        */
 896       bitset<_Nb>&
 897       set()
 898       {
 899         this->_M_do_set();
 900         this->_M_do_sanitize();
 901         return *this;
 902       }
 903
 904       /**
 905        *  @brief Sets a given bit to a particular value.
 906        *  @param  position  The index of the bit.
 907        *  @param  val  Either true or false, defaults to true.
 908        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
 909        */
 910       bitset<_Nb>&
 911       set(size_t __position, bool __val = true)
 912       {
 913         if (__position >= _Nb)
 914           __throw_out_of_range(__N("bitset::set"));
 915         return _Unchecked_set(__position, __val);
 916       }
 917
 918       /**
 919        *  @brief Sets every bit to false.
 920        */
 921       bitset<_Nb>&
 922       reset()
 923       {
 924         this->_M_do_reset();
 925         return *this;
 926       }
 927
 928       /**
 929        *  @brief Sets a given bit to false.
 930        *  @param  position  The index of the bit.
 931        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
 932        *
 933        *  Same as writing @c set(pos,false).
 934        */
 935       bitset<_Nb>&
 936       reset(size_t __position)
 937       {
 938         if (__position >= _Nb)
 939           __throw_out_of_range(__N("bitset::reset"));
 940         return _Unchecked_reset(__position);
 941       }
 942
 943       /**
 944        *  @brief Toggles every bit to its opposite value.
 945        */
 946       bitset<_Nb>&
 947       flip()
 948       {
 949         this->_M_do_flip();
 950         this->_M_do_sanitize();
 951         return *this;
 952       }
 953
 954       /**
 955        *  @brief Toggles a given bit to its opposite value.
 956        *  @param  position  The index of the bit.
 957        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
 958        */
 959       bitset<_Nb>&
 960       flip(size_t __position)
 961       {
 962         if (__position >= _Nb)
 963           __throw_out_of_range(__N("bitset::flip"));
 964         return _Unchecked_flip(__position);
 965       }
 966
 967       /// See the no-argument flip().
 968       bitset<_Nb>
 969       operator~() const
 970       { return bitset<_Nb>(*this).flip(); }
 971
 972       //@{
 973       /**
 974        *  @brief  Array-indexing support.
 975        *  @param  position  Index into the %bitset.
 976        *  @return  A bool for a 'const %bitset'.  For non-const bitsets, an
 977        *           instance of the reference proxy class.
 978        *  @note  These operators do no range checking and throw no exceptions,
 979        *         as required by DR 11 to the standard.
 980        *
 981        *  @if maint
 982        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
 983        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
 984        *  required by that DR's resolution.  -pme
 985        *  The DR has since been changed:  range-checking is a precondition
 986        *  (users' responsibility), and these functions must not throw.  -pme
 987        *  @endif
 988        */
 989       reference
 990       operator[](size_t __position)
 991       { return reference(*this,__position); }
 992
 993       bool
 994       operator[](size_t __position) const
 995       { return _Unchecked_test(__position); }
 996       //@}
 997
 998       /**
 999        *  @brief Retuns a numerical interpretation of the %bitset.
1000        *  @return  The integral equivalent of the bits.
1001        *  @throw  std::overflow_error  If there are too many bits to be
1002        *                               represented in an @c unsigned @c long.
1003        */
1004       unsigned long
1005       to_ulong() const
1006       { return this->_M_do_to_ulong(); }
1007
1008       /**
1009        *  @brief Retuns a character interpretation of the %bitset.
1010        *  @return  The string equivalent of the bits.
1011        *
1012        *  Note the ordering of the bits:  decreasing character positions
1013        *  correspond to increasing bit positions (see the main class notes for
1014        *  an example).
1015        */
1016       template<class _CharT, class _Traits, class _Alloc>
1017         std::basic_string<_CharT, _Traits, _Alloc>
1018         to_string() const
1019         {
1020           std::basic_string<_CharT, _Traits, _Alloc> __result;
1021           _M_copy_to_string(__result);
1022           return __result;
1023         }
1024
1025       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1026       // 434. bitset::to_string() hard to use.
1027       template<class _CharT, class _Traits>
1028         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1029         to_string() const
1030         { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1031
1032       template<class _CharT>
1033         std::basic_string<_CharT, std::char_traits<_CharT>,
1034                           std::allocator<_CharT> >
1035         to_string() const
1036         {
1037           return to_string<_CharT, std::char_traits<_CharT>,
1038                            std::allocator<_CharT> >();
1039         }
1040
1041       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1042       to_string() const
1043       {
1044         return to_string<char, std::char_traits<char>,
1045                          std::allocator<char> >();
1046       }
1047
1048       // Helper functions for string operations.
1049       template<class _CharT, class _Traits, class _Alloc>
1050         void
1051         _M_copy_from_string(const std::basic_string<_CharT,
1052                             _Traits, _Alloc>& __s,
1053                             size_t, size_t);
1054
1055       template<class _CharT, class _Traits, class _Alloc>
1056         void
1057         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&) const;
1058
1059       /// Returns the number of bits which are set.
1060       size_t
1061       count() const
1062       { return this->_M_do_count(); }
1063
1064       /// Returns the total number of bits.
1065       size_t
1066       size() const
1067       { return _Nb; }
1068
1069       //@{
1070       /// These comparisons for equality/inequality are, well, @e bitwise.
1071       bool
1072       operator==(const bitset<_Nb>& __rhs) const
1073       { return this->_M_is_equal(__rhs); }
1074
1075       bool
1076       operator!=(const bitset<_Nb>& __rhs) const
1077       { return !this->_M_is_equal(__rhs); }
1078       //@}
1079
1080       /**
1081        *  @brief Tests the value of a bit.
1082        *  @param  position  The index of a bit.
1083        *  @return  The value at @a pos.
1084        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1085        */
1086       bool
1087       test(size_t __position) const
1088       {
1089         if (__position >= _Nb)
1090           __throw_out_of_range(__N("bitset::test"));
1091         return _Unchecked_test(__position);
1092       }
1093
1094       /**
1095        *  @brief Tests whether any of the bits are on.
1096        *  @return  True if at least one bit is set.
1097        */
1098       bool
1099       any() const
1100       { return this->_M_is_any(); }
1101
1102       /**
1103        *  @brief Tests whether any of the bits are on.
1104        *  @return  True if none of the bits are set.
1105        */
1106       bool
1107       none() const
1108       { return !this->_M_is_any(); }
1109
1110       //@{
1111       /// Self-explanatory.
1112       bitset<_Nb>
1113       operator<<(size_t __position) const
1114       { return bitset<_Nb>(*this) <<= __position; }
1115
1116       bitset<_Nb>
1117       operator>>(size_t __position) const
1118       { return bitset<_Nb>(*this) >>= __position; }
1119       //@}
1120
1121       /**
1122        *  @brief  Finds the index of the first "on" bit.
1123        *  @return  The index of the first bit set, or size() if not found.
1124        *  @ingroup SGIextensions
1125        *  @sa  _Find_next
1126        */
1127       size_t
1128       _Find_first() const
1129       { return this->_M_do_find_first(_Nb); }
1130
1131       /**
1132        *  @brief  Finds the index of the next "on" bit after prev.
1133        *  @return  The index of the next bit set, or size() if not found.
1134        *  @param  prev  Where to start searching.
1135        *  @ingroup SGIextensions
1136        *  @sa  _Find_first
1137        */
1138       size_t
1139       _Find_next(size_t __prev ) const
1140       { return this->_M_do_find_next(__prev, _Nb); }
1141     };
1142
1143   // Definitions of non-inline member functions.
1144   template<size_t _Nb>
1145     template<class _CharT, class _Traits, class _Alloc>
1146       void
1147       bitset<_Nb>::_M_copy_from_string(const std::basic_string<_CharT, _Traits,
1148                                        _Alloc>& __s, size_t __pos, size_t __n)
1149       {
1150         reset();
1151         const size_t __nbits = std::min(_Nb, std::min(__n, __s.size() - __pos));
1152         for (size_t __i = 0; __i < __nbits; ++__i)
1153           {
1154             switch(__s[__pos + __nbits - __i - 1])
1155               {
1156               case '0':
1157                 break;
1158               case '1':
1159                 set(__i);
1160                 break;
1161               default:
1162                 __throw_invalid_argument(__N("bitset::_M_copy_from_string"));
1163               }
1164           }
1165       }
1166
1167   template<size_t _Nb>
1168     template<class _CharT, class _Traits, class _Alloc>
1169       void
1170       bitset<_Nb>::_M_copy_to_string(std::basic_string<_CharT, _Traits,
1171                                      _Alloc>& __s) const
1172       {
1173         __s.assign(_Nb, '0');
1174         for (size_t __i = 0; __i < _Nb; ++__i)
1175           if (_Unchecked_test(__i))
1176             __s[_Nb - 1 - __i] = '1';
1177       }
1178
1179   // 23.3.5.3 bitset operations:
1180   //@{
1181   /**
1182    *  @brief  Global bitwise operations on bitsets.
1183    *  @param  x  A bitset.
1184    *  @param  y  A bitset of the same size as @a x.
1185    *  @return  A new bitset.
1186    *
1187    *  These should be self-explanatory.
1188   */
1189   template<size_t _Nb>
1190     inline bitset<_Nb>
1191     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1192     {
1193       bitset<_Nb> __result(__x);
1194       __result &= __y;
1195       return __result;
1196     }
1197
1198   template<size_t _Nb>
1199     inline bitset<_Nb>
1200     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1201     {
1202       bitset<_Nb> __result(__x);
1203       __result |= __y;
1204       return __result;
1205     }
1206
1207   template <size_t _Nb>
1208     inline bitset<_Nb>
1209     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1210     {
1211       bitset<_Nb> __result(__x);
1212       __result ^= __y;
1213       return __result;
1214     }
1215   //@}
1216
1217   //@{
1218   /**
1219    *  @brief Global I/O operators for bitsets.
1220    *
1221    *  Direct I/O between streams and bitsets is supported.  Output is
1222    *  straightforward.  Input will skip whitespace, only accept '0' and '1'
1223    *  characters, and will only extract as many digits as the %bitset will
1224    *  hold.
1225   */
1226   template<class _CharT, class _Traits, size_t _Nb>
1227     std::basic_istream<_CharT, _Traits>&
1228     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1229     {
1230       typedef typename _Traits::char_type char_type;
1231       std::basic_string<_CharT, _Traits> __tmp;
1232       __tmp.reserve(_Nb);
1233
1234       std::ios_base::iostate __state = std::ios_base::goodbit;
1235       typename std::basic_istream<_CharT, _Traits>::sentry __sentry(__is);
1236       if (__sentry)
1237         {
1238           try
1239             {
1240               basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
1241               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1242               // 303. Bitset input operator underspecified
1243               const char_type __zero = __is.widen('0');
1244               const char_type __one = __is.widen('1');
1245               for (size_t __i = 0; __i < _Nb; ++__i)
1246                 {
1247                   static typename _Traits::int_type __eof = _Traits::eof();
1248
1249                   typename _Traits::int_type __c1 = __buf->sbumpc();
1250                   if (_Traits::eq_int_type(__c1, __eof))
1251                     {
1252                       __state |= std::ios_base::eofbit;
1253                       break;
1254                     }
1255                   else
1256                     {
1257                       const char_type __c2 = _Traits::to_char_type(__c1);
1258                       if (__c2 == __zero)
1259                         __tmp.push_back('0');
1260                       else if (__c2 == __one)
1261                         __tmp.push_back('1');
1262                       else if (_Traits::eq_int_type(__buf->sputbackc(__c2),
1263                                                     __eof))
1264                         {
1265                           __state |= std::ios_base::failbit;
1266                           break;
1267                         }
1268                     }
1269                 }
1270             }
1271           catch(...)
1272             { __is._M_setstate(std::ios_base::badbit); }
1273         }
1274
1275       if (__tmp.empty() && _Nb)
1276         __state |= std::ios_base::failbit;
1277       else
1278         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
1279       if (__state)
1280         __is.setstate(__state);
1281       return __is;
1282     }
1283
1284   template <class _CharT, class _Traits, size_t _Nb>
1285     std::basic_ostream<_CharT, _Traits>&
1286     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1287                const bitset<_Nb>& __x)
1288     {
1289       std::basic_string<_CharT, _Traits> __tmp;
1290       __x._M_copy_to_string(__tmp);
1291       return __os << __tmp;
1292     }
1293   //@}
1294 } // namespace std
1295
1296 #undef _GLIBCXX_BITSET_WORDS
1297 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1298
1299 #ifdef _GLIBCXX_DEBUG
1300 # include <debug/bitset>
1301 #endif
1302
1303 #endif /* _GLIBCXX_BITSET */