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