// (C) Copyright Chuck Allison and Jeremy Siek 2001, 2002.
//
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all
// copies. This software is provided "as is" without express or
// implied warranty, and with no claim as to its suitability for any
// purpose.

// With optimizations, bug fixes, and improvements by Gennaro Prota.

// See http://www.boost.org/libs/dynamic_bitset for documentation.

// -------------------------------------
// CHANGE LOG:
//
// - corrected workaround for Dinkum lib's allocate() [GP]
// - changed macro test for old iostreams [GP]
// - removed #include <vector> for now. [JGS]
// - Added __GNUC__ to compilers that cannot handle the constructor from basic_string. [JGS]
// - corrected to_block_range [GP]
// - corrected from_block_range [GP]
// - Removed __GNUC__ from compilers that cannot handle the constructor
//     from basic_string and added the workaround suggested by GP. [JGS]
// - Removed __BORLANDC__ from the #if around the basic_string
//     constructor. Luckily the fix by GP for g++ also fixes Borland. [JGS]

#ifndef BOOST_DYNAMIC_BITSET_HPP
#define BOOST_DYNAMIC_BITSET_HPP

#include <boost/config.hpp>
#include <cassert>
#include <string>
#include <iosfwd>
#include <cstring>             // for memset, memcpy, memcmp, etc.
#include <stdexcept>           // for std::overflow_error
#include <algorithm>           // for std::swap, std::min, std::copy, std::fill

#if defined(__GNUC__) && !defined(__SGI_STL_PORT)
#include <ctype.h>
#else
#include <cctype>               // for isspace
#endif

#include "boost/dynamic_bitset_fwd.hpp" //G.P.S.
#include "boost/detail/dynamic_bitset.hpp"

#if defined (__STL_CONFIG_H) && !defined (__STL_USE_NEW_IOSTREAMS)
#define BOOST_OLD_IOSTREAMS
#endif


#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
//  in certain situations VC++ requires a redefinition of
//  default template arguments, in contrast with 14.1/12
//
# define BOOST_WORKAROUND_REPEAT_DEFAULT_TEMPLATE_ARGUMENTS // macro 'local' to this file
#endif



namespace boost {

#ifdef BOOST_WORKAROUND_REPEAT_DEFAULT_TEMPLATE_ARGUMENTS
 template <typename Block = unsigned long, typename Allocator = std::allocator<Block> >
#else
 template <typename Block, typename Allocator>
#endif

class dynamic_bitset :
#ifdef BOOST_DYN_BITSET_USE_FRIENDS
    private
#else
    public
#endif
    detail::dynamic_bitset_base<Block, Allocator>
{
  // Portability note: member function templates are defined inside
  // this class definition to avoid problems with VC++. Similarly,
  // with the member functions of the nested class.
public:
    typedef Block block_type;
    typedef std::size_t size_type;
    enum { bits_per_block = CHAR_BIT * sizeof(Block) };

    // reference to a bit
    class reference
    {
        friend class dynamic_bitset<Block, Allocator>;
        dynamic_bitset* bs;
        size_type bit;
        reference(); // intentionally not implemented
        reference(dynamic_bitset& bs_, size_type bit_) : bs(&bs_), bit(bit_){ }
    public:
        reference& operator=(bool value)          // for b[i] = x
        {
            if (value)
                bs->set(bit);
            else
                bs->reset(bit);
            return *this;
        }
        reference& operator|=(bool value)         // for b[i] |= x
        {
            if (value)
                bs->set(bit);
            return *this;
        }
        reference& operator&=(bool value)         // for b[i] &= x
        {
            if (! (value && bs->test(bit)))
                bs->reset(bit);
            return *this;
        }
        reference& operator^=(bool value)         // for b[i] ^= x
        {
            bs->set(bit, bs->test(bit) ^ value);
            return *this;
        }
        reference& operator-=(bool value)         // for b[i] -= x
        {
            if (!value)
                bs->reset(bit);
            return *this;
        }
        reference& operator=(const reference& j)  // for b[i] = b[j]
        {
            if (j.bs->test(j.bit))
                bs->set(bit);
            else
                bs->reset(bit);
            return *this;
        }
        reference& operator|=(const reference& j) // for b[i] |= b[j]
        {
            if (j.bs->test(j.bit))
                bs->set(bit);
            return *this;
        }
        reference& operator&=(const reference& j) // for b[i] &= b[j]
        {
            if (! (j.bs->test(j.bit) && bs->test(bit)))
                bs->reset(bit);
            return *this;
        }
        reference& operator^=(const reference& j) // for b[i] ^= b[j]
        {
            bs->set(bit, bs->test(bit) ^ j.bs->test(j.bit));
            return *this;
        }
        reference& operator-=(const reference& j) // for b[i] -= b[j]
        {
            if (!j.bs->test(j.bit))
                bs->reset(bit);
            return *this;
        }
        bool operator~() const                    // flips the bit
        {
            return ! bs->test(bit);
        }
        operator bool() const                     // for x = b[i]
        {
            return bs->test(bit);
        }
        reference& flip()                         // for b[i].flip();
        {
            bs->flip(bit);
            return *this;
        }
    };
    typedef bool const_reference;

    // constructors, etc.
    explicit
    dynamic_bitset(const Allocator& alloc = Allocator());

    explicit
    dynamic_bitset(size_type num_bits, unsigned long value = 0,
               const Allocator& alloc = Allocator());

    // from string
#if defined(BOOST_OLD_IOSTREAMS)
    explicit
    dynamic_bitset(const std::string& s,
               std::string::size_type pos = 0,
               std::string::size_type n = std::string::npos,
               const Allocator& alloc = Allocator())
        : detail::dynamic_bitset_base<Block, Allocator>
            (std::min(n, s.size() - pos), alloc)
#else
    // The parenthesis around std::basic_string<CharT, Traits, Alloc>::npos
    // in the code below are to avoid a g++ 3.2 bug and a Borland bug. -JGS
    template <typename CharT, typename Traits, typename Alloc>
    explicit
    dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
        typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0,
        typename std::basic_string<CharT, Traits, Alloc>::size_type n
            = (std::basic_string<CharT, Traits, Alloc>::npos),
        const Allocator& alloc = Allocator())
        : detail::dynamic_bitset_base<Block, Allocator>
            (std::min(n, s.size() - pos), alloc)
#endif
    {
        // Locate sub string
        assert(pos <= s.length());
        from_string(s, pos, std::min(n, s.size() - pos));
    }

    // The first bit in *first is the least significant bit, and the
    // last bit in the block just before *last is the most significant bit.
    template <typename BlockInputIterator>
    dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
               const Allocator& alloc = Allocator())
        : detail::dynamic_bitset_base<Block, Allocator>
            (detail::initial_num_blocks(first, last)
            * bits_per_block, alloc)
    {
        if (first != last) {
            if (this->m_num_bits == 0) { // dealing with input iterators
                this->append(first, last);
            } else {
                // dealing with forward iterators, memory has been allocated
                for (std::size_t i = 0; first != last; ++first, ++i)
                    set_block_(i, *first);
            }
        }
    }


    // copy constructor
    dynamic_bitset(const dynamic_bitset& b);

    void swap(dynamic_bitset& b);

    dynamic_bitset& operator=(const dynamic_bitset& b);

    // size changing operations
    void resize(size_type num_bits, bool value = false);
    void clear();
    void push_back(bool bit);
    void append(Block block);

    // This is declared inside the class to avoid compiler bugs.
    template <typename BlockInputIterator>
    void append(BlockInputIterator first, BlockInputIterator last)
    {
        if (first != last) {
            std::size_t nblocks = detail::initial_num_blocks(first, last);
            if (nblocks == 0) { // dealing with input iterators
                for (; first != last; ++first)
                    append(*first);
            } else { // dealing with forward iterators
                if (size() % bits_per_block == 0) {
                    std::size_t old_nblocks = this->m_num_blocks;
                    resize(size() + nblocks * bits_per_block);
                    for (std::size_t i = old_nblocks; first != last; ++first)
                        set_block_(i++, *first);
                } else {
                    // probably should optimize this,
                    // but I'm sick of bit twiddling
                    for (; first != last; ++first)
                        append(*first);
                }
            }
        }
    }


    // bitset operations
    dynamic_bitset& operator&=(const dynamic_bitset& b);
    dynamic_bitset& operator|=(const dynamic_bitset& b);
    dynamic_bitset& operator^=(const dynamic_bitset& b);
    dynamic_bitset& operator-=(const dynamic_bitset& b);
    dynamic_bitset& operator<<=(size_type n);
    dynamic_bitset& operator>>=(size_type n);
    dynamic_bitset operator<<(size_type n) const;
    dynamic_bitset operator>>(size_type n) const;

    // basic bit operations
    dynamic_bitset& set(size_type n, bool val = true);
    dynamic_bitset& set();
    dynamic_bitset& reset(size_type n);
    dynamic_bitset& reset();
    dynamic_bitset& flip(size_type n);
    dynamic_bitset& flip();
    bool test(size_type n) const;
    bool any() const;
    bool none() const;
    dynamic_bitset operator~() const;
    size_type count() const;

    // subscript
    reference operator[](size_type pos) { return reference(*this, pos); }
    bool operator[](size_type pos) const { return test_(pos); } //[gps]

    unsigned long to_ulong() const;

    size_type size() const;
    size_type num_blocks() const;

    bool is_subset_of(const dynamic_bitset& a) const;
    bool is_proper_subset_of(const dynamic_bitset& a) const;


#ifdef BOOST_DYN_BITSET_USE_FRIENDS
    // lexicographical comparison
    template <typename B, typename A>
    friend bool operator==(const dynamic_bitset<B, A>& a,
                           const dynamic_bitset<B, A>& b);
    template <typename B, typename A>
    friend bool operator<(const dynamic_bitset<B, A>& a,
                          const dynamic_bitset<B, A>& b);
    template <typename B, typename A>
    friend bool operator>(const dynamic_bitset<B, A>& a,
                          const dynamic_bitset<B, A>& b);

    template <typename B, typename A, typename BlockOutputIterator>
    friend void to_block_range(const dynamic_bitset<B, A>& b,
                               BlockOutputIterator result);

    template <typename BlockIterator, typename B, typename A>
    friend void from_block_range(BlockIterator first, BlockIterator last,
                                 dynamic_bitset<B, A>& result);

    template <typename B, typename A, typename CharT, typename Alloc>
    friend void dump_to_string(const dynamic_bitset<B, A>& b,
                               std::basic_string<CharT, Alloc>& s);
#endif

private:
    void m_zero_unused_bits();
    void set_(size_type bit);
    bool set_(size_type bit, bool val);
    void reset_(size_type bit);
    bool test_(size_type bit) const;
    void set_block_(size_type blocknum, Block b);

public:

    // This is templated on the whole String instead of just CharT,
    // Traits, Alloc to avoid compiler bugs.
    template <typename String>
    void from_string(const String& s, typename String::size_type pos,
                     typename String::size_type rlen)
    {
        reset(); // bugfix [gps]
        size_type const tot = std::min (rlen, s.length()); // bugfix [gps]

        // Assumes string contains only 0's and 1's
        for (size_type i = 0; i < tot; ++i) {
        if (s[pos + tot - i - 1] == '1') {
                set_(i);
            } else {
            assert(s[pos + tot - i - 1] == '0');
            }
        }
    }

};

// Global Functions:

// comparison
template <typename Block, typename Allocator>
bool operator!=(const dynamic_bitset<Block, Allocator>& a,
                const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>
bool operator<=(const dynamic_bitset<Block, Allocator>& a,
                const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>
bool operator>(const dynamic_bitset<Block, Allocator>& a,
               const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>
bool operator>=(const dynamic_bitset<Block, Allocator>& a,
                const dynamic_bitset<Block, Allocator>& b);

// stream operators
#ifdef BOOST_OLD_IOSTREAMS
template <typename Block, typename Allocator>
std::ostream& operator<<(std::ostream& os,
                         const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>
std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
#else
template <typename CharT, typename Traits, typename Block, typename Allocator>
std::basic_ostream<CharT, Traits>&
operator<<(std::basic_ostream<CharT, Traits>& os,
           const dynamic_bitset<Block, Allocator>& b);

template <typename CharT, typename Traits, typename Block, typename Allocator>
std::basic_istream<CharT, Traits>&
operator>>(std::basic_istream<CharT, Traits>& is,
           dynamic_bitset<Block, Allocator>& b);
#endif

// bitset operations
template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator&(const dynamic_bitset<Block, Allocator>& b1,
          const dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator|(const dynamic_bitset<Block, Allocator>& b1,
          const dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator^(const dynamic_bitset<Block, Allocator>& b1,
          const dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator-(const dynamic_bitset<Block, Allocator>& b1,
          const dynamic_bitset<Block, Allocator>& b2);


template <typename Block, typename Allocator, typename CharT, typename Alloc>
void
to_string(const dynamic_bitset<Block, Allocator>& b,
          std::basic_string<CharT, Alloc>& s);

template <typename Block, typename Allocator, typename BlockOutputIterator>
void
to_block_range(const dynamic_bitset<Block, Allocator>& b,
               BlockOutputIterator result);

template <typename BlockIterator, typename B, typename A>
inline void
from_block_range(BlockIterator first, BlockIterator last,
                 dynamic_bitset<B, A>& result);

//=============================================================================
// dynamic_bitset implementation

#ifdef BOOST_OLD_IOSTREAMS
template <typename Block, typename Allocator>
inline std::ostream&
operator<<(std::ostream& os,
           const typename dynamic_bitset<Block, Allocator>::reference& br)
{
    return os << (bool)br;
}
#else
template <typename CharT, typename Traits, typename Block, typename Allocator>
inline std::basic_ostream<CharT, Traits>&
operator<<(std::basic_ostream<CharT, Traits>& os,
           const typename dynamic_bitset<Block, Allocator>::reference& br)
{
    return os << (bool)br;
}
#endif

//-----------------------------------------------------------------------------
// constructors, etc.

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
  : detail::dynamic_bitset_base<Block, Allocator>(0, alloc) { }

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>::
dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
  : detail::dynamic_bitset_base<Block, Allocator>(num_bits, alloc)
{
  const size_type M = std::min(sizeof(unsigned long) * CHAR_BIT, num_bits);
  for(size_type i = 0; i < M; ++i, value >>= 1) // [G.P.S.] to be optimized
    if ( value & 0x1 )
      set_(i);
}

// copy constructor
template <typename Block, typename Allocator>
inline dynamic_bitset<Block, Allocator>::
dynamic_bitset(const dynamic_bitset& b)
  : detail::dynamic_bitset_base<Block, Allocator>(b.size(), b.m_alloc)
{
    using namespace std;
    memcpy(this->m_bits, b.m_bits, this->m_num_blocks * sizeof(Block));
}

template <typename Block, typename Allocator>
inline void dynamic_bitset<Block, Allocator>::
swap(dynamic_bitset<Block, Allocator>& b)
{
    std::swap(this->m_bits, b.m_bits);
    std::swap(this->m_num_bits, b.m_num_bits);
    std::swap(this->m_num_blocks, b.m_num_blocks);
    std::swap(this->m_alloc, b.m_alloc);
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
operator=(const dynamic_bitset<Block, Allocator>& b)
{
    dynamic_bitset<Block, Allocator> tmp(b);
    this->swap(tmp);
    return *this;
}

//-----------------------------------------------------------------------------
// size changing operations

template <typename Block, typename Allocator>
void dynamic_bitset<Block, Allocator>::
resize(size_type num_bits, bool value)
{
  if (num_bits == size())
    return;
  size_type new_nblocks = this->calc_num_blocks(num_bits);
  Block* d = this->m_alloc.allocate(new_nblocks, static_cast<void const *>(0));
  if (num_bits < size()) { // shrink
    std::copy(this->m_bits, this->m_bits + new_nblocks, d);
    std::swap(d, this->m_bits);
    this->m_alloc.deallocate(d, this->m_num_blocks);
  } else { // grow
    std::copy(this->m_bits, this->m_bits + this->m_num_blocks, d);
    Block val = value? ~static_cast<Block>(0) : static_cast<Block>(0);
    std::fill(d + this->m_num_blocks, d + new_nblocks, val);
    std::swap(d, this->m_bits);
    for (std::size_t i = this->m_num_bits;
         i < this->m_num_blocks * bits_per_block; ++i)
      set_(i, value);
    if (d != 0)
      this->m_alloc.deallocate(d, this->m_num_blocks);
  }
  this->m_num_bits = num_bits;
  this->m_num_blocks = this->calc_num_blocks(num_bits);
  m_zero_unused_bits();
}

template <typename Block, typename Allocator>
void dynamic_bitset<Block, Allocator>::
clear()
{
  if (this->m_bits != 0) {
    this->m_alloc.deallocate(this->m_bits, this->m_num_blocks);
    this->m_bits = 0;
    this->m_num_bits = 0;
    this->m_num_blocks = 0;
  }
}


template <typename Block, typename Allocator>
void dynamic_bitset<Block, Allocator>::
push_back(bool bit)
{
  this->resize(this->size() + 1);
  set_(this->size() - 1, bit);
}

template <typename Block, typename Allocator>
void dynamic_bitset<Block, Allocator>::
append(Block value)
{
  std::size_t old_size = size();
  resize(old_size + bits_per_block);
  if (size() % bits_per_block == 0)
    set_block_(this->m_num_blocks - 1, value);
  else {
      // G.P.S. to be optimized
    for (std::size_t i = old_size; i < size(); ++i, value >>= 1)
      set_(i, value & 1);
  }
}


//-----------------------------------------------------------------------------
// bitset operations
template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
{
    assert(size() == rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] &= rhs.m_bits[i];
    return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
{
    assert(size() == rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] |= rhs.m_bits[i];
    m_zero_unused_bits();
    return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
{
    assert(size() == rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] ^= rhs.m_bits[i];
    m_zero_unused_bits();
    return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
{
    assert(size() == rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] = this->m_bits[i] & ~rhs.m_bits[i];
    m_zero_unused_bits();
    return *this;
}

/* [gps] - snipped
template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
{
    if (n >= this->m_num_bits)
        reset();
    else
    {
        size_type i;
        for (i = this->m_num_bits - 1; i > n; --i)
            set_(i,test_(i-n));
        if (i == n) // careful, unsigned can't go negative!
            set_(i,test_(i-n));
        for (i = 0; i < n; ++i)
            reset_(i);
    }
    return *this;
}*/


template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
{
    if (n >= this->m_num_bits)
        return reset();
    //else
    if (n > 0)
    {
        size_type  const last  = this->m_num_blocks - 1; // m_num_blocks is >= 1
        size_type  const div   = n / bits_per_block; // div is <= last
        size_type  const r     = n % bits_per_block;

        // PRE: div != 0  or  r != 0

        if (r != 0) {

            block_type const rs = bits_per_block - r;

            for (size_type i = last-div; i>0; --i) {
                this->m_bits[i+div] = (this->m_bits[i] << r) | (this->m_bits[i-1] >> rs);
            }
            this->m_bits[div] = this->m_bits[0] << r;

        }
        else {
            for (size_type i = last-div; i>0; --i) {
                this->m_bits[i+div] = this->m_bits[i];
            }
            this->m_bits[div] = this->m_bits[0];
        }


        // div blocks are zero filled at the less significant end
        std::fill(this->m_bits, this->m_bits+div, static_cast<block_type>(0));


    }

    return *this;


}




/* [gps] - snipped
template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::operator>>=(size_type n)
{
    if (n >= this->m_num_bits)
        reset();
    else
    {
        size_type i;
        for (i = 0; i < this->m_num_bits - n; ++i)
            set_(i,test_(i+n));

        for (i = this->m_num_bits - n; i < this->m_num_bits; ++i)
            reset_(i);
    }
    return *this;
}*/




// NOTE: this assumes that within a single block bits are
//       numbered from right to left. G.P.S.
//
//      static Block offset(size_type bit)
//        { return  bit % bits_per_block; }
//
//
// In the implementation below the 'if (r != 0)' is logically
// unnecessary. It's there as an optimization only: in fact
// for r==0 the first branch becomes the second one with the
// b[last-div] = b[last] >> r; statement that does the work of
// the last iteration.
//
template <typename B, typename A>
dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
    if (n >= this->m_num_bits) {
        return reset();
    }
    //else
    if (n>0){

        size_type  const last  = this->m_num_blocks - 1; // m_num_blocks is >= 1
        size_type  const div   = n / bits_per_block; // div is <= last
        size_type  const r     = n % bits_per_block;

        // PRE: div != 0  or  r != 0

        if (r != 0) {

            block_type const ls = bits_per_block - r;

            for (size_type i = div; i < last; ++i) {
                this->m_bits[i-div] = (this->m_bits[i] >> r) | (this->m_bits[i+1]  << ls);
            }
            // r bits go to zero
            this->m_bits[last-div] = this->m_bits[last] >> r;
        }

        else {
            for (size_type i = div; i <= last; ++i) {
                this->m_bits[i-div] = this->m_bits[i];
            }
            // note the '<=': the last iteration 'absorbs'
            // this->m_bits[last-div] = this->m_bits[last] >> 0;
        }



        // div blocks are zero filled at the most significant end
        std::fill(this->m_bits+(this->m_num_blocks-div), this->m_bits+this->m_num_blocks, static_cast<block_type>(0));
    }

    return *this;
}







template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
{
    dynamic_bitset r(*this);
    return r <<= n;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
{
    dynamic_bitset r(*this);
    return r >>= n;
}


//-----------------------------------------------------------------------------
// basic bit operations

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
{
    assert(pos < this->m_num_bits);
    set_(pos, val);
    return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::set()
{
  if (this->m_num_bits > 0) {
    using namespace std;
    memset(this->m_bits, ~0u, this->m_num_blocks * sizeof(this->m_bits[0]));
    m_zero_unused_bits();
  }
  return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::reset(size_type pos)
{
    assert(pos < this->m_num_bits);
    reset_(pos);
    return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::reset()
{
  if (this->m_num_bits > 0) {
    using namespace std;
    memset(this->m_bits, 0, this->m_num_blocks * sizeof(this->m_bits[0]));
  }
  return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::flip(size_type pos)
{
    assert(pos < this->m_num_bits);
    this->m_bits[this->word(pos)] ^= this->mask1(pos);
    return *this;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>&
dynamic_bitset<Block, Allocator>::flip()
{
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] = ~this->m_bits[i];
    m_zero_unused_bits();
    return *this;
}

template <typename Block, typename Allocator>
bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
{
    assert(pos < this->m_num_bits);
    return test_(pos);
}

template <typename Block, typename Allocator>
bool dynamic_bitset<Block, Allocator>::any() const
{
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        if (this->m_bits[i])
            return 1;
    return 0;
}

template <typename Block, typename Allocator>
inline bool dynamic_bitset<Block, Allocator>::none() const
{
    return !any();
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
dynamic_bitset<Block, Allocator>::operator~() const
{
    dynamic_bitset b(*this);
    b.flip();
    return b;
}


/* snipped: [gps]

The following is the straightforward implementation of count(), which
we leave here in a comment for documentation purposes.

template <typename Block, typename Allocator>
typename dynamic_bitset<Block, Allocator>::size_type
dynamic_bitset<Block, Allocator>::count() const
{
    size_type sum = 0;
    for (size_type i = 0; i != this->m_num_bits; ++i)
        if (test_(i))
            ++sum;
    return sum;
}

The actual algorithm used is based on using a lookup
table.


  The basic idea of the method is to pick up X bits at a time
  from the internal array of blocks and consider those bits as
  the binary representation of a number N. Then, to use a table
  of 1<<X elements where table[N] is the number of '1' digits
  in the binary representation of N (i.e. in our X bits).

  Note that the table can be oversized (i.e. can even have more
  than 1<<X elements; in that case only the first 1<<X will be
  actually used) but it cannot be undersized.
  In this implementation X is 8 (but can be easily changed: you
  just have to change the definition of count<>::max_bits) and
  the internal array of blocks is seen as an array of bytes: if
  a byte has exactly 8 bits then it's enough to sum the value
  of table[B] for each byte B. Otherwise 8 bits at a time are
  'extracted' from each byte by using another loop. As a further
  efficiency consideration note that even if you have, let's say,
  32-bit chars the inner loop will not do 4 (i.e. 32/8) iterations,
  unless you have at least one bit set in the highest 8 bits of the
  byte.

  Note also that the outmost if/else is not necessary but is there
  to help the optimizer (and one of the two branches is always dead
  code).

*/


template <typename Block, typename Allocator>
typename dynamic_bitset<Block, Allocator>::size_type
dynamic_bitset<Block, Allocator>::count() const
{
    using detail::byte_t;

    const byte_t * p = reinterpret_cast<const byte_t*>(this->m_bits);
    const byte_t * past_end = p + this->m_num_blocks * sizeof(Block);

    size_type num = 0;
    unsigned int const max_bit = detail::count<>::max_bit;

    if (CHAR_BIT <= max_bit) { // table is large enough
        while (p < past_end) {
            num += detail::count<>::table[*p];
            ++p;
        }
    }
    else {
        while (p < past_end) {
            // this inner loop 'extracts' max_bit bits at a time
            // from the byte at address p, and thus allows to use
            // our (small) table for any (high) CHAR_BIT value
            byte_t value = *p;
            do {
                num += detail::count<>::table[value & ((1<<max_bit)-1)];
            } while (value >>= max_bit);

            ++p;
        }
    }


    return num;
}


//-----------------------------------------------------------------------------
// conversions

// take as ref param instead?
template <typename Block, typename Allocator, typename CharT, typename Alloc>
void
to_string(const dynamic_bitset<Block, Allocator>& b,
          std::basic_string<CharT, Alloc>& s)
{
    s.assign(b.size(), '0');
    for (std::size_t i = 0; i < b.size(); ++i)
        if (b.test(i)) // [G.P.S.]
            s[b.size() - 1 - i] = '1';
}


// Differently from to_string this function dumps out
// every bit of the internal representation (useful
// for debugging purposes)
//
template <typename B, typename A, typename CharT, typename Alloc>
void
dump_to_string(const dynamic_bitset<B, A>& b,
               std::basic_string<CharT, Alloc>& s)
{
    std::size_t const len = b.m_num_blocks * (dynamic_bitset<B, A>::bits_per_block);
    s.assign(len, '0');
    for (std::size_t i = 0; i != len; ++i)
      if (b[i])// could use test_ here, but we have friend issues.-JGS
            s[len - 1 - i] = '1';
}

template <typename Block, typename Allocator, typename BlockOutputIterator>
void
to_block_range(const dynamic_bitset<Block, Allocator>& b,
               BlockOutputIterator result)
{
    assert(b.size() != 0 || b.num_blocks() == 0);
    std::copy (b.m_bits, b.m_bits + b.m_num_blocks, result);
}

template <typename BlockIterator, typename B, typename A>
inline void
from_block_range(BlockIterator first, BlockIterator last,
                 dynamic_bitset<B, A>& result)
{
    // PRE: distance(first, last) == numblocks()
    std::copy (first, last, result.m_bits);
}

template <typename Block, typename Allocator>
unsigned long dynamic_bitset<Block, Allocator>::
to_ulong() const
{
  const std::overflow_error
    overflow("boost::bit_set::operator unsigned long()");

  if (this->m_num_blocks == 0)
    return 0;

  if (sizeof(Block) >= sizeof(unsigned long)) {
    for (size_type i = 1; i < this->m_num_blocks; ++i)
      if (this->m_bits[i])
        throw overflow;
    const Block mask = static_cast<Block>(static_cast<unsigned long>(-1));
    if (this->m_bits[0] & ~mask)
      throw overflow;
    size_type N = std::min(sizeof(unsigned long) * CHAR_BIT, this->size());
    unsigned long num = 0;
    for (size_type j = 0; j < N; ++j)
      if (this->test(j))
        num |= (1 << j);
    return num;
  }
  else { // sizeof(Block) < sizeof(unsigned long).
    const size_type nwords =
      (sizeof(unsigned long) + sizeof(Block) - 1) / sizeof(Block);

    size_type min_nwords = nwords;
    if (this->m_num_blocks > nwords) {
      for (size_type i = nwords; i < this->m_num_blocks; ++i)
        if (this->m_bits[i])
          throw overflow;
    }
    else
      min_nwords = this->m_num_blocks;

    unsigned long result = 0;
    size_type N = std::min(sizeof(unsigned long) * CHAR_BIT, this->size());
    for (size_type i = 0; i < N; ++i)
      if (this->test(i))
        result |= (1 << i);
    return result;
  }
}


template <typename Block, typename Allocator>
inline typename dynamic_bitset<Block, Allocator>::size_type
dynamic_bitset<Block, Allocator>::size() const
{
    return this->m_num_bits;
}

template <typename Block, typename Allocator>
inline typename dynamic_bitset<Block, Allocator>::size_type
dynamic_bitset<Block, Allocator>::num_blocks() const
{
    return this->m_num_blocks;
}


template <typename Block, typename Allocator>
bool dynamic_bitset<Block, Allocator>::
is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
{
    assert(this->size() == a.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        if (this->m_bits[i] & ~a.m_bits[i])
            return false;
    return true;
}

template <typename Block, typename Allocator>
bool dynamic_bitset<Block, Allocator>::
is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
{
    assert(this->size() == a.size());
    bool proper = false;
    for (size_type i = 0; i < this->m_num_blocks; ++i) {
        Block bt = this->m_bits[i], ba = a.m_bits[i];
        if (ba & ~bt)
            proper = true;
        if (bt & ~ba)
            return false;
    }
    return proper;
}

//-----------------------------------------------------------------------------
// comparison

template <typename Block, typename Allocator>
bool operator==(const dynamic_bitset<Block, Allocator>& a,
                const dynamic_bitset<Block, Allocator>& b)
{
    using namespace std;
    return (a.m_num_bits == b.m_num_bits) &&
      ((a.m_num_bits == 0) ||
        !memcmp(a.m_bits, b.m_bits, a.m_num_blocks * sizeof(a.m_bits[0])));
}

template <typename Block, typename Allocator>
inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
                       const dynamic_bitset<Block, Allocator>& b)
{
    return !(a == b);
}

template <typename Block, typename Allocator>
bool operator<(const dynamic_bitset<Block, Allocator>& a,
               const dynamic_bitset<Block, Allocator>& b)
{
    assert(a.size() == b.size());
    typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;

    if (a.size() == 0)
      return false;

    // Since we are storing the most significant bit
    // at pos == size() - 1, we need to do the memcmp in reverse.

    // Compare a block at a time
    for (size_type i = a.m_num_blocks - 1; i > 0; --i)
      if (a.m_bits[i] < b.m_bits[i])
        return true;
      else if (a.m_bits[i] > b.m_bits[i])
        return false;

    if (a.m_bits[0] < b.m_bits[0])
      return true;
    else
      return false;
}

template <typename Block, typename Allocator>
inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
                       const dynamic_bitset<Block, Allocator>& b)
{
    return !(a > b);
}

template <typename Block, typename Allocator>
inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
                      const dynamic_bitset<Block, Allocator>& b)
{
    assert(a.size() == b.size());
    typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;

    if (a.size() == 0)
      return false;

    // Since we are storing the most significant bit
    // at pos == size() - 1, we need to do the memcmp in reverse.

    // Compare a block at a time
    for (size_type i = a.m_num_blocks - 1; i > 0; --i)
      if (a.m_bits[i] < b.m_bits[i])
        return false;
      else if (a.m_bits[i] > b.m_bits[i])
        return true;

    if (a.m_bits[0] > b.m_bits[0])
      return true;
    else
      return false;
}

template <typename Block, typename Allocator>
inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
                       const dynamic_bitset<Block, Allocator>& b)
{
    return !(a < b);
}

//-----------------------------------------------------------------------------
// stream operations

#ifdef BOOST_OLD_IOSTREAMS
template < typename Block, typename Allocator>
std::ostream&
operator<<(std::ostream& os, const dynamic_bitset<Block, Allocator>& b)
{
    std::string s;
    to_string(b, s);
    os << s.c_str();
    return os;
}
#else
template <typename CharT, typename Traits, typename Block, typename Allocator>
std::basic_ostream<CharT, Traits>&
operator<<(std::basic_ostream<CharT, Traits>& os,
           const dynamic_bitset<Block, Allocator>& b)
{
    std::basic_string<CharT, Traits> s;
    to_string(b, s);
    os << s;
    return os;
}
#endif

#ifdef BOOST_OLD_IOSTREAMS
template <typename Block, typename Allocator>
std::istream&
operator>>(std::istream& is, dynamic_bitset<Block, Allocator>& b)
{
    typedef char CharT;
    std::string buf;
    typedef typename std::string::size_type size_type;
    const size_type N = b.size();
    buf.reserve(N);

    // skip whitespace
    if (is.flags() & std::ios::skipws) {
        char c;
        do
            is.get(c);
#if defined(__GNUC__) && !defined(__SGI_STL_PORT)
        while (is && isspace(c));
#else
        while (is && std::isspace(c));
#endif
        if (is)
            is.putback(c);
    }

    size_type i;
    for (i = 0; i < N; ++i)
    {
        CharT c;
        is.get(c);
        if (c == '0' || c == '1')
            buf += c;
        else
        {
            is.putback(c);
            break;
        }
    }

    if (i == 0)
        is.clear(is.rdstate() | std::ios::failbit);
    else
    {
        dynamic_bitset<Block, Allocator> tmp(buf);
        b.swap(tmp);
    }
    return is;
}
#else
template <typename CharT, typename Traits, typename Block, typename Allocator>
std::basic_istream<CharT, Traits>&
operator>>(std::basic_istream<CharT, Traits>& in_stream,
           dynamic_bitset<Block, Allocator>& b)
{
    std::basic_string<CharT,Traits> tmp;
    typedef typename std::basic_string<CharT,Traits>::size_type size_type;
    const size_type N = b.size();
    tmp.reserve(N);

    // skip whitespace
    typename std::basic_istream<CharT, Traits>::sentry sentry(in_stream);
    if (sentry) {
      std::basic_streambuf<CharT, Traits>* read_buf = in_stream.rdbuf();

      for (size_type i = 0; i < N; ++i) {
        typename Traits::int_type c1 = read_buf->sbumpc();
        if (Traits::eq_int_type(c1, Traits::eof())) {
          in_stream.setstate(std::ios_base::eofbit);
          break;
        } else {
          char c2 = Traits::to_char_type(c1);
          char c  = in_stream.narrow(c2, '*');

          if (c == '0' || c == '1')
            tmp += c; // old dinkumware basic_string missing push_back
          else if (Traits::eq_int_type(read_buf->sputbackc(c2), Traits::eof()))
          {
            in_stream.setstate(std::ios_base::failbit);
            break;
          }
        }
      } // for

      if (tmp.empty()) // did not read in enough bits
        in_stream.setstate(std::ios_base::failbit);
      else
          b.from_string(tmp, static_cast<size_type>(0), N);
    } // if (sentry)
    return in_stream;
}
#endif


//-----------------------------------------------------------------------------
// bitset operations

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator&(const dynamic_bitset<Block, Allocator>& x,
          const dynamic_bitset<Block, Allocator>& y)
{
    dynamic_bitset<Block, Allocator> b(x);
    return b &= y;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator|(const dynamic_bitset<Block, Allocator>& x,
          const dynamic_bitset<Block, Allocator>& y)
{
    dynamic_bitset<Block, Allocator> b(x);
    return b |= y;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator^(const dynamic_bitset<Block, Allocator>& x,
          const dynamic_bitset<Block, Allocator>& y)
{
    dynamic_bitset<Block, Allocator> b(x);
    return b ^= y;
}

template <typename Block, typename Allocator>
dynamic_bitset<Block, Allocator>
operator-(const dynamic_bitset<Block, Allocator>& x,
          const dynamic_bitset<Block, Allocator>& y)
{
    dynamic_bitset<Block, Allocator> b(x);
    return b -= y;
}


//-----------------------------------------------------------------------------
// private member functions

template <typename Block, typename Allocator>
inline void dynamic_bitset<Block, Allocator>::
set_(size_type bit)
{
    this->m_bits[this->word(bit)] |= this->mask1(bit);
}

template <typename Block, typename Allocator>
inline void dynamic_bitset<Block, Allocator>::
set_block_(size_type blocknum, Block value)
{
    this->m_bits[blocknum] = value;
}

template <typename Block, typename Allocator>
inline void dynamic_bitset<Block, Allocator>::
reset_(size_type b)
{
    this->m_bits[this->word(b)] &= this->mask0(b);
}

template <typename Block, typename Allocator>
inline bool dynamic_bitset<Block, Allocator>::test_(size_type b) const
{
    return (this->m_bits[this->word(b)] & this->mask1(b)) != static_cast<Block>(0);
}

template <typename Block, typename Allocator>
bool dynamic_bitset<Block, Allocator>::set_(size_type n, bool value)
{
    if (value)
        set_(n);
    else
        reset_(n);
    return value != static_cast<Block>(0);
}


// If size() is not a multiple of bits_per_block
// then not all the bits in the last block are used.
// This function resets the unused bits (convenient
// for the implementation of many member functions)
//
template <typename Block, typename Allocator>
inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
{
    assert (this->m_num_blocks == this->calc_num_blocks(this->m_num_bits));

    // if != 0 this is the number of bits used in the last block
    const size_type used_bits = this->m_num_bits % bits_per_block;

    if (used_bits != 0)
        this->m_bits[this->m_num_blocks - 1] &= ~(~static_cast<Block>(0) << used_bits);

}


} // namespace boost


#undef BOOST_WORKAROUND_REPEAT_DEFAULT_TEMPLATE_ARGUMENTS

#endif // BOOST_DYNAMIC_BITSET_HPP


