epoc32/include/stdapis/boost/detail/dynamic_bitset.hpp
branchSymbian2
changeset 3 e1b950c65cb4
parent 2 2fe1408b6811
child 4 837f303aceeb
     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 +