libstdc++-v3/include/std/bitset

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