contrib/gcc-5.0/libstdc++-v3/include/tr2/dynamic_bitset

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