1.1 --- a/epoc32/include/stdapis/boost/dynamic_bitset/dynamic_bitset.hpp Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1800 +0,0 @@
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 -