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