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