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