1.1 --- a/epoc32/include/stdapis/boost/detail/dynamic_bitset.hpp Wed Mar 31 12:27:01 2010 +0100
1.2 +++ b/epoc32/include/stdapis/boost/detail/dynamic_bitset.hpp Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -12,1789 +12,157 @@
1.4 // See http://www.boost.org/libs/dynamic_bitset for documentation.
1.5
1.6
1.7 +#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
1.8 +#define BOOST_DETAIL_DYNAMIC_BITSET_HPP
1.9
1.10 -#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
1.11 -#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
1.12 -
1.13 -#include <cassert>
1.14 -#include <string>
1.15 -#include <stdexcept> // for std::overflow_error
1.16 -#include <algorithm> // for std::swap, std::min, std::copy, std::fill
1.17 -#include <vector>
1.18 -#include <climits> // for CHAR_BIT
1.19 -
1.20 -#include "boost/dynamic_bitset/config.hpp"
1.21 -
1.22 -#ifndef BOOST_NO_STD_LOCALE
1.23 -# include <locale> // G.P.S
1.24 -#endif
1.25 -
1.26 -#if defined(BOOST_OLD_IOSTREAMS)
1.27 -# include <iostream.h>
1.28 -# include <ctype.h> // for isspace
1.29 -#else
1.30 -# include <istream>
1.31 -# include <ostream>
1.32 -#endif
1.33 -
1.34 -#include "boost/dynamic_bitset_fwd.hpp"
1.35 -#include "boost/detail/dynamic_bitset.hpp"
1.36 -#include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
1.37 -#include "boost/static_assert.hpp"
1.38 -#include "boost/limits.hpp"
1.39 -#include "boost/pending/lowest_bit.hpp" // used by find_first/next
1.40 +#include <cstddef> // for std::size_t
1.41 +#include "boost/config.hpp"
1.42 +#include "boost/detail/workaround.hpp"
1.43 +//#include "boost/static_assert.hpp" // gps
1.44
1.45
1.46 namespace boost {
1.47
1.48 -template
1.49 + namespace detail {
1.50
1.51 -#if defined(BOOST_MSVC) && BOOST_WORKAROUND(BOOST_MSVC, <= 1300) // 1300 == VC++ 7.0
1.52 - // VC++ (up to 7.0) wants the default arguments again
1.53 - <typename Block = unsigned long, typename Allocator = std::allocator<Block> >
1.54 -# else
1.55 - <typename Block, typename Allocator>
1.56 -# endif
1.57 + // Gives (read-)access to the object representation
1.58 + // of an object of type T (3.9p4). CANNOT be used
1.59 + // on a base sub-object
1.60 + //
1.61 + template <typename T>
1.62 + inline const unsigned char * object_representation (T* p)
1.63 + {
1.64 + return static_cast<const unsigned char *>(static_cast<const void *>(p));
1.65 + }
1.66
1.67 -class dynamic_bitset
1.68 -{
1.69 - // Portability note: member function templates are defined inside
1.70 - // this class definition to avoid problems with VC++. Similarly,
1.71 - // with the member functions of nested classes.
1.72
1.73 - BOOST_STATIC_ASSERT(detail::dynamic_bitset_allowed_block_type<Block>::value);
1.74 + // ------- count function implementation --------------
1.75
1.76 -public:
1.77 - typedef Block block_type;
1.78 - typedef Allocator allocator_type;
1.79 - typedef std::size_t size_type;
1.80 - typedef int block_width_type; // gps
1.81 + namespace dynamic_bitset_count_impl {
1.82
1.83 - BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
1.84 - BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
1.85 + typedef unsigned char byte_type;
1.86
1.87 + enum mode { access_by_bytes, access_by_blocks };
1.88
1.89 -public:
1.90 + template <mode> struct mode_to_type {};
1.91
1.92 - // A proxy class to simulate lvalues of bit type.
1.93 - // Shouldn't it be private? [gps]
1.94 + // the table: wrapped in a class template, so
1.95 + // that it is only instantiated if/when needed
1.96 //
1.97 - class reference
1.98 - {
1.99 - friend class dynamic_bitset<Block, Allocator>;
1.100 + template <bool dummy_name = true>
1.101 + struct count_table { static const byte_type table[]; };
1.102
1.103 + template <>
1.104 + struct count_table<false> { /* no table */ };
1.105
1.106 - // the one and only non-copy ctor
1.107 - reference(block_type & b, int pos)
1.108 - :m_block(b), m_mask(block_type(1) << pos)
1.109 - {}
1.110
1.111 - void operator&(); // left undefined
1.112 + const unsigned int table_width = 8;
1.113 + template <bool b>
1.114 + const byte_type count_table<b>::table[] =
1.115 + {
1.116 + // Automatically generated by GPTableGen.exe v.1.0
1.117 + //
1.118 + 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.119 + 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.120 + 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.121 + 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.122 + 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.123 + 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.124 + 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.125 + 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
1.126 + };
1.127
1.128 - public:
1.129
1.130 - // copy constructor: compiler generated
1.131 + // overload for access by bytes
1.132 + //
1.133
1.134 - operator bool() const { return (m_block & m_mask) != 0; }
1.135 - bool operator~() const { return (m_block & m_mask) == 0; }
1.136 + template <typename Iterator>
1.137 + inline std::size_t do_count(Iterator first, std::size_t length,
1.138 + int /*dummy param*/,
1.139 + mode_to_type<access_by_bytes>* )
1.140 + {
1.141 + std::size_t num = 0;
1.142 + if (length)
1.143 + {
1.144 + const byte_type * p = object_representation(&*first);
1.145 + length *= sizeof(*first);
1.146
1.147 - reference& flip() { do_flip(); return *this; }
1.148 + do {
1.149 + num += count_table<>::table[*p];
1.150 + ++p;
1.151 + --length;
1.152
1.153 - reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x
1.154 - reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
1.155 + } while (length);
1.156 + }
1.157
1.158 - reference& operator|=(bool x) { if (x) do_set(); return *this; }
1.159 - reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
1.160 - reference& operator^=(bool x) { if (x) do_flip(); return *this; }
1.161 - reference& operator-=(bool x) { if (x) do_reset(); return *this; }
1.162 + return num;
1.163 + }
1.164
1.165 - private:
1.166 - block_type & m_block;
1.167 - const block_type m_mask;
1.168
1.169 - void do_set() { m_block |= m_mask; }
1.170 - void do_reset() { m_block &= ~m_mask; }
1.171 - void do_flip() { m_block ^= m_mask; }
1.172 - void do_assign(bool x) { x? do_set() : do_reset(); }
1.173 + // overload for access by blocks
1.174 + //
1.175 + template <typename Iterator, typename ValueType>
1.176 + inline std::size_t do_count(Iterator first, std::size_t length, ValueType,
1.177 + mode_to_type<access_by_blocks>*)
1.178 + {
1.179 + std::size_t num = 0;
1.180 + while (length){
1.181 +
1.182 + ValueType value = *first;
1.183 + while (value) {
1.184 + num += count_table<>::table[value & ((1u<<table_width) - 1)];
1.185 + value >>= table_width;
1.186 + }
1.187 +
1.188 + ++first;
1.189 + --length;
1.190 + }
1.191 +
1.192 + return num;
1.193 + }
1.194 +
1.195 +
1.196 + } // dynamic_bitset_count_impl
1.197 + // -------------------------------------------------------
1.198 +
1.199 +
1.200 + // Some library implementations simply return a dummy
1.201 + // value such as
1.202 + //
1.203 + // size_type(-1) / sizeof(T)
1.204 + //
1.205 + // from vector<>::max_size. This tries to get out more
1.206 + // meaningful info.
1.207 + //
1.208 + template <typename T>
1.209 + typename T::size_type vector_max_size_workaround(const T & v) {
1.210 +
1.211 + typedef typename T::allocator_type allocator_type;
1.212 +
1.213 + const typename allocator_type::size_type alloc_max =
1.214 + v.get_allocator().max_size();
1.215 + const typename T::size_type container_max = v.max_size();
1.216 +
1.217 + return alloc_max < container_max?
1.218 + alloc_max :
1.219 + container_max;
1.220 + }
1.221 +
1.222 + // for static_asserts
1.223 + template <typename T>
1.224 + struct dynamic_bitset_allowed_block_type {
1.225 + enum { value = (T(-1) > 0) }; // ensure T has no sign
1.226 };
1.227
1.228 - typedef bool const_reference;
1.229 -
1.230 - // constructors, etc.
1.231 - explicit
1.232 - dynamic_bitset(const Allocator& alloc = Allocator());
1.233 -
1.234 - explicit
1.235 - dynamic_bitset(size_type num_bits, unsigned long value = 0,
1.236 - const Allocator& alloc = Allocator());
1.237 -
1.238 -
1.239 - // The presence of this constructor is a concession to ease of
1.240 - // use, especially for the novice user. A conversion from string
1.241 - // is, in most cases, formatting, and should be done by the standard
1.242 - // formatting convention: operator>>.
1.243 - //
1.244 - // NOTE:
1.245 - // Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
1.246 - // g++ 3.2 requires them and probably the standard will - see core issue 325
1.247 - // NOTE 2:
1.248 - // split into two constructors because of bugs in MSVC 6.0sp5 with STLport
1.249 -
1.250 - template <typename CharT, typename Traits, typename Alloc>
1.251 - dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
1.252 - typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
1.253 - typename std::basic_string<CharT, Traits, Alloc>::size_type n,
1.254 - size_type num_bits = npos,
1.255 - const Allocator& alloc = Allocator())
1.256 -
1.257 - :m_bits(alloc),
1.258 - m_num_bits(0)
1.259 - {
1.260 - init_from_string(s, pos, n, num_bits, alloc);
1.261 - }
1.262 -
1.263 - template <typename CharT, typename Traits, typename Alloc>
1.264 - explicit
1.265 - dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
1.266 - typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
1.267 -
1.268 - :m_bits(Allocator()),
1.269 - m_num_bits(0)
1.270 - {
1.271 - init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
1.272 - npos, Allocator());
1.273 - }
1.274 -
1.275 - // The first bit in *first is the least significant bit, and the
1.276 - // last bit in the block just before *last is the most significant bit.
1.277 - template <typename BlockInputIterator>
1.278 - dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
1.279 - const Allocator& alloc = Allocator())
1.280 -
1.281 - :m_bits(first, last, alloc),
1.282 - m_num_bits(m_bits.size() * bits_per_block)
1.283 - {}
1.284 -
1.285 -
1.286 - // copy constructor
1.287 - dynamic_bitset(const dynamic_bitset& b);
1.288 -
1.289 - ~dynamic_bitset();
1.290 -
1.291 - void swap(dynamic_bitset& b);
1.292 - dynamic_bitset& operator=(const dynamic_bitset& b);
1.293 -
1.294 - allocator_type get_allocator() const;
1.295 -
1.296 - // size changing operations
1.297 - void resize(size_type num_bits, bool value = false);
1.298 - void clear();
1.299 - void push_back(bool bit);
1.300 - void append(Block block);
1.301 -
1.302 - template <typename BlockInputIterator>
1.303 - void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
1.304 - {
1.305 - std::vector<Block, Allocator> v(first, last);
1.306 - m_append(v.begin(), v.end(), std::random_access_iterator_tag());
1.307 - }
1.308 - template <typename BlockInputIterator>
1.309 - void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
1.310 - {
1.311 - assert(first != last);
1.312 - block_width_type r = count_extra_bits();
1.313 - std::size_t d = boost::detail::distance(first, last);
1.314 - m_bits.reserve(num_blocks() + d);
1.315 - if (r == 0) {
1.316 - for( ; first != last; ++first)
1.317 - m_bits.push_back(*first); // could use vector<>::insert()
1.318 - }
1.319 - else {
1.320 - m_highest_block() |= (*first << r);
1.321 - do {
1.322 - Block b = *first >> (bits_per_block - r);
1.323 - ++first;
1.324 - m_bits.push_back(b | (first==last? 0 : *first << r));
1.325 - } while (first != last);
1.326 - }
1.327 - m_num_bits += bits_per_block * d;
1.328 - }
1.329 - template <typename BlockInputIterator>
1.330 - void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
1.331 - {
1.332 - if (first != last) {
1.333 - typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
1.334 - m_append(first, last, cat);
1.335 - }
1.336 - }
1.337 -
1.338 -
1.339 - // bitset operations
1.340 - dynamic_bitset& operator&=(const dynamic_bitset& b);
1.341 - dynamic_bitset& operator|=(const dynamic_bitset& b);
1.342 - dynamic_bitset& operator^=(const dynamic_bitset& b);
1.343 - dynamic_bitset& operator-=(const dynamic_bitset& b);
1.344 - dynamic_bitset& operator<<=(size_type n);
1.345 - dynamic_bitset& operator>>=(size_type n);
1.346 - dynamic_bitset operator<<(size_type n) const;
1.347 - dynamic_bitset operator>>(size_type n) const;
1.348 -
1.349 - // basic bit operations
1.350 - dynamic_bitset& set(size_type n, bool val = true);
1.351 - dynamic_bitset& set();
1.352 - dynamic_bitset& reset(size_type n);
1.353 - dynamic_bitset& reset();
1.354 - dynamic_bitset& flip(size_type n);
1.355 - dynamic_bitset& flip();
1.356 - bool test(size_type n) const;
1.357 - bool any() const;
1.358 - bool none() const;
1.359 - dynamic_bitset operator~() const;
1.360 - size_type count() const;
1.361 -
1.362 - // subscript
1.363 - reference operator[](size_type pos) {
1.364 - return reference(m_bits[block_index(pos)], bit_index(pos));
1.365 - }
1.366 - bool operator[](size_type pos) const { return test(pos); }
1.367 -
1.368 - unsigned long to_ulong() const;
1.369 -
1.370 - size_type size() const;
1.371 - size_type num_blocks() const;
1.372 - size_type max_size() const;
1.373 - bool empty() const;
1.374 -#if 0 // gps
1.375 - void reserve(size_type n);
1.376 - size_type capacity() const;
1.377 -#endif
1.378 -
1.379 - bool is_subset_of(const dynamic_bitset& a) const;
1.380 - bool is_proper_subset_of(const dynamic_bitset& a) const;
1.381 - bool intersects(const dynamic_bitset & a) const;
1.382 -
1.383 - // lookup
1.384 - size_type find_first() const;
1.385 - size_type find_next(size_type pos) const;
1.386 -
1.387 -
1.388 -#if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
1.389 - // lexicographical comparison
1.390 - template <typename B, typename A>
1.391 - friend bool operator==(const dynamic_bitset<B, A>& a,
1.392 - const dynamic_bitset<B, A>& b);
1.393 -
1.394 - template <typename B, typename A>
1.395 - friend bool operator<(const dynamic_bitset<B, A>& a,
1.396 - const dynamic_bitset<B, A>& b);
1.397 -
1.398 -
1.399 - template <typename B, typename A, typename BlockOutputIterator>
1.400 - friend void to_block_range(const dynamic_bitset<B, A>& b,
1.401 - BlockOutputIterator result);
1.402 -
1.403 - template <typename BlockIterator, typename B, typename A>
1.404 - friend void from_block_range(BlockIterator first, BlockIterator last,
1.405 - dynamic_bitset<B, A>& result);
1.406 -
1.407 -
1.408 - template <typename CharT, typename Traits, typename B, typename A>
1.409 - friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
1.410 - dynamic_bitset<B, A>& b);
1.411 -
1.412 - template <typename B, typename A, typename stringT>
1.413 - friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
1.414 -
1.415 -
1.416 -#endif
1.417 -
1.418 -
1.419 -private:
1.420 - BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
1.421 - typedef std::vector<block_type, allocator_type> buffer_type;
1.422 -
1.423 - void m_zero_unused_bits();
1.424 - bool m_check_invariants() const;
1.425 -
1.426 - size_type m_do_find_from(size_type first_block) const;
1.427 -
1.428 - block_width_type count_extra_bits() const { return bit_index(size()); }
1.429 - static size_type block_index(size_type pos) { return pos / bits_per_block; }
1.430 - static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }
1.431 - static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
1.432 -
1.433 - template <typename CharT, typename Traits, typename Alloc>
1.434 - void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
1.435 - typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
1.436 - typename std::basic_string<CharT, Traits, Alloc>::size_type n,
1.437 - size_type num_bits,
1.438 - const Allocator& alloc)
1.439 - {
1.440 - assert(pos <= s.size());
1.441 -
1.442 - typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
1.443 - typedef typename StrT::traits_type Tr;
1.444 -
1.445 - const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); // gps
1.446 - const size_type sz = ( num_bits != npos? num_bits : rlen);
1.447 - m_bits.resize(calc_num_blocks(sz));
1.448 - m_num_bits = sz;
1.449 -
1.450 -
1.451 - BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
1.452 - const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1.453 -
1.454 - const size_type m = num_bits < rlen ? num_bits : rlen; // [gps]
1.455 - typename StrT::size_type i = 0;
1.456 - for( ; i < m; ++i) {
1.457 -
1.458 - const CharT c = s[(pos + m - 1) - i];
1.459 -
1.460 - assert( Tr::eq(c, one)
1.461 - || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
1.462 -
1.463 - if (Tr::eq(c, one))
1.464 - set(i);
1.465 -
1.466 - }
1.467 -
1.468 - }
1.469 -
1.470 -BOOST_DYNAMIC_BITSET_PRIVATE:
1.471 -
1.472 - bool m_unchecked_test(size_type pos) const;
1.473 - static size_type calc_num_blocks(size_type num_bits);
1.474 -
1.475 - Block& m_highest_block();
1.476 - const Block& m_highest_block() const;
1.477 -
1.478 - buffer_type m_bits; // [gps] to be renamed
1.479 - size_type m_num_bits;
1.480 -
1.481 -
1.482 - class bit_appender;
1.483 - friend class bit_appender;
1.484 - class bit_appender {
1.485 - // helper for stream >>
1.486 - // Supplies to the lack of an efficient append at the less
1.487 - // significant end: bits are actually appended "at left" but
1.488 - // rearranged in the destructor. Everything works just as if
1.489 - // dynamic_bitset<> had an append_at_right() function (which
1.490 - // threw, in case, the same exceptions as push_back) except
1.491 - // that the function is actually called bit_appender::do_append().
1.492 - //
1.493 - dynamic_bitset & bs;
1.494 - size_type n;
1.495 - Block mask;
1.496 - Block * current;
1.497 - public:
1.498 - bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
1.499 - ~bit_appender() {
1.500 - // reverse the order of blocks, shift
1.501 - // if needed, and then resize
1.502 - //
1.503 - std::reverse(bs.m_bits.begin(), bs.m_bits.end());
1.504 - const block_width_type offs = bit_index(n);
1.505 - if (offs)
1.506 - bs >>= (bits_per_block - offs);
1.507 - bs.resize(n); // doesn't enlarge, so can't throw
1.508 - assert(bs.m_check_invariants());
1.509 - }
1.510 - inline void do_append(bool value) {
1.511 -
1.512 - if (mask == 0) {
1.513 - bs.append(Block(0));
1.514 - current = &bs.m_highest_block();
1.515 - mask = Block(1) << (bits_per_block - 1);
1.516 - }
1.517 -
1.518 - if(value)
1.519 - *current |= mask;
1.520 -
1.521 - mask /= 2;
1.522 - ++n;
1.523 - }
1.524 - size_type get_count() const { return n; }
1.525 + template <>
1.526 + struct dynamic_bitset_allowed_block_type<bool> {
1.527 + enum { value = false };
1.528 };
1.529
1.530 -};
1.531
1.532 -#if BOOST_WORKAROUND( __IBMCPP__, <=600 )
1.533 -
1.534 -// Workaround for IBM's AIX platform.
1.535 -// See http://comments.gmane.org/gmane.comp.lib.boost.user/15331
1.536 -
1.537 -template<typename Block, typename Allocator>
1.538 -dynamic_bitset<Block, Allocator>::block_width_type const
1.539 -dynamic_bitset<Block, Allocator>::bits_per_block;
1.540 -
1.541 -template<typename Block, typename Allocator>
1.542 -dynamic_bitset<Block, Allocator>::block_width_type const
1.543 -dynamic_bitset<Block, Allocator>::ulong_width;
1.544 -
1.545 -#endif
1.546 -
1.547 -// Global Functions:
1.548 -
1.549 -// comparison
1.550 -template <typename Block, typename Allocator>
1.551 -bool operator!=(const dynamic_bitset<Block, Allocator>& a,
1.552 - const dynamic_bitset<Block, Allocator>& b);
1.553 -
1.554 -template <typename Block, typename Allocator>
1.555 -bool operator<=(const dynamic_bitset<Block, Allocator>& a,
1.556 - const dynamic_bitset<Block, Allocator>& b);
1.557 -
1.558 -template <typename Block, typename Allocator>
1.559 -bool operator>(const dynamic_bitset<Block, Allocator>& a,
1.560 - const dynamic_bitset<Block, Allocator>& b);
1.561 -
1.562 -template <typename Block, typename Allocator>
1.563 -bool operator>=(const dynamic_bitset<Block, Allocator>& a,
1.564 - const dynamic_bitset<Block, Allocator>& b);
1.565 -
1.566 -// stream operators
1.567 -#ifdef BOOST_OLD_IOSTREAMS
1.568 -template <typename Block, typename Allocator>
1.569 -std::ostream& operator<<(std::ostream& os,
1.570 - const dynamic_bitset<Block, Allocator>& b);
1.571 -
1.572 -template <typename Block, typename Allocator>
1.573 -std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
1.574 -#else
1.575 -// NOTE: Digital Mars wants the same template parameter names
1.576 -// here and in the definition! [last tested: 8.48.10]
1.577 -//
1.578 -template <typename Ch, typename Tr, typename Block, typename Alloc>
1.579 -std::basic_ostream<Ch, Tr>&
1.580 -operator<<(std::basic_ostream<Ch, Tr>& os,
1.581 - const dynamic_bitset<Block, Alloc>& b);
1.582 -
1.583 -template <typename Ch, typename Tr, typename Block, typename Alloc>
1.584 -std::basic_istream<Ch, Tr>&
1.585 -operator>>(std::basic_istream<Ch, Tr>& is,
1.586 - dynamic_bitset<Block, Alloc>& b);
1.587 -#endif
1.588 -
1.589 -// bitset operations
1.590 -template <typename Block, typename Allocator>
1.591 -dynamic_bitset<Block, Allocator>
1.592 -operator&(const dynamic_bitset<Block, Allocator>& b1,
1.593 - const dynamic_bitset<Block, Allocator>& b2);
1.594 -
1.595 -template <typename Block, typename Allocator>
1.596 -dynamic_bitset<Block, Allocator>
1.597 -operator|(const dynamic_bitset<Block, Allocator>& b1,
1.598 - const dynamic_bitset<Block, Allocator>& b2);
1.599 -
1.600 -template <typename Block, typename Allocator>
1.601 -dynamic_bitset<Block, Allocator>
1.602 -operator^(const dynamic_bitset<Block, Allocator>& b1,
1.603 - const dynamic_bitset<Block, Allocator>& b2);
1.604 -
1.605 -template <typename Block, typename Allocator>
1.606 -dynamic_bitset<Block, Allocator>
1.607 -operator-(const dynamic_bitset<Block, Allocator>& b1,
1.608 - const dynamic_bitset<Block, Allocator>& b2);
1.609 -
1.610 -// namespace scope swap
1.611 -template<typename Block, typename Allocator>
1.612 -void swap(dynamic_bitset<Block, Allocator>& b1,
1.613 - dynamic_bitset<Block, Allocator>& b2);
1.614 -
1.615 -
1.616 -template <typename Block, typename Allocator, typename stringT>
1.617 -void
1.618 -to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps
1.619 -
1.620 -template <typename Block, typename Allocator, typename BlockOutputIterator>
1.621 -void
1.622 -to_block_range(const dynamic_bitset<Block, Allocator>& b,
1.623 - BlockOutputIterator result);
1.624 -
1.625 -
1.626 -// gps - check docs with Jeremy
1.627 -//
1.628 -template <typename BlockIterator, typename B, typename A>
1.629 -inline void
1.630 -from_block_range(BlockIterator first, BlockIterator last,
1.631 - dynamic_bitset<B, A>& result)
1.632 -{
1.633 - // PRE: distance(first, last) <= numblocks()
1.634 - std::copy (first, last, result.m_bits.begin()); //[gps]
1.635 -}
1.636 -
1.637 -//=============================================================================
1.638 -// dynamic_bitset implementation
1.639 -
1.640 -
1.641 -//-----------------------------------------------------------------------------
1.642 -// constructors, etc.
1.643 -
1.644 -template <typename Block, typename Allocator>
1.645 -dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
1.646 - : m_bits(alloc), m_num_bits(0)
1.647 -{
1.648 -
1.649 -}
1.650 -
1.651 -template <typename Block, typename Allocator>
1.652 -dynamic_bitset<Block, Allocator>::
1.653 -dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
1.654 - : m_bits(calc_num_blocks(num_bits), Block(0), alloc),
1.655 - m_num_bits(num_bits)
1.656 -{
1.657 -
1.658 - if (num_bits == 0)
1.659 - return;
1.660 -
1.661 - typedef unsigned long num_type;
1.662 -
1.663 - // cut off all bits in value that have pos >= num_bits, if any
1.664 - if (num_bits < static_cast<size_type>(ulong_width)) {
1.665 - const num_type mask = (num_type(1) << num_bits) - 1;
1.666 - value &= mask;
1.667 - }
1.668 -
1.669 - if (bits_per_block >= ulong_width) {
1.670 - m_bits[0] = static_cast<block_type>(value);
1.671 - }
1.672 - else {
1.673 - for(size_type i = 0; value != 0; ++i) {
1.674 -
1.675 - m_bits[i] = static_cast<block_type>(value);
1.676 - value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);
1.677 - }
1.678 - }
1.679 -
1.680 -}
1.681 -
1.682 -// copy constructor
1.683 -template <typename Block, typename Allocator>
1.684 -inline dynamic_bitset<Block, Allocator>::
1.685 -dynamic_bitset(const dynamic_bitset& b)
1.686 - : m_bits(b.m_bits), m_num_bits(b.m_num_bits) // [gps]
1.687 -{
1.688 -
1.689 -}
1.690 -
1.691 -template <typename Block, typename Allocator>
1.692 -inline dynamic_bitset<Block, Allocator>::
1.693 -~dynamic_bitset()
1.694 -{
1.695 - assert(m_check_invariants());
1.696 -}
1.697 -
1.698 -template <typename Block, typename Allocator>
1.699 -inline void dynamic_bitset<Block, Allocator>::
1.700 -swap(dynamic_bitset<Block, Allocator>& b) // no throw
1.701 -{
1.702 - std::swap(m_bits, b.m_bits);
1.703 - std::swap(m_num_bits, b.m_num_bits);
1.704 -}
1.705 -
1.706 -template <typename Block, typename Allocator>
1.707 -dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
1.708 -operator=(const dynamic_bitset<Block, Allocator>& b)
1.709 -{
1.710 -#if 0 // gps
1.711 - dynamic_bitset<Block, Allocator> tmp(b);
1.712 - this->swap(tmp);
1.713 - return *this;
1.714 -#else
1.715 - m_bits = b.m_bits;
1.716 - m_num_bits = b.m_num_bits;
1.717 - return *this;
1.718 -#endif
1.719 -}
1.720 -
1.721 -template <typename Block, typename Allocator>
1.722 -inline typename dynamic_bitset<Block, Allocator>::allocator_type
1.723 -dynamic_bitset<Block, Allocator>::get_allocator() const
1.724 -{
1.725 - return m_bits.get_allocator();
1.726 -}
1.727 -
1.728 -//-----------------------------------------------------------------------------
1.729 -// size changing operations
1.730 -
1.731 -template <typename Block, typename Allocator>
1.732 -void dynamic_bitset<Block, Allocator>::
1.733 -resize(size_type num_bits, bool value) // strong guarantee
1.734 -{
1.735 -
1.736 - const size_type old_num_blocks = num_blocks();
1.737 - const size_type required_blocks = calc_num_blocks(num_bits);
1.738 -
1.739 - const block_type v = value? ~Block(0) : Block(0);
1.740 -
1.741 - if (required_blocks != old_num_blocks) {
1.742 - m_bits.resize(required_blocks, v); // s.g. (copy) [gps]
1.743 - }
1.744 -
1.745 -
1.746 - // At this point:
1.747 - //
1.748 - // - if the buffer was shrunk, there's nothing to do, except
1.749 - // a call to m_zero_unused_bits()
1.750 - //
1.751 - // - if it it is enlarged, all the (used) bits in the new blocks have
1.752 - // the correct value, but we should also take care of the bits,
1.753 - // if any, that were 'unused bits' before enlarging: if value == true,
1.754 - // they must be set.
1.755 -
1.756 - if (value && (num_bits > m_num_bits)) {
1.757 -
1.758 - const size_type extra_bits = count_extra_bits(); // gps
1.759 - if (extra_bits) {
1.760 - assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
1.761 -
1.762 - // Set them.
1.763 - m_bits[old_num_blocks - 1] |= (v << extra_bits); // gps
1.764 - }
1.765 -
1.766 - }
1.767 -
1.768 -
1.769 -
1.770 - m_num_bits = num_bits;
1.771 - m_zero_unused_bits();
1.772 -
1.773 -}
1.774 -
1.775 -template <typename Block, typename Allocator>
1.776 -void dynamic_bitset<Block, Allocator>::
1.777 -clear() // no throw
1.778 -{
1.779 - m_bits.clear();
1.780 - m_num_bits = 0;
1.781 -}
1.782 -
1.783 -
1.784 -template <typename Block, typename Allocator>
1.785 -void dynamic_bitset<Block, Allocator>::
1.786 -push_back(bool bit)
1.787 -{
1.788 - resize(size() + 1);
1.789 - set(size() - 1, bit);
1.790 -}
1.791 -
1.792 -template <typename Block, typename Allocator>
1.793 -void dynamic_bitset<Block, Allocator>::
1.794 -append(Block value) // strong guarantee
1.795 -{
1.796 - // G.P.S. to be reviewed...
1.797 -
1.798 - const block_width_type r = count_extra_bits();
1.799 -
1.800 - if (r == 0) {
1.801 - // the buffer is empty, or all blocks are filled
1.802 - m_bits.push_back(value);
1.803 - }
1.804 - else {
1.805 - m_bits.push_back(value >> (bits_per_block - r));
1.806 - m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
1.807 - }
1.808 -
1.809 - m_num_bits += bits_per_block;
1.810 - assert(m_check_invariants());
1.811 -
1.812 -}
1.813 -
1.814 -
1.815 -//-----------------------------------------------------------------------------
1.816 -// bitset operations
1.817 -template <typename Block, typename Allocator>
1.818 -dynamic_bitset<Block, Allocator>&
1.819 -dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
1.820 -{
1.821 - assert(size() == rhs.size());
1.822 - for (size_type i = 0; i < num_blocks(); ++i)
1.823 - m_bits[i] &= rhs.m_bits[i];
1.824 - return *this;
1.825 -}
1.826 -
1.827 -template <typename Block, typename Allocator>
1.828 -dynamic_bitset<Block, Allocator>&
1.829 -dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
1.830 -{
1.831 - assert(size() == rhs.size());
1.832 - for (size_type i = 0; i < num_blocks(); ++i)
1.833 - m_bits[i] |= rhs.m_bits[i];
1.834 - //m_zero_unused_bits();
1.835 - return *this;
1.836 -}
1.837 -
1.838 -template <typename Block, typename Allocator>
1.839 -dynamic_bitset<Block, Allocator>&
1.840 -dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
1.841 -{
1.842 - assert(size() == rhs.size());
1.843 - for (size_type i = 0; i < this->num_blocks(); ++i)
1.844 - m_bits[i] ^= rhs.m_bits[i];
1.845 - //m_zero_unused_bits();
1.846 - return *this;
1.847 -}
1.848 -
1.849 -template <typename Block, typename Allocator>
1.850 -dynamic_bitset<Block, Allocator>&
1.851 -dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
1.852 -{
1.853 - assert(size() == rhs.size());
1.854 - for (size_type i = 0; i < num_blocks(); ++i)
1.855 - m_bits[i] &= ~rhs.m_bits[i];
1.856 - //m_zero_unused_bits();
1.857 - return *this;
1.858 -}
1.859 -
1.860 -//
1.861 -// NOTE:
1.862 -// Note that the 'if (r != 0)' is crucial to avoid undefined
1.863 -// behavior when the left hand operand of >> isn't promoted to a
1.864 -// wider type (because rs would be too large).
1.865 -//
1.866 -template <typename Block, typename Allocator>
1.867 -dynamic_bitset<Block, Allocator>&
1.868 -dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
1.869 -{
1.870 - if (n >= m_num_bits)
1.871 - return reset();
1.872 - //else
1.873 - if (n > 0) {
1.874 -
1.875 - size_type const last = num_blocks() - 1; // num_blocks() is >= 1
1.876 - size_type const div = n / bits_per_block; // div is <= last
1.877 - block_width_type const r = bit_index(n);
1.878 - block_type * const b = &m_bits[0];
1.879 -
1.880 - if (r != 0) {
1.881 -
1.882 - block_width_type const rs = bits_per_block - r;
1.883 -
1.884 - for (size_type i = last-div; i>0; --i) {
1.885 - b[i+div] = (b[i] << r) | (b[i-1] >> rs);
1.886 - }
1.887 - b[div] = b[0] << r;
1.888 -
1.889 - }
1.890 - else {
1.891 - for (size_type i = last-div; i>0; --i) {
1.892 - b[i+div] = b[i];
1.893 - }
1.894 - b[div] = b[0];
1.895 - }
1.896 -
1.897 -
1.898 - // zero out div blocks at the less significant end
1.899 - std::fill_n(b, div, static_cast<block_type>(0));
1.900 -
1.901 - // zero out any 1 bit that flowed into the unused part
1.902 - m_zero_unused_bits(); // thanks to Lester Gong
1.903 -
1.904 -
1.905 - }
1.906 -
1.907 - return *this;
1.908 -
1.909 -
1.910 -}
1.911 -
1.912 -
1.913 -//
1.914 -// NOTE:
1.915 -// see the comments to operator <<=
1.916 -//
1.917 -template <typename B, typename A>
1.918 -dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
1.919 - if (n >= m_num_bits) {
1.920 - return reset();
1.921 - }
1.922 - //else
1.923 - if (n>0) {
1.924 -
1.925 - size_type const last = num_blocks() - 1; // num_blocks() is >= 1
1.926 - size_type const div = n / bits_per_block; // div is <= last
1.927 - block_width_type const r = bit_index(n);
1.928 - block_type * const b = &m_bits[0];
1.929 -
1.930 -
1.931 - if (r != 0) {
1.932 -
1.933 - block_width_type const ls = bits_per_block - r;
1.934 -
1.935 - for (size_type i = div; i < last; ++i) {
1.936 - b[i-div] = (b[i] >> r) | (b[i+1] << ls);
1.937 - }
1.938 - // r bits go to zero
1.939 - b[last-div] = b[last] >> r;
1.940 - }
1.941 -
1.942 - else {
1.943 - for (size_type i = div; i <= last; ++i) {
1.944 - b[i-div] = b[i];
1.945 - }
1.946 - // note the '<=': the last iteration 'absorbs'
1.947 - // b[last-div] = b[last] >> 0;
1.948 - }
1.949 -
1.950 -
1.951 -
1.952 - // div blocks are zero filled at the most significant end
1.953 - std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
1.954 - }
1.955 -
1.956 - return *this;
1.957 -}
1.958 -
1.959 -
1.960 -template <typename Block, typename Allocator>
1.961 -dynamic_bitset<Block, Allocator>
1.962 -dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
1.963 -{
1.964 - dynamic_bitset r(*this);
1.965 - return r <<= n;
1.966 -}
1.967 -
1.968 -template <typename Block, typename Allocator>
1.969 -dynamic_bitset<Block, Allocator>
1.970 -dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
1.971 -{
1.972 - dynamic_bitset r(*this);
1.973 - return r >>= n;
1.974 -}
1.975 -
1.976 -
1.977 -//-----------------------------------------------------------------------------
1.978 -// basic bit operations
1.979 -
1.980 -template <typename Block, typename Allocator>
1.981 -dynamic_bitset<Block, Allocator>&
1.982 -dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
1.983 -{
1.984 - // [gps]
1.985 - //
1.986 - // Below we have no set(size_type) function to call when
1.987 - // value == true; instead of using a helper, I think
1.988 - // overloading set (rather than giving it a default bool
1.989 - // argument) would be more elegant.
1.990 -
1.991 - assert(pos < m_num_bits);
1.992 -
1.993 - if (val)
1.994 - m_bits[block_index(pos)] |= bit_mask(pos);
1.995 - else
1.996 - reset(pos);
1.997 -
1.998 - return *this;
1.999 -}
1.1000 -
1.1001 -template <typename Block, typename Allocator>
1.1002 -dynamic_bitset<Block, Allocator>&
1.1003 -dynamic_bitset<Block, Allocator>::set()
1.1004 -{
1.1005 - std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
1.1006 - m_zero_unused_bits();
1.1007 - return *this;
1.1008 -}
1.1009 -
1.1010 -template <typename Block, typename Allocator>
1.1011 -dynamic_bitset<Block, Allocator>&
1.1012 -dynamic_bitset<Block, Allocator>::reset(size_type pos)
1.1013 -{
1.1014 - assert(pos < m_num_bits);
1.1015 - #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
1.1016 - // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
1.1017 - // use the |^ variation instead.. <grafik>
1.1018 - m_bits[block_index(pos)] |= bit_mask(pos);
1.1019 - m_bits[block_index(pos)] ^= bit_mask(pos);
1.1020 - #else
1.1021 - m_bits[block_index(pos)] &= ~bit_mask(pos);
1.1022 - #endif
1.1023 - return *this;
1.1024 -}
1.1025 -
1.1026 -template <typename Block, typename Allocator>
1.1027 -dynamic_bitset<Block, Allocator>&
1.1028 -dynamic_bitset<Block, Allocator>::reset()
1.1029 -{
1.1030 - std::fill(m_bits.begin(), m_bits.end(), Block(0));
1.1031 - return *this;
1.1032 -}
1.1033 -
1.1034 -template <typename Block, typename Allocator>
1.1035 -dynamic_bitset<Block, Allocator>&
1.1036 -dynamic_bitset<Block, Allocator>::flip(size_type pos)
1.1037 -{
1.1038 - assert(pos < m_num_bits);
1.1039 - m_bits[block_index(pos)] ^= bit_mask(pos);
1.1040 - return *this;
1.1041 -}
1.1042 -
1.1043 -template <typename Block, typename Allocator>
1.1044 -dynamic_bitset<Block, Allocator>&
1.1045 -dynamic_bitset<Block, Allocator>::flip()
1.1046 -{
1.1047 - for (size_type i = 0; i < num_blocks(); ++i)
1.1048 - m_bits[i] = ~m_bits[i];
1.1049 - m_zero_unused_bits();
1.1050 - return *this;
1.1051 -}
1.1052 -
1.1053 -template <typename Block, typename Allocator>
1.1054 -bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
1.1055 -{
1.1056 - return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
1.1057 -}
1.1058 -
1.1059 -template <typename Block, typename Allocator>
1.1060 -bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
1.1061 -{
1.1062 - assert(pos < m_num_bits);
1.1063 - return m_unchecked_test(pos);
1.1064 -}
1.1065 -
1.1066 -template <typename Block, typename Allocator>
1.1067 -bool dynamic_bitset<Block, Allocator>::any() const
1.1068 -{
1.1069 - for (size_type i = 0; i < num_blocks(); ++i)
1.1070 - if (m_bits[i])
1.1071 - return true;
1.1072 - return false;
1.1073 -}
1.1074 -
1.1075 -template <typename Block, typename Allocator>
1.1076 -inline bool dynamic_bitset<Block, Allocator>::none() const
1.1077 -{
1.1078 - return !any();
1.1079 -}
1.1080 -
1.1081 -template <typename Block, typename Allocator>
1.1082 -dynamic_bitset<Block, Allocator>
1.1083 -dynamic_bitset<Block, Allocator>::operator~() const
1.1084 -{
1.1085 - dynamic_bitset b(*this);
1.1086 - b.flip();
1.1087 - return b;
1.1088 -}
1.1089 -
1.1090 -
1.1091 -/*
1.1092 -
1.1093 -The following is the straightforward implementation of count(), which
1.1094 -we leave here in a comment for documentation purposes.
1.1095 -
1.1096 -template <typename Block, typename Allocator>
1.1097 -typename dynamic_bitset<Block, Allocator>::size_type
1.1098 -dynamic_bitset<Block, Allocator>::count() const
1.1099 -{
1.1100 - size_type sum = 0;
1.1101 - for (size_type i = 0; i != this->m_num_bits; ++i)
1.1102 - if (test(i))
1.1103 - ++sum;
1.1104 - return sum;
1.1105 -}
1.1106 -
1.1107 -The actual algorithm uses a lookup table.
1.1108 -
1.1109 -
1.1110 - The basic idea of the method is to pick up X bits at a time
1.1111 - from the internal array of blocks and consider those bits as
1.1112 - the binary representation of a number N. Then, to use a table
1.1113 - of 1<<X elements where table[N] is the number of '1' digits
1.1114 - in the binary representation of N (i.e. in our X bits).
1.1115 -
1.1116 -
1.1117 - In this implementation X is 8 (but can be easily changed: you
1.1118 - just have to modify the definition of table_width and shrink/enlarge
1.1119 - the table accordingly - it could be useful, for instance, to expand
1.1120 - the table to 512 elements on an implementation with 9-bit bytes) and
1.1121 - the internal array of blocks is seen, if possible, as an array of bytes.
1.1122 - In practice the "reinterpretation" as array of bytes is possible if and
1.1123 - only if X >= CHAR_BIT and Block has no padding bits (that would be counted
1.1124 - together with the "real ones" if we saw the array as array of bytes).
1.1125 - Otherwise we simply 'extract' X bits at a time from each Block.
1.1126 -
1.1127 -*/
1.1128 -
1.1129 -
1.1130 -template <typename Block, typename Allocator>
1.1131 -typename dynamic_bitset<Block, Allocator>::size_type
1.1132 -dynamic_bitset<Block, Allocator>::count() const
1.1133 -{
1.1134 - using namespace detail::dynamic_bitset_count_impl;
1.1135 -
1.1136 - const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);
1.1137 - const bool enough_table_width = table_width >= CHAR_BIT;
1.1138 -
1.1139 - typedef mode_to_type< (no_padding && enough_table_width ?
1.1140 - access_by_bytes : access_by_blocks) > m;
1.1141 -
1.1142 - return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(0));
1.1143 -
1.1144 -}
1.1145 -
1.1146 -
1.1147 -//-----------------------------------------------------------------------------
1.1148 -// conversions
1.1149 -
1.1150 -
1.1151 -template <typename B, typename A, typename stringT>
1.1152 -void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
1.1153 - bool dump_all)
1.1154 -{
1.1155 - typedef typename stringT::traits_type Tr;
1.1156 - typedef typename stringT::value_type Ch;
1.1157 -
1.1158 - BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
1.1159 - const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1.1160 - const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1.1161 -
1.1162 - // Note that this function may access (when
1.1163 - // dump_all == true) bits beyond position size() - 1
1.1164 -
1.1165 - typedef typename dynamic_bitset<B, A>::size_type size_type;
1.1166 -
1.1167 - const size_type len = dump_all?
1.1168 - dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
1.1169 - b.size();
1.1170 - s.assign (len, zero);
1.1171 -
1.1172 - for (size_type i = 0; i < len; ++i) {
1.1173 - if (b.m_unchecked_test(i))
1.1174 - Tr::assign(s[len - 1 - i], one);
1.1175 -
1.1176 - }
1.1177 -
1.1178 -}
1.1179 -
1.1180 -
1.1181 -// A comment similar to the one about the constructor from
1.1182 -// basic_string can be done here. Thanks to James Kanze for
1.1183 -// making me (Gennaro) realize this important separation of
1.1184 -// concerns issue, as well as many things about i18n.
1.1185 -//
1.1186 -template <typename Block, typename Allocator, typename stringT> // G.P.S.
1.1187 -inline void
1.1188 -to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
1.1189 -{
1.1190 - to_string_helper(b, s, false);
1.1191 -}
1.1192 -
1.1193 -
1.1194 -// Differently from to_string this function dumps out
1.1195 -// every bit of the internal representation (may be
1.1196 -// useful for debugging purposes)
1.1197 -//
1.1198 -template <typename B, typename A, typename stringT>
1.1199 -inline void
1.1200 -dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.
1.1201 -{
1.1202 - to_string_helper(b, s, true /* =dump_all*/);
1.1203 -}
1.1204 -
1.1205 -template <typename Block, typename Allocator, typename BlockOutputIterator>
1.1206 -inline void
1.1207 -to_block_range(const dynamic_bitset<Block, Allocator>& b,
1.1208 - BlockOutputIterator result)
1.1209 -{
1.1210 - // note how this copies *all* bits, including the
1.1211 - // unused ones in the last block (which are zero)
1.1212 - std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]
1.1213 -}
1.1214 -
1.1215 -template <typename Block, typename Allocator>
1.1216 -unsigned long dynamic_bitset<Block, Allocator>::
1.1217 -to_ulong() const
1.1218 -{
1.1219 -
1.1220 - if (m_num_bits == 0)
1.1221 - return 0; // convention
1.1222 -
1.1223 - // Check for overflows. This may be a performance burden on very
1.1224 - // large bitsets but is required by the specification, sorry
1.1225 - if (find_next(ulong_width - 1) != npos)
1.1226 - throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
1.1227 -
1.1228 -
1.1229 - // Ok, from now on we can be sure there's no "on" bit beyond
1.1230 - // the allowed positions
1.1231 -
1.1232 - if (bits_per_block >= ulong_width)
1.1233 - return m_bits[0];
1.1234 -
1.1235 -
1.1236 - size_type last_block = block_index((std::min)(m_num_bits-1, // gps
1.1237 - (size_type)(ulong_width-1)));
1.1238 - unsigned long result = 0;
1.1239 - for (size_type i = 0; i <= last_block; ++i) {
1.1240 -
1.1241 - assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps
1.1242 -
1.1243 - unsigned long piece = m_bits[i];
1.1244 - result |= (piece << (bits_per_block * i));
1.1245 - }
1.1246 -
1.1247 - return result;
1.1248 -
1.1249 -}
1.1250 -
1.1251 -
1.1252 -template <typename Block, typename Allocator>
1.1253 -inline typename dynamic_bitset<Block, Allocator>::size_type
1.1254 -dynamic_bitset<Block, Allocator>::size() const
1.1255 -{
1.1256 - return m_num_bits;
1.1257 -}
1.1258 -
1.1259 -template <typename Block, typename Allocator>
1.1260 -inline typename dynamic_bitset<Block, Allocator>::size_type
1.1261 -dynamic_bitset<Block, Allocator>::num_blocks() const
1.1262 -{
1.1263 - return m_bits.size();
1.1264 -}
1.1265 -
1.1266 -template <typename Block, typename Allocator>
1.1267 -inline typename dynamic_bitset<Block, Allocator>::size_type
1.1268 -dynamic_bitset<Block, Allocator>::max_size() const
1.1269 -{
1.1270 - // Semantics of vector<>::max_size() aren't very clear
1.1271 - // (see lib issue 197) and many library implementations
1.1272 - // simply return dummy values, _unrelated_ to the underlying
1.1273 - // allocator.
1.1274 - //
1.1275 - // Given these problems, I was tempted to not provide this
1.1276 - // function at all but the user could need it if he provides
1.1277 - // his own allocator.
1.1278 - //
1.1279 -
1.1280 - const size_type m = detail::vector_max_size_workaround(m_bits);
1.1281 -
1.1282 - return m <= (size_type(-1)/bits_per_block) ?
1.1283 - m * bits_per_block :
1.1284 - size_type(-1);
1.1285 -}
1.1286 -
1.1287 -template <typename Block, typename Allocator>
1.1288 -inline bool dynamic_bitset<Block, Allocator>::empty() const
1.1289 -{
1.1290 - return size() == 0;
1.1291 -}
1.1292 -
1.1293 -#if 0 // gps
1.1294 -template <typename Block, typename Allocator>
1.1295 -inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)
1.1296 -{
1.1297 - assert(n <= max_size()); // PRE - G.P.S.
1.1298 - m_bits.reserve(calc_num_blocks(n));
1.1299 -}
1.1300 -
1.1301 -template <typename Block, typename Allocator>
1.1302 -typename dynamic_bitset<Block, Allocator>::size_type
1.1303 -dynamic_bitset<Block, Allocator>::capacity() const
1.1304 -{
1.1305 - // capacity is m_bits.capacity() * bits_per_block
1.1306 - // unless that one overflows
1.1307 - const size_type m = static_cast<size_type>(-1);
1.1308 - const size_type q = m / bits_per_block;
1.1309 -
1.1310 - const size_type c = m_bits.capacity();
1.1311 -
1.1312 - return c <= q ?
1.1313 - c * bits_per_block :
1.1314 - m;
1.1315 -}
1.1316 -#endif
1.1317 -
1.1318 -template <typename Block, typename Allocator>
1.1319 -bool dynamic_bitset<Block, Allocator>::
1.1320 -is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1.1321 -{
1.1322 - assert(size() == a.size());
1.1323 - for (size_type i = 0; i < num_blocks(); ++i)
1.1324 - if (m_bits[i] & ~a.m_bits[i])
1.1325 - return false;
1.1326 - return true;
1.1327 -}
1.1328 -
1.1329 -template <typename Block, typename Allocator>
1.1330 -bool dynamic_bitset<Block, Allocator>::
1.1331 -is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1.1332 -{
1.1333 - assert(size() == a.size());
1.1334 - bool proper = false;
1.1335 - for (size_type i = 0; i < num_blocks(); ++i) {
1.1336 - Block bt = m_bits[i], ba = a.m_bits[i];
1.1337 - if (ba & ~bt)
1.1338 - proper = true;
1.1339 - if (bt & ~ba)
1.1340 - return false;
1.1341 - }
1.1342 - return proper;
1.1343 -}
1.1344 -
1.1345 -template <typename Block, typename Allocator>
1.1346 -bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
1.1347 -{
1.1348 - size_type common_blocks = num_blocks() < b.num_blocks()
1.1349 - ? num_blocks() : b.num_blocks();
1.1350 -
1.1351 - for(size_type i = 0; i < common_blocks; ++i) {
1.1352 - if(m_bits[i] & b.m_bits[i])
1.1353 - return true;
1.1354 - }
1.1355 - return false;
1.1356 -}
1.1357 -
1.1358 -// --------------------------------
1.1359 -// lookup
1.1360 -
1.1361 -
1.1362 -// look for the first bit "on", starting
1.1363 -// from the block with index first_block
1.1364 -//
1.1365 -template <typename Block, typename Allocator>
1.1366 -typename dynamic_bitset<Block, Allocator>::size_type
1.1367 -dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
1.1368 -{
1.1369 - size_type i = first_block;
1.1370 -
1.1371 - // skip null blocks
1.1372 - while (i < num_blocks() && m_bits[i] == 0)
1.1373 - ++i;
1.1374 -
1.1375 - if (i >= num_blocks())
1.1376 - return npos; // not found
1.1377 -
1.1378 - return i * bits_per_block + boost::lowest_bit(m_bits[i]);
1.1379 -
1.1380 -}
1.1381 -
1.1382 -
1.1383 -template <typename Block, typename Allocator>
1.1384 -typename dynamic_bitset<Block, Allocator>::size_type
1.1385 -dynamic_bitset<Block, Allocator>::find_first() const
1.1386 -{
1.1387 - return m_do_find_from(0);
1.1388 -}
1.1389 -
1.1390 -
1.1391 -template <typename Block, typename Allocator>
1.1392 -typename dynamic_bitset<Block, Allocator>::size_type
1.1393 -dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
1.1394 -{
1.1395 -
1.1396 - const size_type sz = size();
1.1397 - if (pos >= (sz-1) || sz == 0)
1.1398 - return npos;
1.1399 -
1.1400 - ++pos;
1.1401 -
1.1402 - const size_type blk = block_index(pos);
1.1403 - const block_width_type ind = bit_index(pos);
1.1404 -
1.1405 - // mask out bits before pos
1.1406 - const Block fore = m_bits[blk] & ( ~Block(0) << ind );
1.1407 -
1.1408 - return fore?
1.1409 - blk * bits_per_block + lowest_bit(fore)
1.1410 - :
1.1411 - m_do_find_from(blk + 1);
1.1412 -
1.1413 -}
1.1414 -
1.1415 -
1.1416 -
1.1417 -//-----------------------------------------------------------------------------
1.1418 -// comparison
1.1419 -
1.1420 -template <typename Block, typename Allocator>
1.1421 -bool operator==(const dynamic_bitset<Block, Allocator>& a,
1.1422 - const dynamic_bitset<Block, Allocator>& b)
1.1423 -{
1.1424 - return (a.m_num_bits == b.m_num_bits)
1.1425 - && (a.m_bits == b.m_bits); // [gps]
1.1426 -}
1.1427 -
1.1428 -template <typename Block, typename Allocator>
1.1429 -inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
1.1430 - const dynamic_bitset<Block, Allocator>& b)
1.1431 -{
1.1432 - return !(a == b);
1.1433 -}
1.1434 -
1.1435 -template <typename Block, typename Allocator>
1.1436 -bool operator<(const dynamic_bitset<Block, Allocator>& a,
1.1437 - const dynamic_bitset<Block, Allocator>& b)
1.1438 -{
1.1439 - assert(a.size() == b.size());
1.1440 - typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
1.1441 -
1.1442 - if (a.size() == 0)
1.1443 - return false;
1.1444 -
1.1445 - // Since we are storing the most significant bit
1.1446 - // at pos == size() - 1, we need to do the comparisons in reverse.
1.1447 -
1.1448 - // Compare a block at a time
1.1449 - for (size_type i = a.num_blocks() - 1; i > 0; --i)
1.1450 - if (a.m_bits[i] < b.m_bits[i])
1.1451 - return true;
1.1452 - else if (a.m_bits[i] > b.m_bits[i])
1.1453 - return false;
1.1454 -
1.1455 - if (a.m_bits[0] < b.m_bits[0])
1.1456 - return true;
1.1457 - else
1.1458 - return false;
1.1459 -}
1.1460 -
1.1461 -template <typename Block, typename Allocator>
1.1462 -inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
1.1463 - const dynamic_bitset<Block, Allocator>& b)
1.1464 -{
1.1465 - return !(a > b);
1.1466 -}
1.1467 -
1.1468 -template <typename Block, typename Allocator>
1.1469 -inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
1.1470 - const dynamic_bitset<Block, Allocator>& b)
1.1471 -{
1.1472 - return b < a;
1.1473 -}
1.1474 -
1.1475 -template <typename Block, typename Allocator>
1.1476 -inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
1.1477 - const dynamic_bitset<Block, Allocator>& b)
1.1478 -{
1.1479 - return !(a < b);
1.1480 -}
1.1481 -
1.1482 -//-----------------------------------------------------------------------------
1.1483 -// stream operations
1.1484 -
1.1485 -#ifdef BOOST_OLD_IOSTREAMS
1.1486 -template < typename Block, typename Alloc>
1.1487 -std::ostream&
1.1488 -operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
1.1489 -{
1.1490 - // NOTE: since this is aimed at "classic" iostreams, exception
1.1491 - // masks on the stream are not supported. The library that
1.1492 - // ships with gcc 2.95 has an exceptions() member function but
1.1493 - // nothing is actually implemented; not even the class ios::failure.
1.1494 -
1.1495 - using namespace std;
1.1496 -
1.1497 - const ios::iostate ok = ios::goodbit;
1.1498 - ios::iostate err = ok;
1.1499 -
1.1500 - if (os.opfx()) { // gps
1.1501 -
1.1502 - //try
1.1503 - typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
1.1504 -
1.1505 - const bitsetsize_type sz = b.size();
1.1506 - std::streambuf * buf = os.rdbuf();
1.1507 - size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0)
1.1508 - || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; //- gps
1.1509 -
1.1510 - const char fill_char = os.fill();
1.1511 - const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
1.1512 -
1.1513 - // if needed fill at left; pad is decresed along the way
1.1514 - if (adjustfield != ios::left) {
1.1515 - for (; 0 < npad; --npad)
1.1516 - if (fill_char != buf->sputc(fill_char)) {
1.1517 - err |= ios::failbit; // gps
1.1518 - break;
1.1519 - }
1.1520 - }
1.1521 -
1.1522 - if (err == ok) {
1.1523 - // output the bitset
1.1524 - for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
1.1525 - const char dig = b.test(i-1)? '1' : '0';
1.1526 - if (EOF == buf->sputc(dig)) { // ok?? gps
1.1527 - err |= ios::failbit;
1.1528 - break;
1.1529 - }
1.1530 - }
1.1531 - }
1.1532 -
1.1533 - if (err == ok) {
1.1534 - // if needed fill at right
1.1535 - for (; 0 < npad; --npad) {
1.1536 - if (fill_char != buf->sputc(fill_char)) {
1.1537 - err |= ios::failbit;
1.1538 - break;
1.1539 - }
1.1540 - }
1.1541 - }
1.1542 -
1.1543 - os.osfx();
1.1544 - os.width(0);
1.1545 -
1.1546 - } // if opfx
1.1547 -
1.1548 - if(err != ok)
1.1549 - os.setstate(err); // assume this does NOT throw - gps
1.1550 - return os;
1.1551 -
1.1552 -}
1.1553 -#else
1.1554 -
1.1555 -template <typename Ch, typename Tr, typename Block, typename Alloc>
1.1556 -std::basic_ostream<Ch, Tr>&
1.1557 -operator<<(std::basic_ostream<Ch, Tr>& os,
1.1558 - const dynamic_bitset<Block, Alloc>& b)
1.1559 -{
1.1560 -
1.1561 - using namespace std;
1.1562 -
1.1563 - const ios_base::iostate ok = ios_base::goodbit;
1.1564 - ios_base::iostate err = ok;
1.1565 -
1.1566 - typename basic_ostream<Ch, Tr>::sentry cerberos(os);
1.1567 - if (cerberos) {
1.1568 -
1.1569 - BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
1.1570 - const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1.1571 - const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1.1572 -
1.1573 - try {
1.1574 -
1.1575 - typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
1.1576 - typedef basic_streambuf<Ch, Tr> buffer_type; // G.P.S.
1.1577 -
1.1578 - buffer_type * buf = os.rdbuf();
1.1579 - size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0)
1.1580 - || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); //- G.P.S.
1.1581 -
1.1582 - const Ch fill_char = os.fill();
1.1583 - const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
1.1584 -
1.1585 - // if needed fill at left; pad is decresed along the way
1.1586 - if (adjustfield != ios_base::left) {
1.1587 - for (; 0 < npad; --npad)
1.1588 - if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1.1589 - err |= ios_base::failbit; // G.P.S.
1.1590 - break;
1.1591 - }
1.1592 - }
1.1593 -
1.1594 - if (err == ok) {
1.1595 - // output the bitset
1.1596 - for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
1.1597 - typename buffer_type::int_type
1.1598 - ret = buf->sputc(b.test(i-1)? one : zero);
1.1599 - if (Tr::eq_int_type(Tr::eof(), ret)) {
1.1600 - err |= ios_base::failbit;
1.1601 - break;
1.1602 - }
1.1603 - }
1.1604 - }
1.1605 -
1.1606 - if (err == ok) {
1.1607 - // if needed fill at right
1.1608 - for (; 0 < npad; --npad) {
1.1609 - if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1.1610 - err |= ios_base::failbit;
1.1611 - break;
1.1612 - }
1.1613 - }
1.1614 - }
1.1615 -
1.1616 -
1.1617 - os.width(0);
1.1618 -
1.1619 - } catch (...) { // see std 27.6.1.1/4
1.1620 - bool rethrow = false;
1.1621 - try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
1.1622 -
1.1623 - if (rethrow)
1.1624 - throw;
1.1625 - }
1.1626 - }
1.1627 -
1.1628 - if(err != ok)
1.1629 - os.setstate(err); // may throw exception
1.1630 - return os;
1.1631 -
1.1632 -}
1.1633 -#endif
1.1634 -
1.1635 -
1.1636 -#ifdef BOOST_OLD_IOSTREAMS
1.1637 -
1.1638 - // gps - A sentry-like class that calls isfx in its
1.1639 - // destructor. Necessary because bit_appender::do_append may throw.
1.1640 - class pseudo_sentry {
1.1641 - std::istream & m_r;
1.1642 - const bool m_ok;
1.1643 - public:
1.1644 - explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
1.1645 - ~pseudo_sentry() { m_r.isfx(); }
1.1646 - operator bool() const { return m_ok; }
1.1647 - };
1.1648 -
1.1649 -template <typename Block, typename Alloc>
1.1650 -std::istream&
1.1651 -operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
1.1652 -{
1.1653 -
1.1654 -// Extractor for classic IO streams (libstdc++ < 3.0)
1.1655 -// ----------------------------------------------------//
1.1656 -// It's assumed that the stream buffer functions, and
1.1657 -// the stream's setstate() _cannot_ throw.
1.1658 -
1.1659 -
1.1660 - typedef dynamic_bitset<Block, Alloc> bitset_type;
1.1661 - typedef typename bitset_type::size_type size_type;
1.1662 -
1.1663 - std::ios::iostate err = std::ios::goodbit; // gps
1.1664 - pseudo_sentry cerberos(is); // skips whitespaces
1.1665 - if(cerberos) {
1.1666 -
1.1667 - b.clear();
1.1668 -
1.1669 - const std::streamsize w = is.width();
1.1670 - const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps
1.1671 - ? w : b.max_size();
1.1672 - typename bitset_type::bit_appender appender(b);
1.1673 - std::streambuf * buf = is.rdbuf();
1.1674 - for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
1.1675 -
1.1676 - if (c == EOF) {
1.1677 - err |= std::ios::eofbit; // G.P.S.
1.1678 - break;
1.1679 - }
1.1680 - else if (char(c) != '0' && char(c) != '1')
1.1681 - break; // non digit character
1.1682 -
1.1683 - else {
1.1684 - try {
1.1685 - //throw std::bad_alloc(); // gps
1.1686 - appender.do_append(char(c) == '1');
1.1687 - }
1.1688 - catch(...) {
1.1689 - is.setstate(std::ios::failbit); // assume this can't throw
1.1690 - throw;
1.1691 - }
1.1692 - }
1.1693 -
1.1694 - } // for
1.1695 - }
1.1696 -
1.1697 - is.width(0); // gps
1.1698 - if (b.size() == 0)
1.1699 - err |= std::ios::failbit;
1.1700 - if (err != std::ios::goodbit) // gps
1.1701 - is.setstate (err); // may throw
1.1702 -
1.1703 - return is;
1.1704 -}
1.1705 -
1.1706 -#else // BOOST_OLD_IOSTREAMS
1.1707 -
1.1708 -template <typename Ch, typename Tr, typename Block, typename Alloc>
1.1709 -std::basic_istream<Ch, Tr>&
1.1710 -operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
1.1711 -{
1.1712 -
1.1713 - using namespace std;
1.1714 -
1.1715 - typedef dynamic_bitset<Block, Alloc> bitset_type;
1.1716 - typedef typename bitset_type::size_type size_type;
1.1717 -
1.1718 - const streamsize w = is.width();
1.1719 - const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? // gps
1.1720 - w : b.max_size();
1.1721 -
1.1722 - ios_base::iostate err = ios_base::goodbit; // gps
1.1723 - typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
1.1724 - if(cerberos) {
1.1725 -
1.1726 - // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
1.1727 - BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
1.1728 - const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1.1729 - const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1.1730 -
1.1731 - b.clear();
1.1732 - try {
1.1733 - typename bitset_type::bit_appender appender(b);
1.1734 - basic_streambuf <Ch, Tr> * buf = is.rdbuf();
1.1735 - typename Tr::int_type c = buf->sgetc(); // G.P.S.
1.1736 - for( ; appender.get_count() < limit; c = buf->snextc() ) {
1.1737 -
1.1738 - if (Tr::eq_int_type(Tr::eof(), c)) {
1.1739 - err |= ios_base::eofbit; // G.P.S.
1.1740 - break;
1.1741 - }
1.1742 - else {
1.1743 - const Ch to_c = Tr::to_char_type(c);
1.1744 - const bool is_one = Tr::eq(to_c, one);
1.1745 -
1.1746 - if (!is_one && !Tr::eq(to_c, zero))
1.1747 - break; // non digit character
1.1748 -
1.1749 - appender.do_append(is_one);
1.1750 -
1.1751 - }
1.1752 -
1.1753 - } // for
1.1754 - }
1.1755 - catch (...) {
1.1756 - // catches from stream buf, or from vector:
1.1757 - //
1.1758 - // bits_stored bits have been extracted and stored, and
1.1759 - // either no further character is extractable or we can't
1.1760 - // append to the underlying vector (out of memory) gps
1.1761 -
1.1762 - bool rethrow = false; // see std 27.6.1.1/4
1.1763 - try { is.setstate(ios_base::badbit); }
1.1764 - catch(...) { rethrow = true; }
1.1765 -
1.1766 - if (rethrow)
1.1767 - throw;
1.1768 -
1.1769 - }
1.1770 - }
1.1771 -
1.1772 - is.width(0); // gps
1.1773 - if (b.size() == 0 /*|| !cerberos*/)
1.1774 - err |= ios_base::failbit;
1.1775 - if (err != ios_base::goodbit) // gps
1.1776 - is.setstate (err); // may throw
1.1777 -
1.1778 - return is;
1.1779 -
1.1780 -}
1.1781 -
1.1782 -
1.1783 -#endif
1.1784 -
1.1785 -
1.1786 -//-----------------------------------------------------------------------------
1.1787 -// bitset operations
1.1788 -
1.1789 -template <typename Block, typename Allocator>
1.1790 -dynamic_bitset<Block, Allocator>
1.1791 -operator&(const dynamic_bitset<Block, Allocator>& x,
1.1792 - const dynamic_bitset<Block, Allocator>& y)
1.1793 -{
1.1794 - dynamic_bitset<Block, Allocator> b(x);
1.1795 - return b &= y;
1.1796 -}
1.1797 -
1.1798 -template <typename Block, typename Allocator>
1.1799 -dynamic_bitset<Block, Allocator>
1.1800 -operator|(const dynamic_bitset<Block, Allocator>& x,
1.1801 - const dynamic_bitset<Block, Allocator>& y)
1.1802 -{
1.1803 - dynamic_bitset<Block, Allocator> b(x);
1.1804 - return b |= y;
1.1805 -}
1.1806 -
1.1807 -template <typename Block, typename Allocator>
1.1808 -dynamic_bitset<Block, Allocator>
1.1809 -operator^(const dynamic_bitset<Block, Allocator>& x,
1.1810 - const dynamic_bitset<Block, Allocator>& y)
1.1811 -{
1.1812 - dynamic_bitset<Block, Allocator> b(x);
1.1813 - return b ^= y;
1.1814 -}
1.1815 -
1.1816 -template <typename Block, typename Allocator>
1.1817 -dynamic_bitset<Block, Allocator>
1.1818 -operator-(const dynamic_bitset<Block, Allocator>& x,
1.1819 - const dynamic_bitset<Block, Allocator>& y)
1.1820 -{
1.1821 - dynamic_bitset<Block, Allocator> b(x);
1.1822 - return b -= y;
1.1823 -}
1.1824 -
1.1825 -//-----------------------------------------------------------------------------
1.1826 -// namespace scope swap
1.1827 -
1.1828 -template<typename Block, typename Allocator>
1.1829 -inline void
1.1830 -swap(dynamic_bitset<Block, Allocator>& left,
1.1831 - dynamic_bitset<Block, Allocator>& right) // no throw
1.1832 -{
1.1833 - left.swap(right); // gps
1.1834 -}
1.1835 -
1.1836 -
1.1837 -//-----------------------------------------------------------------------------
1.1838 -// private (on conforming compilers) member functions
1.1839 -
1.1840 -
1.1841 -template <typename Block, typename Allocator>
1.1842 -inline typename dynamic_bitset<Block, Allocator>::size_type
1.1843 -dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
1.1844 -{
1.1845 - return num_bits / bits_per_block
1.1846 - + static_cast<int>( num_bits % bits_per_block != 0 );
1.1847 -}
1.1848 -
1.1849 -// gives a reference to the highest block
1.1850 -//
1.1851 -template <typename Block, typename Allocator>
1.1852 -inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
1.1853 -{
1.1854 - return const_cast<Block &>
1.1855 - (static_cast<const dynamic_bitset *>(this)->m_highest_block());
1.1856 -}
1.1857 -
1.1858 -// gives a const-reference to the highest block
1.1859 -//
1.1860 -template <typename Block, typename Allocator>
1.1861 -inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
1.1862 -{
1.1863 - assert(size() > 0 && num_blocks() > 0);
1.1864 - return m_bits.back();
1.1865 -}
1.1866 -
1.1867 -
1.1868 -// If size() is not a multiple of bits_per_block
1.1869 -// then not all the bits in the last block are used.
1.1870 -// This function resets the unused bits (convenient
1.1871 -// for the implementation of many member functions)
1.1872 -//
1.1873 -template <typename Block, typename Allocator>
1.1874 -inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
1.1875 -{
1.1876 - assert (num_blocks() == calc_num_blocks(m_num_bits));
1.1877 -
1.1878 - // if != 0 this is the number of bits used in the last block
1.1879 - const block_width_type extra_bits = count_extra_bits();
1.1880 -
1.1881 - if (extra_bits != 0)
1.1882 - m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
1.1883 -
1.1884 -}
1.1885 -
1.1886 -// check class invariants
1.1887 -template <typename Block, typename Allocator>
1.1888 -bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
1.1889 -{
1.1890 - const block_width_type extra_bits = count_extra_bits();
1.1891 - if (extra_bits > 0) {
1.1892 - block_type const mask = (~static_cast<Block>(0) << extra_bits);
1.1893 - if ((m_highest_block() & mask) != 0)
1.1894 - return false;
1.1895 - }
1.1896 - if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
1.1897 - return false;
1.1898 -
1.1899 - return true;
1.1900 -
1.1901 -}
1.1902 -
1.1903 + } // namespace detail
1.1904
1.1905 } // namespace boost
1.1906
1.1907 -
1.1908 -#undef BOOST_BITSET_CHAR
1.1909 -
1.1910 #endif // include guard
1.1911