Chris@16: // -----------------------------------------------------------
Chris@16: //
Chris@16: //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
Chris@16: //        Copyright (c) 2003-2006, 2008 Gennaro Prota
Chris@101: //             Copyright (c) 2014 Ahmed Charles
Chris@101: //
Chris@101: // Copyright (c) 2014 Glen Joseph Fernandes
Chris@101: // glenfe at live dot com
Chris@101: // Copyright (c) 2014 Riccardo Marcangelo
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // -----------------------------------------------------------
Chris@16: 
Chris@16: #ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
Chris@16: #define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
Chris@16: 
Chris@16: #include <assert.h>
Chris@16: #include <string>
Chris@16: #include <stdexcept>
Chris@16: #include <algorithm>
Chris@16: #include <vector>
Chris@16: #include <climits>      // for CHAR_BIT
Chris@16: 
Chris@16: #include "boost/dynamic_bitset/config.hpp"
Chris@16: 
Chris@16: #ifndef BOOST_NO_STD_LOCALE
Chris@16: #  include <locale>
Chris@16: #endif
Chris@16: 
Chris@16: #if defined(BOOST_OLD_IOSTREAMS)
Chris@16: #  include <iostream.h>
Chris@16: #  include <ctype.h> // for isspace
Chris@16: #else
Chris@16: #  include <istream>
Chris@16: #  include <ostream>
Chris@16: #endif
Chris@16: 
Chris@16: #include "boost/dynamic_bitset_fwd.hpp"
Chris@16: #include "boost/detail/dynamic_bitset.hpp"
Chris@16: #include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
Chris@101: #include "boost/move/move.hpp"
Chris@16: #include "boost/limits.hpp"
Chris@16: #include "boost/pending/lowest_bit.hpp"
Chris@101: #include "boost/static_assert.hpp"
Chris@101: #include "boost/utility/addressof.hpp"
Chris@101: #include "boost/detail/no_exceptions_support.hpp"
Chris@101: #include "boost/throw_exception.hpp"
Chris@16: 
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: class dynamic_bitset
Chris@16: {
Chris@101:     // Portability note: member function templates are defined inside
Chris@101:     // this class definition to avoid problems with VC++. Similarly,
Chris@101:     // with the member functions of nested classes.
Chris@101:     //
Chris@101:     // [October 2008: the note above is mostly historical; new versions
Chris@101:     // of VC++ are likely able to digest a more drinking form of the
Chris@101:     // code; but changing it now is probably not worth the risks...]
Chris@16: 
Chris@101:     BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type<Block>::value);
Chris@101:     typedef std::vector<Block, Allocator> buffer_type;
Chris@16: 
Chris@16: public:
Chris@16:     typedef Block block_type;
Chris@16:     typedef Allocator allocator_type;
Chris@16:     typedef std::size_t size_type;
Chris@101:     typedef typename buffer_type::size_type block_width_type;
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
Chris@16:     BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
Chris@16: 
Chris@16: 
Chris@16: public:
Chris@16: 
Chris@16:     // A proxy class to simulate lvalues of bit type.
Chris@16:     //
Chris@16:     class reference
Chris@16:     {
Chris@16:         friend class dynamic_bitset<Block, Allocator>;
Chris@16: 
Chris@16: 
Chris@16:         // the one and only non-copy ctor
Chris@16:         reference(block_type & b, block_type pos)
Chris@16:             :m_block(b),
Chris@16:              m_mask( (assert(pos < bits_per_block),
Chris@16:                       block_type(1) << pos )
Chris@16:                    )
Chris@16:         { }
Chris@16: 
Chris@16:         void operator&(); // left undefined
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         // copy constructor: compiler generated
Chris@16: 
Chris@16:         operator bool() const { return (m_block & m_mask) != 0; }
Chris@16:         bool operator~() const { return (m_block & m_mask) == 0; }
Chris@16: 
Chris@16:         reference& flip() { do_flip(); return *this; }
Chris@16: 
Chris@16:         reference& operator=(bool x)               { do_assign(x);   return *this; } // for b[i] = x
Chris@16:         reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
Chris@16: 
Chris@16:         reference& operator|=(bool x) { if  (x) do_set();   return *this; }
Chris@16:         reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
Chris@16:         reference& operator^=(bool x) { if  (x) do_flip();  return *this; }
Chris@16:         reference& operator-=(bool x) { if  (x) do_reset(); return *this; }
Chris@16: 
Chris@16:      private:
Chris@16:         block_type & m_block;
Chris@16:         const block_type m_mask;
Chris@16: 
Chris@16:         void do_set() { m_block |= m_mask; }
Chris@16:         void do_reset() { m_block &= ~m_mask; }
Chris@16:         void do_flip() { m_block ^= m_mask; }
Chris@16:         void do_assign(bool x) { x? do_set() : do_reset(); }
Chris@16:     };
Chris@16: 
Chris@16:     typedef bool const_reference;
Chris@16: 
Chris@16:     // constructors, etc.
Chris@16:     explicit
Chris@16:     dynamic_bitset(const Allocator& alloc = Allocator());
Chris@16: 
Chris@16:     explicit
Chris@16:     dynamic_bitset(size_type num_bits, unsigned long value = 0,
Chris@16:                const Allocator& alloc = Allocator());
Chris@16: 
Chris@16: 
Chris@16:     // WARNING: you should avoid using this constructor.
Chris@16:     //
Chris@16:     //  A conversion from string is, in most cases, formatting,
Chris@16:     //  and should be performed by using operator>>.
Chris@16:     //
Chris@16:     // NOTE:
Chris@16:     //  Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
Chris@16:     //  g++ 3.2 requires them and probably the standard will - see core issue 325
Chris@16:     // NOTE 2:
Chris@16:     //  split into two constructors because of bugs in MSVC 6.0sp5 with STLport
Chris@16: 
Chris@16:     template <typename CharT, typename Traits, typename Alloc>
Chris@16:     dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
Chris@16:         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
Chris@16:         typename std::basic_string<CharT, Traits, Alloc>::size_type n,
Chris@16:         size_type num_bits = npos,
Chris@16:         const Allocator& alloc = Allocator())
Chris@16: 
Chris@16:     :m_bits(alloc),
Chris@16:      m_num_bits(0)
Chris@16:     {
Chris@16:       init_from_string(s, pos, n, num_bits);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename CharT, typename Traits, typename Alloc>
Chris@16:     explicit
Chris@16:     dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
Chris@16:       typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
Chris@16: 
Chris@16:     :m_bits(Allocator()),
Chris@16:      m_num_bits(0)
Chris@16:     {
Chris@16:       init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
Chris@16:                        npos);
Chris@16:     }
Chris@16: 
Chris@16:     // The first bit in *first is the least significant bit, and the
Chris@16:     // last bit in the block just before *last is the most significant bit.
Chris@16:     template <typename BlockInputIterator>
Chris@16:     dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
Chris@16:                    const Allocator& alloc = Allocator())
Chris@16: 
Chris@16:     :m_bits(alloc),
Chris@16:      m_num_bits(0)
Chris@16:     {
Chris@16:         using boost::detail::dynamic_bitset_impl::value_to_type;
Chris@16:         using boost::detail::dynamic_bitset_impl::is_numeric;
Chris@16: 
Chris@16:         const value_to_type<
Chris@16:             is_numeric<BlockInputIterator>::value> selector;
Chris@16: 
Chris@16:         dispatch_init(first, last, selector);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     void dispatch_init(T num_bits, unsigned long value,
Chris@16:                        detail::dynamic_bitset_impl::value_to_type<true>)
Chris@16:     {
Chris@16:         init_from_unsigned_long(static_cast<size_type>(num_bits), value);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     void dispatch_init(T first, T last,
Chris@16:                        detail::dynamic_bitset_impl::value_to_type<false>)
Chris@16:     {
Chris@16:         init_from_block_range(first, last);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename BlockIter>
Chris@16:     void init_from_block_range(BlockIter first, BlockIter last)
Chris@16:     {
Chris@16:         assert(m_bits.size() == 0);
Chris@16:         m_bits.insert(m_bits.end(), first, last);
Chris@16:         m_num_bits = m_bits.size() * bits_per_block;
Chris@16:     }
Chris@16: 
Chris@16:     // copy constructor
Chris@16:     dynamic_bitset(const dynamic_bitset& b);
Chris@16: 
Chris@16:     ~dynamic_bitset();
Chris@16: 
Chris@16:     void swap(dynamic_bitset& b);
Chris@16:     dynamic_bitset& operator=(const dynamic_bitset& b);
Chris@16: 
Chris@101: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101:     dynamic_bitset(dynamic_bitset&& src);
Chris@101:     dynamic_bitset& operator=(dynamic_bitset&& src);
Chris@101: #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101: 
Chris@16:     allocator_type get_allocator() const;
Chris@16: 
Chris@16:     // size changing operations
Chris@16:     void resize(size_type num_bits, bool value = false);
Chris@16:     void clear();
Chris@16:     void push_back(bool bit);
Chris@101:     void pop_back();
Chris@16:     void append(Block block);
Chris@16: 
Chris@16:     template <typename BlockInputIterator>
Chris@16:     void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
Chris@16:     {
Chris@16:         std::vector<Block, Allocator> v(first, last);
Chris@16:         m_append(v.begin(), v.end(), std::random_access_iterator_tag());
Chris@16:     }
Chris@16:     template <typename BlockInputIterator>
Chris@16:     void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
Chris@16:     {
Chris@16:         assert(first != last);
Chris@16:         block_width_type r = count_extra_bits();
Chris@16:         std::size_t d = boost::detail::distance(first, last);
Chris@16:         m_bits.reserve(num_blocks() + d);
Chris@16:         if (r == 0) {
Chris@16:             for( ; first != last; ++first)
Chris@16:                 m_bits.push_back(*first); // could use vector<>::insert()
Chris@16:         }
Chris@16:         else {
Chris@16:             m_highest_block() |= (*first << r);
Chris@16:             do {
Chris@16:                 Block b = *first >> (bits_per_block - r);
Chris@16:                 ++first;
Chris@16:                 m_bits.push_back(b | (first==last? 0 : *first << r));
Chris@16:             } while (first != last);
Chris@16:         }
Chris@16:         m_num_bits += bits_per_block * d;
Chris@16:     }
Chris@16:     template <typename BlockInputIterator>
Chris@16:     void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
Chris@16:     {
Chris@16:         if (first != last) {
Chris@16:             typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
Chris@16:             m_append(first, last, cat);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     // bitset operations
Chris@16:     dynamic_bitset& operator&=(const dynamic_bitset& b);
Chris@16:     dynamic_bitset& operator|=(const dynamic_bitset& b);
Chris@16:     dynamic_bitset& operator^=(const dynamic_bitset& b);
Chris@16:     dynamic_bitset& operator-=(const dynamic_bitset& b);
Chris@16:     dynamic_bitset& operator<<=(size_type n);
Chris@16:     dynamic_bitset& operator>>=(size_type n);
Chris@16:     dynamic_bitset operator<<(size_type n) const;
Chris@16:     dynamic_bitset operator>>(size_type n) const;
Chris@16: 
Chris@16:     // basic bit operations
Chris@16:     dynamic_bitset& set(size_type n, bool val = true);
Chris@16:     dynamic_bitset& set();
Chris@16:     dynamic_bitset& reset(size_type n);
Chris@16:     dynamic_bitset& reset();
Chris@16:     dynamic_bitset& flip(size_type n);
Chris@16:     dynamic_bitset& flip();
Chris@16:     bool test(size_type n) const;
Chris@101:     bool test_set(size_type n, bool val = true);
Chris@101:     bool all() const;
Chris@16:     bool any() const;
Chris@16:     bool none() const;
Chris@16:     dynamic_bitset operator~() const;
Chris@101:     size_type count() const BOOST_NOEXCEPT;
Chris@16: 
Chris@16:     // subscript
Chris@16:     reference operator[](size_type pos) {
Chris@16:         return reference(m_bits[block_index(pos)], bit_index(pos));
Chris@16:     }
Chris@16:     bool operator[](size_type pos) const { return test(pos); }
Chris@16: 
Chris@16:     unsigned long to_ulong() const;
Chris@16: 
Chris@101:     size_type size() const BOOST_NOEXCEPT;
Chris@101:     size_type num_blocks() const BOOST_NOEXCEPT;
Chris@101:     size_type max_size() const BOOST_NOEXCEPT;
Chris@101:     bool empty() const BOOST_NOEXCEPT;
Chris@16: 
Chris@16:     bool is_subset_of(const dynamic_bitset& a) const;
Chris@16:     bool is_proper_subset_of(const dynamic_bitset& a) const;
Chris@16:     bool intersects(const dynamic_bitset & a) const;
Chris@16: 
Chris@16:     // lookup
Chris@16:     size_type find_first() const;
Chris@16:     size_type find_next(size_type pos) const;
Chris@16: 
Chris@16: 
Chris@16: #if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
Chris@16:     // lexicographical comparison
Chris@16:     template <typename B, typename A>
Chris@16:     friend bool operator==(const dynamic_bitset<B, A>& a,
Chris@16:                            const dynamic_bitset<B, A>& b);
Chris@16: 
Chris@16:     template <typename B, typename A>
Chris@16:     friend bool operator<(const dynamic_bitset<B, A>& a,
Chris@16:                           const dynamic_bitset<B, A>& b);
Chris@16: 
Chris@16: 
Chris@16:     template <typename B, typename A, typename BlockOutputIterator>
Chris@16:     friend void to_block_range(const dynamic_bitset<B, A>& b,
Chris@16:                                BlockOutputIterator result);
Chris@16: 
Chris@16:     template <typename BlockIterator, typename B, typename A>
Chris@16:     friend void from_block_range(BlockIterator first, BlockIterator last,
Chris@16:                                  dynamic_bitset<B, A>& result);
Chris@16: 
Chris@16: 
Chris@16:     template <typename CharT, typename Traits, typename B, typename A>
Chris@16:     friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
Chris@16:                                                          dynamic_bitset<B, A>& b);
Chris@16: 
Chris@16:     template <typename B, typename A, typename stringT>
Chris@16:     friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
Chris@16: 
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: private:
Chris@16:     BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
Chris@16: 
Chris@16:     void m_zero_unused_bits();
Chris@16:     bool m_check_invariants() const;
Chris@16: 
Chris@16:     size_type m_do_find_from(size_type first_block) const;
Chris@16: 
Chris@101:     block_width_type count_extra_bits() const BOOST_NOEXCEPT { return bit_index(size()); }
Chris@101:     static size_type block_index(size_type pos) BOOST_NOEXCEPT { return pos / bits_per_block; }
Chris@101:     static block_width_type bit_index(size_type pos) BOOST_NOEXCEPT { return static_cast<block_width_type>(pos % bits_per_block); }
Chris@101:     static Block bit_mask(size_type pos) BOOST_NOEXCEPT { return Block(1) << bit_index(pos); }
Chris@16: 
Chris@16:     template <typename CharT, typename Traits, typename Alloc>
Chris@16:     void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
Chris@16:         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
Chris@16:         typename std::basic_string<CharT, Traits, Alloc>::size_type n,
Chris@16:         size_type num_bits)
Chris@16:     {
Chris@16:         assert(pos <= s.size());
Chris@16: 
Chris@16:         typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
Chris@16:         typedef typename StrT::traits_type Tr;
Chris@16: 
Chris@16:         const typename StrT::size_type rlen = (std::min)(n, s.size() - pos);
Chris@16:         const size_type sz = ( num_bits != npos? num_bits : rlen);
Chris@16:         m_bits.resize(calc_num_blocks(sz));
Chris@16:         m_num_bits = sz;
Chris@16: 
Chris@16: 
Chris@16:         BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
Chris@16:         const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16: 
Chris@16:         const size_type m = num_bits < rlen ? num_bits : rlen;
Chris@16:         typename StrT::size_type i = 0;
Chris@16:         for( ; i < m; ++i) {
Chris@16: 
Chris@16:             const CharT c = s[(pos + m - 1) - i];
Chris@16: 
Chris@16:             assert( Tr::eq(c, one)
Chris@16:                     || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
Chris@16: 
Chris@16:             if (Tr::eq(c, one))
Chris@16:                 set(i);
Chris@16: 
Chris@16:         }
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16:     void init_from_unsigned_long(size_type num_bits,
Chris@16:                                  unsigned long value/*,
Chris@16:                                  const Allocator& alloc*/)
Chris@16:     {
Chris@16: 
Chris@16:         assert(m_bits.size() == 0);
Chris@16: 
Chris@16:         m_bits.resize(calc_num_blocks(num_bits));
Chris@16:         m_num_bits = num_bits;
Chris@16: 
Chris@16:         typedef unsigned long num_type;
Chris@16:         typedef boost::detail::dynamic_bitset_impl
Chris@16:             ::shifter<num_type, bits_per_block, ulong_width> shifter;
Chris@16: 
Chris@16:         //if (num_bits == 0)
Chris@16:         //    return;
Chris@16: 
Chris@16:         // zero out all bits at pos >= num_bits, if any;
Chris@16:         // note that: num_bits == 0 implies value == 0
Chris@16:         if (num_bits < static_cast<size_type>(ulong_width)) {
Chris@16:             const num_type mask = (num_type(1) << num_bits) - 1;
Chris@16:             value &= mask;
Chris@16:         }
Chris@16: 
Chris@16:         typename buffer_type::iterator it = m_bits.begin();
Chris@16:         for( ; value; shifter::left_shift(value), ++it) {
Chris@16:             *it = static_cast<block_type>(value);
Chris@16:         }
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: BOOST_DYNAMIC_BITSET_PRIVATE:
Chris@16: 
Chris@16:     bool m_unchecked_test(size_type pos) const;
Chris@16:     static size_type calc_num_blocks(size_type num_bits);
Chris@16: 
Chris@16:     Block&        m_highest_block();
Chris@16:     const Block&  m_highest_block() const;
Chris@16: 
Chris@16:     buffer_type m_bits;
Chris@16:     size_type   m_num_bits;
Chris@16: 
Chris@16: 
Chris@16:     class bit_appender;
Chris@16:     friend class bit_appender;
Chris@16:     class bit_appender {
Chris@16:       // helper for stream >>
Chris@16:       // Supplies to the lack of an efficient append at the less
Chris@16:       // significant end: bits are actually appended "at left" but
Chris@16:       // rearranged in the destructor. From the perspective of
Chris@16:       // client code everything works *as if* dynamic_bitset<> had
Chris@16:       // an append_at_right() function (eventually throwing the same
Chris@16:       // exceptions as push_back) except that the function is in fact
Chris@16:       // called bit_appender::do_append().
Chris@16:       //
Chris@16:       dynamic_bitset & bs;
Chris@16:       size_type n;
Chris@16:       Block mask;
Chris@16:       Block * current;
Chris@16: 
Chris@16:       // not implemented
Chris@16:       bit_appender(const bit_appender &);
Chris@16:       bit_appender & operator=(const bit_appender &);
Chris@16: 
Chris@16:     public:
Chris@16:         bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
Chris@16:         ~bit_appender() {
Chris@16:             // reverse the order of blocks, shift
Chris@16:             // if needed, and then resize
Chris@16:             //
Chris@16:             std::reverse(bs.m_bits.begin(), bs.m_bits.end());
Chris@16:             const block_width_type offs = bit_index(n);
Chris@16:             if (offs)
Chris@16:                 bs >>= (bits_per_block - offs);
Chris@16:             bs.resize(n); // doesn't enlarge, so can't throw
Chris@16:             assert(bs.m_check_invariants());
Chris@16:         }
Chris@16:         inline void do_append(bool value) {
Chris@16: 
Chris@16:             if (mask == 0) {
Chris@16:                 bs.append(Block(0));
Chris@16:                 current = &bs.m_highest_block();
Chris@16:                 mask = Block(1) << (bits_per_block - 1);
Chris@16:             }
Chris@16: 
Chris@16:             if(value)
Chris@16:                 *current |= mask;
Chris@16: 
Chris@16:             mask /= 2;
Chris@16:             ++n;
Chris@16:         }
Chris@16:         size_type get_count() const { return n; }
Chris@16:     };
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: #if !defined BOOST_NO_INCLASS_MEMBER_INITIALIZATION
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: const typename dynamic_bitset<Block, Allocator>::block_width_type
Chris@16: dynamic_bitset<Block, Allocator>::bits_per_block;
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: const typename dynamic_bitset<Block, Allocator>::size_type
Chris@16: dynamic_bitset<Block, Allocator>::npos;
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: const typename dynamic_bitset<Block, Allocator>::block_width_type
Chris@16: dynamic_bitset<Block, Allocator>::ulong_width;
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: // Global Functions:
Chris@16: 
Chris@16: // comparison
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool operator!=(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                 const dynamic_bitset<Block, Allocator>& b);
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool operator<=(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                 const dynamic_bitset<Block, Allocator>& b);
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool operator>(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                const dynamic_bitset<Block, Allocator>& b);
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool operator>=(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                 const dynamic_bitset<Block, Allocator>& b);
Chris@16: 
Chris@16: // stream operators
Chris@16: #ifdef BOOST_OLD_IOSTREAMS
Chris@16: template <typename Block, typename Allocator>
Chris@16: std::ostream& operator<<(std::ostream& os,
Chris@16:                          const dynamic_bitset<Block, Allocator>& b);
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
Chris@16: #else
Chris@16: template <typename CharT, typename Traits, typename Block, typename Allocator>
Chris@16: std::basic_ostream<CharT, Traits>&
Chris@16: operator<<(std::basic_ostream<CharT, Traits>& os,
Chris@16:            const dynamic_bitset<Block, Allocator>& b);
Chris@16: 
Chris@16: template <typename CharT, typename Traits, typename Block, typename Allocator>
Chris@16: std::basic_istream<CharT, Traits>&
Chris@16: operator>>(std::basic_istream<CharT, Traits>& is,
Chris@16:            dynamic_bitset<Block, Allocator>& b);
Chris@16: #endif
Chris@16: 
Chris@16: // bitset operations
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator&(const dynamic_bitset<Block, Allocator>& b1,
Chris@16:           const dynamic_bitset<Block, Allocator>& b2);
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator|(const dynamic_bitset<Block, Allocator>& b1,
Chris@16:           const dynamic_bitset<Block, Allocator>& b2);
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator^(const dynamic_bitset<Block, Allocator>& b1,
Chris@16:           const dynamic_bitset<Block, Allocator>& b2);
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator-(const dynamic_bitset<Block, Allocator>& b1,
Chris@16:           const dynamic_bitset<Block, Allocator>& b2);
Chris@16: 
Chris@16: // namespace scope swap
Chris@16: template<typename Block, typename Allocator>
Chris@16: void swap(dynamic_bitset<Block, Allocator>& b1,
Chris@16:           dynamic_bitset<Block, Allocator>& b2);
Chris@16: 
Chris@16: 
Chris@16: template <typename Block, typename Allocator, typename stringT>
Chris@16: void
Chris@16: to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s);
Chris@16: 
Chris@16: template <typename Block, typename Allocator, typename BlockOutputIterator>
Chris@16: void
Chris@16: to_block_range(const dynamic_bitset<Block, Allocator>& b,
Chris@16:                BlockOutputIterator result);
Chris@16: 
Chris@16: 
Chris@16: template <typename BlockIterator, typename B, typename A>
Chris@16: inline void
Chris@16: from_block_range(BlockIterator first, BlockIterator last,
Chris@16:                  dynamic_bitset<B, A>& result)
Chris@16: {
Chris@16:     // PRE: distance(first, last) <= numblocks()
Chris@16:     std::copy (first, last, result.m_bits.begin());
Chris@16: }
Chris@16: 
Chris@16: //=============================================================================
Chris@16: // dynamic_bitset implementation
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // constructors, etc.
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
Chris@16:   : m_bits(alloc), m_num_bits(0)
Chris@16: {
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>::
Chris@16: dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
Chris@16:     : m_bits(alloc),
Chris@16:       m_num_bits(0)
Chris@16: {
Chris@16:     init_from_unsigned_long(num_bits, value);
Chris@16: }
Chris@16: 
Chris@16: // copy constructor
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline dynamic_bitset<Block, Allocator>::
Chris@16: dynamic_bitset(const dynamic_bitset& b)
Chris@16:   : m_bits(b.m_bits), m_num_bits(b.m_num_bits)
Chris@16: {
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline dynamic_bitset<Block, Allocator>::
Chris@16: ~dynamic_bitset()
Chris@16: {
Chris@16:     assert(m_check_invariants());
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline void dynamic_bitset<Block, Allocator>::
Chris@16: swap(dynamic_bitset<Block, Allocator>& b) // no throw
Chris@16: {
Chris@16:     std::swap(m_bits, b.m_bits);
Chris@16:     std::swap(m_num_bits, b.m_num_bits);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
Chris@16: operator=(const dynamic_bitset<Block, Allocator>& b)
Chris@16: {
Chris@16:     m_bits = b.m_bits;
Chris@16:     m_num_bits = b.m_num_bits;
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@101: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101: 
Chris@101: template <typename Block, typename Allocator>
Chris@101: inline dynamic_bitset<Block, Allocator>::
Chris@101: dynamic_bitset(dynamic_bitset<Block, Allocator>&& b)
Chris@101:   : m_bits(boost::move(b.m_bits)), m_num_bits(boost::move(b.m_num_bits))
Chris@101: {
Chris@101:     // Required so that assert(m_check_invariants()); works.
Chris@101:     assert((b.m_bits = buffer_type()).empty());
Chris@101:     b.m_num_bits = 0;
Chris@101: }
Chris@101: 
Chris@101: template <typename Block, typename Allocator>
Chris@101: inline dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
Chris@101: operator=(dynamic_bitset<Block, Allocator>&& b)
Chris@101: {
Chris@101:     if (boost::addressof(b) == this) { return *this; }
Chris@101: 
Chris@101:     m_bits = boost::move(b.m_bits);
Chris@101:     m_num_bits = boost::move(b.m_num_bits);
Chris@101:     // Required so that assert(m_check_invariants()); works.
Chris@101:     assert((b.m_bits = buffer_type()).empty());
Chris@101:     b.m_num_bits = 0;
Chris@101:     return *this;
Chris@101: }
Chris@101: 
Chris@101: #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline typename dynamic_bitset<Block, Allocator>::allocator_type
Chris@16: dynamic_bitset<Block, Allocator>::get_allocator() const
Chris@16: {
Chris@16:     return m_bits.get_allocator();
Chris@16: }
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // size changing operations
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: void dynamic_bitset<Block, Allocator>::
Chris@16: resize(size_type num_bits, bool value) // strong guarantee
Chris@16: {
Chris@16: 
Chris@16:   const size_type old_num_blocks = num_blocks();
Chris@16:   const size_type required_blocks = calc_num_blocks(num_bits);
Chris@16: 
Chris@16:   const block_type v = value? ~Block(0) : Block(0);
Chris@16: 
Chris@16:   if (required_blocks != old_num_blocks) {
Chris@16:     m_bits.resize(required_blocks, v); // s.g. (copy)
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // At this point:
Chris@16:   //
Chris@16:   //  - if the buffer was shrunk, we have nothing more to do,
Chris@16:   //    except a call to m_zero_unused_bits()
Chris@16:   //
Chris@16:   //  - if it was enlarged, all the (used) bits in the new blocks have
Chris@16:   //    the correct value, but we have not yet touched those bits, if
Chris@16:   //    any, that were 'unused bits' before enlarging: if value == true,
Chris@16:   //    they must be set.
Chris@16: 
Chris@16:   if (value && (num_bits > m_num_bits)) {
Chris@16: 
Chris@16:     const block_width_type extra_bits = count_extra_bits();
Chris@16:     if (extra_bits) {
Chris@16:         assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
Chris@16: 
Chris@16:         // Set them.
Chris@16:         m_bits[old_num_blocks - 1] |= (v << extra_bits);
Chris@16:     }
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16:   m_num_bits = num_bits;
Chris@16:   m_zero_unused_bits();
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: void dynamic_bitset<Block, Allocator>::
Chris@16: clear() // no throw
Chris@16: {
Chris@16:   m_bits.clear();
Chris@16:   m_num_bits = 0;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: void dynamic_bitset<Block, Allocator>::
Chris@16: push_back(bool bit)
Chris@16: {
Chris@16:   const size_type sz = size();
Chris@16:   resize(sz + 1);
Chris@16:   set(sz, bit);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: void dynamic_bitset<Block, Allocator>::
Chris@101: pop_back() 
Chris@101: {
Chris@101:   const size_type old_num_blocks = num_blocks();
Chris@101:   const size_type required_blocks = calc_num_blocks(m_num_bits - 1);
Chris@101:   
Chris@101:   if (required_blocks != old_num_blocks) {
Chris@101:     m_bits.pop_back(); 
Chris@101:   }
Chris@101:     
Chris@101:   --m_num_bits;
Chris@101:   m_zero_unused_bits();
Chris@101: }
Chris@101: 
Chris@101: 
Chris@101: template <typename Block, typename Allocator>
Chris@101: void dynamic_bitset<Block, Allocator>::
Chris@16: append(Block value) // strong guarantee
Chris@16: {
Chris@16:     const block_width_type r = count_extra_bits();
Chris@16: 
Chris@16:     if (r == 0) {
Chris@16:         // the buffer is empty, or all blocks are filled
Chris@16:         m_bits.push_back(value);
Chris@16:     }
Chris@16:     else {
Chris@16:         m_bits.push_back(value >> (bits_per_block - r));
Chris@16:         m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
Chris@16:     }
Chris@16: 
Chris@16:     m_num_bits += bits_per_block;
Chris@16:     assert(m_check_invariants());
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // bitset operations
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
Chris@16: {
Chris@16:     assert(size() == rhs.size());
Chris@16:     for (size_type i = 0; i < num_blocks(); ++i)
Chris@16:         m_bits[i] &= rhs.m_bits[i];
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
Chris@16: {
Chris@16:     assert(size() == rhs.size());
Chris@16:     for (size_type i = 0; i < num_blocks(); ++i)
Chris@16:         m_bits[i] |= rhs.m_bits[i];
Chris@16:     //m_zero_unused_bits();
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
Chris@16: {
Chris@16:     assert(size() == rhs.size());
Chris@16:     for (size_type i = 0; i < this->num_blocks(); ++i)
Chris@16:         m_bits[i] ^= rhs.m_bits[i];
Chris@16:     //m_zero_unused_bits();
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
Chris@16: {
Chris@16:     assert(size() == rhs.size());
Chris@16:     for (size_type i = 0; i < num_blocks(); ++i)
Chris@16:         m_bits[i] &= ~rhs.m_bits[i];
Chris@16:     //m_zero_unused_bits();
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: //
Chris@16: // NOTE:
Chris@16: //  Note that the 'if (r != 0)' is crucial to avoid undefined
Chris@16: //  behavior when the left hand operand of >> isn't promoted to a
Chris@16: //  wider type (because rs would be too large).
Chris@16: //
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
Chris@16: {
Chris@16:     if (n >= m_num_bits)
Chris@16:         return reset();
Chris@16:     //else
Chris@16:     if (n > 0) {
Chris@16: 
Chris@16:         size_type    const last = num_blocks() - 1;  // num_blocks() is >= 1
Chris@16:         size_type    const div  = n / bits_per_block; // div is <= last
Chris@16:         block_width_type const r = bit_index(n);
Chris@16:         block_type * const b    = &m_bits[0];
Chris@16: 
Chris@16:         if (r != 0) {
Chris@16: 
Chris@16:             block_width_type const rs = bits_per_block - r;
Chris@16: 
Chris@16:             for (size_type i = last-div; i>0; --i) {
Chris@16:                 b[i+div] = (b[i] << r) | (b[i-1] >> rs);
Chris@16:             }
Chris@16:             b[div] = b[0] << r;
Chris@16: 
Chris@16:         }
Chris@16:         else {
Chris@16:             for (size_type i = last-div; i>0; --i) {
Chris@16:                 b[i+div] = b[i];
Chris@16:             }
Chris@16:             b[div] = b[0];
Chris@16:         }
Chris@16: 
Chris@16:         // zero out div blocks at the less significant end
Chris@101:         std::fill_n(m_bits.begin(), div, static_cast<block_type>(0));
Chris@16: 
Chris@16:         // zero out any 1 bit that flowed into the unused part
Chris@16:         m_zero_unused_bits(); // thanks to Lester Gong
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16:     return *this;
Chris@16: 
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //
Chris@16: // NOTE:
Chris@16: //  see the comments to operator <<=
Chris@16: //
Chris@16: template <typename B, typename A>
Chris@16: dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
Chris@16:     if (n >= m_num_bits) {
Chris@16:         return reset();
Chris@16:     }
Chris@16:     //else
Chris@16:     if (n>0) {
Chris@16: 
Chris@16:         size_type  const last  = num_blocks() - 1; // num_blocks() is >= 1
Chris@16:         size_type  const div   = n / bits_per_block;   // div is <= last
Chris@16:         block_width_type const r     = bit_index(n);
Chris@16:         block_type * const b   = &m_bits[0];
Chris@16: 
Chris@16: 
Chris@16:         if (r != 0) {
Chris@16: 
Chris@16:             block_width_type const ls = bits_per_block - r;
Chris@16: 
Chris@16:             for (size_type i = div; i < last; ++i) {
Chris@16:                 b[i-div] = (b[i] >> r) | (b[i+1]  << ls);
Chris@16:             }
Chris@16:             // r bits go to zero
Chris@16:             b[last-div] = b[last] >> r;
Chris@16:         }
Chris@16: 
Chris@16:         else {
Chris@16:             for (size_type i = div; i <= last; ++i) {
Chris@16:                 b[i-div] = b[i];
Chris@16:             }
Chris@16:             // note the '<=': the last iteration 'absorbs'
Chris@16:             // b[last-div] = b[last] >> 0;
Chris@16:         }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:         // div blocks are zero filled at the most significant end
Chris@101:         std::fill_n(m_bits.begin() + (num_blocks()-div), div, static_cast<block_type>(0));
Chris@16:     }
Chris@16: 
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
Chris@16: {
Chris@16:     dynamic_bitset r(*this);
Chris@16:     return r <<= n;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
Chris@16: {
Chris@16:     dynamic_bitset r(*this);
Chris@16:     return r >>= n;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // basic bit operations
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
Chris@16: {
Chris@16:     assert(pos < m_num_bits);
Chris@16: 
Chris@16:     if (val)
Chris@16:         m_bits[block_index(pos)] |= bit_mask(pos);
Chris@16:     else
Chris@16:         reset(pos);
Chris@16: 
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::set()
Chris@16: {
Chris@16:   std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
Chris@16:   m_zero_unused_bits();
Chris@16:   return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::reset(size_type pos)
Chris@16: {
Chris@16:     assert(pos < m_num_bits);
Chris@16: #if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
Chris@16:     // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
Chris@16:     // use the |^ variation instead.. <grafik>
Chris@16:     m_bits[block_index(pos)] |= bit_mask(pos);
Chris@16:     m_bits[block_index(pos)] ^= bit_mask(pos);
Chris@16: #else
Chris@16:     m_bits[block_index(pos)] &= ~bit_mask(pos);
Chris@16: #endif
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::reset()
Chris@16: {
Chris@16:   std::fill(m_bits.begin(), m_bits.end(), Block(0));
Chris@16:   return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::flip(size_type pos)
Chris@16: {
Chris@16:     assert(pos < m_num_bits);
Chris@16:     m_bits[block_index(pos)] ^= bit_mask(pos);
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>&
Chris@16: dynamic_bitset<Block, Allocator>::flip()
Chris@16: {
Chris@16:     for (size_type i = 0; i < num_blocks(); ++i)
Chris@16:         m_bits[i] = ~m_bits[i];
Chris@16:     m_zero_unused_bits();
Chris@16:     return *this;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
Chris@16: {
Chris@16:     return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
Chris@16: {
Chris@16:     assert(pos < m_num_bits);
Chris@16:     return m_unchecked_test(pos);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@101: bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool val)
Chris@101: {
Chris@101:     bool const b = test(pos);
Chris@101:     if (b != val) {
Chris@101:         set(pos, val);
Chris@101:     }
Chris@101:     return b;
Chris@101: }
Chris@101: 
Chris@101: template <typename Block, typename Allocator>
Chris@101: bool dynamic_bitset<Block, Allocator>::all() const
Chris@101: {
Chris@101:     if (empty()) {
Chris@101:         return true;
Chris@101:     }
Chris@101: 
Chris@101:     const block_width_type extra_bits = count_extra_bits();
Chris@101:     block_type const all_ones = ~static_cast<Block>(0);
Chris@101: 
Chris@101:     if (extra_bits == 0) {
Chris@101:         for (size_type i = 0, e = num_blocks(); i < e; ++i) {
Chris@101:             if (m_bits[i] != all_ones) {
Chris@101:                 return false;
Chris@101:             }
Chris@101:         }
Chris@101:     } else {
Chris@101:         for (size_type i = 0, e = num_blocks() - 1; i < e; ++i) {
Chris@101:             if (m_bits[i] != all_ones) {
Chris@101:                 return false;
Chris@101:             }
Chris@101:         }
Chris@101:         block_type const mask = ~(~static_cast<Block>(0) << extra_bits);
Chris@101:         if (m_highest_block() != mask) {
Chris@101:             return false;
Chris@101:         }
Chris@101:     }
Chris@101:     return true;
Chris@101: }
Chris@101: 
Chris@101: template <typename Block, typename Allocator>
Chris@16: bool dynamic_bitset<Block, Allocator>::any() const
Chris@16: {
Chris@16:     for (size_type i = 0; i < num_blocks(); ++i)
Chris@16:         if (m_bits[i])
Chris@16:             return true;
Chris@16:     return false;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline bool dynamic_bitset<Block, Allocator>::none() const
Chris@16: {
Chris@16:     return !any();
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: dynamic_bitset<Block, Allocator>::operator~() const
Chris@16: {
Chris@16:     dynamic_bitset b(*this);
Chris@16:     b.flip();
Chris@16:     return b;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: typename dynamic_bitset<Block, Allocator>::size_type
Chris@101: dynamic_bitset<Block, Allocator>::count() const BOOST_NOEXCEPT
Chris@16: {
Chris@16:     using detail::dynamic_bitset_impl::table_width;
Chris@16:     using detail::dynamic_bitset_impl::access_by_bytes;
Chris@16:     using detail::dynamic_bitset_impl::access_by_blocks;
Chris@16:     using detail::dynamic_bitset_impl::value_to_type;
Chris@16: 
Chris@16: #if BOOST_WORKAROUND(__GNUC__, == 4) && (__GNUC_MINOR__ == 3) && (__GNUC_PATCHLEVEL__ == 3)
Chris@16:     // NOTE: Explicit qualification of "bits_per_block"
Chris@16:     //       breaks compilation on gcc 4.3.3
Chris@16:     enum { no_padding = bits_per_block == CHAR_BIT * sizeof(Block) };
Chris@16: #else
Chris@16:     // NOTE: Explicitly qualifying "bits_per_block" to workaround
Chris@16:     //       regressions of gcc 3.4.x
Chris@16:     enum { no_padding =
Chris@16:         dynamic_bitset<Block, Allocator>::bits_per_block
Chris@16:         == CHAR_BIT * sizeof(Block) };
Chris@16: #endif
Chris@16: 
Chris@16:     enum { enough_table_width = table_width >= CHAR_BIT };
Chris@16: 
Chris@16:     enum { mode = (no_padding && enough_table_width)
Chris@16:                           ? access_by_bytes
Chris@16:                           : access_by_blocks };
Chris@16: 
Chris@16:     return do_count(m_bits.begin(), num_blocks(), Block(0),
Chris@16:                     static_cast<value_to_type<(bool)mode> *>(0));
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // conversions
Chris@16: 
Chris@16: 
Chris@16: template <typename B, typename A, typename stringT>
Chris@16: void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
Chris@16:                       bool dump_all)
Chris@16: {
Chris@16:     typedef typename stringT::traits_type Tr;
Chris@16:     typedef typename stringT::value_type  Ch;
Chris@16: 
Chris@16:     BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
Chris@16:     const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
Chris@16:     const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16: 
Chris@16:     // Note that this function may access (when
Chris@16:     // dump_all == true) bits beyond position size() - 1
Chris@16: 
Chris@16:     typedef typename dynamic_bitset<B, A>::size_type size_type;
Chris@16: 
Chris@16:     const size_type len = dump_all?
Chris@16:          dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
Chris@16:          b.size();
Chris@16:     s.assign (len, zero);
Chris@16: 
Chris@16:     for (size_type i = 0; i < len; ++i) {
Chris@16:         if (b.m_unchecked_test(i))
Chris@16:             Tr::assign(s[len - 1 - i], one);
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // A comment similar to the one about the constructor from
Chris@16: // basic_string can be done here. Thanks to James Kanze for
Chris@16: // making me (Gennaro) realize this important separation of
Chris@16: // concerns issue, as well as many things about i18n.
Chris@16: //
Chris@16: template <typename Block, typename Allocator, typename stringT>
Chris@16: inline void
Chris@16: to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
Chris@16: {
Chris@16:     to_string_helper(b, s, false);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // Differently from to_string this function dumps out
Chris@16: // every bit of the internal representation (may be
Chris@16: // useful for debugging purposes)
Chris@16: //
Chris@16: template <typename B, typename A, typename stringT>
Chris@16: inline void
Chris@16: dump_to_string(const dynamic_bitset<B, A>& b, stringT& s)
Chris@16: {
Chris@16:     to_string_helper(b, s, true /* =dump_all*/);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator, typename BlockOutputIterator>
Chris@16: inline void
Chris@16: to_block_range(const dynamic_bitset<Block, Allocator>& b,
Chris@16:                BlockOutputIterator result)
Chris@16: {
Chris@16:     // note how this copies *all* bits, including the
Chris@16:     // unused ones in the last block (which are zero)
Chris@16:     std::copy(b.m_bits.begin(), b.m_bits.end(), result);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: unsigned long dynamic_bitset<Block, Allocator>::
Chris@16: to_ulong() const
Chris@16: {
Chris@16: 
Chris@16:   if (m_num_bits == 0)
Chris@16:       return 0; // convention
Chris@16: 
Chris@16:   // Check for overflows. This may be a performance burden on very
Chris@16:   // large bitsets but is required by the specification, sorry
Chris@16:   if (find_next(ulong_width - 1) != npos)
Chris@101:     BOOST_THROW_EXCEPTION(std::overflow_error("boost::dynamic_bitset::to_ulong overflow"));
Chris@16: 
Chris@16: 
Chris@16:   // Ok, from now on we can be sure there's no "on" bit
Chris@16:   // beyond the "allowed" positions
Chris@16:   typedef unsigned long result_type;
Chris@16: 
Chris@16:   const size_type maximum_size =
Chris@16:             (std::min)(m_num_bits, static_cast<size_type>(ulong_width));
Chris@16: 
Chris@16:   const size_type last_block = block_index( maximum_size - 1 );
Chris@16: 
Chris@16:   assert((last_block * bits_per_block) < static_cast<size_type>(ulong_width));
Chris@16: 
Chris@16:   result_type result = 0;
Chris@16:   for (size_type i = 0; i <= last_block; ++i) {
Chris@16:     const size_type offset = i * bits_per_block;
Chris@16:     result |= (static_cast<result_type>(m_bits[i]) << offset);
Chris@16:   }
Chris@16: 
Chris@16:   return result;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@101: dynamic_bitset<Block, Allocator>::size() const BOOST_NOEXCEPT
Chris@16: {
Chris@16:     return m_num_bits;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@101: dynamic_bitset<Block, Allocator>::num_blocks() const BOOST_NOEXCEPT
Chris@16: {
Chris@16:     return m_bits.size();
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@101: dynamic_bitset<Block, Allocator>::max_size() const BOOST_NOEXCEPT
Chris@16: {
Chris@16:     // Semantics of vector<>::max_size() aren't very clear
Chris@16:     // (see lib issue 197) and many library implementations
Chris@16:     // simply return dummy values, _unrelated_ to the underlying
Chris@16:     // allocator.
Chris@16:     //
Chris@16:     // Given these problems, I was tempted to not provide this
Chris@16:     // function at all but the user could need it if he provides
Chris@16:     // his own allocator.
Chris@16:     //
Chris@16: 
Chris@16:     const size_type m = detail::dynamic_bitset_impl::
Chris@16:                         vector_max_size_workaround(m_bits);
Chris@16: 
Chris@16:     return m <= (size_type(-1)/bits_per_block) ?
Chris@16:         m * bits_per_block :
Chris@16:         size_type(-1);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@101: inline bool dynamic_bitset<Block, Allocator>::empty() const BOOST_NOEXCEPT
Chris@16: {
Chris@16:   return size() == 0;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool dynamic_bitset<Block, Allocator>::
Chris@16: is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
Chris@16: {
Chris@16:     assert(size() == a.size());
Chris@16:     for (size_type i = 0; i < num_blocks(); ++i)
Chris@16:         if (m_bits[i] & ~a.m_bits[i])
Chris@16:             return false;
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool dynamic_bitset<Block, Allocator>::
Chris@16: is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
Chris@16: {
Chris@16:     assert(size() == a.size());
Chris@16:     assert(num_blocks() == a.num_blocks());
Chris@16: 
Chris@16:     bool proper = false;
Chris@16:     for (size_type i = 0; i < num_blocks(); ++i) {
Chris@16:         const Block & bt =   m_bits[i];
Chris@16:         const Block & ba = a.m_bits[i];
Chris@16: 
Chris@16:         if (bt & ~ba)
Chris@16:             return false; // not a subset at all
Chris@16:         if (ba & ~bt)
Chris@16:             proper = true;
Chris@16:     }
Chris@16:     return proper;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
Chris@16: {
Chris@16:     size_type common_blocks = num_blocks() < b.num_blocks()
Chris@16:                               ? num_blocks() : b.num_blocks();
Chris@16: 
Chris@16:     for(size_type i = 0; i < common_blocks; ++i) {
Chris@16:         if(m_bits[i] & b.m_bits[i])
Chris@16:             return true;
Chris@16:     }
Chris@16:     return false;
Chris@16: }
Chris@16: 
Chris@16: // --------------------------------
Chris@16: // lookup
Chris@16: 
Chris@16: 
Chris@16: // look for the first bit "on", starting
Chris@16: // from the block with index first_block
Chris@16: //
Chris@16: template <typename Block, typename Allocator>
Chris@16: typename dynamic_bitset<Block, Allocator>::size_type
Chris@16: dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
Chris@16: {
Chris@16:     size_type i = first_block;
Chris@16: 
Chris@16:     // skip null blocks
Chris@16:     while (i < num_blocks() && m_bits[i] == 0)
Chris@16:         ++i;
Chris@16: 
Chris@16:     if (i >= num_blocks())
Chris@16:         return npos; // not found
Chris@16: 
Chris@101:     return i * bits_per_block + static_cast<size_type>(boost::lowest_bit(m_bits[i]));
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: typename dynamic_bitset<Block, Allocator>::size_type
Chris@16: dynamic_bitset<Block, Allocator>::find_first() const
Chris@16: {
Chris@16:     return m_do_find_from(0);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: typename dynamic_bitset<Block, Allocator>::size_type
Chris@16: dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
Chris@16: {
Chris@16: 
Chris@16:     const size_type sz = size();
Chris@16:     if (pos >= (sz-1) || sz == 0)
Chris@16:         return npos;
Chris@16: 
Chris@16:     ++pos;
Chris@16: 
Chris@16:     const size_type blk = block_index(pos);
Chris@16:     const block_width_type ind = bit_index(pos);
Chris@16: 
Chris@101:     // shift bits upto one immediately after current
Chris@101:     const Block fore = m_bits[blk] >> ind;
Chris@16: 
Chris@16:     return fore?
Chris@101:         pos + static_cast<size_type>(lowest_bit(fore))
Chris@16:         :
Chris@16:         m_do_find_from(blk + 1);
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // comparison
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool operator==(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                 const dynamic_bitset<Block, Allocator>& b)
Chris@16: {
Chris@16:     return (a.m_num_bits == b.m_num_bits)
Chris@16:            && (a.m_bits == b.m_bits);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                        const dynamic_bitset<Block, Allocator>& b)
Chris@16: {
Chris@16:     return !(a == b);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool operator<(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                const dynamic_bitset<Block, Allocator>& b)
Chris@16: {
Chris@16:     assert(a.size() == b.size());
Chris@16:     typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
Chris@16: 
Chris@16:     //if (a.size() == 0)
Chris@16:     //  return false;
Chris@16: 
Chris@16:     // Since we are storing the most significant bit
Chris@16:     // at pos == size() - 1, we need to do the comparisons in reverse.
Chris@16:     //
Chris@16:     for (size_type ii = a.num_blocks(); ii > 0; --ii) {
Chris@16:       size_type i = ii-1;
Chris@16:       if (a.m_bits[i] < b.m_bits[i])
Chris@16:         return true;
Chris@16:       else if (a.m_bits[i] > b.m_bits[i])
Chris@16:         return false;
Chris@16:     }
Chris@16:     return false;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                        const dynamic_bitset<Block, Allocator>& b)
Chris@16: {
Chris@16:     return !(a > b);
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                       const dynamic_bitset<Block, Allocator>& b)
Chris@16: {
Chris@16:     return b < a;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
Chris@16:                        const dynamic_bitset<Block, Allocator>& b)
Chris@16: {
Chris@16:     return !(a < b);
Chris@16: }
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // stream operations
Chris@16: 
Chris@16: #ifdef BOOST_OLD_IOSTREAMS
Chris@16: template < typename Block, typename Alloc>
Chris@16: std::ostream&
Chris@16: operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
Chris@16: {
Chris@16:     // NOTE: since this is aimed at "classic" iostreams, exception
Chris@16:     // masks on the stream are not supported. The library that
Chris@16:     // ships with gcc 2.95 has an exceptions() member function but
Chris@16:     // nothing is actually implemented; not even the class ios::failure.
Chris@16: 
Chris@16:     using namespace std;
Chris@16: 
Chris@16:     const ios::iostate ok = ios::goodbit;
Chris@16:     ios::iostate err = ok;
Chris@16: 
Chris@16:     if (os.opfx()) {
Chris@16: 
Chris@16:         //try
Chris@16:         typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
Chris@16: 
Chris@16:         const bitsetsize_type sz = b.size();
Chris@16:         std::streambuf * buf = os.rdbuf();
Chris@16:         size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
Chris@16:             || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz;
Chris@16: 
Chris@16:         const char fill_char = os.fill();
Chris@16:         const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
Chris@16: 
Chris@16:         // if needed fill at left; pad is decresed along the way
Chris@16:         if (adjustfield != ios::left) {
Chris@16:             for (; 0 < npad; --npad)
Chris@16:                 if (fill_char != buf->sputc(fill_char)) {
Chris@16:                     err |= ios::failbit;
Chris@16:                     break;
Chris@16:                 }
Chris@16:         }
Chris@16: 
Chris@16:         if (err == ok) {
Chris@16:             // output the bitset
Chris@16:             for (bitsetsize_type i = b.size(); 0 < i; --i) {
Chris@16:                 const char dig = b.test(i-1)? '1' : '0';
Chris@16:                 if (EOF == buf->sputc(dig)) {
Chris@16:                     err |= ios::failbit;
Chris@16:                     break;
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         if (err == ok) {
Chris@16:             // if needed fill at right
Chris@16:             for (; 0 < npad; --npad) {
Chris@16:                 if (fill_char != buf->sputc(fill_char)) {
Chris@16:                     err |= ios::failbit;
Chris@16:                     break;
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         os.osfx();
Chris@16:         os.width(0);
Chris@16: 
Chris@16:     } // if opfx
Chris@16: 
Chris@16:     if(err != ok)
Chris@16:         os.setstate(err); // assume this does NOT throw
Chris@16:     return os;
Chris@16: 
Chris@16: }
Chris@16: #else
Chris@16: 
Chris@16: template <typename Ch, typename Tr, typename Block, typename Alloc>
Chris@16: std::basic_ostream<Ch, Tr>&
Chris@16: operator<<(std::basic_ostream<Ch, Tr>& os,
Chris@16:            const dynamic_bitset<Block, Alloc>& b)
Chris@16: {
Chris@16: 
Chris@16:     using namespace std;
Chris@16: 
Chris@16:     const ios_base::iostate ok = ios_base::goodbit;
Chris@16:     ios_base::iostate err = ok;
Chris@16: 
Chris@16:     typename basic_ostream<Ch, Tr>::sentry cerberos(os);
Chris@16:     if (cerberos) {
Chris@16: 
Chris@16:         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
Chris@16:         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
Chris@16:         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16: 
Chris@101:         BOOST_TRY {
Chris@16: 
Chris@101:             typedef typename dynamic_bitset<Block, Alloc>::size_type bitset_size_type;
Chris@16:             typedef basic_streambuf<Ch, Tr> buffer_type;
Chris@16: 
Chris@16:             buffer_type * buf = os.rdbuf();
Chris@101:             // careful: os.width() is signed (and can be < 0)
Chris@101:             const bitset_size_type width = (os.width() <= 0) ? 0 : static_cast<bitset_size_type>(os.width());
Chris@101:             streamsize npad = (width <= b.size()) ? 0 : width - b.size();
Chris@16: 
Chris@16:             const Ch fill_char = os.fill();
Chris@16:             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
Chris@16: 
Chris@101:             // if needed fill at left; pad is decreased along the way
Chris@16:             if (adjustfield != ios_base::left) {
Chris@16:                 for (; 0 < npad; --npad)
Chris@16:                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
Chris@16:                           err |= ios_base::failbit;
Chris@16:                           break;
Chris@16:                     }
Chris@16:             }
Chris@16: 
Chris@16:             if (err == ok) {
Chris@16:                 // output the bitset
Chris@101:                 for (bitset_size_type i = b.size(); 0 < i; --i) {
Chris@16:                     typename buffer_type::int_type
Chris@16:                         ret = buf->sputc(b.test(i-1)? one : zero);
Chris@16:                     if (Tr::eq_int_type(Tr::eof(), ret)) {
Chris@16:                         err |= ios_base::failbit;
Chris@16:                         break;
Chris@16:                     }
Chris@16:                 }
Chris@16:             }
Chris@16: 
Chris@16:             if (err == ok) {
Chris@16:                 // if needed fill at right
Chris@16:                 for (; 0 < npad; --npad) {
Chris@16:                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
Chris@16:                         err |= ios_base::failbit;
Chris@16:                         break;
Chris@16:                     }
Chris@16:                 }
Chris@16:             }
Chris@16: 
Chris@16: 
Chris@16:             os.width(0);
Chris@16: 
Chris@101:         } BOOST_CATCH (...) { // see std 27.6.1.1/4
Chris@16:             bool rethrow = false;
Chris@101:             BOOST_TRY { os.setstate(ios_base::failbit); } BOOST_CATCH (...) { rethrow = true; } BOOST_CATCH_END
Chris@16: 
Chris@16:             if (rethrow)
Chris@101:                 BOOST_RETHROW;
Chris@16:         }
Chris@101:         BOOST_CATCH_END
Chris@16:     }
Chris@16: 
Chris@16:     if(err != ok)
Chris@16:         os.setstate(err); // may throw exception
Chris@16:     return os;
Chris@16: 
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: #ifdef BOOST_OLD_IOSTREAMS
Chris@16: 
Chris@16:     // A sentry-like class that calls isfx in its destructor.
Chris@16:     // "Necessary" because bit_appender::do_append may throw.
Chris@16:     class pseudo_sentry {
Chris@16:         std::istream & m_r;
Chris@16:         const bool m_ok;
Chris@16:     public:
Chris@16:         explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
Chris@16:         ~pseudo_sentry() { m_r.isfx(); }
Chris@16:         operator bool() const { return m_ok; }
Chris@16:     };
Chris@16: 
Chris@16: template <typename Block, typename Alloc>
Chris@16: std::istream&
Chris@16: operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
Chris@16: {
Chris@16: 
Chris@16: // Extractor for classic IO streams (libstdc++ < 3.0)
Chris@16: // ----------------------------------------------------//
Chris@16: //  It's assumed that the stream buffer functions, and
Chris@16: //  the stream's setstate() _cannot_ throw.
Chris@16: 
Chris@16: 
Chris@16:     typedef dynamic_bitset<Block, Alloc> bitset_type;
Chris@16:     typedef typename bitset_type::size_type size_type;
Chris@16: 
Chris@16:     std::ios::iostate err = std::ios::goodbit;
Chris@16:     pseudo_sentry cerberos(is); // skips whitespaces
Chris@16:     if(cerberos) {
Chris@16: 
Chris@16:         b.clear();
Chris@16: 
Chris@16:         const std::streamsize w = is.width();
Chris@16:         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()
Chris@101:                                                          ? static_cast<size_type>(w) : b.max_size();
Chris@16:         typename bitset_type::bit_appender appender(b);
Chris@16:         std::streambuf * buf = is.rdbuf();
Chris@16:         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
Chris@16: 
Chris@16:             if (c == EOF) {
Chris@16:                 err |= std::ios::eofbit;
Chris@16:                 break;
Chris@16:             }
Chris@16:             else if (char(c) != '0' && char(c) != '1')
Chris@16:                 break; // non digit character
Chris@16: 
Chris@16:             else {
Chris@101:                 BOOST_TRY {
Chris@16:                     appender.do_append(char(c) == '1');
Chris@16:                 }
Chris@101:                 BOOST_CATCH(...) {
Chris@16:                     is.setstate(std::ios::failbit); // assume this can't throw
Chris@101:                     BOOST_RETHROW;
Chris@16:                 }
Chris@101:                 BOOST_CATCH_END
Chris@16:             }
Chris@16: 
Chris@16:         } // for
Chris@16:     }
Chris@16: 
Chris@16:     is.width(0);
Chris@16:     if (b.size() == 0)
Chris@16:         err |= std::ios::failbit;
Chris@16:     if (err != std::ios::goodbit)
Chris@16:         is.setstate (err); // may throw
Chris@16: 
Chris@16:     return is;
Chris@16: }
Chris@16: 
Chris@16: #else // BOOST_OLD_IOSTREAMS
Chris@16: 
Chris@16: template <typename Ch, typename Tr, typename Block, typename Alloc>
Chris@16: std::basic_istream<Ch, Tr>&
Chris@16: operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
Chris@16: {
Chris@16: 
Chris@16:     using namespace std;
Chris@16: 
Chris@16:     typedef dynamic_bitset<Block, Alloc> bitset_type;
Chris@16:     typedef typename bitset_type::size_type size_type;
Chris@16: 
Chris@16:     const streamsize w = is.width();
Chris@16:     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()?
Chris@101:                                          static_cast<size_type>(w) : b.max_size();
Chris@16: 
Chris@16:     ios_base::iostate err = ios_base::goodbit;
Chris@16:     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
Chris@16:     if(cerberos) {
Chris@16: 
Chris@16:         // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
Chris@16:         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
Chris@16:         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
Chris@16:         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16: 
Chris@16:         b.clear();
Chris@101:         BOOST_TRY {
Chris@16:             typename bitset_type::bit_appender appender(b);
Chris@16:             basic_streambuf <Ch, Tr> * buf = is.rdbuf();
Chris@16:             typename Tr::int_type c = buf->sgetc();
Chris@16:             for( ; appender.get_count() < limit; c = buf->snextc() ) {
Chris@16: 
Chris@16:                 if (Tr::eq_int_type(Tr::eof(), c)) {
Chris@16:                     err |= ios_base::eofbit;
Chris@16:                     break;
Chris@16:                 }
Chris@16:                 else {
Chris@16:                     const Ch to_c = Tr::to_char_type(c);
Chris@16:                     const bool is_one = Tr::eq(to_c, one);
Chris@16: 
Chris@16:                     if (!is_one && !Tr::eq(to_c, zero))
Chris@16:                         break; // non digit character
Chris@16: 
Chris@16:                     appender.do_append(is_one);
Chris@16: 
Chris@16:                 }
Chris@16: 
Chris@16:             } // for
Chris@16:         }
Chris@101:         BOOST_CATCH (...) {
Chris@16:             // catches from stream buf, or from vector:
Chris@16:             //
Chris@16:             // bits_stored bits have been extracted and stored, and
Chris@16:             // either no further character is extractable or we can't
Chris@16:             // append to the underlying vector (out of memory)
Chris@16: 
Chris@16:             bool rethrow = false;   // see std 27.6.1.1/4
Chris@101:             BOOST_TRY { is.setstate(ios_base::badbit); }
Chris@101:             BOOST_CATCH(...) { rethrow = true; }
Chris@101:             BOOST_CATCH_END
Chris@16: 
Chris@16:             if (rethrow)
Chris@101:                 BOOST_RETHROW;
Chris@16: 
Chris@16:         }
Chris@101:         BOOST_CATCH_END
Chris@16:     }
Chris@16: 
Chris@16:     is.width(0);
Chris@16:     if (b.size() == 0 /*|| !cerberos*/)
Chris@16:         err |= ios_base::failbit;
Chris@16:     if (err != ios_base::goodbit)
Chris@16:         is.setstate (err); // may throw
Chris@16: 
Chris@16:     return is;
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // bitset operations
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator&(const dynamic_bitset<Block, Allocator>& x,
Chris@16:           const dynamic_bitset<Block, Allocator>& y)
Chris@16: {
Chris@16:     dynamic_bitset<Block, Allocator> b(x);
Chris@16:     return b &= y;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator|(const dynamic_bitset<Block, Allocator>& x,
Chris@16:           const dynamic_bitset<Block, Allocator>& y)
Chris@16: {
Chris@16:     dynamic_bitset<Block, Allocator> b(x);
Chris@16:     return b |= y;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator^(const dynamic_bitset<Block, Allocator>& x,
Chris@16:           const dynamic_bitset<Block, Allocator>& y)
Chris@16: {
Chris@16:     dynamic_bitset<Block, Allocator> b(x);
Chris@16:     return b ^= y;
Chris@16: }
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: dynamic_bitset<Block, Allocator>
Chris@16: operator-(const dynamic_bitset<Block, Allocator>& x,
Chris@16:           const dynamic_bitset<Block, Allocator>& y)
Chris@16: {
Chris@16:     dynamic_bitset<Block, Allocator> b(x);
Chris@16:     return b -= y;
Chris@16: }
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // namespace scope swap
Chris@16: 
Chris@16: template<typename Block, typename Allocator>
Chris@16: inline void
Chris@16: swap(dynamic_bitset<Block, Allocator>& left,
Chris@16:      dynamic_bitset<Block, Allocator>& right) // no throw
Chris@16: {
Chris@16:     left.swap(right);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // private (on conforming compilers) member functions
Chris@16: 
Chris@16: 
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@16: dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
Chris@16: {
Chris@16:     return num_bits / bits_per_block
Chris@101:            + static_cast<size_type>( num_bits % bits_per_block != 0 );
Chris@16: }
Chris@16: 
Chris@16: // gives a reference to the highest block
Chris@16: //
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
Chris@16: {
Chris@16:     return const_cast<Block &>
Chris@16:            (static_cast<const dynamic_bitset *>(this)->m_highest_block());
Chris@16: }
Chris@16: 
Chris@16: // gives a const-reference to the highest block
Chris@16: //
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
Chris@16: {
Chris@16:     assert(size() > 0 && num_blocks() > 0);
Chris@16:     return m_bits.back();
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // If size() is not a multiple of bits_per_block
Chris@16: // then not all the bits in the last block are used.
Chris@16: // This function resets the unused bits (convenient
Chris@16: // for the implementation of many member functions)
Chris@16: //
Chris@16: template <typename Block, typename Allocator>
Chris@16: inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
Chris@16: {
Chris@16:     assert (num_blocks() == calc_num_blocks(m_num_bits));
Chris@16: 
Chris@16:     // if != 0 this is the number of bits used in the last block
Chris@16:     const block_width_type extra_bits = count_extra_bits();
Chris@16: 
Chris@16:     if (extra_bits != 0)
Chris@16:         m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: // check class invariants
Chris@16: template <typename Block, typename Allocator>
Chris@16: bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
Chris@16: {
Chris@16:     const block_width_type extra_bits = count_extra_bits();
Chris@16:     if (extra_bits > 0) {
Chris@16:         block_type const mask = (~static_cast<Block>(0) << extra_bits);
Chris@16:         if ((m_highest_block() & mask) != 0)
Chris@16:             return false;
Chris@16:     }
Chris@16:     if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
Chris@16:         return false;
Chris@16: 
Chris@16:     return true;
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: 
Chris@16: #undef BOOST_BITSET_CHAR
Chris@16: 
Chris@16: #endif // include guard
Chris@16: