Subversion Repositories openrisc

// TR2  -*- C++ -*-

// Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

/** @file tr2/dynamic_bitset

 *  This is a TR2 C++ Library header.

 */

#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET

#define _GLIBCXX_TR2_DYNAMIC_BITSET 1

#pragma GCC system_header

#include 

#include 

#include  // For size_t

#include 

#include  // For std::allocator

#include    // For invalid_argument, out_of_range,

                                // overflow_error

#include 

#include 

namespace std _GLIBCXX_VISIBILITY(default)

{

namespace tr2

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**

   *  Dynamic Bitset.

   *

   *  See N2050,

   *  Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.

   */

namespace __detail

{

template

class _Bool2UChar

{

  typedef T type;

};

template<>

class _Bool2UChar

{

public:

  typedef unsigned char type;

};

}

  /**

   *  Base class, general case.

   *

   *  See documentation for dynamic_bitset.

   */

  template

           typename _Alloc = std::allocator<_WordT>>

    struct __dynamic_bitset_base

    {

      static_assert(std::is_unsigned<_WordT>::value, "template argument "

                    "_WordT not an unsigned integral type");

      typedef _WordT block_type;

      typedef _Alloc allocator_type;

      typedef size_t size_type;

      static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);

      static const size_type npos = static_cast(-1);

      /// 0 is the least significant word.

      std::vector _M_w;

      explicit

