williamr@2: // --------------------------------------------------
williamr@2: //
williamr@2: // (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.
williamr@2: // (C) Copyright Gennaro Prota                 2003 - 2004.
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0.
williamr@2: //    (See accompanying file LICENSE_1_0.txt or copy at
williamr@2: //          http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //
williamr@2: // -----------------------------------------------------------
williamr@2: 
williamr@2: //  See http://www.boost.org/libs/dynamic_bitset for documentation.
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2: #ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
williamr@2: #define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
williamr@2: 
williamr@2: #include <cassert>
williamr@2: #include <string>
williamr@2: #include <stdexcept>           // for std::overflow_error
williamr@2: #include <algorithm>           // for std::swap, std::min, std::copy, std::fill
williamr@2: #include <vector>
williamr@2: #include <climits>             // for CHAR_BIT
williamr@2: 
williamr@2: #include "boost/dynamic_bitset/config.hpp"
williamr@2: 
williamr@2: #ifndef BOOST_NO_STD_LOCALE
williamr@2: # include <locale> // G.P.S
williamr@2: #endif
williamr@2: 
williamr@2: #if defined(BOOST_OLD_IOSTREAMS)
williamr@2: #  include <iostream.h>
williamr@2: #  include <ctype.h> // for isspace
williamr@2: #else
williamr@2: #  include <istream>
williamr@2: #  include <ostream>
williamr@2: #endif
williamr@2: 
williamr@2: #include "boost/dynamic_bitset_fwd.hpp"
williamr@2: #include "boost/detail/dynamic_bitset.hpp"
williamr@2: #include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
williamr@2: #include "boost/static_assert.hpp"
williamr@2: #include "boost/limits.hpp"
williamr@2: #include "boost/pending/lowest_bit.hpp" // used by find_first/next
williamr@2: 
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2: template
williamr@2: 
williamr@2: #if defined(BOOST_MSVC) && BOOST_WORKAROUND(BOOST_MSVC, <= 1300)  // 1300 == VC++ 7.0
williamr@2:    // VC++ (up to 7.0) wants the default arguments again
williamr@2:    <typename Block = unsigned long, typename Allocator = std::allocator<Block> >
williamr@2: # else
williamr@2:    <typename Block, typename Allocator>
williamr@2: # endif
williamr@2: 
williamr@2: class dynamic_bitset
williamr@2: {
williamr@2:   // Portability note: member function templates are defined inside
williamr@2:   // this class definition to avoid problems with VC++. Similarly,
williamr@2:   // with the member functions of nested classes.
williamr@2: 
williamr@2:   BOOST_STATIC_ASSERT(detail::dynamic_bitset_allowed_block_type<Block>::value);
williamr@2: 
williamr@2: public:
williamr@2:     typedef Block block_type;
williamr@2:     typedef Allocator allocator_type;
williamr@2:     typedef std::size_t size_type;
williamr@2:     typedef int block_width_type; // gps
williamr@2: 
williamr@2:     BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
williamr@2:     BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
williamr@2: 
williamr@2: 
williamr@2: public:
williamr@2: 
williamr@2:     // A proxy class to simulate lvalues of bit type.
williamr@2:     // Shouldn't it be private? [gps]
williamr@2:     //
williamr@2:     class reference
williamr@2:     {
williamr@2:         friend class dynamic_bitset<Block, Allocator>;
williamr@2: 
williamr@2: 
williamr@2:         // the one and only non-copy ctor
williamr@2:         reference(block_type & b, int pos)
williamr@2:             :m_block(b), m_mask(block_type(1) << pos)
williamr@2:         {}
williamr@2: 
williamr@2:         void operator&(); // left undefined
williamr@2: 
williamr@2:     public:
williamr@2: 
williamr@2:         // copy constructor: compiler generated
williamr@2: 
williamr@2:         operator bool() const { return (m_block & m_mask) != 0; }
williamr@2:         bool operator~() const { return (m_block & m_mask) == 0; }
williamr@2: 
williamr@2:         reference& flip() { do_flip(); return *this; }
williamr@2: 
williamr@2:         reference& operator=(bool x)               { do_assign(x);   return *this; } // for b[i] = x
williamr@2:         reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
williamr@2: 
williamr@2:         reference& operator|=(bool x) { if  (x) do_set();   return *this; }
williamr@2:         reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
williamr@2:         reference& operator^=(bool x) { if  (x) do_flip();  return *this; }
williamr@2:         reference& operator-=(bool x) { if  (x) do_reset(); return *this; }
williamr@2: 
williamr@2:      private:
williamr@2:         block_type & m_block;
williamr@2:         const block_type m_mask;
williamr@2: 
williamr@2:         void do_set() { m_block |= m_mask; }
williamr@2:         void do_reset() { m_block &= ~m_mask; }
williamr@2:         void do_flip() { m_block ^= m_mask; }
williamr@2:         void do_assign(bool x) { x? do_set() : do_reset(); }
williamr@2:     };
williamr@2: 
williamr@2:     typedef bool const_reference;
williamr@2: 
williamr@2:     // constructors, etc.
williamr@2:     explicit
williamr@2:     dynamic_bitset(const Allocator& alloc = Allocator());
williamr@2: 
williamr@2:     explicit
williamr@2:     dynamic_bitset(size_type num_bits, unsigned long value = 0,
williamr@2:                const Allocator& alloc = Allocator());
williamr@2: 
williamr@2: 
williamr@2:     // The presence of this constructor is a concession to ease of
williamr@2:     // use, especially for the novice user. A conversion from string
williamr@2:     // is, in most cases, formatting, and should be done by the standard
williamr@2:     // formatting convention: operator>>.
williamr@2:     //
williamr@2:     // NOTE:
williamr@2:     // Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
williamr@2:     // g++ 3.2 requires them and probably the standard will - see core issue 325
williamr@2:     // NOTE 2: 
williamr@2:     // split into two constructors because of bugs in MSVC 6.0sp5 with STLport
williamr@2: 
williamr@2:     template <typename CharT, typename Traits, typename Alloc>
williamr@2:     dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
williamr@2:         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
williamr@2:         typename std::basic_string<CharT, Traits, Alloc>::size_type n,
williamr@2:         size_type num_bits = npos,
williamr@2:         const Allocator& alloc = Allocator())
williamr@2: 
williamr@2:     :m_bits(alloc),
williamr@2:      m_num_bits(0)
williamr@2:     {
williamr@2:       init_from_string(s, pos, n, num_bits, alloc);
williamr@2:     }
williamr@2: 
williamr@2:     template <typename CharT, typename Traits, typename Alloc>
williamr@2:     explicit
williamr@2:     dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
williamr@2:       typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
williamr@2: 
williamr@2:     :m_bits(Allocator()),
williamr@2:      m_num_bits(0)
williamr@2:     {
williamr@2:       init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
williamr@2:                        npos, Allocator());
williamr@2:     }
williamr@2: 
williamr@2:     // The first bit in *first is the least significant bit, and the
williamr@2:     // last bit in the block just before *last is the most significant bit.
williamr@2:     template <typename BlockInputIterator>
williamr@2:     dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
williamr@2:                    const Allocator& alloc = Allocator())
williamr@2: 
williamr@2:     :m_bits(first, last, alloc),
williamr@2:      m_num_bits(m_bits.size() * bits_per_block)
williamr@2:     {}
williamr@2: 
williamr@2: 
williamr@2:     // copy constructor
williamr@2:     dynamic_bitset(const dynamic_bitset& b);
williamr@2: 
williamr@2:     ~dynamic_bitset();
williamr@2: 
williamr@2:     void swap(dynamic_bitset& b);
williamr@2:     dynamic_bitset& operator=(const dynamic_bitset& b);
williamr@2: 
williamr@2:     allocator_type get_allocator() const;
williamr@2: 
williamr@2:     // size changing operations
williamr@2:     void resize(size_type num_bits, bool value = false);
williamr@2:     void clear();
williamr@2:     void push_back(bool bit);
williamr@2:     void append(Block block);
williamr@2: 
williamr@2:     template <typename BlockInputIterator>
williamr@2:     void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
williamr@2:     {
williamr@2:         std::vector<Block, Allocator> v(first, last);
williamr@2:         m_append(v.begin(), v.end(), std::random_access_iterator_tag());
williamr@2:     }
williamr@2:     template <typename BlockInputIterator>
williamr@2:     void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
williamr@2:     {
williamr@2:         assert(first != last);
williamr@2:         block_width_type r = count_extra_bits();
williamr@2:         std::size_t d = boost::detail::distance(first, last);
williamr@2:         m_bits.reserve(num_blocks() + d);
williamr@2:         if (r == 0) {
williamr@2:             for( ; first != last; ++first)
williamr@2:                 m_bits.push_back(*first); // could use vector<>::insert()
williamr@2:         }
williamr@2:         else {
williamr@2:             m_highest_block() |= (*first << r);
williamr@2:             do {
williamr@2:                 Block b = *first >> (bits_per_block - r);
williamr@2:                 ++first;
williamr@2:                 m_bits.push_back(b | (first==last? 0 : *first << r));
williamr@2:             } while (first != last);
williamr@2:         }
williamr@2:         m_num_bits += bits_per_block * d;
williamr@2:     }
williamr@2:     template <typename BlockInputIterator>
williamr@2:     void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
williamr@2:     {
williamr@2:         if (first != last) {
williamr@2:             typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
williamr@2:             m_append(first, last, cat);
williamr@2:         }
williamr@2:     }
williamr@2: 
williamr@2: 
williamr@2:     // bitset operations
williamr@2:     dynamic_bitset& operator&=(const dynamic_bitset& b);
williamr@2:     dynamic_bitset& operator|=(const dynamic_bitset& b);
williamr@2:     dynamic_bitset& operator^=(const dynamic_bitset& b);
williamr@2:     dynamic_bitset& operator-=(const dynamic_bitset& b);
williamr@2:     dynamic_bitset& operator<<=(size_type n);
williamr@2:     dynamic_bitset& operator>>=(size_type n);
williamr@2:     dynamic_bitset operator<<(size_type n) const;
williamr@2:     dynamic_bitset operator>>(size_type n) const;
williamr@2: 
williamr@2:     // basic bit operations
williamr@2:     dynamic_bitset& set(size_type n, bool val = true);
williamr@2:     dynamic_bitset& set();
williamr@2:     dynamic_bitset& reset(size_type n);
williamr@2:     dynamic_bitset& reset();
williamr@2:     dynamic_bitset& flip(size_type n);
williamr@2:     dynamic_bitset& flip();
williamr@2:     bool test(size_type n) const;
williamr@2:     bool any() const;
williamr@2:     bool none() const;
williamr@2:     dynamic_bitset operator~() const;
williamr@2:     size_type count() const;
williamr@2: 
williamr@2:     // subscript
williamr@2:     reference operator[](size_type pos) {
williamr@2:         return reference(m_bits[block_index(pos)], bit_index(pos));
williamr@2:     }
williamr@2:     bool operator[](size_type pos) const { return test(pos); }
williamr@2: 
williamr@2:     unsigned long to_ulong() const;
williamr@2: 
williamr@2:     size_type size() const;
williamr@2:     size_type num_blocks() const;
williamr@2:     size_type max_size() const;
williamr@2:     bool empty() const;
williamr@2: #if 0 // gps
williamr@2:     void reserve(size_type n);
williamr@2:     size_type capacity() const;
williamr@2: #endif
williamr@2: 
williamr@2:     bool is_subset_of(const dynamic_bitset& a) const;
williamr@2:     bool is_proper_subset_of(const dynamic_bitset& a) const;
williamr@2:     bool intersects(const dynamic_bitset & a) const;
williamr@2: 
williamr@2:     // lookup
williamr@2:     size_type find_first() const;
williamr@2:     size_type find_next(size_type pos) const;
williamr@2: 
williamr@2: 
williamr@2: #if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
williamr@2:     // lexicographical comparison
williamr@2:     template <typename B, typename A>
williamr@2:     friend bool operator==(const dynamic_bitset<B, A>& a,
williamr@2:                            const dynamic_bitset<B, A>& b);
williamr@2: 
williamr@2:     template <typename B, typename A>
williamr@2:     friend bool operator<(const dynamic_bitset<B, A>& a,
williamr@2:                           const dynamic_bitset<B, A>& b);
williamr@2: 
williamr@2: 
williamr@2:     template <typename B, typename A, typename BlockOutputIterator>
williamr@2:     friend void to_block_range(const dynamic_bitset<B, A>& b,
williamr@2:                                BlockOutputIterator result);
williamr@2: 
williamr@2:     template <typename BlockIterator, typename B, typename A>
williamr@2:     friend void from_block_range(BlockIterator first, BlockIterator last,
williamr@2:                                  dynamic_bitset<B, A>& result);
williamr@2: 
williamr@2: 
williamr@2:     template <typename CharT, typename Traits, typename B, typename A>
williamr@2:     friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
williamr@2:                                                          dynamic_bitset<B, A>& b);
williamr@2: 
williamr@2:     template <typename B, typename A, typename stringT>
williamr@2:     friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
williamr@2: 
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: 
williamr@2: private:
williamr@2:     BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
williamr@2:     typedef std::vector<block_type, allocator_type> buffer_type;
williamr@2: 
williamr@2:     void m_zero_unused_bits();
williamr@2:     bool m_check_invariants() const;
williamr@2: 
williamr@2:     size_type m_do_find_from(size_type first_block) const;
williamr@2: 
williamr@2:     block_width_type count_extra_bits() const { return bit_index(size()); }
williamr@2:     static size_type block_index(size_type pos) { return pos / bits_per_block; }
williamr@2:     static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }
williamr@2:     static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
williamr@2: 
williamr@2:     template <typename CharT, typename Traits, typename Alloc>
williamr@2:     void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
williamr@2:         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
williamr@2:         typename std::basic_string<CharT, Traits, Alloc>::size_type n,
williamr@2:         size_type num_bits,
williamr@2:         const Allocator& alloc)
williamr@2:     {
williamr@2:         assert(pos <= s.size());
williamr@2: 
williamr@2:         typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
williamr@2:         typedef typename StrT::traits_type Tr;
williamr@2: 
williamr@2:         const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); // gps
williamr@2:         const size_type sz = ( num_bits != npos? num_bits : rlen);
williamr@2:         m_bits.resize(calc_num_blocks(sz));
williamr@2:         m_num_bits = sz;
williamr@2: 
williamr@2: 
williamr@2:         BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
williamr@2:         const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2: 
williamr@2:         const size_type m = num_bits < rlen ? num_bits : rlen; // [gps]
williamr@2:         typename StrT::size_type i = 0;
williamr@2:         for( ; i < m; ++i) {
williamr@2: 
williamr@2:             const CharT c = s[(pos + m - 1) - i];
williamr@2: 
williamr@2:             assert( Tr::eq(c, one)
williamr@2:                     || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
williamr@2: 
williamr@2:             if (Tr::eq(c, one))
williamr@2:                 set(i);
williamr@2: 
williamr@2:         }
williamr@2: 
williamr@2:     }
williamr@2: 
williamr@2: BOOST_DYNAMIC_BITSET_PRIVATE:
williamr@2: 
williamr@2:     bool m_unchecked_test(size_type pos) const;
williamr@2:     static size_type calc_num_blocks(size_type num_bits);
williamr@2: 
williamr@2:     Block&        m_highest_block();
williamr@2:     const Block&  m_highest_block() const;
williamr@2: 
williamr@2:     buffer_type m_bits; // [gps] to be renamed
williamr@2:     size_type   m_num_bits;
williamr@2: 
williamr@2: 
williamr@2:     class bit_appender;
williamr@2:     friend class bit_appender;
williamr@2:     class bit_appender {
williamr@2:       // helper for stream >>
williamr@2:       // Supplies to the lack of an efficient append at the less
williamr@2:       // significant end: bits are actually appended "at left" but
williamr@2:       // rearranged in the destructor. Everything works just as if
williamr@2:       // dynamic_bitset<> had an append_at_right() function (which
williamr@2:       // threw, in case, the same exceptions as push_back) except
williamr@2:       // that the function is actually called bit_appender::do_append().
williamr@2:       //
williamr@2:       dynamic_bitset & bs;
williamr@2:       size_type n;
williamr@2:       Block mask;
williamr@2:       Block * current;
williamr@2:     public:
williamr@2:         bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
williamr@2:         ~bit_appender() {
williamr@2:             // reverse the order of blocks, shift
williamr@2:             // if needed, and then resize
williamr@2:             //
williamr@2:             std::reverse(bs.m_bits.begin(), bs.m_bits.end());
williamr@2:             const block_width_type offs = bit_index(n);
williamr@2:             if (offs)
williamr@2:                 bs >>= (bits_per_block - offs);
williamr@2:             bs.resize(n); // doesn't enlarge, so can't throw
williamr@2:             assert(bs.m_check_invariants());
williamr@2:         }
williamr@2:         inline void do_append(bool value) {
williamr@2: 
williamr@2:             if (mask == 0) {
williamr@2:                 bs.append(Block(0));
williamr@2:                 current = &bs.m_highest_block();
williamr@2:                 mask = Block(1) << (bits_per_block - 1);
williamr@2:             }
williamr@2: 
williamr@2:             if(value)
williamr@2:                 *current |= mask;
williamr@2: 
williamr@2:             mask /= 2;
williamr@2:             ++n;
williamr@2:         }
williamr@2:         size_type get_count() const { return n; }
williamr@2:     };
williamr@2: 
williamr@2: };
williamr@2: 
williamr@2: #if BOOST_WORKAROUND( __IBMCPP__, <=600 )
williamr@2: 
williamr@2: // Workaround for IBM's AIX platform.
williamr@2: // See http://comments.gmane.org/gmane.comp.lib.boost.user/15331
williamr@2: 
williamr@2: template<typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>::block_width_type const
williamr@2: dynamic_bitset<Block, Allocator>::bits_per_block;
williamr@2: 
williamr@2: template<typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>::block_width_type const
williamr@2: dynamic_bitset<Block, Allocator>::ulong_width;
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: // Global Functions:
williamr@2: 
williamr@2: // comparison
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool operator!=(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                 const dynamic_bitset<Block, Allocator>& b);
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool operator<=(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                 const dynamic_bitset<Block, Allocator>& b);
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool operator>(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                const dynamic_bitset<Block, Allocator>& b);
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool operator>=(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                 const dynamic_bitset<Block, Allocator>& b);
williamr@2: 
williamr@2: // stream operators
williamr@2: #ifdef BOOST_OLD_IOSTREAMS
williamr@2: template <typename Block, typename Allocator>
williamr@2: std::ostream& operator<<(std::ostream& os,
williamr@2:                          const dynamic_bitset<Block, Allocator>& b);
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
williamr@2: #else
williamr@2: // NOTE: Digital Mars wants the same template parameter names
williamr@2: //       here and in the definition! [last tested: 8.48.10]
williamr@2: //
williamr@2: template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2: std::basic_ostream<Ch, Tr>&
williamr@2: operator<<(std::basic_ostream<Ch, Tr>& os,
williamr@2:            const dynamic_bitset<Block, Alloc>& b);
williamr@2: 
williamr@2: template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2: std::basic_istream<Ch, Tr>&
williamr@2: operator>>(std::basic_istream<Ch, Tr>& is,
williamr@2:            dynamic_bitset<Block, Alloc>& b);
williamr@2: #endif
williamr@2: 
williamr@2: // bitset operations
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator&(const dynamic_bitset<Block, Allocator>& b1,
williamr@2:           const dynamic_bitset<Block, Allocator>& b2);
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator|(const dynamic_bitset<Block, Allocator>& b1,
williamr@2:           const dynamic_bitset<Block, Allocator>& b2);
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator^(const dynamic_bitset<Block, Allocator>& b1,
williamr@2:           const dynamic_bitset<Block, Allocator>& b2);
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator-(const dynamic_bitset<Block, Allocator>& b1,
williamr@2:           const dynamic_bitset<Block, Allocator>& b2);
williamr@2: 
williamr@2: // namespace scope swap
williamr@2: template<typename Block, typename Allocator>
williamr@2: void swap(dynamic_bitset<Block, Allocator>& b1,
williamr@2:           dynamic_bitset<Block, Allocator>& b2);
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator, typename stringT>
williamr@2: void
williamr@2: to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps
williamr@2: 
williamr@2: template <typename Block, typename Allocator, typename BlockOutputIterator>
williamr@2: void
williamr@2: to_block_range(const dynamic_bitset<Block, Allocator>& b,
williamr@2:                BlockOutputIterator result);
williamr@2: 
williamr@2: 
williamr@2: // gps - check docs with Jeremy
williamr@2: //
williamr@2: template <typename BlockIterator, typename B, typename A>
williamr@2: inline void
williamr@2: from_block_range(BlockIterator first, BlockIterator last,
williamr@2:                  dynamic_bitset<B, A>& result)
williamr@2: {
williamr@2:     // PRE: distance(first, last) <= numblocks()
williamr@2:     std::copy (first, last, result.m_bits.begin()); //[gps]
williamr@2: }
williamr@2: 
williamr@2: //=============================================================================
williamr@2: // dynamic_bitset implementation
williamr@2: 
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // constructors, etc.
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
williamr@2:   : m_bits(alloc), m_num_bits(0)
williamr@2: {
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>::
williamr@2: dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
williamr@2:   : m_bits(calc_num_blocks(num_bits), Block(0), alloc),
williamr@2:     m_num_bits(num_bits)
williamr@2: {
williamr@2: 
williamr@2:   if (num_bits == 0)
williamr@2:       return;
williamr@2: 
williamr@2:   typedef unsigned long num_type;
williamr@2: 
williamr@2:   // cut off all bits in value that have pos >= num_bits, if any
williamr@2:   if (num_bits < static_cast<size_type>(ulong_width)) {
williamr@2:       const num_type mask = (num_type(1) << num_bits) - 1;
williamr@2:       value &= mask;
williamr@2:   }
williamr@2: 
williamr@2:   if (bits_per_block >= ulong_width) {
williamr@2:       m_bits[0] = static_cast<block_type>(value);
williamr@2:   }
williamr@2:   else {
williamr@2:       for(size_type i = 0; value != 0; ++i) {
williamr@2: 
williamr@2:           m_bits[i] = static_cast<block_type>(value);
williamr@2:           value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);
williamr@2:       }
williamr@2:   }
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: // copy constructor
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline dynamic_bitset<Block, Allocator>::
williamr@2: dynamic_bitset(const dynamic_bitset& b)
williamr@2:   : m_bits(b.m_bits), m_num_bits(b.m_num_bits)  // [gps]
williamr@2: {
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline dynamic_bitset<Block, Allocator>::
williamr@2: ~dynamic_bitset()
williamr@2: {
williamr@2:     assert(m_check_invariants());
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline void dynamic_bitset<Block, Allocator>::
williamr@2: swap(dynamic_bitset<Block, Allocator>& b) // no throw
williamr@2: {
williamr@2:     std::swap(m_bits, b.m_bits);
williamr@2:     std::swap(m_num_bits, b.m_num_bits);
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
williamr@2: operator=(const dynamic_bitset<Block, Allocator>& b)
williamr@2: {
williamr@2: #if 0 // gps
williamr@2:     dynamic_bitset<Block, Allocator> tmp(b);
williamr@2:     this->swap(tmp);
williamr@2:     return *this;
williamr@2: #else
williamr@2:     m_bits = b.m_bits;
williamr@2:     m_num_bits = b.m_num_bits;
williamr@2:     return *this;
williamr@2: #endif
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline typename dynamic_bitset<Block, Allocator>::allocator_type
williamr@2: dynamic_bitset<Block, Allocator>::get_allocator() const
williamr@2: {
williamr@2:     return m_bits.get_allocator();
williamr@2: }
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // size changing operations
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: void dynamic_bitset<Block, Allocator>::
williamr@2: resize(size_type num_bits, bool value) // strong guarantee
williamr@2: {
williamr@2: 
williamr@2:   const size_type old_num_blocks = num_blocks();
williamr@2:   const size_type required_blocks = calc_num_blocks(num_bits);
williamr@2: 
williamr@2:   const block_type v = value? ~Block(0) : Block(0);
williamr@2: 
williamr@2:   if (required_blocks != old_num_blocks) {
williamr@2:     m_bits.resize(required_blocks, v); // s.g. (copy) [gps]
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   // At this point:
williamr@2:   //
williamr@2:   //  - if the buffer was shrunk, there's nothing to do, except
williamr@2:   //    a call to m_zero_unused_bits()
williamr@2:   //
williamr@2:   //  - if it it is enlarged, all the (used) bits in the new blocks have
williamr@2:   //    the correct value, but we should also take care of the bits,
williamr@2:   //    if any, that were 'unused bits' before enlarging: if value == true,
williamr@2:   //    they must be set.
williamr@2: 
williamr@2:   if (value && (num_bits > m_num_bits)) {
williamr@2: 
williamr@2:     const size_type extra_bits = count_extra_bits(); // gps
williamr@2:     if (extra_bits) {
williamr@2:         assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
williamr@2: 
williamr@2:         // Set them.
williamr@2:         m_bits[old_num_blocks - 1] |= (v << extra_bits); // gps
williamr@2:     }
williamr@2: 
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2:   m_num_bits = num_bits;
williamr@2:   m_zero_unused_bits();
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: void dynamic_bitset<Block, Allocator>::
williamr@2: clear() // no throw
williamr@2: {
williamr@2:   m_bits.clear();
williamr@2:   m_num_bits = 0;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: void dynamic_bitset<Block, Allocator>::
williamr@2: push_back(bool bit)
williamr@2: {
williamr@2:   resize(size() + 1);
williamr@2:   set(size() - 1, bit);
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: void dynamic_bitset<Block, Allocator>::
williamr@2: append(Block value) // strong guarantee
williamr@2: {
williamr@2:     // G.P.S. to be reviewed...
williamr@2: 
williamr@2:     const block_width_type r = count_extra_bits();
williamr@2: 
williamr@2:     if (r == 0) {
williamr@2:         // the buffer is empty, or all blocks are filled
williamr@2:         m_bits.push_back(value);
williamr@2:     }
williamr@2:     else {
williamr@2:         m_bits.push_back(value >> (bits_per_block - r));
williamr@2:         m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
williamr@2:     }
williamr@2: 
williamr@2:     m_num_bits += bits_per_block;
williamr@2:     assert(m_check_invariants());
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // bitset operations
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
williamr@2: {
williamr@2:     assert(size() == rhs.size());
williamr@2:     for (size_type i = 0; i < num_blocks(); ++i)
williamr@2:         m_bits[i] &= rhs.m_bits[i];
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
williamr@2: {
williamr@2:     assert(size() == rhs.size());
williamr@2:     for (size_type i = 0; i < num_blocks(); ++i)
williamr@2:         m_bits[i] |= rhs.m_bits[i];
williamr@2:     //m_zero_unused_bits();
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
williamr@2: {
williamr@2:     assert(size() == rhs.size());
williamr@2:     for (size_type i = 0; i < this->num_blocks(); ++i)
williamr@2:         m_bits[i] ^= rhs.m_bits[i];
williamr@2:     //m_zero_unused_bits();
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
williamr@2: {
williamr@2:     assert(size() == rhs.size());
williamr@2:     for (size_type i = 0; i < num_blocks(); ++i)
williamr@2:         m_bits[i] &= ~rhs.m_bits[i];
williamr@2:     //m_zero_unused_bits();
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: //
williamr@2: // NOTE:
williamr@2: //  Note that the 'if (r != 0)' is crucial to avoid undefined
williamr@2: //  behavior when the left hand operand of >> isn't promoted to a
williamr@2: //  wider type (because rs would be too large).
williamr@2: //
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
williamr@2: {
williamr@2:     if (n >= m_num_bits)
williamr@2:         return reset();
williamr@2:     //else
williamr@2:     if (n > 0) {
williamr@2: 
williamr@2:         size_type    const last = num_blocks() - 1;  // num_blocks() is >= 1
williamr@2:         size_type    const div  = n / bits_per_block; // div is <= last
williamr@2:         block_width_type const r = bit_index(n);
williamr@2:         block_type * const b    = &m_bits[0];
williamr@2: 
williamr@2:         if (r != 0) {
williamr@2: 
williamr@2:             block_width_type const rs = bits_per_block - r;
williamr@2: 
williamr@2:             for (size_type i = last-div; i>0; --i) {
williamr@2:                 b[i+div] = (b[i] << r) | (b[i-1] >> rs);
williamr@2:             }
williamr@2:             b[div] = b[0] << r;
williamr@2: 
williamr@2:         }
williamr@2:         else {
williamr@2:             for (size_type i = last-div; i>0; --i) {
williamr@2:                 b[i+div] = b[i];
williamr@2:             }
williamr@2:             b[div] = b[0];
williamr@2:         }
williamr@2: 
williamr@2: 
williamr@2:         // zero out div blocks at the less significant end
williamr@2:         std::fill_n(b, div, static_cast<block_type>(0));
williamr@2: 
williamr@2:         // zero out any 1 bit that flowed into the unused part
williamr@2:         m_zero_unused_bits(); // thanks to Lester Gong
williamr@2: 
williamr@2: 
williamr@2:     }
williamr@2: 
williamr@2:     return *this;
williamr@2: 
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: //
williamr@2: // NOTE:
williamr@2: //  see the comments to operator <<=
williamr@2: //
williamr@2: template <typename B, typename A>
williamr@2: dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
williamr@2:     if (n >= m_num_bits) {
williamr@2:         return reset();
williamr@2:     }
williamr@2:     //else
williamr@2:     if (n>0) {
williamr@2: 
williamr@2:         size_type  const last  = num_blocks() - 1; // num_blocks() is >= 1
williamr@2:         size_type  const div   = n / bits_per_block;   // div is <= last
williamr@2:         block_width_type const r     = bit_index(n);
williamr@2:         block_type * const b   = &m_bits[0];
williamr@2: 
williamr@2: 
williamr@2:         if (r != 0) {
williamr@2: 
williamr@2:             block_width_type const ls = bits_per_block - r;
williamr@2: 
williamr@2:             for (size_type i = div; i < last; ++i) {
williamr@2:                 b[i-div] = (b[i] >> r) | (b[i+1]  << ls);
williamr@2:             }
williamr@2:             // r bits go to zero
williamr@2:             b[last-div] = b[last] >> r;
williamr@2:         }
williamr@2: 
williamr@2:         else {
williamr@2:             for (size_type i = div; i <= last; ++i) {
williamr@2:                 b[i-div] = b[i];
williamr@2:             }
williamr@2:             // note the '<=': the last iteration 'absorbs'
williamr@2:             // b[last-div] = b[last] >> 0;
williamr@2:         }
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2:         // div blocks are zero filled at the most significant end
williamr@2:         std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
williamr@2:     }
williamr@2: 
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
williamr@2: {
williamr@2:     dynamic_bitset r(*this);
williamr@2:     return r <<= n;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
williamr@2: {
williamr@2:     dynamic_bitset r(*this);
williamr@2:     return r >>= n;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // basic bit operations
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
williamr@2: {
williamr@2:     // [gps]
williamr@2:     //
williamr@2:     // Below we have no set(size_type) function to call when
williamr@2:     // value == true; instead of using a helper, I think
williamr@2:     // overloading set (rather than giving it a default bool
williamr@2:     // argument) would be more elegant.
williamr@2: 
williamr@2:     assert(pos < m_num_bits);
williamr@2: 
williamr@2:     if (val)
williamr@2:         m_bits[block_index(pos)] |= bit_mask(pos);
williamr@2:     else
williamr@2:         reset(pos);
williamr@2: 
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::set()
williamr@2: {
williamr@2:   std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
williamr@2:   m_zero_unused_bits();
williamr@2:   return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::reset(size_type pos)
williamr@2: {
williamr@2:     assert(pos < m_num_bits);
williamr@2:     #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
williamr@2:     // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
williamr@2:     // use the |^ variation instead.. <grafik>
williamr@2:     m_bits[block_index(pos)] |= bit_mask(pos);
williamr@2:     m_bits[block_index(pos)] ^= bit_mask(pos);
williamr@2:     #else
williamr@2:     m_bits[block_index(pos)] &= ~bit_mask(pos);
williamr@2:     #endif
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::reset()
williamr@2: {
williamr@2:   std::fill(m_bits.begin(), m_bits.end(), Block(0));
williamr@2:   return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::flip(size_type pos)
williamr@2: {
williamr@2:     assert(pos < m_num_bits);
williamr@2:     m_bits[block_index(pos)] ^= bit_mask(pos);
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>&
williamr@2: dynamic_bitset<Block, Allocator>::flip()
williamr@2: {
williamr@2:     for (size_type i = 0; i < num_blocks(); ++i)
williamr@2:         m_bits[i] = ~m_bits[i];
williamr@2:     m_zero_unused_bits();
williamr@2:     return *this;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
williamr@2: {
williamr@2:     return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
williamr@2: {
williamr@2:     assert(pos < m_num_bits);
williamr@2:     return m_unchecked_test(pos);
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool dynamic_bitset<Block, Allocator>::any() const
williamr@2: {
williamr@2:     for (size_type i = 0; i < num_blocks(); ++i)
williamr@2:         if (m_bits[i])
williamr@2:             return true;
williamr@2:     return false;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline bool dynamic_bitset<Block, Allocator>::none() const
williamr@2: {
williamr@2:     return !any();
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: dynamic_bitset<Block, Allocator>::operator~() const
williamr@2: {
williamr@2:     dynamic_bitset b(*this);
williamr@2:     b.flip();
williamr@2:     return b;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: /*
williamr@2: 
williamr@2: The following is the straightforward implementation of count(), which
williamr@2: we leave here in a comment for documentation purposes.
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::count() const
williamr@2: {
williamr@2:     size_type sum = 0;
williamr@2:     for (size_type i = 0; i != this->m_num_bits; ++i)
williamr@2:         if (test(i))
williamr@2:             ++sum;
williamr@2:     return sum;
williamr@2: }
williamr@2: 
williamr@2: The actual algorithm uses a lookup table.
williamr@2: 
williamr@2: 
williamr@2:   The basic idea of the method is to pick up X bits at a time
williamr@2:   from the internal array of blocks and consider those bits as
williamr@2:   the binary representation of a number N. Then, to use a table
williamr@2:   of 1<<X elements where table[N] is the number of '1' digits
williamr@2:   in the binary representation of N (i.e. in our X bits).
williamr@2: 
williamr@2: 
williamr@2:   In this implementation X is 8 (but can be easily changed: you
williamr@2:   just have to modify the definition of table_width and shrink/enlarge
williamr@2:   the table accordingly - it could be useful, for instance, to expand
williamr@2:   the table to 512 elements on an implementation with 9-bit bytes) and
williamr@2:   the internal array of blocks is seen, if possible, as an array of bytes.
williamr@2:   In practice the "reinterpretation" as array of bytes is possible if and
williamr@2:   only if X >= CHAR_BIT and Block has no padding bits (that would be counted
williamr@2:   together with the "real ones" if we saw the array as array of bytes).
williamr@2:   Otherwise we simply 'extract' X bits at a time from each Block.
williamr@2: 
williamr@2: */
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::count() const
williamr@2: {
williamr@2:     using namespace detail::dynamic_bitset_count_impl;
williamr@2: 
williamr@2:     const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);
williamr@2:     const bool enough_table_width = table_width >= CHAR_BIT;
williamr@2: 
williamr@2:     typedef mode_to_type< (no_padding && enough_table_width ?
williamr@2:                           access_by_bytes : access_by_blocks) > m;
williamr@2: 
williamr@2:     return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(0));
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // conversions
williamr@2: 
williamr@2: 
williamr@2: template <typename B, typename A, typename stringT>
williamr@2: void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
williamr@2:                       bool dump_all)
williamr@2: {
williamr@2:     typedef typename stringT::traits_type Tr;
williamr@2:     typedef typename stringT::value_type  Ch;
williamr@2: 
williamr@2:     BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
williamr@2:     const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
williamr@2:     const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2: 
williamr@2:     // Note that this function may access (when
williamr@2:     // dump_all == true) bits beyond position size() - 1
williamr@2: 
williamr@2:     typedef typename dynamic_bitset<B, A>::size_type size_type;
williamr@2: 
williamr@2:     const size_type len = dump_all?
williamr@2:          dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
williamr@2:          b.size();
williamr@2:     s.assign (len, zero);
williamr@2: 
williamr@2:     for (size_type i = 0; i < len; ++i) {
williamr@2:         if (b.m_unchecked_test(i))
williamr@2:             Tr::assign(s[len - 1 - i], one);
williamr@2: 
williamr@2:     }
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: // A comment similar to the one about the constructor from
williamr@2: // basic_string can be done here. Thanks to James Kanze for
williamr@2: // making me (Gennaro) realize this important separation of
williamr@2: // concerns issue, as well as many things about i18n.
williamr@2: //
williamr@2: template <typename Block, typename Allocator, typename stringT> // G.P.S.
williamr@2: inline void
williamr@2: to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
williamr@2: {
williamr@2:     to_string_helper(b, s, false);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: // Differently from to_string this function dumps out
williamr@2: // every bit of the internal representation (may be
williamr@2: // useful for debugging purposes)
williamr@2: //
williamr@2: template <typename B, typename A, typename stringT>
williamr@2: inline void
williamr@2: dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.
williamr@2: {
williamr@2:     to_string_helper(b, s, true /* =dump_all*/);
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator, typename BlockOutputIterator>
williamr@2: inline void
williamr@2: to_block_range(const dynamic_bitset<Block, Allocator>& b,
williamr@2:                BlockOutputIterator result)
williamr@2: {
williamr@2:     // note how this copies *all* bits, including the
williamr@2:     // unused ones in the last block (which are zero)
williamr@2:     std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: unsigned long dynamic_bitset<Block, Allocator>::
williamr@2: to_ulong() const
williamr@2: {
williamr@2: 
williamr@2:   if (m_num_bits == 0)
williamr@2:       return 0; // convention
williamr@2: 
williamr@2:   // Check for overflows. This may be a performance burden on very
williamr@2:   // large bitsets but is required by the specification, sorry
williamr@2:   if (find_next(ulong_width - 1) != npos)
williamr@2:     throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
williamr@2: 
williamr@2: 
williamr@2:   // Ok, from now on we can be sure there's no "on" bit beyond
williamr@2:   // the allowed positions
williamr@2: 
williamr@2:   if (bits_per_block >= ulong_width)
williamr@2:       return m_bits[0];
williamr@2: 
williamr@2: 
williamr@2:   size_type last_block = block_index((std::min)(m_num_bits-1, // gps
williamr@2:                                     (size_type)(ulong_width-1)));
williamr@2:   unsigned long result = 0;
williamr@2:   for (size_type i = 0; i <= last_block; ++i) {
williamr@2: 
williamr@2:     assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps
williamr@2: 
williamr@2:     unsigned long piece = m_bits[i];
williamr@2:     result |= (piece << (bits_per_block * i));
williamr@2:   }
williamr@2: 
williamr@2:   return result;
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::size() const
williamr@2: {
williamr@2:     return m_num_bits;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::num_blocks() const
williamr@2: {
williamr@2:     return m_bits.size();
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::max_size() const
williamr@2: {
williamr@2:     // Semantics of vector<>::max_size() aren't very clear
williamr@2:     // (see lib issue 197) and many library implementations
williamr@2:     // simply return dummy values, _unrelated_ to the underlying
williamr@2:     // allocator.
williamr@2:     //
williamr@2:     // Given these problems, I was tempted to not provide this
williamr@2:     // function at all but the user could need it if he provides
williamr@2:     // his own allocator.
williamr@2:     //
williamr@2: 
williamr@2:     const size_type m = detail::vector_max_size_workaround(m_bits);
williamr@2: 
williamr@2:     return m <= (size_type(-1)/bits_per_block) ?
williamr@2:         m * bits_per_block :
williamr@2:         size_type(-1);
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline bool dynamic_bitset<Block, Allocator>::empty() const
williamr@2: {
williamr@2:   return size() == 0;
williamr@2: }
williamr@2: 
williamr@2: #if 0 // gps
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)
williamr@2: {
williamr@2:     assert(n <= max_size()); // PRE - G.P.S.
williamr@2:     m_bits.reserve(calc_num_blocks(n));
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::capacity() const
williamr@2: {
williamr@2:     // capacity is m_bits.capacity() * bits_per_block
williamr@2:     // unless that one overflows
williamr@2:     const size_type m = static_cast<size_type>(-1);
williamr@2:     const size_type q = m / bits_per_block;
williamr@2: 
williamr@2:     const size_type c = m_bits.capacity();
williamr@2: 
williamr@2:     return c <= q ?
williamr@2:         c * bits_per_block :
williamr@2:         m;
williamr@2: }
williamr@2: #endif
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool dynamic_bitset<Block, Allocator>::
williamr@2: is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
williamr@2: {
williamr@2:     assert(size() == a.size());
williamr@2:     for (size_type i = 0; i < num_blocks(); ++i)
williamr@2:         if (m_bits[i] & ~a.m_bits[i])
williamr@2:             return false;
williamr@2:     return true;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool dynamic_bitset<Block, Allocator>::
williamr@2: is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
williamr@2: {
williamr@2:     assert(size() == a.size());
williamr@2:     bool proper = false;
williamr@2:     for (size_type i = 0; i < num_blocks(); ++i) {
williamr@2:         Block bt = m_bits[i], ba = a.m_bits[i];
williamr@2:         if (ba & ~bt)
williamr@2:             proper = true;
williamr@2:         if (bt & ~ba)
williamr@2:             return false;
williamr@2:     }
williamr@2:     return proper;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
williamr@2: {
williamr@2:     size_type common_blocks = num_blocks() < b.num_blocks()
williamr@2:                               ? num_blocks() : b.num_blocks();
williamr@2: 
williamr@2:     for(size_type i = 0; i < common_blocks; ++i) {
williamr@2:         if(m_bits[i] & b.m_bits[i])
williamr@2:             return true;
williamr@2:     }
williamr@2:     return false;
williamr@2: }
williamr@2: 
williamr@2: // --------------------------------
williamr@2: // lookup
williamr@2: 
williamr@2: 
williamr@2: // look for the first bit "on", starting
williamr@2: // from the block with index first_block
williamr@2: //
williamr@2: template <typename Block, typename Allocator>
williamr@2: typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
williamr@2: {
williamr@2:     size_type i = first_block;
williamr@2: 
williamr@2:     // skip null blocks
williamr@2:     while (i < num_blocks() && m_bits[i] == 0)
williamr@2:         ++i;
williamr@2: 
williamr@2:     if (i >= num_blocks())
williamr@2:         return npos; // not found
williamr@2: 
williamr@2:     return i * bits_per_block + boost::lowest_bit(m_bits[i]);
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::find_first() const
williamr@2: {
williamr@2:     return m_do_find_from(0);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
williamr@2: {
williamr@2: 
williamr@2:     const size_type sz = size();
williamr@2:     if (pos >= (sz-1) || sz == 0)
williamr@2:         return npos;
williamr@2: 
williamr@2:     ++pos;
williamr@2: 
williamr@2:     const size_type blk = block_index(pos);
williamr@2:     const block_width_type ind = bit_index(pos);
williamr@2: 
williamr@2:     // mask out bits before pos
williamr@2:     const Block fore = m_bits[blk] & ( ~Block(0) << ind );
williamr@2: 
williamr@2:     return fore?
williamr@2:         blk * bits_per_block + lowest_bit(fore)
williamr@2:         :
williamr@2:         m_do_find_from(blk + 1);
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // comparison
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool operator==(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                 const dynamic_bitset<Block, Allocator>& b)
williamr@2: {
williamr@2:     return (a.m_num_bits == b.m_num_bits)
williamr@2:            && (a.m_bits == b.m_bits); // [gps]
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                        const dynamic_bitset<Block, Allocator>& b)
williamr@2: {
williamr@2:     return !(a == b);
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool operator<(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                const dynamic_bitset<Block, Allocator>& b)
williamr@2: {
williamr@2:     assert(a.size() == b.size());
williamr@2:     typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
williamr@2: 
williamr@2:     if (a.size() == 0)
williamr@2:       return false;
williamr@2: 
williamr@2:     // Since we are storing the most significant bit
williamr@2:     // at pos == size() - 1, we need to do the comparisons in reverse.
williamr@2: 
williamr@2:     // Compare a block at a time
williamr@2:     for (size_type i = a.num_blocks() - 1; i > 0; --i)
williamr@2:       if (a.m_bits[i] < b.m_bits[i])
williamr@2:         return true;
williamr@2:       else if (a.m_bits[i] > b.m_bits[i])
williamr@2:         return false;
williamr@2: 
williamr@2:     if (a.m_bits[0] < b.m_bits[0])
williamr@2:       return true;
williamr@2:     else
williamr@2:       return false;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                        const dynamic_bitset<Block, Allocator>& b)
williamr@2: {
williamr@2:     return !(a > b);
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                       const dynamic_bitset<Block, Allocator>& b)
williamr@2: {
williamr@2:     return b < a;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
williamr@2:                        const dynamic_bitset<Block, Allocator>& b)
williamr@2: {
williamr@2:     return !(a < b);
williamr@2: }
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // stream operations
williamr@2: 
williamr@2: #ifdef BOOST_OLD_IOSTREAMS
williamr@2: template < typename Block, typename Alloc>
williamr@2: std::ostream&
williamr@2: operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
williamr@2: {
williamr@2:     // NOTE: since this is aimed at "classic" iostreams, exception
williamr@2:     // masks on the stream are not supported. The library that
williamr@2:     // ships with gcc 2.95 has an exceptions() member function but
williamr@2:     // nothing is actually implemented; not even the class ios::failure.
williamr@2: 
williamr@2:     using namespace std;
williamr@2: 
williamr@2:     const ios::iostate ok = ios::goodbit;
williamr@2:     ios::iostate err = ok;
williamr@2: 
williamr@2:     if (os.opfx()) { // gps
williamr@2: 
williamr@2:         //try
williamr@2:         typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
williamr@2: 
williamr@2:         const bitsetsize_type sz = b.size();
williamr@2:         std::streambuf * buf = os.rdbuf();
williamr@2:         size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
williamr@2:             || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; //- gps
williamr@2: 
williamr@2:         const char fill_char = os.fill();
williamr@2:         const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
williamr@2: 
williamr@2:         // if needed fill at left; pad is decresed along the way
williamr@2:         if (adjustfield != ios::left) {
williamr@2:             for (; 0 < npad; --npad)
williamr@2:                 if (fill_char != buf->sputc(fill_char)) {
williamr@2:                     err |= ios::failbit;   // gps
williamr@2:                     break;
williamr@2:                 }
williamr@2:         }
williamr@2: 
williamr@2:         if (err == ok) {
williamr@2:             // output the bitset
williamr@2:             for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
williamr@2:                 const char dig = b.test(i-1)? '1' : '0';
williamr@2:                 if (EOF == buf->sputc(dig)) { // ok?? gps
williamr@2:                     err |= ios::failbit;
williamr@2:                     break;
williamr@2:                 }
williamr@2:             }
williamr@2:         }
williamr@2: 
williamr@2:         if (err == ok) {
williamr@2:             // if needed fill at right
williamr@2:             for (; 0 < npad; --npad) {
williamr@2:                 if (fill_char != buf->sputc(fill_char)) {
williamr@2:                     err |= ios::failbit;
williamr@2:                     break;
williamr@2:                 }
williamr@2:             }
williamr@2:         }
williamr@2: 
williamr@2:         os.osfx();
williamr@2:         os.width(0);
williamr@2: 
williamr@2:     } // if opfx
williamr@2: 
williamr@2:     if(err != ok)
williamr@2:         os.setstate(err); // assume this does NOT throw - gps
williamr@2:     return os;
williamr@2: 
williamr@2: }
williamr@2: #else
williamr@2: 
williamr@2: template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2: std::basic_ostream<Ch, Tr>&
williamr@2: operator<<(std::basic_ostream<Ch, Tr>& os,
williamr@2:            const dynamic_bitset<Block, Alloc>& b)
williamr@2: {
williamr@2: 
williamr@2:     using namespace std;
williamr@2: 
williamr@2:     const ios_base::iostate ok = ios_base::goodbit;
williamr@2:     ios_base::iostate err = ok;
williamr@2: 
williamr@2:     typename basic_ostream<Ch, Tr>::sentry cerberos(os);
williamr@2:     if (cerberos) {
williamr@2: 
williamr@2:         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
williamr@2:         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
williamr@2:         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2: 
williamr@2:         try {
williamr@2: 
williamr@2:             typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
williamr@2:             typedef basic_streambuf<Ch, Tr> buffer_type; // G.P.S.
williamr@2: 
williamr@2:             buffer_type * buf = os.rdbuf();
williamr@2:             size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
williamr@2:                 || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); //- G.P.S.
williamr@2: 
williamr@2:             const Ch fill_char = os.fill();
williamr@2:             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
williamr@2: 
williamr@2:             // if needed fill at left; pad is decresed along the way
williamr@2:             if (adjustfield != ios_base::left) {
williamr@2:                 for (; 0 < npad; --npad)
williamr@2:                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
williamr@2:                           err |= ios_base::failbit;   // G.P.S.
williamr@2:                           break;
williamr@2:                     }
williamr@2:             }
williamr@2: 
williamr@2:             if (err == ok) {
williamr@2:                 // output the bitset
williamr@2:                 for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
williamr@2:                     typename buffer_type::int_type
williamr@2:                         ret = buf->sputc(b.test(i-1)? one : zero);
williamr@2:                     if (Tr::eq_int_type(Tr::eof(), ret)) {
williamr@2:                         err |= ios_base::failbit;
williamr@2:                         break;
williamr@2:                     }
williamr@2:                 }
williamr@2:             }
williamr@2: 
williamr@2:             if (err == ok) {
williamr@2:                 // if needed fill at right
williamr@2:                 for (; 0 < npad; --npad) {
williamr@2:                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
williamr@2:                         err |= ios_base::failbit;
williamr@2:                         break;
williamr@2:                     }
williamr@2:                 }
williamr@2:             }
williamr@2: 
williamr@2: 
williamr@2:             os.width(0);
williamr@2: 
williamr@2:         } catch (...) { // see std 27.6.1.1/4
williamr@2:             bool rethrow = false;
williamr@2:             try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
williamr@2: 
williamr@2:             if (rethrow)
williamr@2:                 throw;
williamr@2:         }
williamr@2:     }
williamr@2: 
williamr@2:     if(err != ok)
williamr@2:         os.setstate(err); // may throw exception
williamr@2:     return os;
williamr@2: 
williamr@2: }
williamr@2: #endif
williamr@2: 
williamr@2: 
williamr@2: #ifdef BOOST_OLD_IOSTREAMS
williamr@2: 
williamr@2:     // gps - A sentry-like class that calls isfx in its
williamr@2:     // destructor. Necessary because bit_appender::do_append may throw.
williamr@2:     class pseudo_sentry {
williamr@2:         std::istream & m_r;
williamr@2:         const bool m_ok;
williamr@2:     public:
williamr@2:         explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
williamr@2:         ~pseudo_sentry() { m_r.isfx(); }
williamr@2:         operator bool() const { return m_ok; }
williamr@2:     };
williamr@2: 
williamr@2: template <typename Block, typename Alloc>
williamr@2: std::istream&
williamr@2: operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
williamr@2: {
williamr@2: 
williamr@2: // Extractor for classic IO streams (libstdc++ < 3.0)
williamr@2: // ----------------------------------------------------//
williamr@2: //  It's assumed that the stream buffer functions, and
williamr@2: //  the stream's setstate() _cannot_ throw.
williamr@2: 
williamr@2: 
williamr@2:     typedef dynamic_bitset<Block, Alloc> bitset_type;
williamr@2:     typedef typename bitset_type::size_type size_type;
williamr@2: 
williamr@2:     std::ios::iostate err = std::ios::goodbit; // gps
williamr@2:     pseudo_sentry cerberos(is); // skips whitespaces
williamr@2:     if(cerberos) {
williamr@2: 
williamr@2:         b.clear();
williamr@2: 
williamr@2:         const std::streamsize w = is.width();
williamr@2:         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps
williamr@2:                                                          ? w : b.max_size();
williamr@2:         typename bitset_type::bit_appender appender(b);
williamr@2:         std::streambuf * buf = is.rdbuf();
williamr@2:         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
williamr@2: 
williamr@2:             if (c == EOF) {
williamr@2:                 err |= std::ios::eofbit; // G.P.S.
williamr@2:                 break;
williamr@2:             }
williamr@2:             else if (char(c) != '0' && char(c) != '1')
williamr@2:                 break; // non digit character
williamr@2: 
williamr@2:             else {
williamr@2:                 try {
williamr@2:                     //throw std::bad_alloc(); // gps
williamr@2:                     appender.do_append(char(c) == '1');
williamr@2:                 }
williamr@2:                 catch(...) {
williamr@2:                     is.setstate(std::ios::failbit); // assume this can't throw
williamr@2:                     throw;
williamr@2:                 }
williamr@2:             }
williamr@2: 
williamr@2:         } // for
williamr@2:     }
williamr@2: 
williamr@2:     is.width(0); // gps
williamr@2:     if (b.size() == 0)
williamr@2:         err |= std::ios::failbit;
williamr@2:     if (err != std::ios::goodbit) // gps
williamr@2:         is.setstate (err); // may throw
williamr@2: 
williamr@2:     return is;
williamr@2: }
williamr@2: 
williamr@2: #else // BOOST_OLD_IOSTREAMS
williamr@2: 
williamr@2: template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2: std::basic_istream<Ch, Tr>&
williamr@2: operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
williamr@2: {
williamr@2: 
williamr@2:     using namespace std;
williamr@2: 
williamr@2:     typedef dynamic_bitset<Block, Alloc> bitset_type;
williamr@2:     typedef typename bitset_type::size_type size_type;
williamr@2: 
williamr@2:     const streamsize w = is.width();
williamr@2:     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? // gps
williamr@2:                                          w : b.max_size();
williamr@2: 
williamr@2:     ios_base::iostate err = ios_base::goodbit; // gps
williamr@2:     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
williamr@2:     if(cerberos) {
williamr@2: 
williamr@2:         // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
williamr@2:         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
williamr@2:         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
williamr@2:         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2: 
williamr@2:         b.clear();
williamr@2:         try {
williamr@2:             typename bitset_type::bit_appender appender(b);
williamr@2:             basic_streambuf <Ch, Tr> * buf = is.rdbuf();
williamr@2:             typename Tr::int_type c = buf->sgetc(); // G.P.S.
williamr@2:             for( ; appender.get_count() < limit; c = buf->snextc() ) {
williamr@2: 
williamr@2:                 if (Tr::eq_int_type(Tr::eof(), c)) {
williamr@2:                     err |= ios_base::eofbit; // G.P.S.
williamr@2:                     break;
williamr@2:                 }
williamr@2:                 else {
williamr@2:                     const Ch to_c = Tr::to_char_type(c);
williamr@2:                     const bool is_one = Tr::eq(to_c, one);
williamr@2: 
williamr@2:                     if (!is_one && !Tr::eq(to_c, zero))
williamr@2:                         break; // non digit character
williamr@2: 
williamr@2:                     appender.do_append(is_one);
williamr@2: 
williamr@2:                 }
williamr@2: 
williamr@2:             } // for
williamr@2:         }
williamr@2:         catch (...) {
williamr@2:             // catches from stream buf, or from vector:
williamr@2:             //
williamr@2:             // bits_stored bits have been extracted and stored, and
williamr@2:             // either no further character is extractable or we can't
williamr@2:             // append to the underlying vector (out of memory) gps
williamr@2: 
williamr@2:             bool rethrow = false;   // see std 27.6.1.1/4
williamr@2:             try { is.setstate(ios_base::badbit); }
williamr@2:             catch(...) { rethrow = true; }
williamr@2: 
williamr@2:             if (rethrow)
williamr@2:                 throw;
williamr@2: 
williamr@2:         }
williamr@2:     }
williamr@2: 
williamr@2:     is.width(0); // gps
williamr@2:     if (b.size() == 0 /*|| !cerberos*/)
williamr@2:         err |= ios_base::failbit;
williamr@2:     if (err != ios_base::goodbit) // gps
williamr@2:         is.setstate (err); // may throw
williamr@2: 
williamr@2:     return is;
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // bitset operations
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator&(const dynamic_bitset<Block, Allocator>& x,
williamr@2:           const dynamic_bitset<Block, Allocator>& y)
williamr@2: {
williamr@2:     dynamic_bitset<Block, Allocator> b(x);
williamr@2:     return b &= y;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator|(const dynamic_bitset<Block, Allocator>& x,
williamr@2:           const dynamic_bitset<Block, Allocator>& y)
williamr@2: {
williamr@2:     dynamic_bitset<Block, Allocator> b(x);
williamr@2:     return b |= y;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator^(const dynamic_bitset<Block, Allocator>& x,
williamr@2:           const dynamic_bitset<Block, Allocator>& y)
williamr@2: {
williamr@2:     dynamic_bitset<Block, Allocator> b(x);
williamr@2:     return b ^= y;
williamr@2: }
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: dynamic_bitset<Block, Allocator>
williamr@2: operator-(const dynamic_bitset<Block, Allocator>& x,
williamr@2:           const dynamic_bitset<Block, Allocator>& y)
williamr@2: {
williamr@2:     dynamic_bitset<Block, Allocator> b(x);
williamr@2:     return b -= y;
williamr@2: }
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // namespace scope swap
williamr@2: 
williamr@2: template<typename Block, typename Allocator>
williamr@2: inline void
williamr@2: swap(dynamic_bitset<Block, Allocator>& left,
williamr@2:      dynamic_bitset<Block, Allocator>& right) // no throw
williamr@2: {
williamr@2:     left.swap(right); // gps
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: //-----------------------------------------------------------------------------
williamr@2: // private (on conforming compilers) member functions
williamr@2: 
williamr@2: 
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2: dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
williamr@2: {
williamr@2:     return num_bits / bits_per_block
williamr@2:            + static_cast<int>( num_bits % bits_per_block != 0 );
williamr@2: }
williamr@2: 
williamr@2: // gives a reference to the highest block
williamr@2: //
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
williamr@2: {
williamr@2:     return const_cast<Block &>
williamr@2:            (static_cast<const dynamic_bitset *>(this)->m_highest_block());
williamr@2: }
williamr@2: 
williamr@2: // gives a const-reference to the highest block
williamr@2: //
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
williamr@2: {
williamr@2:     assert(size() > 0 && num_blocks() > 0);
williamr@2:     return m_bits.back();
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: // If size() is not a multiple of bits_per_block
williamr@2: // then not all the bits in the last block are used.
williamr@2: // This function resets the unused bits (convenient
williamr@2: // for the implementation of many member functions)
williamr@2: //
williamr@2: template <typename Block, typename Allocator>
williamr@2: inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
williamr@2: {
williamr@2:     assert (num_blocks() == calc_num_blocks(m_num_bits));
williamr@2: 
williamr@2:     // if != 0 this is the number of bits used in the last block
williamr@2:     const block_width_type extra_bits = count_extra_bits();
williamr@2: 
williamr@2:     if (extra_bits != 0)
williamr@2:         m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: // check class invariants
williamr@2: template <typename Block, typename Allocator>
williamr@2: bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
williamr@2: {
williamr@2:     const block_width_type extra_bits = count_extra_bits();
williamr@2:     if (extra_bits > 0) {
williamr@2:         block_type const mask = (~static_cast<Block>(0) << extra_bits);
williamr@2:         if ((m_highest_block() & mask) != 0)
williamr@2:             return false;
williamr@2:     }
williamr@2:     if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
williamr@2:         return false;
williamr@2: 
williamr@2:     return true;
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: 
williamr@2: #undef BOOST_BITSET_CHAR
williamr@2: 
williamr@2: #endif // include guard
williamr@2: