libstdc++-v3/include/tr2/dynamic_bitset

   1 // TR2 <dynamic_bitset> -*- C++ -*-
   2
   3 // Copyright (C) 2009-2014 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file tr2/dynamic_bitset
  26  *  This is a TR2 C++ Library header.
  27  */
  28
  29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
  30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
  31
  32 #pragma GCC system_header
  33
  34 #include <limits>
  35 #include <vector>
  36 #include <string>
  37 #include <memory> // For std::allocator
  38 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
  39                                 // overflow_error
  40 #include <iosfwd>
  41 #include <bits/cxxabi_forced.h>
  42
  43 namespace std _GLIBCXX_VISIBILITY(default)
  44 {
  45 namespace tr2
  46 {
  47 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  48
  49   /**
  50    *  Dynamic Bitset.
  51    *
  52    *  See N2050,
  53    *  Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
  54    */
  55 namespace __detail
  56 {
  57
  58 template<typename T>
  59 class _Bool2UChar
  60 {
  61   typedef T type;
  62 };
  63
  64 template<>
  65 class _Bool2UChar<bool>
  66 {
  67 public:
  68   typedef unsigned char type;
  69 };
  70
  71 }
  72
  73   /**
  74    *  Base class, general case.
  75    *
  76    *  See documentation for dynamic_bitset.
  77    */
  78   template<typename _WordT = unsigned long long,
  79            typename _Alloc = std::allocator<_WordT>>
  80     struct __dynamic_bitset_base
  81     {
  82       static_assert(std::is_unsigned<_WordT>::value, "template argument "
  83                     "_WordT not an unsigned integral type");
  84
  85       typedef _WordT block_type;
  86       typedef _Alloc allocator_type;
  87       typedef size_t size_type;
  88
  89       static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
  90       static const size_type npos = static_cast<size_type>(-1);
  91
  92       /// 0 is the least significant word.
  93       std::vector<block_type, allocator_type> _M_w;
  94
  95       explicit
  96       __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
  97       : _M_w(__alloc)
  98       { }
  99
 100       explicit
 101       __dynamic_bitset_base(__dynamic_bitset_base&& __b)
 102       { this->_M_w.swap(__b._M_w); }
 103
 104       explicit
 105       __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
 106                            const allocator_type& __alloc = allocator_type())
 107       : _M_w(__nbits / _S_bits_per_block
 108              + (__nbits % _S_bits_per_block > 0),
 109              __val, __alloc)
 110       {
 111         unsigned long long __mask = ~static_cast<block_type>(0);
 112         size_t __n = std::min(this->_M_w.size(),
 113                               sizeof(unsigned long long) / sizeof(block_type));
 114         for (size_t __i = 0; __i < __n; ++__i)
 115           {
 116             this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
 117             __mask <<= _S_bits_per_block;
 118           }
 119       }
 120
 121       void
 122       _M_assign(const __dynamic_bitset_base& __b)
 123       { this->_M_w = __b._M_w; }
 124
 125       void
 126       _M_swap(__dynamic_bitset_base& __b)
 127       { this->_M_w.swap(__b._M_w); }
 128
 129       void
 130       _M_clear()
 131       { this->_M_w.clear(); }
 132
 133       void
 134       _M_resize(size_t __nbits, bool __value)
 135       {
 136         size_t __sz = __nbits / _S_bits_per_block;
 137         if (__nbits % _S_bits_per_block > 0)
 138           ++__sz;
 139         if (__sz != this->_M_w.size())
 140           {
 141             block_type __val = 0;
 142             if (__value)
 143               __val = std::numeric_limits<block_type>::max();
 144             this->_M_w.resize(__sz, __val);
 145           }
 146       }
 147
 148       allocator_type
 149       _M_get_allocator() const
 150       { return this->_M_w.get_allocator(); }
 151
 152       static size_type
 153       _S_whichword(size_type __pos) noexcept
 154       { return __pos / _S_bits_per_block; }
 155
 156       static size_type
 157       _S_whichbyte(size_type __pos) noexcept
 158       { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
 159
 160       static size_type
 161       _S_whichbit(size_type __pos) noexcept
 162       { return __pos % _S_bits_per_block; }
 163
 164       static block_type
 165       _S_maskbit(size_type __pos) noexcept
 166       { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
 167
 168       block_type&
 169       _M_getword(size_type __pos)
 170       { return this->_M_w[_S_whichword(__pos)]; }
 171
 172       block_type
 173       _M_getword(size_type __pos) const
 174       { return this->_M_w[_S_whichword(__pos)]; }
 175
 176       block_type&
 177       _M_hiword()
 178       { return this->_M_w[_M_w.size() - 1]; }
 179
 180       block_type
 181       _M_hiword() const
 182       { return this->_M_w[_M_w.size() - 1]; }
 183
 184       void
 185       _M_do_and(const __dynamic_bitset_base& __x)
 186       {
 187         if (__x._M_w.size() == this->_M_w.size())
 188           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 189             this->_M_w[__i] &= __x._M_w[__i];
 190         else
 191           return;
 192       }
 193
 194       void
 195       _M_do_or(const __dynamic_bitset_base& __x)
 196       {
 197         if (__x._M_w.size() == this->_M_w.size())
 198           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 199             this->_M_w[__i] |= __x._M_w[__i];
 200         else
 201           return;
 202       }
 203
 204       void
 205       _M_do_xor(const __dynamic_bitset_base& __x)
 206       {
 207         if (__x._M_w.size() == this->_M_w.size())
 208           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 209             this->_M_w[__i] ^= __x._M_w[__i];
 210         else
 211           return;
 212       }
 213
 214       void
 215       _M_do_dif(const __dynamic_bitset_base& __x)
 216       {
 217         if (__x._M_w.size() == this->_M_w.size())
 218           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 219             this->_M_w[__i] &= ~__x._M_w[__i];
 220         else
 221           return;
 222       }
 223
 224       void
 225       _M_do_left_shift(size_t __shift);
 226
 227       void
 228       _M_do_right_shift(size_t __shift);
 229
 230       void
 231       _M_do_flip()
 232       {
 233         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 234           this->_M_w[__i] = ~this->_M_w[__i];
 235       }
 236
 237       void
 238       _M_do_set()
 239       {
 240         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 241           this->_M_w[__i] = ~static_cast<block_type>(0);
 242       }
 243
 244       void
 245       _M_do_reset()
 246       {
 247         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 248           this->_M_w[__i] = static_cast<block_type>(0);
 249       }
 250
 251       bool
 252       _M_is_equal(const __dynamic_bitset_base& __x) const
 253       {
 254         if (__x._M_w.size() == this->_M_w.size())
 255           {
 256             for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 257               if (this->_M_w[__i] != __x._M_w[__i])
 258                 return false;
 259             return true;
 260           }
 261         else
 262           return false;
 263       }
 264
 265       bool
 266       _M_is_less(const __dynamic_bitset_base& __x) const
 267       {
 268         if (__x._M_w.size() == this->_M_w.size())
 269           {
 270             for (size_t __i = this->_M_w.size(); __i > 0; --__i)
 271               {
 272                 if (this->_M_w[__i-1] < __x._M_w[__i-1])
 273                   return true;
 274                 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
 275                   return false;
 276               }
 277             return false;
 278           }
 279         else
 280           return false;
 281       }
 282
 283       size_t
 284       _M_are_all_aux() const
 285       {
 286         for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
 287           if (_M_w[__i] != ~static_cast<block_type>(0))
 288             return 0;
 289         return ((this->_M_w.size() - 1) * _S_bits_per_block
 290                 + __builtin_popcountll(this->_M_hiword()));
 291       }
 292
 293       bool
 294       _M_is_any() const
 295       {
 296         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 297           if (this->_M_w[__i] != static_cast<block_type>(0))
 298             return true;
 299         return false;
 300       }
 301
 302       bool
 303       _M_is_subset_of(const __dynamic_bitset_base& __b)
 304       {
 305         if (__b._M_w.size() == this->_M_w.size())
 306           {
 307             for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 308               if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
 309                 return false;
 310             return true;
 311           }
 312         else
 313           return false;
 314       }
 315
 316       bool
 317       _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
 318       {
 319         if (this->is_subset_of(__b))
 320           {
 321             if (*this == __b)
 322               return false;
 323             else
 324               return true;
 325           }
 326         else
 327           return false;
 328       }
 329
 330       size_t
 331       _M_do_count() const
 332       {
 333         size_t __result = 0;
 334         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 335           __result += __builtin_popcountll(this->_M_w[__i]);
 336         return __result;
 337       }
 338
 339       size_type
 340       _M_size() const noexcept
 341       { return this->_M_w.size(); }
 342
 343       unsigned long
 344       _M_do_to_ulong() const;
 345
 346       unsigned long long
 347       _M_do_to_ullong() const;
 348
 349       // find first "on" bit
 350       size_type
 351       _M_do_find_first(size_t __not_found) const;
 352
 353       // find the next "on" bit that follows "prev"
 354       size_type
 355       _M_do_find_next(size_t __prev, size_t __not_found) const;
 356
 357       // do append of block
 358       void
 359       _M_do_append_block(block_type __block, size_type __pos)
 360       {
 361         size_t __offset = __pos % _S_bits_per_block;
 362         if (__offset == 0)
 363           this->_M_w.push_back(__block);
 364         else
 365           {
 366             this->_M_hiword() |= (__block << __offset);
 367             this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
 368           }
 369       }
 370     };
 371
 372   /**
 373    *  @brief  The %dynamic_bitset class represents a sequence of bits.
 374    *
 375    *  @ingroup containers
 376    *
 377    *  (Note that %dynamic_bitset does @e not meet the formal
 378    *  requirements of a <a href="tables.html#65">container</a>.
 379    *  Mainly, it lacks iterators.)
 380    *
 381    *  The template argument, @a Nb, may be any non-negative number,
 382    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
 383    *
 384    *  In the general unoptimized case, storage is allocated in
 385    *  word-sized blocks.  Let B be the number of bits in a word, then
 386    *  (Nb+(B-1))/B words will be used for storage.  B - Nb%B bits are
 387    *  unused.  (They are the high-order bits in the highest word.)  It
 388    *  is a class invariant that those unused bits are always zero.
 389    *
 390    *  If you think of %dynamic_bitset as "a simple array of bits," be
 391    *  aware that your mental picture is reversed: a %dynamic_bitset
 392    *  behaves the same way as bits in integers do, with the bit at
 393    *  index 0 in the "least significant / right-hand" position, and
 394    *  the bit at index Nb-1 in the "most significant / left-hand"
 395    *  position.  Thus, unlike other containers, a %dynamic_bitset's
 396    *  index "counts from right to left," to put it very loosely.
 397    *
 398    *  This behavior is preserved when translating to and from strings.
 399    *  For example, the first line of the following program probably
 400    *  prints "b('a') is 0001100001" on a modern ASCII system.
 401    *
 402    *  @code
 403    *     #include <dynamic_bitset>
 404    *     #include <iostream>
 405    *     #include <sstream>
 406    *
 407    *     using namespace std;
 408    *
 409    *     int main()
 410    *     {
 411    *         long         a = 'a';
 412    *         dynamic_bitset   b(a);
 413    *
 414    *         cout << "b('a') is " << b << endl;
 415    *
 416    *         ostringstream s;
 417    *         s << b;
 418    *         string  str = s.str();
 419    *         cout << "index 3 in the string is " << str[3] << " but\n"
 420    *              << "index 3 in the bitset is " << b[3] << endl;
 421    *     }
 422    *  @endcode
 423    *
 424    *  Also see:
 425    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
 426    *  for a description of extensions.
 427    *
 428    *  Most of the actual code isn't contained in %dynamic_bitset<>
 429    *  itself, but in the base class __dynamic_bitset_base.  The base
 430    *  class works with whole words, not with individual bits.  This
 431    *  allows us to specialize __dynamic_bitset_base for the important
 432    *  special case where the %dynamic_bitset is only a single word.
 433    *
 434    *  Extra confusion can result due to the fact that the storage for
 435    *  __dynamic_bitset_base @e is a vector, and is indexed as such.  This is
 436    *  carefully encapsulated.
 437    */
 438   template<typename _WordT = unsigned long long,
 439            typename _Alloc = std::allocator<_WordT>>
 440     class dynamic_bitset
 441     : private __dynamic_bitset_base<_WordT, _Alloc>
 442     {
 443       static_assert(std::is_unsigned<_WordT>::value, "template argument "
 444                     "_WordT not an unsigned integral type");
 445
 446     public:
 447
 448       typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
 449       typedef _WordT block_type;
 450       typedef _Alloc allocator_type;
 451       typedef size_t size_type;
 452
 453       static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
 454       // Use this: constexpr size_type std::numeric_limits<size_type>::max().
 455       static const size_type npos = static_cast<size_type>(-1);
 456
 457     private:
 458
 459       //  Clear the unused bits in the uppermost word.
 460       void
 461       _M_do_sanitize()
 462       {
 463         size_type __shift = this->_M_Nb % bits_per_block;
 464         if (__shift > 0)
 465           this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
 466       }
 467
 468       //  Set the unused bits in the uppermost word.
 469       void
 470       _M_do_fill()
 471       {
 472         size_type __shift = this->_M_Nb % bits_per_block;
 473         if (__shift > 0)
 474           this->_M_hiword() |= ((~static_cast<block_type>(0)) << __shift);
 475       }
 476
 477       /**
 478        *  These versions of single-bit set, reset, flip, and test
 479        *  do no range checking.
 480        */
 481       dynamic_bitset<_WordT, _Alloc>&
 482       _M_unchecked_set(size_type __pos)
 483       {
 484         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 485         return *this;
 486       }
 487
 488       dynamic_bitset<_WordT, _Alloc>&
 489       _M_unchecked_set(size_type __pos, int __val)
 490       {
 491         if (__val)
 492           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 493         else
 494           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 495         return *this;
 496       }
 497
 498       dynamic_bitset<_WordT, _Alloc>&
 499       _M_unchecked_reset(size_type __pos)
 500       {
 501         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 502         return *this;
 503       }
 504
 505       dynamic_bitset<_WordT, _Alloc>&
 506       _M_unchecked_flip(size_type __pos)
 507       {
 508         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
 509         return *this;
 510       }
 511
 512       bool
 513       _M_unchecked_test(size_type __pos) const
 514       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
 515                 != static_cast<_WordT>(0)); }
 516
 517       size_type _M_Nb;
 518
 519     public:
 520       /**
 521        *  This encapsulates the concept of a single bit.  An instance
 522        *  of this class is a proxy for an actual bit; this way the
 523        *  individual bit operations are done as faster word-size
 524        *  bitwise instructions.
 525        *
 526        *  Most users will never need to use this class directly;
 527        *  conversions to and from bool are automatic and should be
 528        *  transparent.  Overloaded operators help to preserve the
 529        *  illusion.
 530        *
 531        *  (On a typical system, this "bit %reference" is 64 times the
 532        *  size of an actual bit.  Ha.)
 533        */
 534       class reference
 535       {
 536         friend class dynamic_bitset;
 537
 538         block_type *_M_wp;
 539         size_type _M_bpos;
 540
 541         // left undefined
 542         reference();
 543
 544       public:
 545         reference(dynamic_bitset& __b, size_type __pos)
 546         {
 547           this->_M_wp = &__b._M_getword(__pos);
 548           this->_M_bpos = _Base::_S_whichbit(__pos);
 549         }
 550
 551         ~reference()
 552         { }
 553
 554         // For b[i] = __x;
 555         reference&
 556         operator=(bool __x)
 557         {
 558           if (__x)
 559             *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
 560           else
 561             *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
 562           return *this;
 563         }
 564
 565         // For b[i] = b[__j];
 566         reference&
 567         operator=(const reference& __j)
 568         {
 569           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
 570             *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
 571           else
 572             *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
 573           return *this;
 574         }
 575
 576         // Flips the bit
 577         bool
 578         operator~() const
 579         { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
 580
 581         // For __x = b[i];
 582         operator bool() const
 583         { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
 584
 585         // For b[i].flip();
 586         reference&
 587         flip()
 588         {
 589           *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
 590           return *this;
 591         }
 592       };
 593
 594       friend class reference;
 595
 596       typedef bool const_reference;
 597
 598       // 23.3.5.1 constructors:
 599       /// All bits set to zero.
 600       explicit
 601       dynamic_bitset(const allocator_type& __alloc = allocator_type())
 602       : _Base(__alloc), _M_Nb(0)
 603       { }
 604
 605       /// Initial bits bitwise-copied from a single word (others set to zero).
 606       explicit
 607       dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
 608                      const allocator_type& __alloc = allocator_type())
 609       : _Base(__nbits, __val, __alloc),
 610         _M_Nb(__nbits)
 611       { }
 612
 613       dynamic_bitset(initializer_list<block_type> __il,
 614                      const allocator_type& __alloc = allocator_type())
 615       : _Base(__alloc), _M_Nb(0)
 616       { this->append(__il); }
 617
 618       /**
 619        *  @brief  Use a subset of a string.
 620        *  @param  __str  A string of '0' and '1' characters.
 621        *  @param  __pos  Index of the first character in @p __str to use.
 622        *  @param  __n    The number of characters to copy.
 623        *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.
 624        *  @throw  std::invalid_argument  If a character appears in the string
 625        *                                 which is neither '0' nor '1'.
 626        */
 627       template<typename _CharT, typename _Traits, typename _Alloc1>
 628         explicit
 629         dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
 630                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
 631                        __pos = 0,
 632                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
 633                        __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
 634                        _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
 635                        const allocator_type& __alloc = allocator_type())
 636         : _Base(__alloc),
 637           _M_Nb(0) // Watch for npos.
 638         {
 639           if (__pos > __str.size())
 640             __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
 641                                      "not valid"));
 642
 643           // Watch for npos.
 644           this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
 645           this->resize(this->_M_Nb);
 646           this->_M_copy_from_string(__str, __pos, __n,
 647                                     _CharT('0'), _CharT('1'));
 648         }
 649
 650       /**
 651        *  @brief  Construct from a string.
 652        *  @param  __str  A string of '0' and '1' characters.
 653        *  @throw  std::invalid_argument  If a character appears in the string
 654        *                                 which is neither '0' nor '1'.
 655        */
 656       explicit
 657       dynamic_bitset(const char* __str,
 658                      const allocator_type& __alloc = allocator_type())
 659       : _Base(__alloc)
 660       {
 661         size_t __len = 0;
 662         if (__str)
 663           while (__str[__len] != '\0')
 664             ++__len;
 665         this->resize(__len);
 666         this->_M_copy_from_ptr<char,std::char_traits<char>>
 667                    (__str, __len, 0, __len, '0', '1');
 668       }
 669
 670       /**
 671        *  @brief  Copy constructor.
 672        */
 673       dynamic_bitset(const dynamic_bitset& __b)
 674       : _Base(__b), _M_Nb(__b.size())
 675       { }
 676
 677       /**
 678        *  @brief  Move constructor.
 679        */
 680       dynamic_bitset(dynamic_bitset&& __b)
 681       : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
 682       { }
 683
 684       /**
 685        *  @brief  Swap with another bitset.
 686        */
 687       void
 688       swap(dynamic_bitset& __b)
 689       {
 690         this->_M_swap(__b);
 691         std::swap(this->_M_Nb, __b._M_Nb);
 692       }
 693
 694       /**
 695        *  @brief  Assignment.
 696        */
 697       dynamic_bitset&
 698       operator=(const dynamic_bitset& __b)
 699       {
 700         if (&__b != this)
 701           {
 702             this->_M_assign(__b);
 703             this->_M_Nb = __b._M_Nb;
 704           }
 705       }
 706
 707       /**
 708        *  @brief  Move assignment.
 709        */
 710       dynamic_bitset&
 711       operator=(dynamic_bitset&& __b)
 712       {
 713         this->swap(__b);
 714         return *this;
 715       }
 716
 717       /**
 718        *  @brief  Return the allocator for the bitset.
 719        */
 720       allocator_type
 721       get_allocator() const
 722       { return this->_M_get_allocator(); }
 723
 724       /**
 725        *  @brief  Resize the bitset.
 726        */
 727       void
 728       resize(size_type __nbits, bool __value = false)
 729       {
 730         if (__value)
 731           this->_M_do_fill();
 732         this->_M_resize(__nbits, __value);
 733         this->_M_Nb = __nbits;
 734         this->_M_do_sanitize();
 735       }
 736
 737       /**
 738        *  @brief  Clear the bitset.
 739        */
 740       void
 741       clear()
 742       {
 743         this->_M_clear();
 744         this->_M_Nb = 0;
 745       }
 746
 747       /**
 748        *  @brief  Push a bit onto the high end of the bitset.
 749        */
 750       void
 751       push_back(bool __bit)
 752       {
 753         if (size_t __offset = this->size() % bits_per_block == 0)
 754           this->_M_do_append_block(block_type(0), this->_M_Nb);
 755         ++this->_M_Nb;
 756         this->_M_unchecked_set(this->_M_Nb, __bit);
 757       }
 758
 759       /**
 760        *  @brief  Append a block.
 761        */
 762       void
 763       append(block_type __block)
 764       {
 765         this->_M_do_append_block(__block, this->_M_Nb);
 766         this->_M_Nb += bits_per_block;
 767       }
 768
 769       /**
 770        *  @brief
 771        */
 772       void
 773       append(initializer_list<block_type> __il)
 774       { this->append(__il.begin(), __il.end()); }
 775
 776       /**
 777        *  @brief  Append an iterator range of blocks.
 778        */
 779       template <typename _BlockInputIterator>
 780         void
 781         append(_BlockInputIterator __first, _BlockInputIterator __last)
 782         {
 783           for (; __first != __last; ++__first)
 784             this->append(*__first);
 785         }
 786
 787       // 23.3.5.2 dynamic_bitset operations:
 788       //@{
 789       /**
 790        *  @brief  Operations on dynamic_bitsets.
 791        *  @param  __rhs  A same-sized dynamic_bitset.
 792        *
 793        *  These should be self-explanatory.
 794        */
 795       dynamic_bitset<_WordT, _Alloc>&
 796       operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
 797       {
 798         this->_M_do_and(__rhs);
 799         return *this;
 800       }
 801
 802       dynamic_bitset<_WordT, _Alloc>&
 803       operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
 804       {
 805         this->_M_do_and(std::move(__rhs));
 806         return *this;
 807       }
 808
 809       dynamic_bitset<_WordT, _Alloc>&
 810       operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
 811       {
 812         this->_M_do_or(__rhs);
 813         return *this;
 814       }
 815
 816       dynamic_bitset<_WordT, _Alloc>&
 817       operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
 818       {
 819         this->_M_do_xor(__rhs);
 820         return *this;
 821       }
 822
 823       dynamic_bitset<_WordT, _Alloc>&
 824       operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
 825       {
 826         this->_M_do_dif(__rhs);
 827         return *this;
 828       }
 829       //@}
 830
 831       //@{
 832       /**
 833        *  @brief  Operations on dynamic_bitsets.
 834        *  @param  __pos The number of places to shift.
 835        *
 836        *  These should be self-explanatory.
 837        */
 838       dynamic_bitset<_WordT, _Alloc>&
 839       operator<<=(size_type __pos)
 840       {
 841         if (__builtin_expect(__pos < this->_M_Nb, 1))
 842           {
 843             this->_M_do_left_shift(__pos);
 844             this->_M_do_sanitize();
 845           }
 846         else
 847           this->_M_do_reset();
 848         return *this;
 849       }
 850
 851       dynamic_bitset<_WordT, _Alloc>&
 852       operator>>=(size_type __pos)
 853       {
 854         if (__builtin_expect(__pos < this->_M_Nb, 1))
 855           {
 856             this->_M_do_right_shift(__pos);
 857             this->_M_do_sanitize();
 858           }
 859         else
 860           this->_M_do_reset();
 861         return *this;
 862       }
 863       //@}
 864
 865       // Set, reset, and flip.
 866       /**
 867        *  @brief Sets every bit to true.
 868        */
 869       dynamic_bitset<_WordT, _Alloc>&
 870       set()
 871       {
 872         this->_M_do_set();
 873         this->_M_do_sanitize();
 874         return *this;
 875       }
 876
 877       /**
 878        *  @brief Sets a given bit to a particular value.
 879        *  @param  __pos  The index of the bit.
 880        *  @param  __val  Either true or false, defaults to true.
 881        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
 882        */
 883       dynamic_bitset<_WordT, _Alloc>&
 884       set(size_type __pos, bool __val = true)
 885       {
 886         if (__pos >= _M_Nb)
 887           __throw_out_of_range(__N("dynamic_bitset::set"));
 888         return this->_M_unchecked_set(__pos, __val);
 889       }
 890
 891       /**
 892        *  @brief Sets every bit to false.
 893        */
 894       dynamic_bitset<_WordT, _Alloc>&
 895       reset()
 896       {
 897         this->_M_do_reset();
 898         return *this;
 899       }
 900
 901       /**
 902        *  @brief Sets a given bit to false.
 903        *  @param  __pos  The index of the bit.
 904        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
 905        *
 906        *  Same as writing @c set(__pos, false).
 907        */
 908       dynamic_bitset<_WordT, _Alloc>&
 909       reset(size_type __pos)
 910       {
 911         if (__pos >= _M_Nb)
 912           __throw_out_of_range(__N("dynamic_bitset::reset"));
 913         return this->_M_unchecked_reset(__pos);
 914       }
 915
 916       /**
 917        *  @brief Toggles every bit to its opposite value.
 918        */
 919       dynamic_bitset<_WordT, _Alloc>&
 920       flip()
 921       {
 922         this->_M_do_flip();
 923         this->_M_do_sanitize();
 924         return *this;
 925       }
 926
 927       /**
 928        *  @brief Toggles a given bit to its opposite value.
 929        *  @param  __pos  The index of the bit.
 930        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
 931        */
 932       dynamic_bitset<_WordT, _Alloc>&
 933       flip(size_type __pos)
 934       {
 935         if (__pos >= _M_Nb)
 936           __throw_out_of_range(__N("dynamic_bitset::flip"));
 937         return this->_M_unchecked_flip(__pos);
 938       }
 939
 940       /// See the no-argument flip().
 941       dynamic_bitset<_WordT, _Alloc>
 942       operator~() const
 943       { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
 944
 945       //@{
 946       /**
 947        *  @brief  Array-indexing support.
 948        *  @param  __pos  Index into the %dynamic_bitset.
 949        *  @return A bool for a 'const %dynamic_bitset'.  For non-const
 950        *           bitsets, an instance of the reference proxy class.
 951        *  @note These operators do no range checking and throw no
 952        *         exceptions, as required by DR 11 to the standard.
 953        */
 954       reference
 955       operator[](size_type __pos)
 956       { return reference(*this,__pos); }
 957
 958       const_reference
 959       operator[](size_type __pos) const
 960       { return _M_unchecked_test(__pos); }
 961       //@}
 962
 963       /**
 964        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
 965        *  @return  The integral equivalent of the bits.
 966        *  @throw  std::overflow_error  If there are too many bits to be
 967        *                               represented in an @c unsigned @c long.
 968        */
 969       unsigned long
 970       to_ulong() const
 971       { return this->_M_do_to_ulong(); }
 972
 973       /**
 974        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
 975        *  @return  The integral equivalent of the bits.
 976        *  @throw  std::overflow_error  If there are too many bits to be
 977        *                               represented in an @c unsigned @c long.
 978        */
 979       unsigned long long
 980       to_ullong() const
 981       { return this->_M_do_to_ullong(); }
 982
 983       /**
 984        *  @brief Returns a character interpretation of the %dynamic_bitset.
 985        *  @return  The string equivalent of the bits.
 986        *
 987        *  Note the ordering of the bits:  decreasing character positions
 988        *  correspond to increasing bit positions (see the main class notes for
 989        *  an example).
 990        */
 991       template<typename _CharT = char,
 992                typename _Traits = std::char_traits<_CharT>,
 993                typename _Alloc1 = std::allocator<_CharT>>
 994         std::basic_string<_CharT, _Traits, _Alloc1>
 995         to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
 996         {
 997           std::basic_string<_CharT, _Traits, _Alloc1> __result;
 998           _M_copy_to_string(__result, __zero, __one);
 999           return __result;
1000         }
1001
1002       // Helper functions for string operations.
1003       template<typename _CharT, typename _Traits>
1004         void
1005         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1006                          _CharT, _CharT);
1007
1008       template<typename _CharT, typename _Traits, typename _Alloc1>
1009         void
1010         _M_copy_from_string(const std::basic_string<_CharT,
1011                             _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
1012                             _CharT __zero = _CharT('0'),
1013                             _CharT __one = _CharT('1'))
1014         { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
1015                                             __pos, __n, __zero, __one); }
1016
1017       template<typename _CharT, typename _Traits, typename _Alloc1>
1018         void
1019         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1020                           _CharT __zero = _CharT('0'),
1021                           _CharT __one = _CharT('1')) const;
1022
1023       /// Returns the number of bits which are set.
1024       size_type
1025       count() const noexcept
1026       { return this->_M_do_count(); }
1027
1028       /// Returns the total number of bits.
1029       size_type
1030       size() const noexcept
1031       { return this->_M_Nb; }
1032
1033       /// Returns the total number of blocks.
1034       size_type
1035       num_blocks() const noexcept
1036       { return this->_M_size(); }
1037
1038       /// Returns true if the dynamic_bitset is empty.
1039       bool
1040       empty() const noexcept
1041       { return (this->_M_Nb == 0); }
1042
1043       /// Returns the maximum size of a dynamic_bitset object having the same
1044       /// type as *this.
1045       /// The real answer is max() * bits_per_block but is likely to overflow.
1046       constexpr size_type
1047       max_size() noexcept
1048       { return std::numeric_limits<block_type>::max(); }
1049
1050       /**
1051        *  @brief Tests the value of a bit.
1052        *  @param  __pos  The index of a bit.
1053        *  @return  The value at @a __pos.
1054        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
1055        */
1056       bool
1057       test(size_type __pos) const
1058       {
1059         if (__pos >= _M_Nb)
1060           __throw_out_of_range(__N("dynamic_bitset::test"));
1061         return _M_unchecked_test(__pos);
1062       }
1063
1064       /**
1065        *  @brief Tests whether all the bits are on.
1066        *  @return  True if all the bits are set.
1067        */
1068       bool
1069       all() const
1070       { return this->_M_are_all_aux() == _M_Nb; }
1071
1072       /**
1073        *  @brief Tests whether any of the bits are on.
1074        *  @return  True if at least one bit is set.
1075        */
1076       bool
1077       any() const
1078       { return this->_M_is_any(); }
1079
1080       /**
1081        *  @brief Tests whether any of the bits are on.
1082        *  @return  True if none of the bits are set.
1083        */
1084       bool
1085       none() const
1086       { return !this->_M_is_any(); }
1087
1088       //@{
1089       /// Self-explanatory.
1090       dynamic_bitset<_WordT, _Alloc>
1091       operator<<(size_type __pos) const
1092       { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1093
1094       dynamic_bitset<_WordT, _Alloc>
1095       operator>>(size_type __pos) const
1096       { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1097       //@}
1098
1099       /**
1100        *  @brief  Finds the index of the first "on" bit.
1101        *  @return  The index of the first bit set, or size() if not found.
1102        *  @sa  find_next
1103        */
1104       size_type
1105       find_first() const
1106       { return this->_M_do_find_first(this->_M_Nb); }
1107
1108       /**
1109        *  @brief  Finds the index of the next "on" bit after prev.
1110        *  @return  The index of the next bit set, or size() if not found.
1111        *  @param  __prev  Where to start searching.
1112        *  @sa  find_first
1113        */
1114       size_type
1115       find_next(size_t __prev) const
1116       { return this->_M_do_find_next(__prev, this->_M_Nb); }
1117
1118       bool
1119       is_subset_of(const dynamic_bitset& __b) const
1120       { return this->_M_is_subset_of(__b); }
1121
1122       bool
1123       is_proper_subset_of(const dynamic_bitset& __b) const
1124       { return this->_M_is_proper_subset_of(__b); }
1125
1126       friend bool
1127       operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1128                  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1129       { return __lhs._M_is_equal(__rhs); }
1130
1131       friend bool
1132       operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1133                 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1134       { return __lhs._M_is_less(__rhs); }
1135     };
1136
1137   template<typename _WordT, typename _Alloc>
1138     template<typename _CharT, typename _Traits, typename _Alloc1>
1139       inline void
1140       dynamic_bitset<_WordT, _Alloc>::
1141       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1142                         _CharT __zero, _CharT __one) const
1143       {
1144         __str.assign(_M_Nb, __zero);
1145         for (size_t __i = _M_Nb; __i > 0; --__i)
1146           if (_M_unchecked_test(__i - 1))
1147             _Traits::assign(__str[_M_Nb - __i], __one);
1148       }
1149
1150
1151   //@{
1152   /// These comparisons for equality/inequality are, well, @e bitwise.
1153
1154   template<typename _WordT, typename _Alloc>
1155     inline bool
1156     operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1157                const dynamic_bitset<_WordT, _Alloc>& __rhs)
1158     { return !(__lhs == __rhs); }
1159
1160   template<typename _WordT, typename _Alloc>
1161     inline bool
1162     operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1163                const dynamic_bitset<_WordT, _Alloc>& __rhs)
1164     { return !(__lhs > __rhs); }
1165
1166   template<typename _WordT, typename _Alloc>
1167     inline bool
1168     operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1169               const dynamic_bitset<_WordT, _Alloc>& __rhs)
1170     { return __rhs < __lhs; }
1171
1172   template<typename _WordT, typename _Alloc>
1173     inline bool
1174     operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1175                const dynamic_bitset<_WordT, _Alloc>& __rhs)
1176     { return !(__lhs < __rhs); }
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<typename _WordT, typename _Alloc>
1190     inline dynamic_bitset<_WordT, _Alloc>
1191     operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1192               const dynamic_bitset<_WordT, _Alloc>& __y)
1193     {
1194       dynamic_bitset<_WordT, _Alloc> __result(__x);
1195       __result &= __y;
1196       return __result;
1197     }
1198
1199   template<typename _WordT, typename _Alloc>
1200     inline dynamic_bitset<_WordT, _Alloc>
1201     operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1202               const dynamic_bitset<_WordT, _Alloc>& __y)
1203     {
1204       dynamic_bitset<_WordT, _Alloc> __result(__x);
1205       __result |= __y;
1206       return __result;
1207     }
1208
1209   template <typename _WordT, typename _Alloc>
1210     inline dynamic_bitset<_WordT, _Alloc>
1211     operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1212               const dynamic_bitset<_WordT, _Alloc>& __y)
1213     {
1214       dynamic_bitset<_WordT, _Alloc> __result(__x);
1215       __result ^= __y;
1216       return __result;
1217     }
1218
1219   template <typename _WordT, typename _Alloc>
1220     inline dynamic_bitset<_WordT, _Alloc>
1221     operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1222               const dynamic_bitset<_WordT, _Alloc>& __y)
1223     {
1224       dynamic_bitset<_WordT, _Alloc> __result(__x);
1225       __result -= __y;
1226       return __result;
1227     }
1228   //@}
1229
1230   /**
1231    *  @defgroup Global I/O operators for bitsets.
1232    *  @{
1233    *  @brief Global I/O operators for bitsets.
1234    *
1235    *  Direct I/O between streams and bitsets is supported.  Output is
1236    *  straightforward.  Input will skip whitespace and only accept '0'
1237    *  and '1' characters.  The %dynamic_bitset will grow as necessary
1238    *  to hold the string of bits.
1239    */
1240   template <typename _CharT, typename _Traits,
1241             typename _WordT, typename _Alloc>
1242     inline std::basic_ostream<_CharT, _Traits>&
1243     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1244                const dynamic_bitset<_WordT, _Alloc>& __x)
1245     {
1246       std::basic_string<_CharT, _Traits> __tmp;
1247
1248       const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1249       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1250       return __os << __tmp;
1251     }
1252   /**
1253    *  @}
1254    */
1255
1256 _GLIBCXX_END_NAMESPACE_VERSION
1257 } // tr2
1258 } // std
1259
1260 #include <tr2/dynamic_bitset.tcc>
1261
1262 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */