Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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