--- 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_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
-#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
-
-#include <cassert>
-#include <string>
-#include <stdexcept> // for std::overflow_error
-#include <algorithm> // for std::swap, std::min, std::copy, std::fill
-#include <vector>
-#include <climits> // for CHAR_BIT
-
-#include "boost/dynamic_bitset/config.hpp"
+#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
+#define BOOST_DETAIL_DYNAMIC_BITSET_HPP
-#ifndef BOOST_NO_STD_LOCALE
-# include <locale> // G.P.S
-#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" // used by find_first/next
+#include <cstddef> // for std::size_t
+#include "boost/config.hpp"
+#include "boost/detail/workaround.hpp"
+//#include "boost/static_assert.hpp" // gps
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
- <typename Block = unsigned long, typename Allocator = std::allocator<Block> >
-# else
- <typename Block, typename Allocator>
-# 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<Block>::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<Block>::digits));
- BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
-
-
-public:
-
- // A proxy class to simulate lvalues of bit type.
- // Shouldn't it be private? [gps]
- //
- class reference
- {
- friend class dynamic_bitset<Block, Allocator>;
-
-
- // the one and only non-copy ctor
- reference(block_type & b, int pos)
- :m_block(b), m_mask(block_type(1) << pos)
- {}
+ namespace detail {
- 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>>.
+ // Gives (read-)access to the object representation
+ // of an object of type T (3.9p4). CANNOT be used
+ // on a base sub-object
//
- // 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, alloc);
- }
-
- 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)
+ template <typename T>
+ inline const unsigned char * object_representation (T* p)
{
- init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::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 <typename BlockInputIterator>
- 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 <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);
- }
+ return static_cast<const unsigned char *>(static_cast<const void *>(p));
}
- // 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;
+ // ------- count function implementation --------------
- 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 <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);
-
+ namespace dynamic_bitset_count_impl {
- 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<int>(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,
- const Allocator& alloc)
- {
- assert(pos <= s.size());
-
- typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
- typedef typename StrT::traits_type Tr;
+ typedef unsigned char byte_type;
- 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;
-
+ enum mode { access_by_bytes, access_by_blocks };
- 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; }
- };
-
-};
-
-#if BOOST_WORKAROUND( __IBMCPP__, <=600 )
-
-// Workaround for IBM's AIX platform.
-// See http://comments.gmane.org/gmane.comp.lib.boost.user/15331
-
-template<typename Block, typename Allocator>
-dynamic_bitset<Block, Allocator>::block_width_type const
-dynamic_bitset<Block, Allocator>::bits_per_block;
-
-template<typename Block, typename Allocator>
-dynamic_bitset<Block, Allocator>::block_width_type const
-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 <mode> struct mode_to_type {};
-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
-// NOTE: Digital Mars wants the same template parameter names
-// here and in the definition! [last tested: 8.48.10]
-//
-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);
-
-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);
-#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);
+ // the table: wrapped in a class template, so
+ // that it is only instantiated if/when needed
+ //
+ template <bool dummy_name = true>
+ struct count_table { static const byte_type table[]; };
-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); // gps
-
-template <typename Block, typename Allocator, typename BlockOutputIterator>
-void
-to_block_range(const dynamic_bitset<Block, Allocator>& b,
- BlockOutputIterator result);
-
-
-// gps - check docs with Jeremy
-//
-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()); //[gps]
-}
-
-//=============================================================================
-// dynamic_bitset implementation
+ template <>
+ struct count_table<false> { /* no table */ };
-//-----------------------------------------------------------------------------
-// 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(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<size_type>(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<block_type>(value);
- }
- else {
- for(size_type i = 0; value != 0; ++i) {
-
- m_bits[i] = static_cast<block_type>(value);
- value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);
- }
- }
-
-}
-
-// 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) // [gps]
-{
-
-}
-
-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)
-{
-#if 0 // gps
- dynamic_bitset<Block, Allocator> tmp(b);
- this->swap(tmp);
- return *this;
-#else
- m_bits = b.m_bits;
- m_num_bits = b.m_num_bits;
- return *this;
-#endif
-}
-
-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) [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 <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)
-{
- resize(size() + 1);
- set(size() - 1, bit);
-}
-
-template <typename Block, typename Allocator>
-void dynamic_bitset<Block, Allocator>::
-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());
-
-}
+ const unsigned int table_width = 8;
+ template <bool b>
+ const byte_type count_table<b>::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
+ };
-//-----------------------------------------------------------------------------
-// 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;
-}
-
+ // overload for access by bytes
+ //
-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)
-{
- // [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 <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 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 Iterator>
+ inline std::size_t do_count(Iterator first, std::size_t length,
+ int /*dummy param*/,
+ mode_to_type<access_by_bytes>* )
+ {
+ std::size_t num = 0;
+ if (length)
+ {
+ const byte_type * p = object_representation(&*first);
+ length *= sizeof(*first);
-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;
-}
+ do {
+ num += count_table<>::table[*p];
+ ++p;
+ --length;
-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;
-}
-
-
-/*
+ } while (length);
+ }
-The following is the straightforward implementation of count(), which
-we leave here in a comment for documentation purposes.
-
-template <typename Block, typename Allocator>
-typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::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<<X elements where table[N] is the number of '1' digits
- in the binary representation of N (i.e. in our X bits).
+ return num;
+ }
- In this implementation X is 8 (but can be easily changed: you
- just have to modify the definition of table_width and shrink/enlarge
- the table accordingly - it could be useful, for instance, to expand
- the table to 512 elements on an implementation with 9-bit bytes) and
- the internal array of blocks is seen, if possible, as an array of bytes.
- In practice the "reinterpretation" as array of bytes is possible if and
- only if X >= 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 Block, typename Allocator>
-typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::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<m*>(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);
-
- }
-
-}
-
+ // overload for access by blocks
+ //
+ template <typename Iterator, typename ValueType>
+ inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
+ mode_to_type<access_by_blocks>*)
+ {
+ std::size_t num = 0;
+ while (length){
-// 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> // G.P.S.
-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) // G.P.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); // [gps]
-}
+ ValueType value = *first;
+ while (value) {
+ num += count_table<>::table[value & ((1u<<table_width) - 1)];
+ value >>= table_width;
+ }
-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
+ ++first;
+ --length;
+ }
- 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;
-
-}
+ return num;
+ }
-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::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;
-}
-
-#if 0 // gps
-template <typename Block, typename Allocator>
-inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)
-{
- assert(n <= max_size()); // PRE - G.P.S.
- m_bits.reserve(calc_num_blocks(n));
-}
-
-template <typename Block, typename Allocator>
-typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::capacity() const
-{
- // capacity is m_bits.capacity() * bits_per_block
- // unless that one overflows
- const size_type m = static_cast<size_type>(-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 <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());
- 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 <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);
-
-}
-
+ } // dynamic_bitset_count_impl
+ // -------------------------------------------------------
-//-----------------------------------------------------------------------------
-// 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); // [gps]
-}
-
-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.
-
- // 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 <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()) { // gps
-
- //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; //- 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;
- }
- }
+ // 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>
+ typename T::size_type vector_max_size_workaround(const T & v) {
- 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 <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');
+ typedef typename T::allocator_type allocator_type;
- try {
-
- typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
- typedef basic_streambuf<Ch, Tr> 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;
- }
- }
+ const typename allocator_type::size_type alloc_max =
+ v.get_allocator().max_size();
+ const typename T::size_type container_max = v.max_size();
- 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;
- }
+ return alloc_max < container_max?
+ alloc_max :
+ container_max;
}
- 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; }
+ // for static_asserts
+ template <typename T>
+ struct dynamic_bitset_allowed_block_type {
+ enum { value = (T(-1) > 0) }; // ensure T has no sign
};
-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.
+ template <>
+ struct dynamic_bitset_allowed_block_type<bool> {
+ enum { value = false };
+ };
- typedef dynamic_bitset<Block, Alloc> 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<size_type>(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 <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()? // gps
- w : b.max_size();
-
- ios_base::iostate err = ios_base::goodbit; // gps
- 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(); // 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 <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); // gps
-}
-
-
-//-----------------------------------------------------------------------------
-// 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 detail
} // namespace boost
-
-#undef BOOST_BITSET_CHAR
-
#endif // include guard