libstdc++
dynamic_bitset
Go to the documentation of this file.
00001 // TR2 <dynamic_bitset> -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file tr2/dynamic_bitset
00026  *  This is a TR2 C++ Library header.
00027  */
00028 
00029 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
00030 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
00031 
00032 #pragma GCC system_header
00033 
00034 #include <limits>
00035 #include <vector>
00036 #include <string>
00037 #include <memory> // For std::allocator
00038 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
00039                                 // overflow_error
00040 #include <iosfwd>
00041 #include <bits/cxxabi_forced.h>
00042 
00043 namespace std _GLIBCXX_VISIBILITY(default)
00044 {
00045 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00046 
00047 namespace tr2
00048 {
00049   /**
00050    *  @defgroup dynamic_bitset Dynamic Bitset.
00051    *  @ingroup extensions
00052    *
00053    *  @{
00054    */
00055 
00056   /**
00057    *  Base class, general case.
00058    *
00059    *  See documentation for dynamic_bitset.
00060    */
00061   template<typename _WordT = unsigned long long,
00062            typename _Alloc = std::allocator<_WordT>>
00063     struct __dynamic_bitset_base
00064     {
00065       static_assert(std::is_unsigned<_WordT>::value, "template argument "
00066                     "_WordT not an unsigned integral type");
00067 
00068       typedef _WordT block_type;
00069       typedef _Alloc allocator_type;
00070       typedef size_t size_type;
00071 
00072       static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
00073       static const size_type npos = static_cast<size_type>(-1);
00074 
00075       /// 0 is the least significant word.
00076       std::vector<block_type, allocator_type> _M_w;
00077 
00078       explicit
00079       __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
00080       : _M_w(__alloc)
00081       { }
00082 
00083       explicit
00084       __dynamic_bitset_base(__dynamic_bitset_base&& __b)
00085       { this->_M_w.swap(__b._M_w); }
00086 
00087       explicit
00088       __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
00089                            const allocator_type& __alloc = allocator_type())
00090       : _M_w(__nbits / _S_bits_per_block
00091              + (__nbits % _S_bits_per_block > 0),
00092              __val, __alloc)
00093       {
00094         unsigned long long __mask = ~static_cast<block_type>(0);
00095         size_t __n = std::min(this->_M_w.size(),
00096                               sizeof(unsigned long long) / sizeof(block_type));
00097         for (size_t __i = 0; __i < __n; ++__i)
00098           {
00099             this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
00100             __mask <<= _S_bits_per_block;
00101           }
00102       }
00103 
00104       void
00105       _M_assign(const __dynamic_bitset_base& __b)
00106       { this->_M_w = __b._M_w; }
00107 
00108       void
00109       _M_swap(__dynamic_bitset_base& __b)
00110       { this->_M_w.swap(__b._M_w); }
00111 
00112       void
00113       _M_clear()
00114       { this->_M_w.clear(); }
00115 
00116       void
00117       _M_resize(size_t __nbits, bool __value)
00118       {
00119         size_t __sz = __nbits / _S_bits_per_block;
00120         if (__nbits % _S_bits_per_block > 0)
00121           ++__sz;
00122         if (__sz != this->_M_w.size())
00123           {
00124             block_type __val = 0;
00125             if (__value)
00126               __val = std::numeric_limits<block_type>::max();
00127             this->_M_w.resize(__sz, __val);
00128           }
00129       }
00130 
00131       allocator_type
00132       _M_get_allocator() const
00133       { return this->_M_w.get_allocator(); }
00134 
00135       static size_type
00136       _S_whichword(size_type __pos) noexcept
00137       { return __pos / _S_bits_per_block; }
00138 
00139       static size_type
00140       _S_whichbyte(size_type __pos) noexcept
00141       { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
00142 
00143       static size_type
00144       _S_whichbit(size_type __pos) noexcept
00145       { return __pos % _S_bits_per_block; }
00146 
00147       static block_type
00148       _S_maskbit(size_type __pos) noexcept
00149       { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
00150 
00151       block_type&
00152       _M_getword(size_type __pos)
00153       { return this->_M_w[_S_whichword(__pos)]; }
00154 
00155       block_type
00156       _M_getword(size_type __pos) const
00157       { return this->_M_w[_S_whichword(__pos)]; }
00158 
00159       block_type&
00160       _M_hiword()
00161       { return this->_M_w[_M_w.size() - 1]; }
00162 
00163       block_type
00164       _M_hiword() const
00165       { return this->_M_w[_M_w.size() - 1]; }
00166 
00167       void
00168       _M_do_and(const __dynamic_bitset_base& __x)
00169       {
00170         if (__x._M_w.size() == this->_M_w.size())
00171           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00172             this->_M_w[__i] &= __x._M_w[__i];
00173         else
00174           return;
00175       }
00176 
00177       void
00178       _M_do_or(const __dynamic_bitset_base& __x)
00179       {
00180         if (__x._M_w.size() == this->_M_w.size())
00181           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00182             this->_M_w[__i] |= __x._M_w[__i];
00183         else
00184           return;
00185       }
00186 
00187       void
00188       _M_do_xor(const __dynamic_bitset_base& __x)
00189       {
00190         if (__x._M_w.size() == this->_M_w.size())
00191           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00192             this->_M_w[__i] ^= __x._M_w[__i];
00193         else
00194           return;
00195       }
00196 
00197       void
00198       _M_do_dif(const __dynamic_bitset_base& __x)
00199       {
00200         if (__x._M_w.size() == this->_M_w.size())
00201           for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00202             this->_M_w[__i] &= ~__x._M_w[__i];
00203         else
00204           return;
00205       }
00206 
00207       void
00208       _M_do_left_shift(size_t __shift);
00209 
00210       void
00211       _M_do_right_shift(size_t __shift);
00212 
00213       void
00214       _M_do_flip()
00215       {
00216         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00217           this->_M_w[__i] = ~this->_M_w[__i];
00218       }
00219 
00220       void
00221       _M_do_set()
00222       {
00223         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00224           this->_M_w[__i] = ~static_cast<block_type>(0);
00225       }
00226 
00227       void
00228       _M_do_reset()
00229       {
00230         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00231           this->_M_w[__i] = static_cast<block_type>(0);
00232       }
00233 
00234       bool
00235       _M_is_equal(const __dynamic_bitset_base& __x) const
00236       {
00237         if (__x._M_w.size() == this->_M_w.size())
00238           {
00239             for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00240               if (this->_M_w[__i] != __x._M_w[__i])
00241                 return false;
00242             return true;
00243           }
00244         else
00245           return false;
00246       }
00247 
00248       bool
00249       _M_is_less(const __dynamic_bitset_base& __x) const
00250       {
00251         if (__x._M_w.size() == this->_M_w.size())
00252           {
00253             for (size_t __i = this->_M_w.size(); __i > 0; --__i)
00254               {
00255                 if (this->_M_w[__i-1] < __x._M_w[__i-1])
00256                   return true;
00257                 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
00258                   return false;
00259               }
00260             return false;
00261           }
00262         else
00263           return false;
00264       }
00265 
00266       size_t
00267       _M_are_all_aux() const
00268       {
00269         for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
00270           if (_M_w[__i] != ~static_cast<block_type>(0))
00271             return 0;
00272         return ((this->_M_w.size() - 1) * _S_bits_per_block
00273                 + __builtin_popcountll(this->_M_hiword()));
00274       }
00275 
00276       bool
00277       _M_is_any() const
00278       {
00279         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00280           if (this->_M_w[__i] != static_cast<block_type>(0))
00281             return true;
00282         return false;
00283       }
00284 
00285       bool
00286       _M_is_subset_of(const __dynamic_bitset_base& __b)
00287       {
00288         if (__b._M_w.size() == this->_M_w.size())
00289           {
00290             for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00291               if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
00292                 return false;
00293             return true;
00294           }
00295         else
00296           return false;
00297       }
00298 
00299       bool
00300       _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
00301       {
00302         if (this->is_subset_of(__b))
00303           {
00304             if (*this == __b)
00305               return false;
00306             else
00307               return true;
00308           }
00309         else
00310           return false;
00311       }
00312 
00313       size_t
00314       _M_do_count() const
00315       {
00316         size_t __result = 0;
00317         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00318           __result += __builtin_popcountll(this->_M_w[__i]);
00319         return __result;
00320       }
00321 
00322       size_type
00323       _M_size() const noexcept
00324       { return this->_M_w.size(); }
00325 
00326       unsigned long
00327       _M_do_to_ulong() const;
00328 
00329       unsigned long long
00330       _M_do_to_ullong() const;
00331 
00332       // find first "on" bit
00333       size_type
00334       _M_do_find_first(size_t __not_found) const;
00335 
00336       // find the next "on" bit that follows "prev"
00337       size_type
00338       _M_do_find_next(size_t __prev, size_t __not_found) const;
00339 
00340       // do append of block
00341       void
00342       _M_do_append_block(block_type __block, size_type __pos)
00343       {
00344         size_t __offset = __pos % _S_bits_per_block;
00345         if (__offset == 0)
00346           this->_M_w.push_back(__block);
00347         else
00348           {
00349             this->_M_hiword() |= (__block << __offset);
00350             this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
00351           }
00352       }
00353     };
00354 
00355   /**
00356    *  @brief  The %dynamic_bitset class represents a sequence of bits.
00357    *
00358    *  See N2050,
00359    *  Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
00360    *
00361    *  In the general unoptimized case, storage is allocated in
00362    *  word-sized blocks.  Let B be the number of bits in a word, then
00363    *  (Nb+(B-1))/B words will be used for storage.  B - Nb%B bits are
00364    *  unused.  (They are the high-order bits in the highest word.)  It
00365    *  is a class invariant that those unused bits are always zero.
00366    *
00367    *  If you think of %dynamic_bitset as "a simple array of bits," be
00368    *  aware that your mental picture is reversed: a %dynamic_bitset
00369    *  behaves the same way as bits in integers do, with the bit at
00370    *  index 0 in the "least significant / right-hand" position, and
00371    *  the bit at index Nb-1 in the "most significant / left-hand"
00372    *  position.  Thus, unlike other containers, a %dynamic_bitset's
00373    *  index "counts from right to left," to put it very loosely.
00374    *
00375    *  This behavior is preserved when translating to and from strings.
00376    *  For example, the first line of the following program probably
00377    *  prints "b('a') is 0001100001" on a modern ASCII system.
00378    *
00379    *  @code
00380    *     #include <dynamic_bitset>
00381    *     #include <iostream>
00382    *     #include <sstream>
00383    *
00384    *     using namespace std;
00385    *
00386    *     int main()
00387    *     {
00388    *         long         a = 'a';
00389    *         dynamic_bitset<> b(a);
00390    *
00391    *         cout << "b('a') is " << b << endl;
00392    *
00393    *         ostringstream s;
00394    *         s << b;
00395    *         string  str = s.str();
00396    *         cout << "index 3 in the string is " << str[3] << " but\n"
00397    *              << "index 3 in the bitset is " << b[3] << endl;
00398    *     }
00399    *  @endcode
00400    *
00401    *  Most of the actual code isn't contained in %dynamic_bitset<>
00402    *  itself, but in the base class __dynamic_bitset_base.  The base
00403    *  class works with whole words, not with individual bits.  This
00404    *  allows us to specialize __dynamic_bitset_base for the important
00405    *  special case where the %dynamic_bitset is only a single word.
00406    *
00407    *  Extra confusion can result due to the fact that the storage for
00408    *  __dynamic_bitset_base @e is a vector, and is indexed as such.  This is
00409    *  carefully encapsulated.
00410    */
00411   template<typename _WordT = unsigned long long,
00412            typename _Alloc = std::allocator<_WordT>>
00413     class dynamic_bitset
00414     : private __dynamic_bitset_base<_WordT, _Alloc>
00415     {
00416       static_assert(std::is_unsigned<_WordT>::value, "template argument "
00417                     "_WordT not an unsigned integral type");
00418 
00419     public:
00420 
00421       typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
00422       typedef _WordT block_type;
00423       typedef _Alloc allocator_type;
00424       typedef size_t size_type;
00425 
00426       static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
00427       // Use this: constexpr size_type std::numeric_limits<size_type>::max().
00428       static const size_type npos = static_cast<size_type>(-1);
00429 
00430     private:
00431 
00432       //  Clear the unused bits in the uppermost word.
00433       void
00434       _M_do_sanitize()
00435       {
00436         size_type __shift = this->_M_Nb % bits_per_block;
00437         if (__shift > 0)
00438           this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
00439       }
00440 
00441       //  Set the unused bits in the uppermost word.
00442       void
00443       _M_do_fill()
00444       {
00445         size_type __shift = this->_M_Nb % bits_per_block;
00446         if (__shift > 0)
00447           this->_M_hiword() |= ((~static_cast<block_type>(0)) << __shift);
00448       }
00449 
00450       /**
00451        *  These versions of single-bit set, reset, flip, and test
00452        *  do no range checking.
00453        */
00454       dynamic_bitset<_WordT, _Alloc>&
00455       _M_unchecked_set(size_type __pos)
00456       {
00457         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00458         return *this;
00459       }
00460 
00461       dynamic_bitset<_WordT, _Alloc>&
00462       _M_unchecked_set(size_type __pos, int __val)
00463       {
00464         if (__val)
00465           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00466         else
00467           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00468         return *this;
00469       }
00470 
00471       dynamic_bitset<_WordT, _Alloc>&
00472       _M_unchecked_reset(size_type __pos)
00473       {
00474         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00475         return *this;
00476       }
00477 
00478       dynamic_bitset<_WordT, _Alloc>&
00479       _M_unchecked_flip(size_type __pos)
00480       {
00481         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
00482         return *this;
00483       }
00484 
00485       bool
00486       _M_unchecked_test(size_type __pos) const
00487       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
00488                 != static_cast<_WordT>(0)); }
00489 
00490       size_type _M_Nb;
00491 
00492     public:
00493       /**
00494        *  This encapsulates the concept of a single bit.  An instance
00495        *  of this class is a proxy for an actual bit; this way the
00496        *  individual bit operations are done as faster word-size
00497        *  bitwise instructions.
00498        *
00499        *  Most users will never need to use this class directly;
00500        *  conversions to and from bool are automatic and should be
00501        *  transparent.  Overloaded operators help to preserve the
00502        *  illusion.
00503        *
00504        *  (On a typical system, this "bit %reference" is 64 times the
00505        *  size of an actual bit.  Ha.)
00506        */
00507       class reference
00508       {
00509         friend class dynamic_bitset;
00510 
00511         block_type *_M_wp;
00512         size_type _M_bpos;
00513 
00514         // left undefined
00515         reference();
00516 
00517       public:
00518         reference(dynamic_bitset& __b, size_type __pos)
00519         {
00520           this->_M_wp = &__b._M_getword(__pos);
00521           this->_M_bpos = _Base::_S_whichbit(__pos);
00522         }
00523 
00524         ~reference()
00525         { }
00526 
00527         // For b[i] = __x;
00528         reference&
00529         operator=(bool __x)
00530         {
00531           if (__x)
00532             *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
00533           else
00534             *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
00535           return *this;
00536         }
00537 
00538         // For b[i] = b[__j];
00539         reference&
00540         operator=(const reference& __j)
00541         {
00542           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
00543             *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
00544           else
00545             *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
00546           return *this;
00547         }
00548 
00549         // Flips the bit
00550         bool
00551         operator~() const
00552         { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
00553 
00554         // For __x = b[i];
00555         operator bool() const
00556         { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
00557 
00558         // For b[i].flip();
00559         reference&
00560         flip()
00561         {
00562           *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
00563           return *this;
00564         }
00565       };
00566 
00567       friend class reference;
00568 
00569       typedef bool const_reference;
00570 
00571       // 23.3.5.1 constructors:
00572       /// All bits set to zero.
00573       explicit
00574       dynamic_bitset(const allocator_type& __alloc = allocator_type())
00575       : _Base(__alloc), _M_Nb(0)
00576       { }
00577 
00578       /// Initial bits bitwise-copied from a single word (others set to zero).
00579       explicit
00580       dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
00581                      const allocator_type& __alloc = allocator_type())
00582       : _Base(__nbits, __val, __alloc),
00583         _M_Nb(__nbits)
00584       { }
00585 
00586       dynamic_bitset(initializer_list<block_type> __il,
00587                      const allocator_type& __alloc = allocator_type())
00588       : _Base(__alloc), _M_Nb(0)
00589       { this->append(__il); }
00590 
00591       /**
00592        *  @brief  Use a subset of a string.
00593        *  @param  __str  A string of '0' and '1' characters.
00594        *  @param  __pos  Index of the first character in @p __str to use.
00595        *  @param  __n    The number of characters to copy.
00596        *  @param  __zero The character to use for unset bits.
00597        *  @param  __one  The character to use for set bits.
00598        *  @param  __alloc An allocator.
00599        *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.
00600        *  @throw  std::invalid_argument  If a character appears in the string
00601        *                                 which is neither '0' nor '1'.
00602        */
00603       template<typename _CharT, typename _Traits, typename _Alloc1>
00604         explicit
00605         dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
00606                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00607                        __pos = 0,
00608                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00609                        __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
00610                        _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
00611                        const allocator_type& __alloc = allocator_type())
00612         : _Base(__alloc),
00613           _M_Nb(0) // Watch for npos.
00614         {
00615           if (__pos > __str.size())
00616             __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
00617                                      "not valid"));
00618 
00619           // Watch for npos.
00620           this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
00621           this->resize(this->_M_Nb);
00622           this->_M_copy_from_string(__str, __pos, __n,
00623                                     _CharT('0'), _CharT('1'));
00624         }
00625 
00626       /**
00627        *  @brief  Construct from a string.
00628        *  @param  __str  A string of '0' and '1' characters.
00629        *  @param  __alloc An allocator.
00630        *  @throw  std::invalid_argument  If a character appears in the string
00631        *                                 which is neither '0' nor '1'.
00632        */
00633       explicit
00634       dynamic_bitset(const char* __str,
00635                      const allocator_type& __alloc = allocator_type())
00636       : _Base(__alloc)
00637       {
00638         size_t __len = 0;
00639         if (__str)
00640           while (__str[__len] != '\0')
00641             ++__len;
00642         this->resize(__len);
00643         this->_M_copy_from_ptr<char,std::char_traits<char>>
00644                    (__str, __len, 0, __len, '0', '1');
00645       }
00646 
00647       /**
00648        *  @brief  Copy constructor.
00649        */
00650       dynamic_bitset(const dynamic_bitset& __b)
00651       : _Base(__b), _M_Nb(__b.size())
00652       { }
00653 
00654       /**
00655        *  @brief  Move constructor.
00656        */
00657       dynamic_bitset(dynamic_bitset&& __b)
00658       : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
00659       { }
00660 
00661       /**
00662        *  @brief  Swap with another bitset.
00663        */
00664       void
00665       swap(dynamic_bitset& __b)
00666       {
00667         this->_M_swap(__b);
00668         std::swap(this->_M_Nb, __b._M_Nb);
00669       }
00670 
00671       /**
00672        *  @brief  Assignment.
00673        */
00674       dynamic_bitset&
00675       operator=(const dynamic_bitset& __b)
00676       {
00677         if (&__b != this)
00678           {
00679             this->_M_assign(__b);
00680             this->_M_Nb = __b._M_Nb;
00681           }
00682       }
00683 
00684       /**
00685        *  @brief  Move assignment.
00686        */
00687       dynamic_bitset&
00688       operator=(dynamic_bitset&& __b)
00689       {
00690         this->swap(__b);
00691         return *this;
00692       }
00693 
00694       /**
00695        *  @brief  Return the allocator for the bitset.
00696        */
00697       allocator_type
00698       get_allocator() const
00699       { return this->_M_get_allocator(); }
00700 
00701       /**
00702        *  @brief  Resize the bitset.
00703        */
00704       void
00705       resize(size_type __nbits, bool __value = false)
00706       {
00707         if (__value)
00708           this->_M_do_fill();
00709         this->_M_resize(__nbits, __value);
00710         this->_M_Nb = __nbits;
00711         this->_M_do_sanitize();
00712       }
00713 
00714       /**
00715        *  @brief  Clear the bitset.
00716        */
00717       void
00718       clear()
00719       {
00720         this->_M_clear();
00721         this->_M_Nb = 0;
00722       }
00723 
00724       /**
00725        *  @brief  Push a bit onto the high end of the bitset.
00726        */
00727       void
00728       push_back(bool __bit)
00729       {
00730         if (this->size() % bits_per_block == 0)
00731           this->_M_do_append_block(block_type(__bit), this->_M_Nb);
00732         else
00733           this->_M_unchecked_set(this->_M_Nb, __bit);
00734         ++this->_M_Nb;
00735       }
00736 
00737       /**
00738        *  @brief  Append a block.
00739        */
00740       void
00741       append(block_type __block)
00742       {
00743         this->_M_do_append_block(__block, this->_M_Nb);
00744         this->_M_Nb += bits_per_block;
00745       }
00746 
00747       /**
00748        *  @brief
00749        */
00750       void
00751       append(initializer_list<block_type> __il)
00752       { this->append(__il.begin(), __il.end()); }
00753 
00754       /**
00755        *  @brief  Append an iterator range of blocks.
00756        */
00757       template <typename _BlockInputIterator>
00758         void
00759         append(_BlockInputIterator __first, _BlockInputIterator __last)
00760         {
00761           for (; __first != __last; ++__first)
00762             this->append(*__first);
00763         }
00764 
00765       // 23.3.5.2 dynamic_bitset operations:
00766       //@{
00767       /**
00768        *  @brief  Operations on dynamic_bitsets.
00769        *  @param  __rhs  A same-sized dynamic_bitset.
00770        *
00771        *  These should be self-explanatory.
00772        */
00773       dynamic_bitset<_WordT, _Alloc>&
00774       operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00775       {
00776         this->_M_do_and(__rhs);
00777         return *this;
00778       }
00779 
00780       dynamic_bitset<_WordT, _Alloc>&
00781       operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
00782       {
00783         this->_M_do_and(std::move(__rhs));
00784         return *this;
00785       }
00786 
00787       dynamic_bitset<_WordT, _Alloc>&
00788       operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00789       {
00790         this->_M_do_or(__rhs);
00791         return *this;
00792       }
00793 
00794       dynamic_bitset<_WordT, _Alloc>&
00795       operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00796       {
00797         this->_M_do_xor(__rhs);
00798         return *this;
00799       }
00800 
00801       dynamic_bitset<_WordT, _Alloc>&
00802       operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00803       {
00804         this->_M_do_dif(__rhs);
00805         return *this;
00806       }
00807       //@}
00808 
00809       //@{
00810       /**
00811        *  @brief  Operations on dynamic_bitsets.
00812        *  @param  __pos The number of places to shift.
00813        *
00814        *  These should be self-explanatory.
00815        */
00816       dynamic_bitset<_WordT, _Alloc>&
00817       operator<<=(size_type __pos)
00818       {
00819         if (__builtin_expect(__pos < this->_M_Nb, 1))
00820           {
00821             this->_M_do_left_shift(__pos);
00822             this->_M_do_sanitize();
00823           }
00824         else
00825           this->_M_do_reset();
00826         return *this;
00827       }
00828 
00829       dynamic_bitset<_WordT, _Alloc>&
00830       operator>>=(size_type __pos)
00831       {
00832         if (__builtin_expect(__pos < this->_M_Nb, 1))
00833           {
00834             this->_M_do_right_shift(__pos);
00835             this->_M_do_sanitize();
00836           }
00837         else
00838           this->_M_do_reset();
00839         return *this;
00840       }
00841       //@}
00842 
00843       // Set, reset, and flip.
00844       /**
00845        *  @brief Sets every bit to true.
00846        */
00847       dynamic_bitset<_WordT, _Alloc>&
00848       set()
00849       {
00850         this->_M_do_set();
00851         this->_M_do_sanitize();
00852         return *this;
00853       }
00854 
00855       /**
00856        *  @brief Sets a given bit to a particular value.
00857        *  @param  __pos  The index of the bit.
00858        *  @param  __val  Either true or false, defaults to true.
00859        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
00860        */
00861       dynamic_bitset<_WordT, _Alloc>&
00862       set(size_type __pos, bool __val = true)
00863       {
00864         if (__pos >= _M_Nb)
00865           __throw_out_of_range(__N("dynamic_bitset::set"));
00866         return this->_M_unchecked_set(__pos, __val);
00867       }
00868 
00869       /**
00870        *  @brief Sets every bit to false.
00871        */
00872       dynamic_bitset<_WordT, _Alloc>&
00873       reset()
00874       {
00875         this->_M_do_reset();
00876         return *this;
00877       }
00878 
00879       /**
00880        *  @brief Sets a given bit to false.
00881        *  @param  __pos  The index of the bit.
00882        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
00883        *
00884        *  Same as writing @c set(__pos, false).
00885        */
00886       dynamic_bitset<_WordT, _Alloc>&
00887       reset(size_type __pos)
00888       {
00889         if (__pos >= _M_Nb)
00890           __throw_out_of_range(__N("dynamic_bitset::reset"));
00891         return this->_M_unchecked_reset(__pos);
00892       }
00893 
00894       /**
00895        *  @brief Toggles every bit to its opposite value.
00896        */
00897       dynamic_bitset<_WordT, _Alloc>&
00898       flip()
00899       {
00900         this->_M_do_flip();
00901         this->_M_do_sanitize();
00902         return *this;
00903       }
00904 
00905       /**
00906        *  @brief Toggles a given bit to its opposite value.
00907        *  @param  __pos  The index of the bit.
00908        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
00909        */
00910       dynamic_bitset<_WordT, _Alloc>&
00911       flip(size_type __pos)
00912       {
00913         if (__pos >= _M_Nb)
00914           __throw_out_of_range(__N("dynamic_bitset::flip"));
00915         return this->_M_unchecked_flip(__pos);
00916       }
00917 
00918       /// See the no-argument flip().
00919       dynamic_bitset<_WordT, _Alloc>
00920       operator~() const
00921       { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
00922 
00923       //@{
00924       /**
00925        *  @brief  Array-indexing support.
00926        *  @param  __pos  Index into the %dynamic_bitset.
00927        *  @return A bool for a 'const %dynamic_bitset'.  For non-const
00928        *           bitsets, an instance of the reference proxy class.
00929        *  @note These operators do no range checking and throw no
00930        *         exceptions, as required by DR 11 to the standard.
00931        */
00932       reference
00933       operator[](size_type __pos)
00934       { return reference(*this,__pos); }
00935 
00936       const_reference
00937       operator[](size_type __pos) const
00938       { return _M_unchecked_test(__pos); }
00939       //@}
00940 
00941       /**
00942        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
00943        *  @return  The integral equivalent of the bits.
00944        *  @throw  std::overflow_error  If there are too many bits to be
00945        *                               represented in an @c unsigned @c long.
00946        */
00947       unsigned long
00948       to_ulong() const
00949       { return this->_M_do_to_ulong(); }
00950 
00951       /**
00952        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
00953        *  @return  The integral equivalent of the bits.
00954        *  @throw  std::overflow_error  If there are too many bits to be
00955        *                               represented in an @c unsigned @c long.
00956        */
00957       unsigned long long
00958       to_ullong() const
00959       { return this->_M_do_to_ullong(); }
00960 
00961       /**
00962        *  @brief Returns a character interpretation of the %dynamic_bitset.
00963        *  @return  The string equivalent of the bits.
00964        *
00965        *  Note the ordering of the bits:  decreasing character positions
00966        *  correspond to increasing bit positions (see the main class notes for
00967        *  an example).
00968        */
00969       template<typename _CharT = char,
00970                typename _Traits = std::char_traits<_CharT>,
00971                typename _Alloc1 = std::allocator<_CharT>>
00972         std::basic_string<_CharT, _Traits, _Alloc1>
00973         to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
00974         {
00975           std::basic_string<_CharT, _Traits, _Alloc1> __result;
00976           _M_copy_to_string(__result, __zero, __one);
00977           return __result;
00978         }
00979 
00980       // Helper functions for string operations.
00981       template<typename _CharT, typename _Traits>
00982         void
00983         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
00984                          _CharT, _CharT);
00985 
00986       template<typename _CharT, typename _Traits, typename _Alloc1>
00987         void
00988         _M_copy_from_string(const std::basic_string<_CharT,
00989                             _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
00990                             _CharT __zero = _CharT('0'),
00991                             _CharT __one = _CharT('1'))
00992         { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
00993                                             __pos, __n, __zero, __one); }
00994 
00995       template<typename _CharT, typename _Traits, typename _Alloc1>
00996         void
00997         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
00998                           _CharT __zero = _CharT('0'),
00999                           _CharT __one = _CharT('1')) const;
01000 
01001       /// Returns the number of bits which are set.
01002       size_type
01003       count() const noexcept
01004       { return this->_M_do_count(); }
01005 
01006       /// Returns the total number of bits.
01007       size_type
01008       size() const noexcept
01009       { return this->_M_Nb; }
01010 
01011       /// Returns the total number of blocks.
01012       size_type
01013       num_blocks() const noexcept
01014       { return this->_M_size(); }
01015 
01016       /// Returns true if the dynamic_bitset is empty.
01017       _GLIBCXX_NODISCARD bool
01018       empty() const noexcept
01019       { return (this->_M_Nb == 0); }
01020 
01021       /// Returns the maximum size of a dynamic_bitset object having the same
01022       /// type as *this.
01023       /// The real answer is max() * bits_per_block but is likely to overflow.
01024       constexpr size_type
01025       max_size() noexcept
01026       { return std::numeric_limits<block_type>::max(); }
01027 
01028       /**
01029        *  @brief Tests the value of a bit.
01030        *  @param  __pos  The index of a bit.
01031        *  @return  The value at @a __pos.
01032        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01033        */
01034       bool
01035       test(size_type __pos) const
01036       {
01037         if (__pos >= _M_Nb)
01038           __throw_out_of_range(__N("dynamic_bitset::test"));
01039         return _M_unchecked_test(__pos);
01040       }
01041 
01042       /**
01043        *  @brief Tests whether all the bits are on.
01044        *  @return  True if all the bits are set.
01045        */
01046       bool
01047       all() const
01048       { return this->_M_are_all_aux() == _M_Nb; }
01049 
01050       /**
01051        *  @brief Tests whether any of the bits are on.
01052        *  @return  True if at least one bit is set.
01053        */
01054       bool
01055       any() const
01056       { return this->_M_is_any(); }
01057 
01058       /**
01059        *  @brief Tests whether any of the bits are on.
01060        *  @return  True if none of the bits are set.
01061        */
01062       bool
01063       none() const
01064       { return !this->_M_is_any(); }
01065 
01066       //@{
01067       /// Self-explanatory.
01068       dynamic_bitset<_WordT, _Alloc>
01069       operator<<(size_type __pos) const
01070       { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
01071 
01072       dynamic_bitset<_WordT, _Alloc>
01073       operator>>(size_type __pos) const
01074       { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
01075       //@}
01076 
01077       /**
01078        *  @brief  Finds the index of the first "on" bit.
01079        *  @return  The index of the first bit set, or size() if not found.
01080        *  @sa  find_next
01081        */
01082       size_type
01083       find_first() const
01084       { return this->_M_do_find_first(this->_M_Nb); }
01085 
01086       /**
01087        *  @brief  Finds the index of the next "on" bit after prev.
01088        *  @return  The index of the next bit set, or size() if not found.
01089        *  @param  __prev  Where to start searching.
01090        *  @sa  find_first
01091        */
01092       size_type
01093       find_next(size_t __prev) const
01094       { return this->_M_do_find_next(__prev, this->_M_Nb); }
01095 
01096       bool
01097       is_subset_of(const dynamic_bitset& __b) const
01098       { return this->_M_is_subset_of(__b); }
01099 
01100       bool
01101       is_proper_subset_of(const dynamic_bitset& __b) const
01102       { return this->_M_is_proper_subset_of(__b); }
01103 
01104       friend bool
01105       operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01106                  const dynamic_bitset<_WordT, _Alloc>& __rhs)
01107       { return __lhs._M_is_equal(__rhs); }
01108 
01109       friend bool
01110       operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01111                 const dynamic_bitset<_WordT, _Alloc>& __rhs)
01112       { return __lhs._M_is_less(__rhs); }
01113     };
01114 
01115   template<typename _WordT, typename _Alloc>
01116     template<typename _CharT, typename _Traits, typename _Alloc1>
01117       inline void
01118       dynamic_bitset<_WordT, _Alloc>::
01119       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
01120                         _CharT __zero, _CharT __one) const
01121       {
01122         __str.assign(_M_Nb, __zero);
01123         for (size_t __i = _M_Nb; __i > 0; --__i)
01124           if (_M_unchecked_test(__i - 1))
01125             _Traits::assign(__str[_M_Nb - __i], __one);
01126       }
01127 
01128 
01129   //@{
01130   /// These comparisons for equality/inequality are, well, @e bitwise.
01131 
01132   template<typename _WordT, typename _Alloc>
01133     inline bool
01134     operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01135                const dynamic_bitset<_WordT, _Alloc>& __rhs)
01136     { return !(__lhs == __rhs); }
01137 
01138   template<typename _WordT, typename _Alloc>
01139     inline bool
01140     operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01141                const dynamic_bitset<_WordT, _Alloc>& __rhs)
01142     { return !(__lhs > __rhs); }
01143 
01144   template<typename _WordT, typename _Alloc>
01145     inline bool
01146     operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01147               const dynamic_bitset<_WordT, _Alloc>& __rhs)
01148     { return __rhs < __lhs; }
01149 
01150   template<typename _WordT, typename _Alloc>
01151     inline bool
01152     operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01153                const dynamic_bitset<_WordT, _Alloc>& __rhs)
01154     { return !(__lhs < __rhs); }
01155   //@}
01156 
01157   // 23.3.5.3 bitset operations:
01158   //@{
01159   /**
01160    *  @brief  Global bitwise operations on bitsets.
01161    *  @param  __x  A bitset.
01162    *  @param  __y  A bitset of the same size as @a __x.
01163    *  @return  A new bitset.
01164    *
01165    *  These should be self-explanatory.
01166    */
01167   template<typename _WordT, typename _Alloc>
01168     inline dynamic_bitset<_WordT, _Alloc>
01169     operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
01170               const dynamic_bitset<_WordT, _Alloc>& __y)
01171     {
01172       dynamic_bitset<_WordT, _Alloc> __result(__x);
01173       __result &= __y;
01174       return __result;
01175     }
01176 
01177   template<typename _WordT, typename _Alloc>
01178     inline dynamic_bitset<_WordT, _Alloc>
01179     operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
01180               const dynamic_bitset<_WordT, _Alloc>& __y)
01181     {
01182       dynamic_bitset<_WordT, _Alloc> __result(__x);
01183       __result |= __y;
01184       return __result;
01185     }
01186 
01187   template <typename _WordT, typename _Alloc>
01188     inline dynamic_bitset<_WordT, _Alloc>
01189     operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
01190               const dynamic_bitset<_WordT, _Alloc>& __y)
01191     {
01192       dynamic_bitset<_WordT, _Alloc> __result(__x);
01193       __result ^= __y;
01194       return __result;
01195     }
01196 
01197   template <typename _WordT, typename _Alloc>
01198     inline dynamic_bitset<_WordT, _Alloc>
01199     operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
01200               const dynamic_bitset<_WordT, _Alloc>& __y)
01201     {
01202       dynamic_bitset<_WordT, _Alloc> __result(__x);
01203       __result -= __y;
01204       return __result;
01205     }
01206   //@}
01207 
01208   /// Stream output operator for dynamic_bitset.
01209   template <typename _CharT, typename _Traits,
01210             typename _WordT, typename _Alloc>
01211     inline std::basic_ostream<_CharT, _Traits>&
01212     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01213                const dynamic_bitset<_WordT, _Alloc>& __x)
01214     {
01215       std::basic_string<_CharT, _Traits> __tmp;
01216 
01217       const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
01218       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
01219       return __os << __tmp;
01220     }
01221   /**
01222    *  @}
01223    */
01224 } // tr2
01225 
01226 _GLIBCXX_END_NAMESPACE_VERSION
01227 } // std
01228 
01229 #include <tr2/dynamic_bitset.tcc>
01230 
01231 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */