contrib/libstdc++/include/std/std_bitset.h

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