libstdc++
dynamic_bitset
Go to the documentation of this file.
00001 // TR2 <dynamic_bitset> -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2015 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 namespace tr2
00046 {
00047 _GLIBCXX_BEGIN_NAMESPACE_VERSION
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        *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.
00597        *  @throw  std::invalid_argument  If a character appears in the string
00598        *                                 which is neither '0' nor '1'.
00599        */
00600       template<typename _CharT, typename _Traits, typename _Alloc1>
00601         explicit
00602         dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
00603                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00604                        __pos = 0,
00605                        typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00606                        __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
00607                        _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
00608                        const allocator_type& __alloc = allocator_type())
00609         : _Base(__alloc),
00610           _M_Nb(0) // Watch for npos.
00611         {
00612           if (__pos > __str.size())
00613             __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
00614                                      "not valid"));
00615 
00616           // Watch for npos.
00617           this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
00618           this->resize(this->_M_Nb);
00619           this->_M_copy_from_string(__str, __pos, __n,
00620                                     _CharT('0'), _CharT('1'));
00621         }
00622 
00623       /**
00624        *  @brief  Construct from a string.
00625        *  @param  __str  A string of '0' and '1' characters.
00626        *  @param  __alloc An allocator.
00627        *  @throw  std::invalid_argument  If a character appears in the string
00628        *                                 which is neither '0' nor '1'.
00629        */
00630       explicit
00631       dynamic_bitset(const char* __str,
00632                      const allocator_type& __alloc = allocator_type())
00633       : _Base(__alloc)
00634       {
00635         size_t __len = 0;
00636         if (__str)
00637           while (__str[__len] != '\0')
00638             ++__len;
00639         this->resize(__len);
00640         this->_M_copy_from_ptr<char,std::char_traits<char>>
00641                    (__str, __len, 0, __len, '0', '1');
00642       }
00643 
00644       /**
00645        *  @brief  Copy constructor.
00646        */
00647       dynamic_bitset(const dynamic_bitset& __b)
00648       : _Base(__b), _M_Nb(__b.size())
00649       { }
00650 
00651       /**
00652        *  @brief  Move constructor.
00653        */
00654       dynamic_bitset(dynamic_bitset&& __b)
00655       : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
00656       { }
00657 
00658       /**
00659        *  @brief  Swap with another bitset.
00660        */
00661       void
00662       swap(dynamic_bitset& __b)
00663       {
00664         this->_M_swap(__b);
00665         std::swap(this->_M_Nb, __b._M_Nb);
00666       }
00667 
00668       /**
00669        *  @brief  Assignment.
00670        */
00671       dynamic_bitset&
00672       operator=(const dynamic_bitset& __b)
00673       {
00674         if (&__b != this)
00675           {
00676             this->_M_assign(__b);
00677             this->_M_Nb = __b._M_Nb;
00678           }
00679       }
00680 
00681       /**
00682        *  @brief  Move assignment.
00683        */
00684       dynamic_bitset&
00685       operator=(dynamic_bitset&& __b)
00686       {
00687         this->swap(__b);
00688         return *this;
00689       }
00690 
00691       /**
00692        *  @brief  Return the allocator for the bitset.
00693        */
00694       allocator_type
00695       get_allocator() const
00696       { return this->_M_get_allocator(); }
00697 
00698       /**
00699        *  @brief  Resize the bitset.
00700        */
00701       void
00702       resize(size_type __nbits, bool __value = false)
00703       {
00704         if (__value)
00705           this->_M_do_fill();
00706         this->_M_resize(__nbits, __value);
00707         this->_M_Nb = __nbits;
00708         this->_M_do_sanitize();
00709       }
00710 
00711       /**
00712        *  @brief  Clear the bitset.
00713        */
00714       void
00715       clear()
00716       {
00717         this->_M_clear();
00718         this->_M_Nb = 0;
00719       }
00720 
00721       /**
00722        *  @brief  Push a bit onto the high end of the bitset.
00723        */
00724       void
00725       push_back(bool __bit)
00726       {
00727         if (size_t __offset = this->size() % bits_per_block == 0)
00728           this->_M_do_append_block(block_type(0), this->_M_Nb);
00729         ++this->_M_Nb;
00730         this->_M_unchecked_set(this->_M_Nb, __bit);
00731       }
00732 
00733       /**
00734        *  @brief  Append a block.
00735        */
00736       void
00737       append(block_type __block)
00738       {
00739         this->_M_do_append_block(__block, this->_M_Nb);
00740         this->_M_Nb += bits_per_block;
00741       }
00742 
00743       /**
00744        *  @brief
00745        */
00746       void
00747       append(initializer_list<block_type> __il)
00748       { this->append(__il.begin(), __il.end()); }
00749 
00750       /**
00751        *  @brief  Append an iterator range of blocks.
00752        */
00753       template <typename _BlockInputIterator>
00754         void
00755         append(_BlockInputIterator __first, _BlockInputIterator __last)
00756         {
00757           for (; __first != __last; ++__first)
00758             this->append(*__first);
00759         }
00760 
00761       // 23.3.5.2 dynamic_bitset operations:
00762       //@{
00763       /**
00764        *  @brief  Operations on dynamic_bitsets.
00765        *  @param  __rhs  A same-sized dynamic_bitset.
00766        *
00767        *  These should be self-explanatory.
00768        */
00769       dynamic_bitset<_WordT, _Alloc>&
00770       operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00771       {
00772         this->_M_do_and(__rhs);
00773         return *this;
00774       }
00775 
00776       dynamic_bitset<_WordT, _Alloc>&
00777       operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
00778       {
00779         this->_M_do_and(std::move(__rhs));
00780         return *this;
00781       }
00782 
00783       dynamic_bitset<_WordT, _Alloc>&
00784       operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00785       {
00786         this->_M_do_or(__rhs);
00787         return *this;
00788       }
00789 
00790       dynamic_bitset<_WordT, _Alloc>&
00791       operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00792       {
00793         this->_M_do_xor(__rhs);
00794         return *this;
00795       }
00796 
00797       dynamic_bitset<_WordT, _Alloc>&
00798       operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00799       {
00800         this->_M_do_dif(__rhs);
00801         return *this;
00802       }
00803       //@}
00804 
00805       //@{
00806       /**
00807        *  @brief  Operations on dynamic_bitsets.
00808        *  @param  __pos The number of places to shift.
00809        *
00810        *  These should be self-explanatory.
00811        */
00812       dynamic_bitset<_WordT, _Alloc>&
00813       operator<<=(size_type __pos)
00814       {
00815         if (__builtin_expect(__pos < this->_M_Nb, 1))
00816           {
00817             this->_M_do_left_shift(__pos);
00818             this->_M_do_sanitize();
00819           }
00820         else
00821           this->_M_do_reset();
00822         return *this;
00823       }
00824 
00825       dynamic_bitset<_WordT, _Alloc>&
00826       operator>>=(size_type __pos)
00827       {
00828         if (__builtin_expect(__pos < this->_M_Nb, 1))
00829           {
00830             this->_M_do_right_shift(__pos);
00831             this->_M_do_sanitize();
00832           }
00833         else
00834           this->_M_do_reset();
00835         return *this;
00836       }
00837       //@}
00838 
00839       // Set, reset, and flip.
00840       /**
00841        *  @brief Sets every bit to true.
00842        */
00843       dynamic_bitset<_WordT, _Alloc>&
00844       set()
00845       {
00846         this->_M_do_set();
00847         this->_M_do_sanitize();
00848         return *this;
00849       }
00850 
00851       /**
00852        *  @brief Sets a given bit to a particular value.
00853        *  @param  __pos  The index of the bit.
00854        *  @param  __val  Either true or false, defaults to true.
00855        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
00856        */
00857       dynamic_bitset<_WordT, _Alloc>&
00858       set(size_type __pos, bool __val = true)
00859       {
00860         if (__pos >= _M_Nb)
00861           __throw_out_of_range(__N("dynamic_bitset::set"));
00862         return this->_M_unchecked_set(__pos, __val);
00863       }
00864 
00865       /**
00866        *  @brief Sets every bit to false.
00867        */
00868       dynamic_bitset<_WordT, _Alloc>&
00869       reset()
00870       {
00871         this->_M_do_reset();
00872         return *this;
00873       }
00874 
00875       /**
00876        *  @brief Sets a given bit to false.
00877        *  @param  __pos  The index of the bit.
00878        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
00879        *
00880        *  Same as writing @c set(__pos, false).
00881        */
00882       dynamic_bitset<_WordT, _Alloc>&
00883       reset(size_type __pos)
00884       {
00885         if (__pos >= _M_Nb)
00886           __throw_out_of_range(__N("dynamic_bitset::reset"));
00887         return this->_M_unchecked_reset(__pos);
00888       }
00889 
00890       /**
00891        *  @brief Toggles every bit to its opposite value.
00892        */
00893       dynamic_bitset<_WordT, _Alloc>&
00894       flip()
00895       {
00896         this->_M_do_flip();
00897         this->_M_do_sanitize();
00898         return *this;
00899       }
00900 
00901       /**
00902        *  @brief Toggles a given bit to its opposite value.
00903        *  @param  __pos  The index of the bit.
00904        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
00905        */
00906       dynamic_bitset<_WordT, _Alloc>&
00907       flip(size_type __pos)
00908       {
00909         if (__pos >= _M_Nb)
00910           __throw_out_of_range(__N("dynamic_bitset::flip"));
00911         return this->_M_unchecked_flip(__pos);
00912       }
00913 
00914       /// See the no-argument flip().
00915       dynamic_bitset<_WordT, _Alloc>
00916       operator~() const
00917       { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
00918 
00919       //@{
00920       /**
00921        *  @brief  Array-indexing support.
00922        *  @param  __pos  Index into the %dynamic_bitset.
00923        *  @return A bool for a 'const %dynamic_bitset'.  For non-const
00924        *           bitsets, an instance of the reference proxy class.
00925        *  @note These operators do no range checking and throw no
00926        *         exceptions, as required by DR 11 to the standard.
00927        */
00928       reference
00929       operator[](size_type __pos)
00930       { return reference(*this,__pos); }
00931 
00932       const_reference
00933       operator[](size_type __pos) const
00934       { return _M_unchecked_test(__pos); }
00935       //@}
00936 
00937       /**
00938        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
00939        *  @return  The integral equivalent of the bits.
00940        *  @throw  std::overflow_error  If there are too many bits to be
00941        *                               represented in an @c unsigned @c long.
00942        */
00943       unsigned long
00944       to_ulong() const
00945       { return this->_M_do_to_ulong(); }
00946 
00947       /**
00948        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
00949        *  @return  The integral equivalent of the bits.
00950        *  @throw  std::overflow_error  If there are too many bits to be
00951        *                               represented in an @c unsigned @c long.
00952        */
00953       unsigned long long
00954       to_ullong() const
00955       { return this->_M_do_to_ullong(); }
00956 
00957       /**
00958        *  @brief Returns a character interpretation of the %dynamic_bitset.
00959        *  @return  The string equivalent of the bits.
00960        *
00961        *  Note the ordering of the bits:  decreasing character positions
00962        *  correspond to increasing bit positions (see the main class notes for
00963        *  an example).
00964        */
00965       template<typename _CharT = char,
00966                typename _Traits = std::char_traits<_CharT>,
00967                typename _Alloc1 = std::allocator<_CharT>>
00968         std::basic_string<_CharT, _Traits, _Alloc1>
00969         to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
00970         {
00971           std::basic_string<_CharT, _Traits, _Alloc1> __result;
00972           _M_copy_to_string(__result, __zero, __one);
00973           return __result;
00974         }
00975 
00976       // Helper functions for string operations.
00977       template<typename _CharT, typename _Traits>
00978         void
00979         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
00980                          _CharT, _CharT);
00981 
00982       template<typename _CharT, typename _Traits, typename _Alloc1>
00983         void
00984         _M_copy_from_string(const std::basic_string<_CharT,
00985                             _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
00986                             _CharT __zero = _CharT('0'),
00987                             _CharT __one = _CharT('1'))
00988         { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
00989                                             __pos, __n, __zero, __one); }
00990 
00991       template<typename _CharT, typename _Traits, typename _Alloc1>
00992         void
00993         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
00994                           _CharT __zero = _CharT('0'),
00995                           _CharT __one = _CharT('1')) const;
00996 
00997       /// Returns the number of bits which are set.
00998       size_type
00999       count() const noexcept
01000       { return this->_M_do_count(); }
01001 
01002       /// Returns the total number of bits.
01003       size_type
01004       size() const noexcept
01005       { return this->_M_Nb; }
01006 
01007       /// Returns the total number of blocks.
01008       size_type
01009       num_blocks() const noexcept
01010       { return this->_M_size(); }
01011 
01012       /// Returns true if the dynamic_bitset is empty.
01013       bool
01014       empty() const noexcept
01015       { return (this->_M_Nb == 0); }
01016 
01017       /// Returns the maximum size of a dynamic_bitset object having the same
01018       /// type as *this.
01019       /// The real answer is max() * bits_per_block but is likely to overflow.
01020       constexpr size_type
01021       max_size() noexcept
01022       { return std::numeric_limits<block_type>::max(); }
01023 
01024       /**
01025        *  @brief Tests the value of a bit.
01026        *  @param  __pos  The index of a bit.
01027        *  @return  The value at @a __pos.
01028        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01029        */
01030       bool
01031       test(size_type __pos) const
01032       {
01033         if (__pos >= _M_Nb)
01034           __throw_out_of_range(__N("dynamic_bitset::test"));
01035         return _M_unchecked_test(__pos);
01036       }
01037 
01038       /**
01039        *  @brief Tests whether all the bits are on.
01040        *  @return  True if all the bits are set.
01041        */
01042       bool
01043       all() const
01044       { return this->_M_are_all_aux() == _M_Nb; }
01045 
01046       /**
01047        *  @brief Tests whether any of the bits are on.
01048        *  @return  True if at least one bit is set.
01049        */
01050       bool
01051       any() const
01052       { return this->_M_is_any(); }
01053 
01054       /**
01055        *  @brief Tests whether any of the bits are on.
01056        *  @return  True if none of the bits are set.
01057        */
01058       bool
01059       none() const
01060       { return !this->_M_is_any(); }
01061 
01062       //@{
01063       /// Self-explanatory.
01064       dynamic_bitset<_WordT, _Alloc>
01065       operator<<(size_type __pos) const
01066       { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
01067 
01068       dynamic_bitset<_WordT, _Alloc>
01069       operator>>(size_type __pos) const
01070       { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
01071       //@}
01072 
01073       /**
01074        *  @brief  Finds the index of the first "on" bit.
01075        *  @return  The index of the first bit set, or size() if not found.
01076        *  @sa  find_next
01077        */
01078       size_type
01079       find_first() const
01080       { return this->_M_do_find_first(this->_M_Nb); }
01081 
01082       /**
01083        *  @brief  Finds the index of the next "on" bit after prev.
01084        *  @return  The index of the next bit set, or size() if not found.
01085        *  @param  __prev  Where to start searching.
01086        *  @sa  find_first
01087        */
01088       size_type
01089       find_next(size_t __prev) const
01090       { return this->_M_do_find_next(__prev, this->_M_Nb); }
01091 
01092       bool
01093       is_subset_of(const dynamic_bitset& __b) const
01094       { return this->_M_is_subset_of(__b); }
01095 
01096       bool
01097       is_proper_subset_of(const dynamic_bitset& __b) const
01098       { return this->_M_is_proper_subset_of(__b); }
01099 
01100       friend bool
01101       operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01102                  const dynamic_bitset<_WordT, _Alloc>& __rhs)
01103       { return __lhs._M_is_equal(__rhs); }
01104 
01105       friend bool
01106       operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01107                 const dynamic_bitset<_WordT, _Alloc>& __rhs)
01108       { return __lhs._M_is_less(__rhs); }
01109     };
01110 
01111   template<typename _WordT, typename _Alloc>
01112     template<typename _CharT, typename _Traits, typename _Alloc1>
01113       inline void
01114       dynamic_bitset<_WordT, _Alloc>::
01115       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
01116                         _CharT __zero, _CharT __one) const
01117       {
01118         __str.assign(_M_Nb, __zero);
01119         for (size_t __i = _M_Nb; __i > 0; --__i)
01120           if (_M_unchecked_test(__i - 1))
01121             _Traits::assign(__str[_M_Nb - __i], __one);
01122       }
01123 
01124 
01125   //@{
01126   /// These comparisons for equality/inequality are, well, @e bitwise.
01127 
01128   template<typename _WordT, typename _Alloc>
01129     inline bool
01130     operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01131                const dynamic_bitset<_WordT, _Alloc>& __rhs)
01132     { return !(__lhs == __rhs); }
01133 
01134   template<typename _WordT, typename _Alloc>
01135     inline bool
01136     operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01137                const dynamic_bitset<_WordT, _Alloc>& __rhs)
01138     { return !(__lhs > __rhs); }
01139 
01140   template<typename _WordT, typename _Alloc>
01141     inline bool
01142     operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01143               const dynamic_bitset<_WordT, _Alloc>& __rhs)
01144     { return __rhs < __lhs; }
01145 
01146   template<typename _WordT, typename _Alloc>
01147     inline bool
01148     operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01149                const dynamic_bitset<_WordT, _Alloc>& __rhs)
01150     { return !(__lhs < __rhs); }
01151   //@}
01152 
01153   // 23.3.5.3 bitset operations:
01154   //@{
01155   /**
01156    *  @brief  Global bitwise operations on bitsets.
01157    *  @param  __x  A bitset.
01158    *  @param  __y  A bitset of the same size as @a __x.
01159    *  @return  A new bitset.
01160    *
01161    *  These should be self-explanatory.
01162    */
01163   template<typename _WordT, typename _Alloc>
01164     inline dynamic_bitset<_WordT, _Alloc>
01165     operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
01166               const dynamic_bitset<_WordT, _Alloc>& __y)
01167     {
01168       dynamic_bitset<_WordT, _Alloc> __result(__x);
01169       __result &= __y;
01170       return __result;
01171     }
01172 
01173   template<typename _WordT, typename _Alloc>
01174     inline dynamic_bitset<_WordT, _Alloc>
01175     operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
01176               const dynamic_bitset<_WordT, _Alloc>& __y)
01177     {
01178       dynamic_bitset<_WordT, _Alloc> __result(__x);
01179       __result |= __y;
01180       return __result;
01181     }
01182 
01183   template <typename _WordT, typename _Alloc>
01184     inline dynamic_bitset<_WordT, _Alloc>
01185     operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
01186               const dynamic_bitset<_WordT, _Alloc>& __y)
01187     {
01188       dynamic_bitset<_WordT, _Alloc> __result(__x);
01189       __result ^= __y;
01190       return __result;
01191     }
01192 
01193   template <typename _WordT, typename _Alloc>
01194     inline dynamic_bitset<_WordT, _Alloc>
01195     operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
01196               const dynamic_bitset<_WordT, _Alloc>& __y)
01197     {
01198       dynamic_bitset<_WordT, _Alloc> __result(__x);
01199       __result -= __y;
01200       return __result;
01201     }
01202   //@}
01203 
01204   /// Stream output operator for dynamic_bitset.
01205   template <typename _CharT, typename _Traits,
01206             typename _WordT, typename _Alloc>
01207     inline std::basic_ostream<_CharT, _Traits>&
01208     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01209                const dynamic_bitset<_WordT, _Alloc>& __x)
01210     {
01211       std::basic_string<_CharT, _Traits> __tmp;
01212 
01213       const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
01214       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
01215       return __os << __tmp;
01216     }
01217   /**
01218    *  @}
01219    */
01220 
01221 _GLIBCXX_END_NAMESPACE_VERSION
01222 } // tr2
01223 } // std
01224 
01225 #include <tr2/dynamic_bitset.tcc>
01226 
01227 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */