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: