// --------------------------------------------------

//

// (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.

// (C) Copyright Gennaro Prota                 2003 - 2004.

//

// Distributed under the Boost Software License, Version 1.0.

//    (See accompanying file LICENSE_1_0.txt or copy at

//          http://www.boost.org/LICENSE_1_0.txt)

//

// -----------------------------------------------------------

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

#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP

#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP

#include <cassert>

#include <string>

#include <stdexcept>           // for std::overflow_error

#include <algorithm>           // for std::swap, std::min, std::copy, std::fill

#include <vector>

#include <climits>             // for CHAR_BIT

#include "boost/dynamic_bitset/config.hpp"

#ifndef BOOST_NO_STD_LOCALE

# include <locale> // G.P.S

#endif

#if defined(BOOST_OLD_IOSTREAMS)

#  include <iostream.h>

#  include <ctype.h> // for isspace

#else

#  include <istream>

#  include <ostream>

#endif

#include "boost/dynamic_bitset_fwd.hpp"

#include "boost/detail/dynamic_bitset.hpp"

#include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)

#include "boost/static_assert.hpp"

#include "boost/limits.hpp"

#include "boost/pending/lowest_bit.hpp" // used by find_first/next

namespace boost {

template

#if defined(BOOST_MSVC) && BOOST_WORKAROUND(BOOST_MSVC, <= 1300)  // 1300 == VC++ 7.0

   // VC++ (up to 7.0) wants the default arguments again

   <typename Block = unsigned long, typename Allocator = std::allocator<Block> >

# else

   <typename Block, typename Allocator>

# endif

class dynamic_bitset

{

  // Portability note: member function templates are defined inside

  // this class definition to avoid problems with VC++. Similarly,

  // with the member functions of nested classes.

  BOOST_STATIC_ASSERT(detail::dynamic_bitset_allowed_block_type<Block>::value);

public:

    typedef Block block_type;

    typedef Allocator allocator_type;

    typedef std::size_t size_type;

    typedef int block_width_type; // gps

    BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));

    BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));

public:

    // A proxy class to simulate lvalues of bit type.

    // Shouldn't it be private? [gps]

    //

    class reference

    {

        friend class dynamic_bitset<Block, Allocator>;

        // the one and only non-copy ctor

        reference(block_type & b, int pos)

            :m_block(b), m_mask(block_type(1) << pos)

        {}

        void operator&(); // left undefined

    public:

        // copy constructor: compiler generated

        operator bool() const { return (m_block & m_mask) != 0; }

        bool operator~() const { return (m_block & m_mask) == 0; }

        reference& flip() { do_flip(); return *this; }

        reference& operator=(bool x)               { do_assign(x);   return *this; } // for b[i] = x

        reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]

        reference& operator|=(bool x) { if  (x) do_set();   return *this; }

        reference& operator&=(bool x) { if (!x) do_reset(); return *this; }

        reference& operator^=(bool x) { if  (x) do_flip();  return *this; }

        reference& operator-=(bool x) { if  (x) do_reset(); return *this; }

     private:

        block_type & m_block;

        const block_type m_mask;

        void do_set() { m_block |= m_mask; }

        void do_reset() { m_block &= ~m_mask; }

        void do_flip() { m_block ^= m_mask; }

        void do_assign(bool x) { x? do_set() : do_reset(); }

    };

    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());

    // The presence of this constructor is a concession to ease of

    // use, especially for the novice user. A conversion from string

    // is, in most cases, formatting, and should be done by the standard

    // formatting convention: operator>>.

    //

    // NOTE:

    // Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.

    // g++ 3.2 requires them and probably the standard will - see core issue 325

    // NOTE 2: 

    // split into two constructors because of bugs in MSVC 6.0sp5 with STLport

    template <typename CharT, typename Traits, typename Alloc>

    dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,

        typename std::basic_string<CharT, Traits, Alloc>::size_type pos,

        typename std::basic_string<CharT, Traits, Alloc>::size_type n,

        size_type num_bits = npos,

        const Allocator& alloc = Allocator())

    :m_bits(alloc),

     m_num_bits(0)

    {

      init_from_string(s, pos, n, num_bits, alloc);

    }

    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)

    :m_bits(Allocator()),

     m_num_bits(0)

    {

      init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),

                       npos, Allocator());

    }

    // 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())

    :m_bits(first, last, alloc),

     m_num_bits(m_bits.size() * bits_per_block)

    {}

    // copy constructor

    dynamic_bitset(const dynamic_bitset& b);

    ~dynamic_bitset();

    void swap(dynamic_bitset& b);

    dynamic_bitset& operator=(const dynamic_bitset& b);

    allocator_type get_allocator() const;

    // size changing operations

    void resize(size_type num_bits, bool value = false);

    void clear();

    void push_back(bool bit);

    void append(Block block);

    template <typename BlockInputIterator>

    void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)

    {

        std::vector<Block, Allocator> v(first, last);

        m_append(v.begin(), v.end(), std::random_access_iterator_tag());

    }

    template <typename BlockInputIterator>

    void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)

    {

        assert(first != last);

        block_width_type r = count_extra_bits();

        std::size_t d = boost::detail::distance(first, last);

        m_bits.reserve(num_blocks() + d);

        if (r == 0) {

            for( ; first != last; ++first)

                m_bits.push_back(*first); // could use vector<>::insert()

        }

        else {

            m_highest_block() |= (*first << r);

            do {

                Block b = *first >> (bits_per_block - r);

                ++first;

                m_bits.push_back(b | (first==last? 0 : *first << r));

            } while (first != last);

        }

        m_num_bits += bits_per_block * d;

    }

    template <typename BlockInputIterator>

    void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee

    {

        if (first != last) {

            typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;

            m_append(first, last, cat);

        }

    }

    // 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(m_bits[block_index(pos)], bit_index(pos));

    }

    bool operator[](size_type pos) const { return test(pos); }

    unsigned long to_ulong() const;

    size_type size() const;

    size_type num_blocks() const;

    size_type max_size() const;

    bool empty() const;

#if 0 // gps

    void reserve(size_type n);

    size_type capacity() const;

#endif

    bool is_subset_of(const dynamic_bitset& a) const;

    bool is_proper_subset_of(const dynamic_bitset& a) const;

    bool intersects(const dynamic_bitset & a) const;

    // lookup

    size_type find_first() const;

    size_type find_next(size_type pos) const;

#if !defined BOOST_DYNAMIC_BITSET_DONT_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, 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 CharT, typename Traits, typename B, typename A>

    friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,

                                                         dynamic_bitset<B, A>& b);

    template <typename B, typename A, typename stringT>

    friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);

#endif

private:

    BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);

    typedef std::vector<block_type, allocator_type> buffer_type;

    void m_zero_unused_bits();

    bool m_check_invariants() const;

    size_type m_do_find_from(size_type first_block) const;

    block_width_type count_extra_bits() const { return bit_index(size()); }

    static size_type block_index(size_type pos) { return pos / bits_per_block; }

    static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }

    static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }

    template <typename CharT, typename Traits, typename Alloc>

    void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,

        typename std::basic_string<CharT, Traits, Alloc>::size_type pos,

        typename std::basic_string<CharT, Traits, Alloc>::size_type n,

        size_type num_bits,

        const Allocator& alloc)

    {

        assert(pos <= s.size());

        typedef typename std::basic_string<CharT, Traits, Alloc> StrT;

        typedef typename StrT::traits_type Tr;

        const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); // gps

        const size_type sz = ( num_bits != npos? num_bits : rlen);

        m_bits.resize(calc_num_blocks(sz));

        m_num_bits = sz;

        BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());

        const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');

        const size_type m = num_bits < rlen ? num_bits : rlen; // [gps]

        typename StrT::size_type i = 0;

        for( ; i < m; ++i) {

            const CharT c = s[(pos + m - 1) - i];

            assert( Tr::eq(c, one)

                    || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );

            if (Tr::eq(c, one))

                set(i);

        }

    }

BOOST_DYNAMIC_BITSET_PRIVATE:

    bool m_unchecked_test(size_type pos) const;

    static size_type calc_num_blocks(size_type num_bits);

    Block&        m_highest_block();

    const Block&  m_highest_block() const;

    buffer_type m_bits; // [gps] to be renamed

    size_type   m_num_bits;

    class bit_appender;

    friend class bit_appender;

    class bit_appender {

      // helper for stream >>

      // Supplies to the lack of an efficient append at the less

      // significant end: bits are actually appended "at left" but

      // rearranged in the destructor. Everything works just as if

      // dynamic_bitset<> had an append_at_right() function (which

      // threw, in case, the same exceptions as push_back) except

      // that the function is actually called bit_appender::do_append().

      //

      dynamic_bitset & bs;

      size_type n;

      Block mask;

      Block * current;

    public:

        bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}

        ~bit_appender() {

            // reverse the order of blocks, shift

            // if needed, and then resize

            //

            std::reverse(bs.m_bits.begin(), bs.m_bits.end());

            const block_width_type offs = bit_index(n);

            if (offs)

                bs >>= (bits_per_block - offs);

            bs.resize(n); // doesn't enlarge, so can't throw

            assert(bs.m_check_invariants());

        }

        inline void do_append(bool value) {

            if (mask == 0) {

                bs.append(Block(0));

                current = &bs.m_highest_block();

                mask = Block(1) << (bits_per_block - 1);

            }

            if(value)

                *current |= mask;

            mask /= 2;

            ++n;

        }

        size_type get_count() const { return n; }

    };

};

#if BOOST_WORKAROUND( __IBMCPP__, <=600 )

// Workaround for IBM's AIX platform.

// See http://comments.gmane.org/gmane.comp.lib.boost.user/15331

template<typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>::block_width_type const

dynamic_bitset<Block, Allocator>::bits_per_block;

template<typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>::block_width_type const

dynamic_bitset<Block, Allocator>::ulong_width;

#endif

// 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

// NOTE: Digital Mars wants the same template parameter names

//       here and in the definition! [last tested: 8.48.10]

//

template <typename Ch, typename Tr, typename Block, typename Alloc>

std::basic_ostream<Ch, Tr>&

operator<<(std::basic_ostream<Ch, Tr>& os,

           const dynamic_bitset<Block, Alloc>& b);

template <typename Ch, typename Tr, typename Block, typename Alloc>

std::basic_istream<Ch, Tr>&

operator>>(std::basic_istream<Ch, Tr>& is,

           dynamic_bitset<Block, Alloc>& 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);

// namespace scope swap

template<typename Block, typename Allocator>

void swap(dynamic_bitset<Block, Allocator>& b1,

          dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator, typename stringT>

void

to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps

template <typename Block, typename Allocator, typename BlockOutputIterator>

void

to_block_range(const dynamic_bitset<Block, Allocator>& b,

               BlockOutputIterator result);

// gps - check docs with Jeremy

//

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.begin()); //[gps]

}

//=============================================================================

// dynamic_bitset implementation

//-----------------------------------------------------------------------------

// constructors, etc.

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)

  : m_bits(alloc), m_num_bits(0)

{

}

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>::

dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)

  : m_bits(calc_num_blocks(num_bits), Block(0), alloc),

    m_num_bits(num_bits)

{

  if (num_bits == 0)

      return;

  typedef unsigned long num_type;

  // cut off all bits in value that have pos >= num_bits, if any

  if (num_bits < static_cast<size_type>(ulong_width)) {

      const num_type mask = (num_type(1) << num_bits) - 1;

      value &= mask;

  }

  if (bits_per_block >= ulong_width) {

      m_bits[0] = static_cast<block_type>(value);

  }

  else {

      for(size_type i = 0; value != 0; ++i) {

          m_bits[i] = static_cast<block_type>(value);

          value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);

      }

  }

}

// copy constructor

template <typename Block, typename Allocator>

inline dynamic_bitset<Block, Allocator>::

dynamic_bitset(const dynamic_bitset& b)

  : m_bits(b.m_bits), m_num_bits(b.m_num_bits)  // [gps]

{

}

template <typename Block, typename Allocator>

inline dynamic_bitset<Block, Allocator>::

~dynamic_bitset()

{

    assert(m_check_invariants());

}

template <typename Block, typename Allocator>

inline void dynamic_bitset<Block, Allocator>::

swap(dynamic_bitset<Block, Allocator>& b) // no throw

{

    std::swap(m_bits, b.m_bits);

    std::swap(m_num_bits, b.m_num_bits);

}

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::

operator=(const dynamic_bitset<Block, Allocator>& b)

{

#if 0 // gps

    dynamic_bitset<Block, Allocator> tmp(b);

    this->swap(tmp);

    return *this;

#else

    m_bits = b.m_bits;

    m_num_bits = b.m_num_bits;

    return *this;

#endif

}

template <typename Block, typename Allocator>

inline typename dynamic_bitset<Block, Allocator>::allocator_type

dynamic_bitset<Block, Allocator>::get_allocator() const

{

    return m_bits.get_allocator();

}

//-----------------------------------------------------------------------------

// size changing operations

template <typename Block, typename Allocator>

void dynamic_bitset<Block, Allocator>::

resize(size_type num_bits, bool value) // strong guarantee

{

  const size_type old_num_blocks = num_blocks();

  const size_type required_blocks = calc_num_blocks(num_bits);

  const block_type v = value? ~Block(0) : Block(0);

  if (required_blocks != old_num_blocks) {

    m_bits.resize(required_blocks, v); // s.g. (copy) [gps]

  }

  // At this point:

  //

  //  - if the buffer was shrunk, there's nothing to do, except

  //    a call to m_zero_unused_bits()

  //

  //  - if it it is enlarged, all the (used) bits in the new blocks have

  //    the correct value, but we should also take care of the bits,

  //    if any, that were 'unused bits' before enlarging: if value == true,

  //    they must be set.

  if (value && (num_bits > m_num_bits)) {

    const size_type extra_bits = count_extra_bits(); // gps

    if (extra_bits) {

        assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());

        // Set them.

        m_bits[old_num_blocks - 1] |= (v << extra_bits); // gps

    }

  }

  m_num_bits = num_bits;

  m_zero_unused_bits();

}

template <typename Block, typename Allocator>

void dynamic_bitset<Block, Allocator>::

clear() // no throw

{

  m_bits.clear();

  m_num_bits = 0;

}

template <typename Block, typename Allocator>

void dynamic_bitset<Block, Allocator>::

push_back(bool bit)

{

  resize(size() + 1);

  set(size() - 1, bit);

}

template <typename Block, typename Allocator>

void dynamic_bitset<Block, Allocator>::

append(Block value) // strong guarantee

{

    // G.P.S. to be reviewed...

    const block_width_type r = count_extra_bits();

    if (r == 0) {

        // the buffer is empty, or all blocks are filled

        m_bits.push_back(value);

    }

    else {

        m_bits.push_back(value >> (bits_per_block - r));

        m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2

    }

    m_num_bits += bits_per_block;

    assert(m_check_invariants());

}

//-----------------------------------------------------------------------------

// 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 < num_blocks(); ++i)

        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 < num_blocks(); ++i)

        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->num_blocks(); ++i)

        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 < num_blocks(); ++i)

        m_bits[i] &= ~rhs.m_bits[i];

    //m_zero_unused_bits();

    return *this;

}

//

// NOTE:

//  Note that the 'if (r != 0)' is crucial to avoid undefined

//  behavior when the left hand operand of >> isn't promoted to a

//  wider type (because rs would be too large).

//

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>&

dynamic_bitset<Block, Allocator>::operator<<=(size_type n)

{

    if (n >= m_num_bits)

        return reset();

    //else

    if (n > 0) {

        size_type    const last = num_blocks() - 1;  // num_blocks() is >= 1

        size_type    const div  = n / bits_per_block; // div is <= last

        block_width_type const r = bit_index(n);

        block_type * const b    = &m_bits[0];

        if (r != 0) {

            block_width_type const rs = bits_per_block - r;

            for (size_type i = last-div; i>0; --i) {

                b[i+div] = (b[i] << r) | (b[i-1] >> rs);

            }

            b[div] = b[0] << r;

        }

        else {

            for (size_type i = last-div; i>0; --i) {

                b[i+div] = b[i];

            }

            b[div] = b[0];

        }

        // zero out div blocks at the less significant end

        std::fill_n(b, div, static_cast<block_type>(0));

        // zero out any 1 bit that flowed into the unused part

        m_zero_unused_bits(); // thanks to Lester Gong

    }

    return *this;

}

//

// NOTE:

//  see the comments to operator <<=

//

template <typename B, typename A>

dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {

    if (n >= m_num_bits) {

        return reset();

    }

    //else

    if (n>0) {

        size_type  const last  = num_blocks() - 1; // num_blocks() is >= 1

        size_type  const div   = n / bits_per_block;   // div is <= last

        block_width_type const r     = bit_index(n);

        block_type * const b   = &m_bits[0];

        if (r != 0) {

            block_width_type const ls = bits_per_block - r;

            for (size_type i = div; i < last; ++i) {

                b[i-div] = (b[i] >> r) | (b[i+1]  << ls);

            }

            // r bits go to zero

            b[last-div] = b[last] >> r;

        }

        else {

            for (size_type i = div; i <= last; ++i) {

                b[i-div] = b[i];

            }

            // note the '<=': the last iteration 'absorbs'

            // b[last-div] = b[last] >> 0;

        }

        // div blocks are zero filled at the most significant end

        std::fill_n(b + (num_blocks()-div), div, 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)

{

    // [gps]

    //

    // Below we have no set(size_type) function to call when

    // value == true; instead of using a helper, I think

    // overloading set (rather than giving it a default bool

    // argument) would be more elegant.

    assert(pos < m_num_bits);

    if (val)

        m_bits[block_index(pos)] |= bit_mask(pos);

    else

        reset(pos);

    return *this;

}

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>&

dynamic_bitset<Block, Allocator>::set()

{

  std::fill(m_bits.begin(), m_bits.end(), ~Block(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 < m_num_bits);

    #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x

    // CodeWarrior 8 generates incorrect code when the &=~ is compiled,

    // use the |^ variation instead.. <grafik>

    m_bits[block_index(pos)] |= bit_mask(pos);

    m_bits[block_index(pos)] ^= bit_mask(pos);

    #else

    m_bits[block_index(pos)] &= ~bit_mask(pos);

    #endif

    return *this;

}

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>&

dynamic_bitset<Block, Allocator>::reset()

{

  std::fill(m_bits.begin(), m_bits.end(), Block(0));

  return *this;

}

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>&

dynamic_bitset<Block, Allocator>::flip(size_type pos)

{

    assert(pos < m_num_bits);

    m_bits[block_index(pos)] ^= bit_mask(pos);

    return *this;

}

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>&

dynamic_bitset<Block, Allocator>::flip()

{

    for (size_type i = 0; i < num_blocks(); ++i)

        m_bits[i] = ~m_bits[i];

    m_zero_unused_bits();

    return *this;

}

template <typename Block, typename Allocator>

bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const

{

    return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;

}

template <typename Block, typename Allocator>

bool dynamic_bitset<Block, Allocator>::test(size_type pos) const

{

    assert(pos < m_num_bits);

    return m_unchecked_test(pos);

}

template <typename Block, typename Allocator>

bool dynamic_bitset<Block, Allocator>::any() const

{

    for (size_type i = 0; i < num_blocks(); ++i)

        if (m_bits[i])

            return true;

    return false;

}

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;

}

/*

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;