      __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())

      : _M_w(__alloc)

      { }

      explicit

      __dynamic_bitset_base(__dynamic_bitset_base&& __b)

      { this->_M_w.swap(__b._M_w); }

      explicit

      __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,

                           const allocator_type& __alloc = allocator_type())

      : _M_w(__nbits / _S_bits_per_block

             + (__nbits % _S_bits_per_block > 0),

             __val, __alloc)

      {

        unsigned long long __mask = ~static_cast(0);

        size_t __n = std::min(this->_M_w.size(),

                              sizeof(unsigned long long) / sizeof(block_type));

        for (size_t __i = 0; __i < __n; ++__i)

          {

            this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);

            __mask <<= _S_bits_per_block;

          }

      }

      void

      _M_assign(const __dynamic_bitset_base& __b)

      { this->_M_w = __b._M_w; }

      void

      _M_swap(__dynamic_bitset_base& __b)

      { this->_M_w.swap(__b._M_w); }

      void

      _M_clear()

      { this->_M_w.clear(); }

      void

      _M_resize(size_t __nbits, bool __value)

      {

        size_t __sz = __nbits / _S_bits_per_block;

        if (__nbits % _S_bits_per_block > 0)

          ++__sz;

        if (__sz != this->_M_w.size())

          this->_M_w.resize(__sz);

      }

      allocator_type

      _M_get_allocator() const

      { return this->_M_w.get_allocator(); }

      static size_type

      _S_whichword(size_type __pos)

      { return __pos / _S_bits_per_block; }

      static size_type

      _S_whichbyte(size_type __pos)

      { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }

      static size_type

      _S_whichbit(size_type __pos)

      { return __pos % _S_bits_per_block; }

      static block_type

      _S_maskbit(size_type __pos)

      { return (static_cast(1)) << _S_whichbit(__pos); }

      block_type&

      _M_getword(size_type __pos)

      { return this->_M_w[_S_whichword(__pos)]; }

      block_type

      _M_getword(size_type __pos) const

      { return this->_M_w[_S_whichword(__pos)]; }

      block_type&

      _M_hiword()

      { return this->_M_w[_M_w.size() - 1]; }

      block_type

      _M_hiword() const

      { return this->_M_w[_M_w.size() - 1]; }

      void

      _M_do_and(const __dynamic_bitset_base& __x)

      {

        if (__x._M_w.size() == this->_M_w.size())

          for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

            this->_M_w[__i] &= __x._M_w[__i];

        else

          return;

      }

      void

      _M_do_or(const __dynamic_bitset_base& __x)

      {

        if (__x._M_w.size() == this->_M_w.size())

          for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

            this->_M_w[__i] |= __x._M_w[__i];

        else

          return;

      }

      void

      _M_do_xor(const __dynamic_bitset_base& __x)

      {

        if (__x._M_w.size() == this->_M_w.size())

          for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

            this->_M_w[__i] ^= __x._M_w[__i];

        else

          return;

      }

      void

      _M_do_dif(const __dynamic_bitset_base& __x)

      {

        if (__x._M_w.size() == this->_M_w.size())

          for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

            this->_M_w[__i] &= ~__x._M_w[__i];

        else

          return;

      }

      void

      _M_do_left_shift(size_t __shift);

      void

      _M_do_right_shift(size_t __shift);

      void

      _M_do_flip()

      {

        for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

          this->_M_w[__i] = ~this->_M_w[__i];

      }

      void

      _M_do_set()

      {

        for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

          this->_M_w[__i] = ~static_cast(0);

      }

      void

      _M_do_reset()

      {

        for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

          this->_M_w[__i] = static_cast(0);

      }

      bool

      _M_is_equal(const __dynamic_bitset_base& __x) const

      {

        if (__x.size() == this->size())

          {

            for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

              if (this->_M_w[__i] != __x._M_w[__i])

                return false;

            return true;

          }

        else

          return false;

      }

      bool

      _M_is_less(const __dynamic_bitset_base& __x) const

      {

        if (__x.size() == this->size())

          {

            for (size_t __i = this->_M_w.size(); __i > 0; --__i)

              {

                if (this->_M_w[__i-1] < __x._M_w[__i-1])

                  return true;

                else if (this->_M_w[__i-1] > __x._M_w[__i-1])

                  return false;

              }

            return false;

          }

        else

          return false;

      }

      size_t

      _M_are_all_aux() const

      {

        for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)

          if (_M_w[__i] != ~static_cast(0))

            return 0;

        return ((this->_M_w.size() - 1) * _S_bits_per_block

                + __builtin_popcountl(this->_M_hiword()));

      }

      bool

      _M_is_any() const

      {

        for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

          if (this->_M_w[__i] != static_cast(0))

            return true;

        return false;

      }

      bool

      _M_is_subset_of(const __dynamic_bitset_base& __b)

      {

        if (__b.size() == this->size())

          {

            for (size_t __i = 0; __i < _M_w.size(); ++__i)

              if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))

                return false;

            return true;

          }

        else

          return false;

      }

      bool

      _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const

      {

        if (this->is_subset_of(__b))

          {

            if (*this == __b)

              return false;

            else

              return true;

          }

        else

          return false;

      }

      size_t

      _M_do_count() const

      {

        size_t __result = 0;

        for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

          __result += __builtin_popcountl(this->_M_w[__i]);

        return __result;

      }

      size_type

      _M_size() const

      { return this->_M_w.size(); }

      unsigned long

      _M_do_to_ulong() const;

      unsigned long long

      _M_do_to_ullong() const;

      // find first "on" bit

      size_type

      _M_do_find_first(size_t __not_found) const;

      // find the next "on" bit that follows "prev"

      size_type

      _M_do_find_next(size_t __prev, size_t __not_found) const;

      // do append of block

      void

      _M_do_append_block(block_type __block, size_type __pos)

      {

        size_t __offset = __pos % _S_bits_per_block;

        if (__offset == 0)

          this->_M_w.push_back(__block);

        else

          {

            this->_M_hiword() |= (__block << __offset);

            this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));

          }

      }

    };

  // Definitions of non-inline functions from __dynamic_bitset_base.

  template

    void

    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)

    {

      if (__builtin_expect(__shift != 0, 1))

        {

          const size_t __wshift = __shift / _S_bits_per_block;

          const size_t __offset = __shift % _S_bits_per_block;

          if (__offset == 0)

            for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)

              this->_M_w[__n] = this->_M_w[__n - __wshift];

          else

            {

              const size_t __sub_offset = _S_bits_per_block - __offset;

              for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)

                this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)

                             | (this->_M_w[__n - __wshift - 1] >> __sub_offset));

              this->_M_w[__wshift] = this->_M_w[0] << __offset;

            }

          //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,

          ////          static_cast<_WordT>(0));

        }

    }

  template

    void

    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)

    {

      if (__builtin_expect(__shift != 0, 1))

        {

          const size_t __wshift = __shift / _S_bits_per_block;

          const size_t __offset = __shift % _S_bits_per_block;

          const size_t __limit = this->_M_w.size() - __wshift - 1;

          if (__offset == 0)

            for (size_t __n = 0; __n <= __limit; ++__n)

              this->_M_w[__n] = this->_M_w[__n + __wshift];

          else

            {

              const size_t __sub_offset = (_S_bits_per_block

                                           - __offset);

              for (size_t __n = 0; __n < __limit; ++__n)

                this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)

                             | (this->_M_w[__n + __wshift + 1] << __sub_offset));

              this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;

            }

          ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),

          ////          static_cast<_WordT>(0));

        }

    }

  template

    unsigned long

    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const

    {

      size_t __n = sizeof(unsigned long) / sizeof(block_type);

      for (size_t __i = __n; __i < this->_M_w.size(); ++__i)

        if (this->_M_w[__i])

          __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));

      unsigned long __res = 0UL;

      for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)

        __res += this->_M_w[__i] << (__i * _S_bits_per_block);

      return __res;

    }

  template

    unsigned long long

    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const

    {

      size_t __n = sizeof(unsigned long long) / sizeof(block_type);

      for (size_t __i = __n; __i < this->_M_w.size(); ++__i)

        if (this->_M_w[__i])

          __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));

      unsigned long long __res = 0ULL;

      for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)

        __res += this->_M_w[__i] << (__i * _S_bits_per_block);

      return __res;

    }

  template

    size_t

    __dynamic_bitset_base<_WordT, _Alloc>

    ::_M_do_find_first(size_t __not_found) const

    {

      for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

        {

          _WordT __thisword = this->_M_w[__i];

          if (__thisword != static_cast<_WordT>(0))

            return (__i * _S_bits_per_block

                    + __builtin_ctzl(__thisword));

        }

      // not found, so return an indication of failure.

      return __not_found;

    }

  template

    size_t

    __dynamic_bitset_base<_WordT, _Alloc>

    ::_M_do_find_next(size_t __prev, size_t __not_found) const

    {

      // make bound inclusive

      ++__prev;

      // check out of bounds

      if (__prev >= this->_M_w.size() * _S_bits_per_block)

        return __not_found;

      // search first word

      size_t __i = _S_whichword(__prev);

      _WordT __thisword = this->_M_w[__i];

      // mask off bits below bound

      __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);

      if (__thisword != static_cast<_WordT>(0))

        return (__i * _S_bits_per_block

                + __builtin_ctzl(__thisword));

      // check subsequent words

      for (++__i; __i < this->_M_w.size(); ++__i)

        {

          __thisword = this->_M_w[__i];

          if (__thisword != static_cast<_WordT>(0))

            return (__i * _S_bits_per_block

                    + __builtin_ctzl(__thisword));

        }

      // not found, so return an indication of failure.

      return __not_found;

    } // end _M_do_find_next

  /**

   *  @brief  The %dynamic_bitset class represents a sequence of bits.

   *

   *  @ingroup containers

   *

   *  (Note that %dynamic_bitset does @e not meet the formal

   *  requirements of a container.

   *  Mainly, it lacks iterators.)

   *

   *  The template argument, @a Nb, may be any non-negative number,

   *  specifying the number of bits (e.g., "0", "12", "1024*1024").

   *

   *  In the general unoptimized case, storage is allocated in

   *  word-sized blocks.  Let B be the number of bits in a word, then

   *  (Nb+(B-1))/B words will be used for storage.  B - Nb%B bits are

   *  unused.  (They are the high-order bits in the highest word.)  It

   *  is a class invariant that those unused bits are always zero.

   *

   *  If you think of %dynamic_bitset as "a simple array of bits," be

   *  aware that your mental picture is reversed: a %dynamic_bitset

   *  behaves the same way as bits in integers do, with the bit at

   *  index 0 in the "least significant / right-hand" position, and

   *  the bit at index Nb-1 in the "most significant / left-hand"

   *  position.  Thus, unlike other containers, a %dynamic_bitset's

   *  index "counts from right to left," to put it very loosely.

   *

   *  This behavior is preserved when translating to and from strings.

   *  For example, the first line of the following program probably

   *  prints "b('a') is 0001100001" on a modern ASCII system.

   *

   *  @code

   *     #include 

   *     #include 

   *     #include 

   *

   *     using namespace std;

   *

   *     int main()

   *     {

   *         long         a = 'a';

   *         dynamic_bitset   b(a);

   *

   *         cout << "b('a') is " << b << endl;

   *

   *         ostringstream s;

   *         s << b;

   *         string  str = s.str();

   *         cout << "index 3 in the string is " << str[3] << " but\n"

   *              << "index 3 in the bitset is " << b[3] << endl;

   *     }

   *  @endcode

   *

   *  Also see:

   *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html

   *  for a description of extensions.

   *

   *  Most of the actual code isn't contained in %dynamic_bitset<>

   *  itself, but in the base class __dynamic_bitset_base.  The base

   *  class works with whole words, not with individual bits.  This

   *  allows us to specialize __dynamic_bitset_base for the important

   *  special case where the %dynamic_bitset is only a single word.

   *

   *  Extra confusion can result due to the fact that the storage for

   *  __dynamic_bitset_base @e is a vector, and is indexed as such.  This is

   *  carefully encapsulated.

   */

  template

           typename _Alloc = std::allocator<_WordT>>

    class dynamic_bitset

    : private __dynamic_bitset_base<_WordT, _Alloc>

    {

      static_assert(std::is_unsigned<_WordT>::value, "template argument "

                    "_WordT not an unsigned integral type");

    public:

      typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;

      typedef _WordT block_type;

      typedef _Alloc allocator_type;

      typedef size_t size_type;

      static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);

      // Use this: constexpr size_type std::numeric_limits::max().

      static const size_type npos = static_cast(-1);

    private:

      //  Clear the unused bits in the uppermost word.

      void

      _M_do_sanitize()

      {

        size_type __shift = this->_M_Nb % bits_per_block;

        if (__shift > 0)

          this->_M_hiword() &= ~((~static_cast(0)) << __shift);

      }

      /**

       *  These versions of single-bit set, reset, flip, and test

       *  do no range checking.

       */

      dynamic_bitset<_WordT, _Alloc>&

      _M_unchecked_set(size_type __pos)

      {

        this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);

        return *this;

      }

      dynamic_bitset<_WordT, _Alloc>&

      _M_unchecked_set(size_type __pos, int __val)

      {

        if (__val)

          this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);

        else

          this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);

        return *this;

      }

      dynamic_bitset<_WordT, _Alloc>&

      _M_unchecked_reset(size_type __pos)

      {

        this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);

        return *this;

      }

      dynamic_bitset<_WordT, _Alloc>&

      _M_unchecked_flip(size_type __pos)

      {

        this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);

        return *this;

      }

      bool

      _M_unchecked_test(size_type __pos) const

      { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))

                != static_cast<_WordT>(0)); }

      size_type _M_Nb;

    public:

      /**

       *  This encapsulates the concept of a single bit.  An instance

       *  of this class is a proxy for an actual bit; this way the

       *  individual bit operations are done as faster word-size

       *  bitwise instructions.

       *

       *  Most users will never need to use this class directly;

       *  conversions to and from bool are automatic and should be

       *  transparent.  Overloaded operators help to preserve the

       *  illusion.

       *

       *  (On a typical system, this "bit %reference" is 64 times the

       *  size of an actual bit.  Ha.)

       */

      class reference

      {

        friend class dynamic_bitset;

        block_type *_M_wp;

        size_type _M_bpos;

        // left undefined

        reference();

      public:

        reference(dynamic_bitset& __b, size_type __pos)

        {

          this->_M_wp = &__b._M_getword(__pos);

          this->_M_bpos = _Base::_S_whichbit(__pos);

        }

        ~reference()

        { }

        // For b[i] = __x;

        reference&

        operator=(bool __x)

        {

          if (__x)

            *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);

          else

            *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);

          return *this;

        }

        // For b[i] = b[__j];

        reference&

        operator=(const reference& __j)

        {

          if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))

            *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);

          else

            *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);

          return *this;

        }

        // Flips the bit

        bool

        operator~() const

        { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }

        // For __x = b[i];

        operator bool() const

        { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }

        // For b[i].flip();

        reference&

        flip()

        {

          *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);

          return *this;

        }

      };

      friend class reference;

      typedef bool const_reference;

      // 23.3.5.1 constructors:

      /// All bits set to zero.

      explicit

      dynamic_bitset(const allocator_type& __alloc = allocator_type())

      : _Base(__alloc), _M_Nb(0)

      { }

      /// Initial bits bitwise-copied from a single word (others set to zero).

      explicit

      dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,

                     const allocator_type& __alloc = allocator_type())

      : _Base(__nbits, __val, __alloc),

        _M_Nb(__nbits)

      { }

      dynamic_bitset(initializer_list __il,

                     const allocator_type& __alloc = allocator_type())

      : _Base(__alloc), _M_Nb(0)

      { this->append(__il); }

      /**

       *  @brief  Use a subset of a string.

       *  @param  __str  A string of '0' and '1' characters.

       *  @param  __pos  Index of the first character in @p __str to use.

       *  @param  __n    The number of characters to copy.

       *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.

       *  @throw  std::invalid_argument  If a character appears in the string

       *                                 which is neither '0' nor '1'.

       */

      template

        explicit

        dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,

                       typename basic_string<_CharT,_Traits,_Alloc1>::size_type

                       __pos = 0,

                       typename basic_string<_CharT,_Traits,_Alloc1>::size_type

                       __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,

                       _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),

                       const allocator_type& __alloc = allocator_type())

        : _Base(__alloc),

          _M_Nb(0) // Watch for npos.

        {

          if (__pos > __str.size())

            __throw_out_of_range(__N("dynamic_bitset::bitset initial position "

                                     "not valid"));

          // Watch for npos.

          this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);

          this->resize(this->_M_Nb);

          this->_M_copy_from_string(__str, __pos, __n,

                                    _CharT('0'), _CharT('1'));

        }

      /**

       *  @brief  Construct from a string.

       *  @param  __str  A string of '0' and '1' characters.

       *  @throw  std::invalid_argument  If a character appears in the string

       *                                 which is neither '0' nor '1'.

       */

      explicit

      dynamic_bitset(const char* __str,

                     const allocator_type& __alloc = allocator_type())

      : _Base(__alloc)

      {

        size_t __len = 0;

        if (__str)

          while (__str[__len] != '\0')

            ++__len;

        this->resize(__len);

        this->_M_copy_from_ptr>

                   (__str, __len, 0, __len, '0', '1');

      }

      /**

       *  @brief  Copy constructor.

       */

      dynamic_bitset(const dynamic_bitset& __b)

      : _Base(__b), _M_Nb(__b.size())

      { }

      /**

       *  @brief  Move constructor.

       */

      dynamic_bitset(dynamic_bitset&& __b)

      : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())

      { }

      /**

       *  @brief  Swap with another bitset.

       */

      void

      swap(dynamic_bitset& __b)

      {

        this->_M_swap(__b);

        std::swap(this->_M_Nb, __b._M_Nb);

      }

      /**

       *  @brief  Assignment.

       */

      dynamic_bitset&

      operator=(const dynamic_bitset& __b)

      {

        if (&__b != this)

          {

            this->_M_assign(__b);

            this->_M_Nb = __b._M_Nb;

          }

      }

      /**

       *  @brief  Move assignment.

       */

      dynamic_bitset&

      operator=(dynamic_bitset&& __b)

      {

        this->swap(__b);

        return *this;

      }

      /**

       *  @brief  Return the allocator for the bitset.

       */

      allocator_type

      get_allocator() const

      { return this->_M_get_allocator(); }

      /**

       *  @brief  Resize the bitset.

       */

      void

      resize(size_type __nbits, bool __value = false)

      {

        this->_M_resize(__nbits, __value);

        this->_M_Nb = __nbits;

        this->_M_do_sanitize();

      }

      /**

       *  @brief  Clear the bitset.

       */

      void

      clear()

      {

        this->_M_clear();

        this->_M_Nb = 0;

      }

      /**

       *  @brief  Push a bit onto the high end of the bitset.

       */

      void

      push_back(bool __bit)

      {

        if (size_t __offset = this->size() % bits_per_block == 0)

          this->_M_do_append_block(block_type(0), this->_M_Nb);

        ++this->_M_Nb;

        this->_M_unchecked_set(this->_M_Nb, __bit);

      }

      /**

       *  @brief  Append a block.

       */

      void

      append(block_type __block)

      {

        this->_M_do_append_block(__block, this->_M_Nb);

        this->_M_Nb += bits_per_block;

      }

      /**

       *  @brief

       */

      void

      append(initializer_list __il)

      { this->append(__il.begin(), __il.end()); }

      /**

       *  @brief  Append an iterator range of blocks.

       */

      template 

        void

        append(_BlockInputIterator __first, _BlockInputIterator __last)

        {

          for (; __first != __last; ++__first)

            this->append(*__first);

        }

      // 23.3.5.2 dynamic_bitset operations:

      //@{

      /**

       *  @brief  Operations on dynamic_bitsets.

       *  @param  __rhs  A same-sized dynamic_bitset.

       *

       *  These should be self-explanatory.

       */

      dynamic_bitset<_WordT, _Alloc>&

      operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)

      {

        this->_M_do_and(__rhs);

        return *this;

      }

      dynamic_bitset<_WordT, _Alloc>&

      operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)

      {

        this->_M_do_and(std::move(__rhs));

        return *this;

      }

      dynamic_bitset<_WordT, _Alloc>&

      operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)

      {

        this->_M_do_or(__rhs);

        return *this;

      }