diff -r e1b950c65cb4 -r 837f303aceeb epoc32/include/stdapis/boost/detail/dynamic_bitset.hpp --- a/epoc32/include/stdapis/boost/detail/dynamic_bitset.hpp Wed Mar 31 12:27:01 2010 +0100 +++ b/epoc32/include/stdapis/boost/detail/dynamic_bitset.hpp Wed Mar 31 12:33:34 2010 +0100 @@ -12,1789 +12,157 @@ // See http://www.boost.org/libs/dynamic_bitset for documentation. +#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP +#define BOOST_DETAIL_DYNAMIC_BITSET_HPP -#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 +#include // for std::size_t +#include "boost/config.hpp" +#include "boost/detail/workaround.hpp" +//#include "boost/static_assert.hpp" // gps namespace boost { -template + namespace detail { -#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 + // Gives (read-)access to the object representation + // of an object of type T (3.9p4). CANNOT be used + // on a base sub-object + // + template + inline const unsigned char * object_representation (T* p) + { + return static_cast(static_cast(p)); + } -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); + // ------- count function implementation -------------- -public: - typedef Block block_type; - typedef Allocator allocator_type; - typedef std::size_t size_type; - typedef int block_width_type; // gps + namespace dynamic_bitset_count_impl { - BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits::digits)); - BOOST_STATIC_CONSTANT(size_type, npos = static_cast(-1)); + typedef unsigned char byte_type; + enum mode { access_by_bytes, access_by_blocks }; -public: + template struct mode_to_type {}; - // A proxy class to simulate lvalues of bit type. - // Shouldn't it be private? [gps] + // the table: wrapped in a class template, so + // that it is only instantiated if/when needed // - class reference - { - friend class dynamic_bitset; + template + struct count_table { static const byte_type table[]; }; + template <> + struct count_table { /* no table */ }; - // 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 + const unsigned int table_width = 8; + template + const byte_type count_table::table[] = + { + // Automatically generated by GPTableGen.exe v.1.0 + // + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 + }; - public: - // copy constructor: compiler generated + // overload for access by bytes + // - operator bool() const { return (m_block & m_mask) != 0; } - bool operator~() const { return (m_block & m_mask) == 0; } + template + inline std::size_t do_count(Iterator first, std::size_t length, + int /*dummy param*/, + mode_to_type* ) + { + std::size_t num = 0; + if (length) + { + const byte_type * p = object_representation(&*first); + length *= sizeof(*first); - reference& flip() { do_flip(); return *this; } + do { + num += count_table<>::table[*p]; + ++p; + --length; - 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] + } while (length); + } - 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; } + return num; + } - 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(); } + // overload for access by blocks + // + template + inline std::size_t do_count(Iterator first, std::size_t length, ValueType, + mode_to_type*) + { + std::size_t num = 0; + while (length){ + + ValueType value = *first; + while (value) { + num += count_table<>::table[value & ((1u<>= table_width; + } + + ++first; + --length; + } + + return num; + } + + + } // dynamic_bitset_count_impl + // ------------------------------------------------------- + + + // Some library implementations simply return a dummy + // value such as + // + // size_type(-1) / sizeof(T) + // + // from vector<>::max_size. This tries to get out more + // meaningful info. + // + template + typename T::size_type vector_max_size_workaround(const T & v) { + + typedef typename T::allocator_type allocator_type; + + const typename allocator_type::size_type alloc_max = + v.get_allocator().max_size(); + const typename T::size_type container_max = v.max_size(); + + return alloc_max < container_max? + alloc_max : + container_max; + } + + // for static_asserts + template + struct dynamic_bitset_allowed_block_type { + enum { value = (T(-1) > 0) }; // ensure T has no sign }; - 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; } + template <> + struct dynamic_bitset_allowed_block_type { + enum { value = false }; }; -}; -#if BOOST_WORKAROUND( __IBMCPP__, <=600 ) - -// Workaround for IBM's AIX platform. -// See http://comments.gmane.org/gmane.comp.lib.boost.user/15331 - -template -dynamic_bitset::block_width_type const -dynamic_bitset::bits_per_block; - -template -dynamic_bitset::block_width_type const -dynamic_bitset::ulong_width; - -#endif - -// 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 -// NOTE: Digital Mars wants the same template parameter names -// here and in the definition! [last tested: 8.48.10] -// -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 detail } // namespace boost - -#undef BOOST_BITSET_CHAR - #endif // include guard