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

 //

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

 }

 The actual algorithm uses 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).

   In this implementation X is 8 (but can be easily changed: you

   just have to modify the definition of table_width and shrink/enlarge

   the table accordingly - it could be useful, for instance, to expand

   the table to 512 elements on an implementation with 9-bit bytes) and

   the internal array of blocks is seen, if possible, as an array of bytes.

   In practice the "reinterpretation" as array of bytes is possible if and

   only if X >= CHAR_BIT and Block has no padding bits (that would be counted

   together with the "real ones" if we saw the array as array of bytes).

   Otherwise we simply 'extract' X bits at a time from each Block.

 */

 template <typename Block, typename Allocator>

 typename dynamic_bitset<Block, Allocator>::size_type

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

 {

     using namespace detail::dynamic_bitset_count_impl;

     const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);

     const bool enough_table_width = table_width >= CHAR_BIT;

     typedef mode_to_type< (no_padding && enough_table_width ?

                           access_by_bytes : access_by_blocks) > m;

     return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(0));

 }

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

 // conversions

 template <typename B, typename A, typename stringT>

 void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,

                       bool dump_all)

 {

     typedef typename stringT::traits_type Tr;

     typedef typename stringT::value_type  Ch;

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

     const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');

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

     // Note that this function may access (when

     // dump_all == true) bits beyond position size() - 1

     typedef typename dynamic_bitset<B, A>::size_type size_type;

     const size_type len = dump_all?

          dynamic_bitset<B, A>::bits_per_block * b.num_blocks():

          b.size();

     s.assign (len, zero);

     for (size_type i = 0; i < len; ++i) {

         if (b.m_unchecked_test(i))

             Tr::assign(s[len - 1 - i], one);

     }

 }

 // A comment similar to the one about the constructor from

 // basic_string can be done here. Thanks to James Kanze for

 // making me (Gennaro) realize this important separation of

 // concerns issue, as well as many things about i18n.

 //

 template <typename Block, typename Allocator, typename stringT> // G.P.S.

 inline void

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

 {

     to_string_helper(b, s, false);

 }

 // Differently from to_string this function dumps out

 // every bit of the internal representation (may be

 // useful for debugging purposes)

 //

 template <typename B, typename A, typename stringT>

 inline void

 dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.

 {

     to_string_helper(b, s, true /* =dump_all*/);

 }

 template <typename Block, typename Allocator, typename BlockOutputIterator>

 inline void

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

                BlockOutputIterator result)

 {

     // note how this copies *all* bits, including the

     // unused ones in the last block (which are zero)

     std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]

 }

 template <typename Block, typename Allocator>

 unsigned long dynamic_bitset<Block, Allocator>::

 to_ulong() const

 {

   if (m_num_bits == 0)

       return 0; // convention

   // Check for overflows. This may be a performance burden on very

   // large bitsets but is required by the specification, sorry

   if (find_next(ulong_width - 1) != npos)

     throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");

   // Ok, from now on we can be sure there's no "on" bit beyond

   // the allowed positions

   if (bits_per_block >= ulong_width)

       return m_bits[0];

   size_type last_block = block_index((std::min)(m_num_bits-1, // gps

                                     (size_type)(ulong_width-1)));

   unsigned long result = 0;

   for (size_type i = 0; i <= last_block; ++i) {

     assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps

     unsigned long piece = m_bits[i];

     result |= (piece << (bits_per_block * i));

   }

   return result;

 }

 template <typename Block, typename Allocator>

 inline typename dynamic_bitset<Block, Allocator>::size_type

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

 {

     return m_num_bits;

 }

 template <typename Block, typename Allocator>

 inline typename dynamic_bitset<Block, Allocator>::size_type

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

 {

     return m_bits.size();

 }

 template <typename Block, typename Allocator>

 inline typename dynamic_bitset<Block, Allocator>::size_type

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

 {

     // Semantics of vector<>::max_size() aren't very clear

     // (see lib issue 197) and many library implementations

     // simply return dummy values, _unrelated_ to the underlying

     // allocator.

     //

     // Given these problems, I was tempted to not provide this

     // function at all but the user could need it if he provides

     // his own allocator.

     //

     const size_type m = detail::vector_max_size_workaround(m_bits);

     return m <= (size_type(-1)/bits_per_block) ?

         m * bits_per_block :

         size_type(-1);

 }

 template <typename Block, typename Allocator>

 inline bool dynamic_bitset<Block, Allocator>::empty() const

 {

   return size() == 0;

 }

 #if 0 // gps

 template <typename Block, typename Allocator>

 inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)

 {

     assert(n <= max_size()); // PRE - G.P.S.

     m_bits.reserve(calc_num_blocks(n));

 }

 template <typename Block, typename Allocator>

 typename dynamic_bitset<Block, Allocator>::size_type

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

 {

     // capacity is m_bits.capacity() * bits_per_block

     // unless that one overflows

     const size_type m = static_cast<size_type>(-1);

     const size_type q = m / bits_per_block;

     const size_type c = m_bits.capacity();

     return c <= q ?

         c * bits_per_block :

         m;

 }

 #endif

 template <typename Block, typename Allocator>

 bool dynamic_bitset<Block, Allocator>::

 is_subset_of(const dynamic_bitset<Block, Allocator>& a) const

 {

     assert(size() == a.size());

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

         if (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(size() == a.size());

     bool proper = false;

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

         Block bt = m_bits[i], ba = a.m_bits[i];

         if (ba & ~bt)

             proper = true;

         if (bt & ~ba)

             return false;

     }

     return proper;

 }

 template <typename Block, typename Allocator>

 bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const

 {

     size_type common_blocks = num_blocks() < b.num_blocks()

                               ? num_blocks() : b.num_blocks();

     for(size_type i = 0; i < common_blocks; ++i) {

         if(m_bits[i] & b.m_bits[i])

             return true;

     }

     return false;

 }

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

 // lookup

 // look for the first bit "on", starting

 // from the block with index first_block

 //

 template <typename Block, typename Allocator>

 typename dynamic_bitset<Block, Allocator>::size_type

 dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const

 {

     size_type i = first_block;

     // skip null blocks

     while (i < num_blocks() && m_bits[i] == 0)

         ++i;

     if (i >= num_blocks())

         return npos; // not found

     return i * bits_per_block + boost::lowest_bit(m_bits[i]);

 }

 template <typename Block, typename Allocator>

 typename dynamic_bitset<Block, Allocator>::size_type

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

 {

     return m_do_find_from(0);

 }

 template <typename Block, typename Allocator>

 typename dynamic_bitset<Block, Allocator>::size_type

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

 {

     const size_type sz = size();

     if (pos >= (sz-1) || sz == 0)

         return npos;

     ++pos;

     const size_type blk = block_index(pos);

     const block_width_type ind = bit_index(pos);

     // mask out bits before pos

     const Block fore = m_bits[blk] & ( ~Block(0) << ind );

     return fore?

         blk * bits_per_block + lowest_bit(fore)

         :

         m_do_find_from(blk + 1);

 }

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

 // comparison

 template <typename Block, typename Allocator>

 bool operator==(const dynamic_bitset<Block, Allocator>& a,

                 const dynamic_bitset<Block, Allocator>& b)

 {

     return (a.m_num_bits == b.m_num_bits)

            && (a.m_bits == b.m_bits); // [gps]

 }

 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 comparisons in reverse.

     // Compare a block at a time

     for (size_type i = a.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)

 {

     return b < a;

 }

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

 std::ostream&

 operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)

 {

     // NOTE: since this is aimed at "classic" iostreams, exception

     // masks on the stream are not supported. The library that

     // ships with gcc 2.95 has an exceptions() member function but

     // nothing is actually implemented; not even the class ios::failure.

     using namespace std;

     const ios::iostate ok = ios::goodbit;

     ios::iostate err = ok;

     if (os.opfx()) { // gps

         //try

         typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;

         const bitsetsize_type sz = b.size();

         std::streambuf * buf = os.rdbuf();

         size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)

             || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; //- gps

         const char fill_char = os.fill();

         const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;

         // if needed fill at left; pad is decresed along the way

         if (adjustfield != ios::left) {

             for (; 0 < npad; --npad)

                 if (fill_char != buf->sputc(fill_char)) {

                     err |= ios::failbit;   // gps

                     break;

                 }

         }

         if (err == ok) {

             // output the bitset

             for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.

                 const char dig = b.test(i-1)? '1' : '0';

                 if (EOF == buf->sputc(dig)) { // ok?? gps

                     err |= ios::failbit;

                     break;

                 }

             }

         }

         if (err == ok) {

             // if needed fill at right

             for (; 0 < npad; --npad) {

                 if (fill_char != buf->sputc(fill_char)) {

                     err |= ios::failbit;

                     break;

                 }

             }

         }

         os.osfx();

         os.width(0);

     } // if opfx

     if(err != ok)

         os.setstate(err); // assume this does NOT throw - gps

     return os;

 }

 #else

 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)

 {

     using namespace std;

     const ios_base::iostate ok = ios_base::goodbit;

     ios_base::iostate err = ok;

     typename basic_ostream<Ch, Tr>::sentry cerberos(os);

     if (cerberos) {

         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());

         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');

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

         try {

             typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;

             typedef basic_streambuf<Ch, Tr> buffer_type; // G.P.S.

             buffer_type * buf = os.rdbuf();

             size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)

                 || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); //- G.P.S.

             const Ch fill_char = os.fill();

             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;

             // if needed fill at left; pad is decresed along the way

             if (adjustfield != ios_base::left) {

                 for (; 0 < npad; --npad)

                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {

                           err |= ios_base::failbit;   // G.P.S.

                           break;

                     }

             }

             if (err == ok) {

                 // output the bitset

                 for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.

                     typename buffer_type::int_type

                         ret = buf->sputc(b.test(i-1)? one : zero);

                     if (Tr::eq_int_type(Tr::eof(), ret)) {

                         err |= ios_base::failbit;

                         break;

                     }

                 }

             }

             if (err == ok) {

                 // if needed fill at right

                 for (; 0 < npad; --npad) {

                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {

                         err |= ios_base::failbit;

                         break;

                     }

                 }

             }

             os.width(0);

         } catch (...) { // see std 27.6.1.1/4

             bool rethrow = false;

             try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }

             if (rethrow)

                 throw;

         }

     }

     if(err != ok)

         os.setstate(err); // may throw exception

     return os;

 }

 #endif

 #ifdef BOOST_OLD_IOSTREAMS

     // gps - A sentry-like class that calls isfx in its

     // destructor. Necessary because bit_appender::do_append may throw.

     class pseudo_sentry {

         std::istream & m_r;

         const bool m_ok;

     public:

         explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }

         ~pseudo_sentry() { m_r.isfx(); }

         operator bool() const { return m_ok; }

     };

 template <typename Block, typename Alloc>

 std::istream&

 operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)

 {

 // Extractor for classic IO streams (libstdc++ < 3.0)

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

 //  It's assumed that the stream buffer functions, and

 //  the stream's setstate() _cannot_ throw.

     typedef dynamic_bitset<Block, Alloc> bitset_type;

     typedef typename bitset_type::size_type size_type;

     std::ios::iostate err = std::ios::goodbit; // gps

     pseudo_sentry cerberos(is); // skips whitespaces

     if(cerberos) {

         b.clear();

         const std::streamsize w = is.width();

         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps

                                                          ? w : b.max_size();

         typename bitset_type::bit_appender appender(b);

         std::streambuf * buf = is.rdbuf();

         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {

             if (c == EOF) {

                 err |= std::ios::eofbit; // G.P.S.

                 break;

             }

             else if (char(c) != '0' && char(c) != '1')

                 break; // non digit character

             else {

                 try {

                     //throw std::bad_alloc(); // gps

                     appender.do_append(char(c) == '1');

                 }

                 catch(...) {

                     is.setstate(std::ios::failbit); // assume this can't throw

                     throw;

                 }

             }

         } // for

     }

     is.width(0); // gps

     if (b.size() == 0)

         err |= std::ios::failbit;

     if (err != std::ios::goodbit) // gps

         is.setstate (err); // may throw

     return is;

 }

 #else // BOOST_OLD_IOSTREAMS

 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)

 {

     using namespace std;

     typedef dynamic_bitset<Block, Alloc> bitset_type;

     typedef typename bitset_type::size_type size_type;

     const streamsize w = is.width();

     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? // gps

                                          w : b.max_size();

     ios_base::iostate err = ios_base::goodbit; // gps

     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces

     if(cerberos) {

         // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]

         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());

         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');

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

         b.clear();

         try {

             typename bitset_type::bit_appender appender(b);

             basic_streambuf <Ch, Tr> * buf = is.rdbuf();

             typename Tr::int_type c = buf->sgetc(); // G.P.S.

             for( ; appender.get_count() < limit; c = buf->snextc() ) {

                 if (Tr::eq_int_type(Tr::eof(), c)) {

                     err |= ios_base::eofbit; // G.P.S.

                     break;

                 }

                 else {

                     const Ch to_c = Tr::to_char_type(c);

                     const bool is_one = Tr::eq(to_c, one);

                     if (!is_one && !Tr::eq(to_c, zero))

                         break; // non digit character

                     appender.do_append(is_one);

                 }

             } // for

         }

         catch (...) {

             // catches from stream buf, or from vector:

             //

             // bits_stored bits have been extracted and stored, and

             // either no further character is extractable or we can't

             // append to the underlying vector (out of memory) gps

             bool rethrow = false;   // see std 27.6.1.1/4

             try { is.setstate(ios_base::badbit); }

             catch(...) { rethrow = true; }

             if (rethrow)

                 throw;

         }

     }

     is.width(0); // gps

     if (b.size() == 0 /*|| !cerberos*/)

         err |= ios_base::failbit;

     if (err != ios_base::goodbit) // gps

         is.setstate (err); // may throw

     return is;

 }

 #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;

 }

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

 // namespace scope swap

 template<typename Block, typename Allocator>

 inline void

 swap(dynamic_bitset<Block, Allocator>& left,

      dynamic_bitset<Block, Allocator>& right) // no throw

 {

     left.swap(right); // gps

 }

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

 // private (on conforming compilers) member functions

 template <typename Block, typename Allocator>

 inline typename dynamic_bitset<Block, Allocator>::size_type

 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)

 {

     return num_bits / bits_per_block

            + static_cast<int>( num_bits % bits_per_block != 0 );

 }

 // gives a reference to the highest block

 //

 template <typename Block, typename Allocator>

 inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()

 {

     return const_cast<Block &>

            (static_cast<const dynamic_bitset *>(this)->m_highest_block());

 }

 // gives a const-reference to the highest block

 //

 template <typename Block, typename Allocator>

 inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const

 {

     assert(size() > 0 && num_blocks() > 0);

     return m_bits.back();

 }

 // 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 (num_blocks() == calc_num_blocks(m_num_bits));

     // if != 0 this is the number of bits used in the last block

     const block_width_type extra_bits = count_extra_bits();

     if (extra_bits != 0)

         m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);

 }

 // check class invariants

 template <typename Block, typename Allocator>

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

 {

     const block_width_type extra_bits = count_extra_bits();

     if (extra_bits > 0) {

         block_type const mask = (~static_cast<Block>(0) << extra_bits);

         if ((m_highest_block() & mask) != 0)

             return false;

     }

     if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))

         return false;

     return true;

 }

 } // namespace boost

 #undef BOOST_BITSET_CHAR

 #endif // include guard