libstdc++-v3/include/std/bitset

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