epoc32/include/stdapis/boost/dynamic_bitset/dynamic_bitset.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
williamr@2
     1
// --------------------------------------------------
williamr@2
     2
//
williamr@2
     3
// (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.
williamr@2
     4
// (C) Copyright Gennaro Prota                 2003 - 2004.
williamr@2
     5
//
williamr@2
     6
// Distributed under the Boost Software License, Version 1.0.
williamr@2
     7
//    (See accompanying file LICENSE_1_0.txt or copy at
williamr@2
     8
//          http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     9
//
williamr@2
    10
// -----------------------------------------------------------
williamr@2
    11
williamr@2
    12
//  See http://www.boost.org/libs/dynamic_bitset for documentation.
williamr@2
    13
williamr@2
    14
williamr@2
    15
williamr@2
    16
#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
williamr@2
    17
#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
williamr@2
    18
williamr@2
    19
#include <cassert>
williamr@2
    20
#include <string>
williamr@2
    21
#include <stdexcept>           // for std::overflow_error
williamr@2
    22
#include <algorithm>           // for std::swap, std::min, std::copy, std::fill
williamr@2
    23
#include <vector>
williamr@2
    24
#include <climits>             // for CHAR_BIT
williamr@2
    25
williamr@2
    26
#include "boost/dynamic_bitset/config.hpp"
williamr@2
    27
williamr@2
    28
#ifndef BOOST_NO_STD_LOCALE
williamr@2
    29
# include <locale> // G.P.S
williamr@2
    30
#endif
williamr@2
    31
williamr@2
    32
#if defined(BOOST_OLD_IOSTREAMS)
williamr@2
    33
#  include <iostream.h>
williamr@2
    34
#  include <ctype.h> // for isspace
williamr@2
    35
#else
williamr@2
    36
#  include <istream>
williamr@2
    37
#  include <ostream>
williamr@2
    38
#endif
williamr@2
    39
williamr@2
    40
#include "boost/dynamic_bitset_fwd.hpp"
williamr@2
    41
#include "boost/detail/dynamic_bitset.hpp"
williamr@2
    42
#include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
williamr@2
    43
#include "boost/static_assert.hpp"
williamr@2
    44
#include "boost/limits.hpp"
williamr@2
    45
#include "boost/pending/lowest_bit.hpp" // used by find_first/next
williamr@2
    46
williamr@2
    47
williamr@2
    48
namespace boost {
williamr@2
    49
williamr@2
    50
template
williamr@2
    51
williamr@2
    52
#if defined(BOOST_MSVC) && BOOST_WORKAROUND(BOOST_MSVC, <= 1300)  // 1300 == VC++ 7.0
williamr@2
    53
   // VC++ (up to 7.0) wants the default arguments again
williamr@2
    54
   <typename Block = unsigned long, typename Allocator = std::allocator<Block> >
williamr@2
    55
# else
williamr@2
    56
   <typename Block, typename Allocator>
williamr@2
    57
# endif
williamr@2
    58
williamr@2
    59
class dynamic_bitset
williamr@2
    60
{
williamr@2
    61
  // Portability note: member function templates are defined inside
williamr@2
    62
  // this class definition to avoid problems with VC++. Similarly,
williamr@2
    63
  // with the member functions of nested classes.
williamr@2
    64
williamr@2
    65
  BOOST_STATIC_ASSERT(detail::dynamic_bitset_allowed_block_type<Block>::value);
williamr@2
    66
williamr@2
    67
public:
williamr@2
    68
    typedef Block block_type;
williamr@2
    69
    typedef Allocator allocator_type;
williamr@2
    70
    typedef std::size_t size_type;
williamr@2
    71
    typedef int block_width_type; // gps
williamr@2
    72
williamr@2
    73
    BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
williamr@2
    74
    BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
williamr@2
    75
williamr@2
    76
williamr@2
    77
public:
williamr@2
    78
williamr@2
    79
    // A proxy class to simulate lvalues of bit type.
williamr@2
    80
    // Shouldn't it be private? [gps]
williamr@2
    81
    //
williamr@2
    82
    class reference
williamr@2
    83
    {
williamr@2
    84
        friend class dynamic_bitset<Block, Allocator>;
williamr@2
    85
williamr@2
    86
williamr@2
    87
        // the one and only non-copy ctor
williamr@2
    88
        reference(block_type & b, int pos)
williamr@2
    89
            :m_block(b), m_mask(block_type(1) << pos)
williamr@2
    90
        {}
williamr@2
    91
williamr@2
    92
        void operator&(); // left undefined
williamr@2
    93
williamr@2
    94
    public:
williamr@2
    95
williamr@2
    96
        // copy constructor: compiler generated
williamr@2
    97
williamr@2
    98
        operator bool() const { return (m_block & m_mask) != 0; }
williamr@2
    99
        bool operator~() const { return (m_block & m_mask) == 0; }
williamr@2
   100
williamr@2
   101
        reference& flip() { do_flip(); return *this; }
williamr@2
   102
williamr@2
   103
        reference& operator=(bool x)               { do_assign(x);   return *this; } // for b[i] = x
williamr@2
   104
        reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
williamr@2
   105
williamr@2
   106
        reference& operator|=(bool x) { if  (x) do_set();   return *this; }
williamr@2
   107
        reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
williamr@2
   108
        reference& operator^=(bool x) { if  (x) do_flip();  return *this; }
williamr@2
   109
        reference& operator-=(bool x) { if  (x) do_reset(); return *this; }
williamr@2
   110
williamr@2
   111
     private:
williamr@2
   112
        block_type & m_block;
williamr@2
   113
        const block_type m_mask;
williamr@2
   114
williamr@2
   115
        void do_set() { m_block |= m_mask; }
williamr@2
   116
        void do_reset() { m_block &= ~m_mask; }
williamr@2
   117
        void do_flip() { m_block ^= m_mask; }
williamr@2
   118
        void do_assign(bool x) { x? do_set() : do_reset(); }
williamr@2
   119
    };
williamr@2
   120
williamr@2
   121
    typedef bool const_reference;
williamr@2
   122
williamr@2
   123
    // constructors, etc.
williamr@2
   124
    explicit
williamr@2
   125
    dynamic_bitset(const Allocator& alloc = Allocator());
williamr@2
   126
williamr@2
   127
    explicit
williamr@2
   128
    dynamic_bitset(size_type num_bits, unsigned long value = 0,
williamr@2
   129
               const Allocator& alloc = Allocator());
williamr@2
   130
williamr@2
   131
williamr@2
   132
    // The presence of this constructor is a concession to ease of
williamr@2
   133
    // use, especially for the novice user. A conversion from string
williamr@2
   134
    // is, in most cases, formatting, and should be done by the standard
williamr@2
   135
    // formatting convention: operator>>.
williamr@2
   136
    //
williamr@2
   137
    // NOTE:
williamr@2
   138
    // Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
williamr@2
   139
    // g++ 3.2 requires them and probably the standard will - see core issue 325
williamr@2
   140
    // NOTE 2: 
williamr@2
   141
    // split into two constructors because of bugs in MSVC 6.0sp5 with STLport
williamr@2
   142
williamr@2
   143
    template <typename CharT, typename Traits, typename Alloc>
williamr@2
   144
    dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
williamr@2
   145
        typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
williamr@2
   146
        typename std::basic_string<CharT, Traits, Alloc>::size_type n,
williamr@2
   147
        size_type num_bits = npos,
williamr@2
   148
        const Allocator& alloc = Allocator())
williamr@2
   149
williamr@2
   150
    :m_bits(alloc),
williamr@2
   151
     m_num_bits(0)
williamr@2
   152
    {
williamr@2
   153
      init_from_string(s, pos, n, num_bits, alloc);
williamr@2
   154
    }
williamr@2
   155
williamr@2
   156
    template <typename CharT, typename Traits, typename Alloc>
williamr@2
   157
    explicit
williamr@2
   158
    dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
williamr@2
   159
      typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
williamr@2
   160
williamr@2
   161
    :m_bits(Allocator()),
williamr@2
   162
     m_num_bits(0)
williamr@2
   163
    {
williamr@2
   164
      init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
williamr@2
   165
                       npos, Allocator());
williamr@2
   166
    }
williamr@2
   167
williamr@2
   168
    // The first bit in *first is the least significant bit, and the
williamr@2
   169
    // last bit in the block just before *last is the most significant bit.
williamr@2
   170
    template <typename BlockInputIterator>
williamr@2
   171
    dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
williamr@2
   172
                   const Allocator& alloc = Allocator())
williamr@2
   173
williamr@2
   174
    :m_bits(first, last, alloc),
williamr@2
   175
     m_num_bits(m_bits.size() * bits_per_block)
williamr@2
   176
    {}
williamr@2
   177
williamr@2
   178
williamr@2
   179
    // copy constructor
williamr@2
   180
    dynamic_bitset(const dynamic_bitset& b);
williamr@2
   181
williamr@2
   182
    ~dynamic_bitset();
williamr@2
   183
williamr@2
   184
    void swap(dynamic_bitset& b);
williamr@2
   185
    dynamic_bitset& operator=(const dynamic_bitset& b);
williamr@2
   186
williamr@2
   187
    allocator_type get_allocator() const;
williamr@2
   188
williamr@2
   189
    // size changing operations
williamr@2
   190
    void resize(size_type num_bits, bool value = false);
williamr@2
   191
    void clear();
williamr@2
   192
    void push_back(bool bit);
williamr@2
   193
    void append(Block block);
williamr@2
   194
williamr@2
   195
    template <typename BlockInputIterator>
williamr@2
   196
    void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
williamr@2
   197
    {
williamr@2
   198
        std::vector<Block, Allocator> v(first, last);
williamr@2
   199
        m_append(v.begin(), v.end(), std::random_access_iterator_tag());
williamr@2
   200
    }
williamr@2
   201
    template <typename BlockInputIterator>
williamr@2
   202
    void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
williamr@2
   203
    {
williamr@2
   204
        assert(first != last);
williamr@2
   205
        block_width_type r = count_extra_bits();
williamr@2
   206
        std::size_t d = boost::detail::distance(first, last);
williamr@2
   207
        m_bits.reserve(num_blocks() + d);
williamr@2
   208
        if (r == 0) {
williamr@2
   209
            for( ; first != last; ++first)
williamr@2
   210
                m_bits.push_back(*first); // could use vector<>::insert()
williamr@2
   211
        }
williamr@2
   212
        else {
williamr@2
   213
            m_highest_block() |= (*first << r);
williamr@2
   214
            do {
williamr@2
   215
                Block b = *first >> (bits_per_block - r);
williamr@2
   216
                ++first;
williamr@2
   217
                m_bits.push_back(b | (first==last? 0 : *first << r));
williamr@2
   218
            } while (first != last);
williamr@2
   219
        }
williamr@2
   220
        m_num_bits += bits_per_block * d;
williamr@2
   221
    }
williamr@2
   222
    template <typename BlockInputIterator>
williamr@2
   223
    void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
williamr@2
   224
    {
williamr@2
   225
        if (first != last) {
williamr@2
   226
            typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
williamr@2
   227
            m_append(first, last, cat);
williamr@2
   228
        }
williamr@2
   229
    }
williamr@2
   230
williamr@2
   231
williamr@2
   232
    // bitset operations
williamr@2
   233
    dynamic_bitset& operator&=(const dynamic_bitset& b);
williamr@2
   234
    dynamic_bitset& operator|=(const dynamic_bitset& b);
williamr@2
   235
    dynamic_bitset& operator^=(const dynamic_bitset& b);
williamr@2
   236
    dynamic_bitset& operator-=(const dynamic_bitset& b);
williamr@2
   237
    dynamic_bitset& operator<<=(size_type n);
williamr@2
   238
    dynamic_bitset& operator>>=(size_type n);
williamr@2
   239
    dynamic_bitset operator<<(size_type n) const;
williamr@2
   240
    dynamic_bitset operator>>(size_type n) const;
williamr@2
   241
williamr@2
   242
    // basic bit operations
williamr@2
   243
    dynamic_bitset& set(size_type n, bool val = true);
williamr@2
   244
    dynamic_bitset& set();
williamr@2
   245
    dynamic_bitset& reset(size_type n);
williamr@2
   246
    dynamic_bitset& reset();
williamr@2
   247
    dynamic_bitset& flip(size_type n);
williamr@2
   248
    dynamic_bitset& flip();
williamr@2
   249
    bool test(size_type n) const;
williamr@2
   250
    bool any() const;
williamr@2
   251
    bool none() const;
williamr@2
   252
    dynamic_bitset operator~() const;
williamr@2
   253
    size_type count() const;
williamr@2
   254
williamr@2
   255
    // subscript
williamr@2
   256
    reference operator[](size_type pos) {
williamr@2
   257
        return reference(m_bits[block_index(pos)], bit_index(pos));
williamr@2
   258
    }
williamr@2
   259
    bool operator[](size_type pos) const { return test(pos); }
williamr@2
   260
williamr@2
   261
    unsigned long to_ulong() const;
williamr@2
   262
williamr@2
   263
    size_type size() const;
williamr@2
   264
    size_type num_blocks() const;
williamr@2
   265
    size_type max_size() const;
williamr@2
   266
    bool empty() const;
williamr@2
   267
#if 0 // gps
williamr@2
   268
    void reserve(size_type n);
williamr@2
   269
    size_type capacity() const;
williamr@2
   270
#endif
williamr@2
   271
williamr@2
   272
    bool is_subset_of(const dynamic_bitset& a) const;
williamr@2
   273
    bool is_proper_subset_of(const dynamic_bitset& a) const;
williamr@2
   274
    bool intersects(const dynamic_bitset & a) const;
williamr@2
   275
williamr@2
   276
    // lookup
williamr@2
   277
    size_type find_first() const;
williamr@2
   278
    size_type find_next(size_type pos) const;
williamr@2
   279
williamr@2
   280
williamr@2
   281
#if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
williamr@2
   282
    // lexicographical comparison
williamr@2
   283
    template <typename B, typename A>
williamr@2
   284
    friend bool operator==(const dynamic_bitset<B, A>& a,
williamr@2
   285
                           const dynamic_bitset<B, A>& b);
williamr@2
   286
williamr@2
   287
    template <typename B, typename A>
williamr@2
   288
    friend bool operator<(const dynamic_bitset<B, A>& a,
williamr@2
   289
                          const dynamic_bitset<B, A>& b);
williamr@2
   290
williamr@2
   291
williamr@2
   292
    template <typename B, typename A, typename BlockOutputIterator>
williamr@2
   293
    friend void to_block_range(const dynamic_bitset<B, A>& b,
williamr@2
   294
                               BlockOutputIterator result);
williamr@2
   295
williamr@2
   296
    template <typename BlockIterator, typename B, typename A>
williamr@2
   297
    friend void from_block_range(BlockIterator first, BlockIterator last,
williamr@2
   298
                                 dynamic_bitset<B, A>& result);
williamr@2
   299
williamr@2
   300
williamr@2
   301
    template <typename CharT, typename Traits, typename B, typename A>
williamr@2
   302
    friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
williamr@2
   303
                                                         dynamic_bitset<B, A>& b);
williamr@2
   304
williamr@2
   305
    template <typename B, typename A, typename stringT>
williamr@2
   306
    friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
williamr@2
   307
williamr@2
   308
williamr@2
   309
#endif
williamr@2
   310
williamr@2
   311
williamr@2
   312
private:
williamr@2
   313
    BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
williamr@2
   314
    typedef std::vector<block_type, allocator_type> buffer_type;
williamr@2
   315
williamr@2
   316
    void m_zero_unused_bits();
williamr@2
   317
    bool m_check_invariants() const;
williamr@2
   318
williamr@2
   319
    size_type m_do_find_from(size_type first_block) const;
williamr@2
   320
williamr@2
   321
    block_width_type count_extra_bits() const { return bit_index(size()); }
williamr@2
   322
    static size_type block_index(size_type pos) { return pos / bits_per_block; }
williamr@2
   323
    static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }
williamr@2
   324
    static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
williamr@2
   325
williamr@2
   326
    template <typename CharT, typename Traits, typename Alloc>
williamr@2
   327
    void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
williamr@2
   328
        typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
williamr@2
   329
        typename std::basic_string<CharT, Traits, Alloc>::size_type n,
williamr@2
   330
        size_type num_bits,
williamr@2
   331
        const Allocator& alloc)
williamr@2
   332
    {
williamr@2
   333
        assert(pos <= s.size());
williamr@2
   334
williamr@2
   335
        typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
williamr@2
   336
        typedef typename StrT::traits_type Tr;
williamr@2
   337
williamr@2
   338
        const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); // gps
williamr@2
   339
        const size_type sz = ( num_bits != npos? num_bits : rlen);
williamr@2
   340
        m_bits.resize(calc_num_blocks(sz));
williamr@2
   341
        m_num_bits = sz;
williamr@2
   342
williamr@2
   343
williamr@2
   344
        BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
williamr@2
   345
        const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2
   346
williamr@2
   347
        const size_type m = num_bits < rlen ? num_bits : rlen; // [gps]
williamr@2
   348
        typename StrT::size_type i = 0;
williamr@2
   349
        for( ; i < m; ++i) {
williamr@2
   350
williamr@2
   351
            const CharT c = s[(pos + m - 1) - i];
williamr@2
   352
williamr@2
   353
            assert( Tr::eq(c, one)
williamr@2
   354
                    || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
williamr@2
   355
williamr@2
   356
            if (Tr::eq(c, one))
williamr@2
   357
                set(i);
williamr@2
   358
williamr@2
   359
        }
williamr@2
   360
williamr@2
   361
    }
williamr@2
   362
williamr@2
   363
BOOST_DYNAMIC_BITSET_PRIVATE:
williamr@2
   364
williamr@2
   365
    bool m_unchecked_test(size_type pos) const;
williamr@2
   366
    static size_type calc_num_blocks(size_type num_bits);
williamr@2
   367
williamr@2
   368
    Block&        m_highest_block();
williamr@2
   369
    const Block&  m_highest_block() const;
williamr@2
   370
williamr@2
   371
    buffer_type m_bits; // [gps] to be renamed
williamr@2
   372
    size_type   m_num_bits;
williamr@2
   373
williamr@2
   374
williamr@2
   375
    class bit_appender;
williamr@2
   376
    friend class bit_appender;
williamr@2
   377
    class bit_appender {
williamr@2
   378
      // helper for stream >>
williamr@2
   379
      // Supplies to the lack of an efficient append at the less
williamr@2
   380
      // significant end: bits are actually appended "at left" but
williamr@2
   381
      // rearranged in the destructor. Everything works just as if
williamr@2
   382
      // dynamic_bitset<> had an append_at_right() function (which
williamr@2
   383
      // threw, in case, the same exceptions as push_back) except
williamr@2
   384
      // that the function is actually called bit_appender::do_append().
williamr@2
   385
      //
williamr@2
   386
      dynamic_bitset & bs;
williamr@2
   387
      size_type n;
williamr@2
   388
      Block mask;
williamr@2
   389
      Block * current;
williamr@2
   390
    public:
williamr@2
   391
        bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
williamr@2
   392
        ~bit_appender() {
williamr@2
   393
            // reverse the order of blocks, shift
williamr@2
   394
            // if needed, and then resize
williamr@2
   395
            //
williamr@2
   396
            std::reverse(bs.m_bits.begin(), bs.m_bits.end());
williamr@2
   397
            const block_width_type offs = bit_index(n);
williamr@2
   398
            if (offs)
williamr@2
   399
                bs >>= (bits_per_block - offs);
williamr@2
   400
            bs.resize(n); // doesn't enlarge, so can't throw
williamr@2
   401
            assert(bs.m_check_invariants());
williamr@2
   402
        }
williamr@2
   403
        inline void do_append(bool value) {
williamr@2
   404
williamr@2
   405
            if (mask == 0) {
williamr@2
   406
                bs.append(Block(0));
williamr@2
   407
                current = &bs.m_highest_block();
williamr@2
   408
                mask = Block(1) << (bits_per_block - 1);
williamr@2
   409
            }
williamr@2
   410
williamr@2
   411
            if(value)
williamr@2
   412
                *current |= mask;
williamr@2
   413
williamr@2
   414
            mask /= 2;
williamr@2
   415
            ++n;
williamr@2
   416
        }
williamr@2
   417
        size_type get_count() const { return n; }
williamr@2
   418
    };
williamr@2
   419
williamr@2
   420
};
williamr@2
   421
williamr@2
   422
#if BOOST_WORKAROUND( __IBMCPP__, <=600 )
williamr@2
   423
williamr@2
   424
// Workaround for IBM's AIX platform.
williamr@2
   425
// See http://comments.gmane.org/gmane.comp.lib.boost.user/15331
williamr@2
   426
williamr@2
   427
template<typename Block, typename Allocator>
williamr@2
   428
dynamic_bitset<Block, Allocator>::block_width_type const
williamr@2
   429
dynamic_bitset<Block, Allocator>::bits_per_block;
williamr@2
   430
williamr@2
   431
template<typename Block, typename Allocator>
williamr@2
   432
dynamic_bitset<Block, Allocator>::block_width_type const
williamr@2
   433
dynamic_bitset<Block, Allocator>::ulong_width;
williamr@2
   434
williamr@2
   435
#endif
williamr@2
   436
williamr@2
   437
// Global Functions:
williamr@2
   438
williamr@2
   439
// comparison
williamr@2
   440
template <typename Block, typename Allocator>
williamr@2
   441
bool operator!=(const dynamic_bitset<Block, Allocator>& a,
williamr@2
   442
                const dynamic_bitset<Block, Allocator>& b);
williamr@2
   443
williamr@2
   444
template <typename Block, typename Allocator>
williamr@2
   445
bool operator<=(const dynamic_bitset<Block, Allocator>& a,
williamr@2
   446
                const dynamic_bitset<Block, Allocator>& b);
williamr@2
   447
williamr@2
   448
template <typename Block, typename Allocator>
williamr@2
   449
bool operator>(const dynamic_bitset<Block, Allocator>& a,
williamr@2
   450
               const dynamic_bitset<Block, Allocator>& b);
williamr@2
   451
williamr@2
   452
template <typename Block, typename Allocator>
williamr@2
   453
bool operator>=(const dynamic_bitset<Block, Allocator>& a,
williamr@2
   454
                const dynamic_bitset<Block, Allocator>& b);
williamr@2
   455
williamr@2
   456
// stream operators
williamr@2
   457
#ifdef BOOST_OLD_IOSTREAMS
williamr@2
   458
template <typename Block, typename Allocator>
williamr@2
   459
std::ostream& operator<<(std::ostream& os,
williamr@2
   460
                         const dynamic_bitset<Block, Allocator>& b);
williamr@2
   461
williamr@2
   462
template <typename Block, typename Allocator>
williamr@2
   463
std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
williamr@2
   464
#else
williamr@2
   465
// NOTE: Digital Mars wants the same template parameter names
williamr@2
   466
//       here and in the definition! [last tested: 8.48.10]
williamr@2
   467
//
williamr@2
   468
template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2
   469
std::basic_ostream<Ch, Tr>&
williamr@2
   470
operator<<(std::basic_ostream<Ch, Tr>& os,
williamr@2
   471
           const dynamic_bitset<Block, Alloc>& b);
williamr@2
   472
williamr@2
   473
template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2
   474
std::basic_istream<Ch, Tr>&
williamr@2
   475
operator>>(std::basic_istream<Ch, Tr>& is,
williamr@2
   476
           dynamic_bitset<Block, Alloc>& b);
williamr@2
   477
#endif
williamr@2
   478
williamr@2
   479
// bitset operations
williamr@2
   480
template <typename Block, typename Allocator>
williamr@2
   481
dynamic_bitset<Block, Allocator>
williamr@2
   482
operator&(const dynamic_bitset<Block, Allocator>& b1,
williamr@2
   483
          const dynamic_bitset<Block, Allocator>& b2);
williamr@2
   484
williamr@2
   485
template <typename Block, typename Allocator>
williamr@2
   486
dynamic_bitset<Block, Allocator>
williamr@2
   487
operator|(const dynamic_bitset<Block, Allocator>& b1,
williamr@2
   488
          const dynamic_bitset<Block, Allocator>& b2);
williamr@2
   489
williamr@2
   490
template <typename Block, typename Allocator>
williamr@2
   491
dynamic_bitset<Block, Allocator>
williamr@2
   492
operator^(const dynamic_bitset<Block, Allocator>& b1,
williamr@2
   493
          const dynamic_bitset<Block, Allocator>& b2);
williamr@2
   494
williamr@2
   495
template <typename Block, typename Allocator>
williamr@2
   496
dynamic_bitset<Block, Allocator>
williamr@2
   497
operator-(const dynamic_bitset<Block, Allocator>& b1,
williamr@2
   498
          const dynamic_bitset<Block, Allocator>& b2);
williamr@2
   499
williamr@2
   500
// namespace scope swap
williamr@2
   501
template<typename Block, typename Allocator>
williamr@2
   502
void swap(dynamic_bitset<Block, Allocator>& b1,
williamr@2
   503
          dynamic_bitset<Block, Allocator>& b2);
williamr@2
   504
williamr@2
   505
williamr@2
   506
template <typename Block, typename Allocator, typename stringT>
williamr@2
   507
void
williamr@2
   508
to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps
williamr@2
   509
williamr@2
   510
template <typename Block, typename Allocator, typename BlockOutputIterator>
williamr@2
   511
void
williamr@2
   512
to_block_range(const dynamic_bitset<Block, Allocator>& b,
williamr@2
   513
               BlockOutputIterator result);
williamr@2
   514
williamr@2
   515
williamr@2
   516
// gps - check docs with Jeremy
williamr@2
   517
//
williamr@2
   518
template <typename BlockIterator, typename B, typename A>
williamr@2
   519
inline void
williamr@2
   520
from_block_range(BlockIterator first, BlockIterator last,
williamr@2
   521
                 dynamic_bitset<B, A>& result)
williamr@2
   522
{
williamr@2
   523
    // PRE: distance(first, last) <= numblocks()
williamr@2
   524
    std::copy (first, last, result.m_bits.begin()); //[gps]
williamr@2
   525
}
williamr@2
   526
williamr@2
   527
//=============================================================================
williamr@2
   528
// dynamic_bitset implementation
williamr@2
   529
williamr@2
   530
williamr@2
   531
//-----------------------------------------------------------------------------
williamr@2
   532
// constructors, etc.
williamr@2
   533
williamr@2
   534
template <typename Block, typename Allocator>
williamr@2
   535
dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
williamr@2
   536
  : m_bits(alloc), m_num_bits(0)
williamr@2
   537
{
williamr@2
   538
williamr@2
   539
}
williamr@2
   540
williamr@2
   541
template <typename Block, typename Allocator>
williamr@2
   542
dynamic_bitset<Block, Allocator>::
williamr@2
   543
dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
williamr@2
   544
  : m_bits(calc_num_blocks(num_bits), Block(0), alloc),
williamr@2
   545
    m_num_bits(num_bits)
williamr@2
   546
{
williamr@2
   547
williamr@2
   548
  if (num_bits == 0)
williamr@2
   549
      return;
williamr@2
   550
williamr@2
   551
  typedef unsigned long num_type;
williamr@2
   552
williamr@2
   553
  // cut off all bits in value that have pos >= num_bits, if any
williamr@2
   554
  if (num_bits < static_cast<size_type>(ulong_width)) {
williamr@2
   555
      const num_type mask = (num_type(1) << num_bits) - 1;
williamr@2
   556
      value &= mask;
williamr@2
   557
  }
williamr@2
   558
williamr@2
   559
  if (bits_per_block >= ulong_width) {
williamr@2
   560
      m_bits[0] = static_cast<block_type>(value);
williamr@2
   561
  }
williamr@2
   562
  else {
williamr@2
   563
      for(size_type i = 0; value != 0; ++i) {
williamr@2
   564
williamr@2
   565
          m_bits[i] = static_cast<block_type>(value);
williamr@2
   566
          value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);
williamr@2
   567
      }
williamr@2
   568
  }
williamr@2
   569
williamr@2
   570
}
williamr@2
   571
williamr@2
   572
// copy constructor
williamr@2
   573
template <typename Block, typename Allocator>
williamr@2
   574
inline dynamic_bitset<Block, Allocator>::
williamr@2
   575
dynamic_bitset(const dynamic_bitset& b)
williamr@2
   576
  : m_bits(b.m_bits), m_num_bits(b.m_num_bits)  // [gps]
williamr@2
   577
{
williamr@2
   578
williamr@2
   579
}
williamr@2
   580
williamr@2
   581
template <typename Block, typename Allocator>
williamr@2
   582
inline dynamic_bitset<Block, Allocator>::
williamr@2
   583
~dynamic_bitset()
williamr@2
   584
{
williamr@2
   585
    assert(m_check_invariants());
williamr@2
   586
}
williamr@2
   587
williamr@2
   588
template <typename Block, typename Allocator>
williamr@2
   589
inline void dynamic_bitset<Block, Allocator>::
williamr@2
   590
swap(dynamic_bitset<Block, Allocator>& b) // no throw
williamr@2
   591
{
williamr@2
   592
    std::swap(m_bits, b.m_bits);
williamr@2
   593
    std::swap(m_num_bits, b.m_num_bits);
williamr@2
   594
}
williamr@2
   595
williamr@2
   596
template <typename Block, typename Allocator>
williamr@2
   597
dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
williamr@2
   598
operator=(const dynamic_bitset<Block, Allocator>& b)
williamr@2
   599
{
williamr@2
   600
#if 0 // gps
williamr@2
   601
    dynamic_bitset<Block, Allocator> tmp(b);
williamr@2
   602
    this->swap(tmp);
williamr@2
   603
    return *this;
williamr@2
   604
#else
williamr@2
   605
    m_bits = b.m_bits;
williamr@2
   606
    m_num_bits = b.m_num_bits;
williamr@2
   607
    return *this;
williamr@2
   608
#endif
williamr@2
   609
}
williamr@2
   610
williamr@2
   611
template <typename Block, typename Allocator>
williamr@2
   612
inline typename dynamic_bitset<Block, Allocator>::allocator_type
williamr@2
   613
dynamic_bitset<Block, Allocator>::get_allocator() const
williamr@2
   614
{
williamr@2
   615
    return m_bits.get_allocator();
williamr@2
   616
}
williamr@2
   617
williamr@2
   618
//-----------------------------------------------------------------------------
williamr@2
   619
// size changing operations
williamr@2
   620
williamr@2
   621
template <typename Block, typename Allocator>
williamr@2
   622
void dynamic_bitset<Block, Allocator>::
williamr@2
   623
resize(size_type num_bits, bool value) // strong guarantee
williamr@2
   624
{
williamr@2
   625
williamr@2
   626
  const size_type old_num_blocks = num_blocks();
williamr@2
   627
  const size_type required_blocks = calc_num_blocks(num_bits);
williamr@2
   628
williamr@2
   629
  const block_type v = value? ~Block(0) : Block(0);
williamr@2
   630
williamr@2
   631
  if (required_blocks != old_num_blocks) {
williamr@2
   632
    m_bits.resize(required_blocks, v); // s.g. (copy) [gps]
williamr@2
   633
  }
williamr@2
   634
williamr@2
   635
williamr@2
   636
  // At this point:
williamr@2
   637
  //
williamr@2
   638
  //  - if the buffer was shrunk, there's nothing to do, except
williamr@2
   639
  //    a call to m_zero_unused_bits()
williamr@2
   640
  //
williamr@2
   641
  //  - if it it is enlarged, all the (used) bits in the new blocks have
williamr@2
   642
  //    the correct value, but we should also take care of the bits,
williamr@2
   643
  //    if any, that were 'unused bits' before enlarging: if value == true,
williamr@2
   644
  //    they must be set.
williamr@2
   645
williamr@2
   646
  if (value && (num_bits > m_num_bits)) {
williamr@2
   647
williamr@2
   648
    const size_type extra_bits = count_extra_bits(); // gps
williamr@2
   649
    if (extra_bits) {
williamr@2
   650
        assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
williamr@2
   651
williamr@2
   652
        // Set them.
williamr@2
   653
        m_bits[old_num_blocks - 1] |= (v << extra_bits); // gps
williamr@2
   654
    }
williamr@2
   655
williamr@2
   656
  }
williamr@2
   657
williamr@2
   658
williamr@2
   659
williamr@2
   660
  m_num_bits = num_bits;
williamr@2
   661
  m_zero_unused_bits();
williamr@2
   662
williamr@2
   663
}
williamr@2
   664
williamr@2
   665
template <typename Block, typename Allocator>
williamr@2
   666
void dynamic_bitset<Block, Allocator>::
williamr@2
   667
clear() // no throw
williamr@2
   668
{
williamr@2
   669
  m_bits.clear();
williamr@2
   670
  m_num_bits = 0;
williamr@2
   671
}
williamr@2
   672
williamr@2
   673
williamr@2
   674
template <typename Block, typename Allocator>
williamr@2
   675
void dynamic_bitset<Block, Allocator>::
williamr@2
   676
push_back(bool bit)
williamr@2
   677
{
williamr@2
   678
  resize(size() + 1);
williamr@2
   679
  set(size() - 1, bit);
williamr@2
   680
}
williamr@2
   681
williamr@2
   682
template <typename Block, typename Allocator>
williamr@2
   683
void dynamic_bitset<Block, Allocator>::
williamr@2
   684
append(Block value) // strong guarantee
williamr@2
   685
{
williamr@2
   686
    // G.P.S. to be reviewed...
williamr@2
   687
williamr@2
   688
    const block_width_type r = count_extra_bits();
williamr@2
   689
williamr@2
   690
    if (r == 0) {
williamr@2
   691
        // the buffer is empty, or all blocks are filled
williamr@2
   692
        m_bits.push_back(value);
williamr@2
   693
    }
williamr@2
   694
    else {
williamr@2
   695
        m_bits.push_back(value >> (bits_per_block - r));
williamr@2
   696
        m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
williamr@2
   697
    }
williamr@2
   698
williamr@2
   699
    m_num_bits += bits_per_block;
williamr@2
   700
    assert(m_check_invariants());
williamr@2
   701
williamr@2
   702
}
williamr@2
   703
williamr@2
   704
williamr@2
   705
//-----------------------------------------------------------------------------
williamr@2
   706
// bitset operations
williamr@2
   707
template <typename Block, typename Allocator>
williamr@2
   708
dynamic_bitset<Block, Allocator>&
williamr@2
   709
dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
williamr@2
   710
{
williamr@2
   711
    assert(size() == rhs.size());
williamr@2
   712
    for (size_type i = 0; i < num_blocks(); ++i)
williamr@2
   713
        m_bits[i] &= rhs.m_bits[i];
williamr@2
   714
    return *this;
williamr@2
   715
}
williamr@2
   716
williamr@2
   717
template <typename Block, typename Allocator>
williamr@2
   718
dynamic_bitset<Block, Allocator>&
williamr@2
   719
dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
williamr@2
   720
{
williamr@2
   721
    assert(size() == rhs.size());
williamr@2
   722
    for (size_type i = 0; i < num_blocks(); ++i)
williamr@2
   723
        m_bits[i] |= rhs.m_bits[i];
williamr@2
   724
    //m_zero_unused_bits();
williamr@2
   725
    return *this;
williamr@2
   726
}
williamr@2
   727
williamr@2
   728
template <typename Block, typename Allocator>
williamr@2
   729
dynamic_bitset<Block, Allocator>&
williamr@2
   730
dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
williamr@2
   731
{
williamr@2
   732
    assert(size() == rhs.size());
williamr@2
   733
    for (size_type i = 0; i < this->num_blocks(); ++i)
williamr@2
   734
        m_bits[i] ^= rhs.m_bits[i];
williamr@2
   735
    //m_zero_unused_bits();
williamr@2
   736
    return *this;
williamr@2
   737
}
williamr@2
   738
williamr@2
   739
template <typename Block, typename Allocator>
williamr@2
   740
dynamic_bitset<Block, Allocator>&
williamr@2
   741
dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
williamr@2
   742
{
williamr@2
   743
    assert(size() == rhs.size());
williamr@2
   744
    for (size_type i = 0; i < num_blocks(); ++i)
williamr@2
   745
        m_bits[i] &= ~rhs.m_bits[i];
williamr@2
   746
    //m_zero_unused_bits();
williamr@2
   747
    return *this;
williamr@2
   748
}
williamr@2
   749
williamr@2
   750
//
williamr@2
   751
// NOTE:
williamr@2
   752
//  Note that the 'if (r != 0)' is crucial to avoid undefined
williamr@2
   753
//  behavior when the left hand operand of >> isn't promoted to a
williamr@2
   754
//  wider type (because rs would be too large).
williamr@2
   755
//
williamr@2
   756
template <typename Block, typename Allocator>
williamr@2
   757
dynamic_bitset<Block, Allocator>&
williamr@2
   758
dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
williamr@2
   759
{
williamr@2
   760
    if (n >= m_num_bits)
williamr@2
   761
        return reset();
williamr@2
   762
    //else
williamr@2
   763
    if (n > 0) {
williamr@2
   764
williamr@2
   765
        size_type    const last = num_blocks() - 1;  // num_blocks() is >= 1
williamr@2
   766
        size_type    const div  = n / bits_per_block; // div is <= last
williamr@2
   767
        block_width_type const r = bit_index(n);
williamr@2
   768
        block_type * const b    = &m_bits[0];
williamr@2
   769
williamr@2
   770
        if (r != 0) {
williamr@2
   771
williamr@2
   772
            block_width_type const rs = bits_per_block - r;
williamr@2
   773
williamr@2
   774
            for (size_type i = last-div; i>0; --i) {
williamr@2
   775
                b[i+div] = (b[i] << r) | (b[i-1] >> rs);
williamr@2
   776
            }
williamr@2
   777
            b[div] = b[0] << r;
williamr@2
   778
williamr@2
   779
        }
williamr@2
   780
        else {
williamr@2
   781
            for (size_type i = last-div; i>0; --i) {
williamr@2
   782
                b[i+div] = b[i];
williamr@2
   783
            }
williamr@2
   784
            b[div] = b[0];
williamr@2
   785
        }
williamr@2
   786
williamr@2
   787
williamr@2
   788
        // zero out div blocks at the less significant end
williamr@2
   789
        std::fill_n(b, div, static_cast<block_type>(0));
williamr@2
   790
williamr@2
   791
        // zero out any 1 bit that flowed into the unused part
williamr@2
   792
        m_zero_unused_bits(); // thanks to Lester Gong
williamr@2
   793
williamr@2
   794
williamr@2
   795
    }
williamr@2
   796
williamr@2
   797
    return *this;
williamr@2
   798
williamr@2
   799
williamr@2
   800
}
williamr@2
   801
williamr@2
   802
williamr@2
   803
//
williamr@2
   804
// NOTE:
williamr@2
   805
//  see the comments to operator <<=
williamr@2
   806
//
williamr@2
   807
template <typename B, typename A>
williamr@2
   808
dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
williamr@2
   809
    if (n >= m_num_bits) {
williamr@2
   810
        return reset();
williamr@2
   811
    }
williamr@2
   812
    //else
williamr@2
   813
    if (n>0) {
williamr@2
   814
williamr@2
   815
        size_type  const last  = num_blocks() - 1; // num_blocks() is >= 1
williamr@2
   816
        size_type  const div   = n / bits_per_block;   // div is <= last
williamr@2
   817
        block_width_type const r     = bit_index(n);
williamr@2
   818
        block_type * const b   = &m_bits[0];
williamr@2
   819
williamr@2
   820
williamr@2
   821
        if (r != 0) {
williamr@2
   822
williamr@2
   823
            block_width_type const ls = bits_per_block - r;
williamr@2
   824
williamr@2
   825
            for (size_type i = div; i < last; ++i) {
williamr@2
   826
                b[i-div] = (b[i] >> r) | (b[i+1]  << ls);
williamr@2
   827
            }
williamr@2
   828
            // r bits go to zero
williamr@2
   829
            b[last-div] = b[last] >> r;
williamr@2
   830
        }
williamr@2
   831
williamr@2
   832
        else {
williamr@2
   833
            for (size_type i = div; i <= last; ++i) {
williamr@2
   834
                b[i-div] = b[i];
williamr@2
   835
            }
williamr@2
   836
            // note the '<=': the last iteration 'absorbs'
williamr@2
   837
            // b[last-div] = b[last] >> 0;
williamr@2
   838
        }
williamr@2
   839
williamr@2
   840
williamr@2
   841
williamr@2
   842
        // div blocks are zero filled at the most significant end
williamr@2
   843
        std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
williamr@2
   844
    }
williamr@2
   845
williamr@2
   846
    return *this;
williamr@2
   847
}
williamr@2
   848
williamr@2
   849
williamr@2
   850
template <typename Block, typename Allocator>
williamr@2
   851
dynamic_bitset<Block, Allocator>
williamr@2
   852
dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
williamr@2
   853
{
williamr@2
   854
    dynamic_bitset r(*this);
williamr@2
   855
    return r <<= n;
williamr@2
   856
}
williamr@2
   857
williamr@2
   858
template <typename Block, typename Allocator>
williamr@2
   859
dynamic_bitset<Block, Allocator>
williamr@2
   860
dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
williamr@2
   861
{
williamr@2
   862
    dynamic_bitset r(*this);
williamr@2
   863
    return r >>= n;
williamr@2
   864
}
williamr@2
   865
williamr@2
   866
williamr@2
   867
//-----------------------------------------------------------------------------
williamr@2
   868
// basic bit operations
williamr@2
   869
williamr@2
   870
template <typename Block, typename Allocator>
williamr@2
   871
dynamic_bitset<Block, Allocator>&
williamr@2
   872
dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
williamr@2
   873
{
williamr@2
   874
    // [gps]
williamr@2
   875
    //
williamr@2
   876
    // Below we have no set(size_type) function to call when
williamr@2
   877
    // value == true; instead of using a helper, I think
williamr@2
   878
    // overloading set (rather than giving it a default bool
williamr@2
   879
    // argument) would be more elegant.
williamr@2
   880
williamr@2
   881
    assert(pos < m_num_bits);
williamr@2
   882
williamr@2
   883
    if (val)
williamr@2
   884
        m_bits[block_index(pos)] |= bit_mask(pos);
williamr@2
   885
    else
williamr@2
   886
        reset(pos);
williamr@2
   887
williamr@2
   888
    return *this;
williamr@2
   889
}
williamr@2
   890
williamr@2
   891
template <typename Block, typename Allocator>
williamr@2
   892
dynamic_bitset<Block, Allocator>&
williamr@2
   893
dynamic_bitset<Block, Allocator>::set()
williamr@2
   894
{
williamr@2
   895
  std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
williamr@2
   896
  m_zero_unused_bits();
williamr@2
   897
  return *this;
williamr@2
   898
}
williamr@2
   899
williamr@2
   900
template <typename Block, typename Allocator>
williamr@2
   901
dynamic_bitset<Block, Allocator>&
williamr@2
   902
dynamic_bitset<Block, Allocator>::reset(size_type pos)
williamr@2
   903
{
williamr@2
   904
    assert(pos < m_num_bits);
williamr@2
   905
    #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
williamr@2
   906
    // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
williamr@2
   907
    // use the |^ variation instead.. <grafik>
williamr@2
   908
    m_bits[block_index(pos)] |= bit_mask(pos);
williamr@2
   909
    m_bits[block_index(pos)] ^= bit_mask(pos);
williamr@2
   910
    #else
williamr@2
   911
    m_bits[block_index(pos)] &= ~bit_mask(pos);
williamr@2
   912
    #endif
williamr@2
   913
    return *this;
williamr@2
   914
}
williamr@2
   915
williamr@2
   916
template <typename Block, typename Allocator>
williamr@2
   917
dynamic_bitset<Block, Allocator>&
williamr@2
   918
dynamic_bitset<Block, Allocator>::reset()
williamr@2
   919
{
williamr@2
   920
  std::fill(m_bits.begin(), m_bits.end(), Block(0));
williamr@2
   921
  return *this;
williamr@2
   922
}
williamr@2
   923
williamr@2
   924
template <typename Block, typename Allocator>
williamr@2
   925
dynamic_bitset<Block, Allocator>&
williamr@2
   926
dynamic_bitset<Block, Allocator>::flip(size_type pos)
williamr@2
   927
{
williamr@2
   928
    assert(pos < m_num_bits);
williamr@2
   929
    m_bits[block_index(pos)] ^= bit_mask(pos);
williamr@2
   930
    return *this;
williamr@2
   931
}
williamr@2
   932
williamr@2
   933
template <typename Block, typename Allocator>
williamr@2
   934
dynamic_bitset<Block, Allocator>&
williamr@2
   935
dynamic_bitset<Block, Allocator>::flip()
williamr@2
   936
{
williamr@2
   937
    for (size_type i = 0; i < num_blocks(); ++i)
williamr@2
   938
        m_bits[i] = ~m_bits[i];
williamr@2
   939
    m_zero_unused_bits();
williamr@2
   940
    return *this;
williamr@2
   941
}
williamr@2
   942
williamr@2
   943
template <typename Block, typename Allocator>
williamr@2
   944
bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
williamr@2
   945
{
williamr@2
   946
    return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
williamr@2
   947
}
williamr@2
   948
williamr@2
   949
template <typename Block, typename Allocator>
williamr@2
   950
bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
williamr@2
   951
{
williamr@2
   952
    assert(pos < m_num_bits);
williamr@2
   953
    return m_unchecked_test(pos);
williamr@2
   954
}
williamr@2
   955
williamr@2
   956
template <typename Block, typename Allocator>
williamr@2
   957
bool dynamic_bitset<Block, Allocator>::any() const
williamr@2
   958
{
williamr@2
   959
    for (size_type i = 0; i < num_blocks(); ++i)
williamr@2
   960
        if (m_bits[i])
williamr@2
   961
            return true;
williamr@2
   962
    return false;
williamr@2
   963
}
williamr@2
   964
williamr@2
   965
template <typename Block, typename Allocator>
williamr@2
   966
inline bool dynamic_bitset<Block, Allocator>::none() const
williamr@2
   967
{
williamr@2
   968
    return !any();
williamr@2
   969
}
williamr@2
   970
williamr@2
   971
template <typename Block, typename Allocator>
williamr@2
   972
dynamic_bitset<Block, Allocator>
williamr@2
   973
dynamic_bitset<Block, Allocator>::operator~() const
williamr@2
   974
{
williamr@2
   975
    dynamic_bitset b(*this);
williamr@2
   976
    b.flip();
williamr@2
   977
    return b;
williamr@2
   978
}
williamr@2
   979
williamr@2
   980
williamr@2
   981
/*
williamr@2
   982
williamr@2
   983
The following is the straightforward implementation of count(), which
williamr@2
   984
we leave here in a comment for documentation purposes.
williamr@2
   985
williamr@2
   986
template <typename Block, typename Allocator>
williamr@2
   987
typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
   988
dynamic_bitset<Block, Allocator>::count() const
williamr@2
   989
{
williamr@2
   990
    size_type sum = 0;
williamr@2
   991
    for (size_type i = 0; i != this->m_num_bits; ++i)
williamr@2
   992
        if (test(i))
williamr@2
   993
            ++sum;
williamr@2
   994
    return sum;
williamr@2
   995
}
williamr@2
   996
williamr@2
   997
The actual algorithm uses a lookup table.
williamr@2
   998
williamr@2
   999
williamr@2
  1000
  The basic idea of the method is to pick up X bits at a time
williamr@2
  1001
  from the internal array of blocks and consider those bits as
williamr@2
  1002
  the binary representation of a number N. Then, to use a table
williamr@2
  1003
  of 1<<X elements where table[N] is the number of '1' digits
williamr@2
  1004
  in the binary representation of N (i.e. in our X bits).
williamr@2
  1005
williamr@2
  1006
williamr@2
  1007
  In this implementation X is 8 (but can be easily changed: you
williamr@2
  1008
  just have to modify the definition of table_width and shrink/enlarge
williamr@2
  1009
  the table accordingly - it could be useful, for instance, to expand
williamr@2
  1010
  the table to 512 elements on an implementation with 9-bit bytes) and
williamr@2
  1011
  the internal array of blocks is seen, if possible, as an array of bytes.
williamr@2
  1012
  In practice the "reinterpretation" as array of bytes is possible if and
williamr@2
  1013
  only if X >= CHAR_BIT and Block has no padding bits (that would be counted
williamr@2
  1014
  together with the "real ones" if we saw the array as array of bytes).
williamr@2
  1015
  Otherwise we simply 'extract' X bits at a time from each Block.
williamr@2
  1016
williamr@2
  1017
*/
williamr@2
  1018
williamr@2
  1019
williamr@2
  1020
template <typename Block, typename Allocator>
williamr@2
  1021
typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1022
dynamic_bitset<Block, Allocator>::count() const
williamr@2
  1023
{
williamr@2
  1024
    using namespace detail::dynamic_bitset_count_impl;
williamr@2
  1025
williamr@2
  1026
    const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);
williamr@2
  1027
    const bool enough_table_width = table_width >= CHAR_BIT;
williamr@2
  1028
williamr@2
  1029
    typedef mode_to_type< (no_padding && enough_table_width ?
williamr@2
  1030
                          access_by_bytes : access_by_blocks) > m;
williamr@2
  1031
williamr@2
  1032
    return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(0));
williamr@2
  1033
williamr@2
  1034
}
williamr@2
  1035
williamr@2
  1036
williamr@2
  1037
//-----------------------------------------------------------------------------
williamr@2
  1038
// conversions
williamr@2
  1039
williamr@2
  1040
williamr@2
  1041
template <typename B, typename A, typename stringT>
williamr@2
  1042
void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
williamr@2
  1043
                      bool dump_all)
williamr@2
  1044
{
williamr@2
  1045
    typedef typename stringT::traits_type Tr;
williamr@2
  1046
    typedef typename stringT::value_type  Ch;
williamr@2
  1047
williamr@2
  1048
    BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
williamr@2
  1049
    const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
williamr@2
  1050
    const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2
  1051
williamr@2
  1052
    // Note that this function may access (when
williamr@2
  1053
    // dump_all == true) bits beyond position size() - 1
williamr@2
  1054
williamr@2
  1055
    typedef typename dynamic_bitset<B, A>::size_type size_type;
williamr@2
  1056
williamr@2
  1057
    const size_type len = dump_all?
williamr@2
  1058
         dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
williamr@2
  1059
         b.size();
williamr@2
  1060
    s.assign (len, zero);
williamr@2
  1061
williamr@2
  1062
    for (size_type i = 0; i < len; ++i) {
williamr@2
  1063
        if (b.m_unchecked_test(i))
williamr@2
  1064
            Tr::assign(s[len - 1 - i], one);
williamr@2
  1065
williamr@2
  1066
    }
williamr@2
  1067
williamr@2
  1068
}
williamr@2
  1069
williamr@2
  1070
williamr@2
  1071
// A comment similar to the one about the constructor from
williamr@2
  1072
// basic_string can be done here. Thanks to James Kanze for
williamr@2
  1073
// making me (Gennaro) realize this important separation of
williamr@2
  1074
// concerns issue, as well as many things about i18n.
williamr@2
  1075
//
williamr@2
  1076
template <typename Block, typename Allocator, typename stringT> // G.P.S.
williamr@2
  1077
inline void
williamr@2
  1078
to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
williamr@2
  1079
{
williamr@2
  1080
    to_string_helper(b, s, false);
williamr@2
  1081
}
williamr@2
  1082
williamr@2
  1083
williamr@2
  1084
// Differently from to_string this function dumps out
williamr@2
  1085
// every bit of the internal representation (may be
williamr@2
  1086
// useful for debugging purposes)
williamr@2
  1087
//
williamr@2
  1088
template <typename B, typename A, typename stringT>
williamr@2
  1089
inline void
williamr@2
  1090
dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.
williamr@2
  1091
{
williamr@2
  1092
    to_string_helper(b, s, true /* =dump_all*/);
williamr@2
  1093
}
williamr@2
  1094
williamr@2
  1095
template <typename Block, typename Allocator, typename BlockOutputIterator>
williamr@2
  1096
inline void
williamr@2
  1097
to_block_range(const dynamic_bitset<Block, Allocator>& b,
williamr@2
  1098
               BlockOutputIterator result)
williamr@2
  1099
{
williamr@2
  1100
    // note how this copies *all* bits, including the
williamr@2
  1101
    // unused ones in the last block (which are zero)
williamr@2
  1102
    std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]
williamr@2
  1103
}
williamr@2
  1104
williamr@2
  1105
template <typename Block, typename Allocator>
williamr@2
  1106
unsigned long dynamic_bitset<Block, Allocator>::
williamr@2
  1107
to_ulong() const
williamr@2
  1108
{
williamr@2
  1109
williamr@2
  1110
  if (m_num_bits == 0)
williamr@2
  1111
      return 0; // convention
williamr@2
  1112
williamr@2
  1113
  // Check for overflows. This may be a performance burden on very
williamr@2
  1114
  // large bitsets but is required by the specification, sorry
williamr@2
  1115
  if (find_next(ulong_width - 1) != npos)
williamr@2
  1116
    throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
williamr@2
  1117
williamr@2
  1118
williamr@2
  1119
  // Ok, from now on we can be sure there's no "on" bit beyond
williamr@2
  1120
  // the allowed positions
williamr@2
  1121
williamr@2
  1122
  if (bits_per_block >= ulong_width)
williamr@2
  1123
      return m_bits[0];
williamr@2
  1124
williamr@2
  1125
williamr@2
  1126
  size_type last_block = block_index((std::min)(m_num_bits-1, // gps
williamr@2
  1127
                                    (size_type)(ulong_width-1)));
williamr@2
  1128
  unsigned long result = 0;
williamr@2
  1129
  for (size_type i = 0; i <= last_block; ++i) {
williamr@2
  1130
williamr@2
  1131
    assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps
williamr@2
  1132
williamr@2
  1133
    unsigned long piece = m_bits[i];
williamr@2
  1134
    result |= (piece << (bits_per_block * i));
williamr@2
  1135
  }
williamr@2
  1136
williamr@2
  1137
  return result;
williamr@2
  1138
williamr@2
  1139
}
williamr@2
  1140
williamr@2
  1141
williamr@2
  1142
template <typename Block, typename Allocator>
williamr@2
  1143
inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1144
dynamic_bitset<Block, Allocator>::size() const
williamr@2
  1145
{
williamr@2
  1146
    return m_num_bits;
williamr@2
  1147
}
williamr@2
  1148
williamr@2
  1149
template <typename Block, typename Allocator>
williamr@2
  1150
inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1151
dynamic_bitset<Block, Allocator>::num_blocks() const
williamr@2
  1152
{
williamr@2
  1153
    return m_bits.size();
williamr@2
  1154
}
williamr@2
  1155
williamr@2
  1156
template <typename Block, typename Allocator>
williamr@2
  1157
inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1158
dynamic_bitset<Block, Allocator>::max_size() const
williamr@2
  1159
{
williamr@2
  1160
    // Semantics of vector<>::max_size() aren't very clear
williamr@2
  1161
    // (see lib issue 197) and many library implementations
williamr@2
  1162
    // simply return dummy values, _unrelated_ to the underlying
williamr@2
  1163
    // allocator.
williamr@2
  1164
    //
williamr@2
  1165
    // Given these problems, I was tempted to not provide this
williamr@2
  1166
    // function at all but the user could need it if he provides
williamr@2
  1167
    // his own allocator.
williamr@2
  1168
    //
williamr@2
  1169
williamr@2
  1170
    const size_type m = detail::vector_max_size_workaround(m_bits);
williamr@2
  1171
williamr@2
  1172
    return m <= (size_type(-1)/bits_per_block) ?
williamr@2
  1173
        m * bits_per_block :
williamr@2
  1174
        size_type(-1);
williamr@2
  1175
}
williamr@2
  1176
williamr@2
  1177
template <typename Block, typename Allocator>
williamr@2
  1178
inline bool dynamic_bitset<Block, Allocator>::empty() const
williamr@2
  1179
{
williamr@2
  1180
  return size() == 0;
williamr@2
  1181
}
williamr@2
  1182
williamr@2
  1183
#if 0 // gps
williamr@2
  1184
template <typename Block, typename Allocator>
williamr@2
  1185
inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)
williamr@2
  1186
{
williamr@2
  1187
    assert(n <= max_size()); // PRE - G.P.S.
williamr@2
  1188
    m_bits.reserve(calc_num_blocks(n));
williamr@2
  1189
}
williamr@2
  1190
williamr@2
  1191
template <typename Block, typename Allocator>
williamr@2
  1192
typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1193
dynamic_bitset<Block, Allocator>::capacity() const
williamr@2
  1194
{
williamr@2
  1195
    // capacity is m_bits.capacity() * bits_per_block
williamr@2
  1196
    // unless that one overflows
williamr@2
  1197
    const size_type m = static_cast<size_type>(-1);
williamr@2
  1198
    const size_type q = m / bits_per_block;
williamr@2
  1199
williamr@2
  1200
    const size_type c = m_bits.capacity();
williamr@2
  1201
williamr@2
  1202
    return c <= q ?
williamr@2
  1203
        c * bits_per_block :
williamr@2
  1204
        m;
williamr@2
  1205
}
williamr@2
  1206
#endif
williamr@2
  1207
williamr@2
  1208
template <typename Block, typename Allocator>
williamr@2
  1209
bool dynamic_bitset<Block, Allocator>::
williamr@2
  1210
is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
williamr@2
  1211
{
williamr@2
  1212
    assert(size() == a.size());
williamr@2
  1213
    for (size_type i = 0; i < num_blocks(); ++i)
williamr@2
  1214
        if (m_bits[i] & ~a.m_bits[i])
williamr@2
  1215
            return false;
williamr@2
  1216
    return true;
williamr@2
  1217
}
williamr@2
  1218
williamr@2
  1219
template <typename Block, typename Allocator>
williamr@2
  1220
bool dynamic_bitset<Block, Allocator>::
williamr@2
  1221
is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
williamr@2
  1222
{
williamr@2
  1223
    assert(size() == a.size());
williamr@2
  1224
    bool proper = false;
williamr@2
  1225
    for (size_type i = 0; i < num_blocks(); ++i) {
williamr@2
  1226
        Block bt = m_bits[i], ba = a.m_bits[i];
williamr@2
  1227
        if (ba & ~bt)
williamr@2
  1228
            proper = true;
williamr@2
  1229
        if (bt & ~ba)
williamr@2
  1230
            return false;
williamr@2
  1231
    }
williamr@2
  1232
    return proper;
williamr@2
  1233
}
williamr@2
  1234
williamr@2
  1235
template <typename Block, typename Allocator>
williamr@2
  1236
bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
williamr@2
  1237
{
williamr@2
  1238
    size_type common_blocks = num_blocks() < b.num_blocks()
williamr@2
  1239
                              ? num_blocks() : b.num_blocks();
williamr@2
  1240
williamr@2
  1241
    for(size_type i = 0; i < common_blocks; ++i) {
williamr@2
  1242
        if(m_bits[i] & b.m_bits[i])
williamr@2
  1243
            return true;
williamr@2
  1244
    }
williamr@2
  1245
    return false;
williamr@2
  1246
}
williamr@2
  1247
williamr@2
  1248
// --------------------------------
williamr@2
  1249
// lookup
williamr@2
  1250
williamr@2
  1251
williamr@2
  1252
// look for the first bit "on", starting
williamr@2
  1253
// from the block with index first_block
williamr@2
  1254
//
williamr@2
  1255
template <typename Block, typename Allocator>
williamr@2
  1256
typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1257
dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
williamr@2
  1258
{
williamr@2
  1259
    size_type i = first_block;
williamr@2
  1260
williamr@2
  1261
    // skip null blocks
williamr@2
  1262
    while (i < num_blocks() && m_bits[i] == 0)
williamr@2
  1263
        ++i;
williamr@2
  1264
williamr@2
  1265
    if (i >= num_blocks())
williamr@2
  1266
        return npos; // not found
williamr@2
  1267
williamr@2
  1268
    return i * bits_per_block + boost::lowest_bit(m_bits[i]);
williamr@2
  1269
williamr@2
  1270
}
williamr@2
  1271
williamr@2
  1272
williamr@2
  1273
template <typename Block, typename Allocator>
williamr@2
  1274
typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1275
dynamic_bitset<Block, Allocator>::find_first() const
williamr@2
  1276
{
williamr@2
  1277
    return m_do_find_from(0);
williamr@2
  1278
}
williamr@2
  1279
williamr@2
  1280
williamr@2
  1281
template <typename Block, typename Allocator>
williamr@2
  1282
typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1283
dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
williamr@2
  1284
{
williamr@2
  1285
williamr@2
  1286
    const size_type sz = size();
williamr@2
  1287
    if (pos >= (sz-1) || sz == 0)
williamr@2
  1288
        return npos;
williamr@2
  1289
williamr@2
  1290
    ++pos;
williamr@2
  1291
williamr@2
  1292
    const size_type blk = block_index(pos);
williamr@2
  1293
    const block_width_type ind = bit_index(pos);
williamr@2
  1294
williamr@2
  1295
    // mask out bits before pos
williamr@2
  1296
    const Block fore = m_bits[blk] & ( ~Block(0) << ind );
williamr@2
  1297
williamr@2
  1298
    return fore?
williamr@2
  1299
        blk * bits_per_block + lowest_bit(fore)
williamr@2
  1300
        :
williamr@2
  1301
        m_do_find_from(blk + 1);
williamr@2
  1302
williamr@2
  1303
}
williamr@2
  1304
williamr@2
  1305
williamr@2
  1306
williamr@2
  1307
//-----------------------------------------------------------------------------
williamr@2
  1308
// comparison
williamr@2
  1309
williamr@2
  1310
template <typename Block, typename Allocator>
williamr@2
  1311
bool operator==(const dynamic_bitset<Block, Allocator>& a,
williamr@2
  1312
                const dynamic_bitset<Block, Allocator>& b)
williamr@2
  1313
{
williamr@2
  1314
    return (a.m_num_bits == b.m_num_bits)
williamr@2
  1315
           && (a.m_bits == b.m_bits); // [gps]
williamr@2
  1316
}
williamr@2
  1317
williamr@2
  1318
template <typename Block, typename Allocator>
williamr@2
  1319
inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
williamr@2
  1320
                       const dynamic_bitset<Block, Allocator>& b)
williamr@2
  1321
{
williamr@2
  1322
    return !(a == b);
williamr@2
  1323
}
williamr@2
  1324
williamr@2
  1325
template <typename Block, typename Allocator>
williamr@2
  1326
bool operator<(const dynamic_bitset<Block, Allocator>& a,
williamr@2
  1327
               const dynamic_bitset<Block, Allocator>& b)
williamr@2
  1328
{
williamr@2
  1329
    assert(a.size() == b.size());
williamr@2
  1330
    typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
williamr@2
  1331
williamr@2
  1332
    if (a.size() == 0)
williamr@2
  1333
      return false;
williamr@2
  1334
williamr@2
  1335
    // Since we are storing the most significant bit
williamr@2
  1336
    // at pos == size() - 1, we need to do the comparisons in reverse.
williamr@2
  1337
williamr@2
  1338
    // Compare a block at a time
williamr@2
  1339
    for (size_type i = a.num_blocks() - 1; i > 0; --i)
williamr@2
  1340
      if (a.m_bits[i] < b.m_bits[i])
williamr@2
  1341
        return true;
williamr@2
  1342
      else if (a.m_bits[i] > b.m_bits[i])
williamr@2
  1343
        return false;
williamr@2
  1344
williamr@2
  1345
    if (a.m_bits[0] < b.m_bits[0])
williamr@2
  1346
      return true;
williamr@2
  1347
    else
williamr@2
  1348
      return false;
williamr@2
  1349
}
williamr@2
  1350
williamr@2
  1351
template <typename Block, typename Allocator>
williamr@2
  1352
inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
williamr@2
  1353
                       const dynamic_bitset<Block, Allocator>& b)
williamr@2
  1354
{
williamr@2
  1355
    return !(a > b);
williamr@2
  1356
}
williamr@2
  1357
williamr@2
  1358
template <typename Block, typename Allocator>
williamr@2
  1359
inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
williamr@2
  1360
                      const dynamic_bitset<Block, Allocator>& b)
williamr@2
  1361
{
williamr@2
  1362
    return b < a;
williamr@2
  1363
}
williamr@2
  1364
williamr@2
  1365
template <typename Block, typename Allocator>
williamr@2
  1366
inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
williamr@2
  1367
                       const dynamic_bitset<Block, Allocator>& b)
williamr@2
  1368
{
williamr@2
  1369
    return !(a < b);
williamr@2
  1370
}
williamr@2
  1371
williamr@2
  1372
//-----------------------------------------------------------------------------
williamr@2
  1373
// stream operations
williamr@2
  1374
williamr@2
  1375
#ifdef BOOST_OLD_IOSTREAMS
williamr@2
  1376
template < typename Block, typename Alloc>
williamr@2
  1377
std::ostream&
williamr@2
  1378
operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
williamr@2
  1379
{
williamr@2
  1380
    // NOTE: since this is aimed at "classic" iostreams, exception
williamr@2
  1381
    // masks on the stream are not supported. The library that
williamr@2
  1382
    // ships with gcc 2.95 has an exceptions() member function but
williamr@2
  1383
    // nothing is actually implemented; not even the class ios::failure.
williamr@2
  1384
williamr@2
  1385
    using namespace std;
williamr@2
  1386
williamr@2
  1387
    const ios::iostate ok = ios::goodbit;
williamr@2
  1388
    ios::iostate err = ok;
williamr@2
  1389
williamr@2
  1390
    if (os.opfx()) { // gps
williamr@2
  1391
williamr@2
  1392
        //try
williamr@2
  1393
        typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
williamr@2
  1394
williamr@2
  1395
        const bitsetsize_type sz = b.size();
williamr@2
  1396
        std::streambuf * buf = os.rdbuf();
williamr@2
  1397
        size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
williamr@2
  1398
            || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; //- gps
williamr@2
  1399
williamr@2
  1400
        const char fill_char = os.fill();
williamr@2
  1401
        const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
williamr@2
  1402
williamr@2
  1403
        // if needed fill at left; pad is decresed along the way
williamr@2
  1404
        if (adjustfield != ios::left) {
williamr@2
  1405
            for (; 0 < npad; --npad)
williamr@2
  1406
                if (fill_char != buf->sputc(fill_char)) {
williamr@2
  1407
                    err |= ios::failbit;   // gps
williamr@2
  1408
                    break;
williamr@2
  1409
                }
williamr@2
  1410
        }
williamr@2
  1411
williamr@2
  1412
        if (err == ok) {
williamr@2
  1413
            // output the bitset
williamr@2
  1414
            for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
williamr@2
  1415
                const char dig = b.test(i-1)? '1' : '0';
williamr@2
  1416
                if (EOF == buf->sputc(dig)) { // ok?? gps
williamr@2
  1417
                    err |= ios::failbit;
williamr@2
  1418
                    break;
williamr@2
  1419
                }
williamr@2
  1420
            }
williamr@2
  1421
        }
williamr@2
  1422
williamr@2
  1423
        if (err == ok) {
williamr@2
  1424
            // if needed fill at right
williamr@2
  1425
            for (; 0 < npad; --npad) {
williamr@2
  1426
                if (fill_char != buf->sputc(fill_char)) {
williamr@2
  1427
                    err |= ios::failbit;
williamr@2
  1428
                    break;
williamr@2
  1429
                }
williamr@2
  1430
            }
williamr@2
  1431
        }
williamr@2
  1432
williamr@2
  1433
        os.osfx();
williamr@2
  1434
        os.width(0);
williamr@2
  1435
williamr@2
  1436
    } // if opfx
williamr@2
  1437
williamr@2
  1438
    if(err != ok)
williamr@2
  1439
        os.setstate(err); // assume this does NOT throw - gps
williamr@2
  1440
    return os;
williamr@2
  1441
williamr@2
  1442
}
williamr@2
  1443
#else
williamr@2
  1444
williamr@2
  1445
template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2
  1446
std::basic_ostream<Ch, Tr>&
williamr@2
  1447
operator<<(std::basic_ostream<Ch, Tr>& os,
williamr@2
  1448
           const dynamic_bitset<Block, Alloc>& b)
williamr@2
  1449
{
williamr@2
  1450
williamr@2
  1451
    using namespace std;
williamr@2
  1452
williamr@2
  1453
    const ios_base::iostate ok = ios_base::goodbit;
williamr@2
  1454
    ios_base::iostate err = ok;
williamr@2
  1455
williamr@2
  1456
    typename basic_ostream<Ch, Tr>::sentry cerberos(os);
williamr@2
  1457
    if (cerberos) {
williamr@2
  1458
williamr@2
  1459
        BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
williamr@2
  1460
        const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
williamr@2
  1461
        const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2
  1462
williamr@2
  1463
        try {
williamr@2
  1464
williamr@2
  1465
            typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
williamr@2
  1466
            typedef basic_streambuf<Ch, Tr> buffer_type; // G.P.S.
williamr@2
  1467
williamr@2
  1468
            buffer_type * buf = os.rdbuf();
williamr@2
  1469
            size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
williamr@2
  1470
                || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); //- G.P.S.
williamr@2
  1471
williamr@2
  1472
            const Ch fill_char = os.fill();
williamr@2
  1473
            const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
williamr@2
  1474
williamr@2
  1475
            // if needed fill at left; pad is decresed along the way
williamr@2
  1476
            if (adjustfield != ios_base::left) {
williamr@2
  1477
                for (; 0 < npad; --npad)
williamr@2
  1478
                    if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
williamr@2
  1479
                          err |= ios_base::failbit;   // G.P.S.
williamr@2
  1480
                          break;
williamr@2
  1481
                    }
williamr@2
  1482
            }
williamr@2
  1483
williamr@2
  1484
            if (err == ok) {
williamr@2
  1485
                // output the bitset
williamr@2
  1486
                for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
williamr@2
  1487
                    typename buffer_type::int_type
williamr@2
  1488
                        ret = buf->sputc(b.test(i-1)? one : zero);
williamr@2
  1489
                    if (Tr::eq_int_type(Tr::eof(), ret)) {
williamr@2
  1490
                        err |= ios_base::failbit;
williamr@2
  1491
                        break;
williamr@2
  1492
                    }
williamr@2
  1493
                }
williamr@2
  1494
            }
williamr@2
  1495
williamr@2
  1496
            if (err == ok) {
williamr@2
  1497
                // if needed fill at right
williamr@2
  1498
                for (; 0 < npad; --npad) {
williamr@2
  1499
                    if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
williamr@2
  1500
                        err |= ios_base::failbit;
williamr@2
  1501
                        break;
williamr@2
  1502
                    }
williamr@2
  1503
                }
williamr@2
  1504
            }
williamr@2
  1505
williamr@2
  1506
williamr@2
  1507
            os.width(0);
williamr@2
  1508
williamr@2
  1509
        } catch (...) { // see std 27.6.1.1/4
williamr@2
  1510
            bool rethrow = false;
williamr@2
  1511
            try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
williamr@2
  1512
williamr@2
  1513
            if (rethrow)
williamr@2
  1514
                throw;
williamr@2
  1515
        }
williamr@2
  1516
    }
williamr@2
  1517
williamr@2
  1518
    if(err != ok)
williamr@2
  1519
        os.setstate(err); // may throw exception
williamr@2
  1520
    return os;
williamr@2
  1521
williamr@2
  1522
}
williamr@2
  1523
#endif
williamr@2
  1524
williamr@2
  1525
williamr@2
  1526
#ifdef BOOST_OLD_IOSTREAMS
williamr@2
  1527
williamr@2
  1528
    // gps - A sentry-like class that calls isfx in its
williamr@2
  1529
    // destructor. Necessary because bit_appender::do_append may throw.
williamr@2
  1530
    class pseudo_sentry {
williamr@2
  1531
        std::istream & m_r;
williamr@2
  1532
        const bool m_ok;
williamr@2
  1533
    public:
williamr@2
  1534
        explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
williamr@2
  1535
        ~pseudo_sentry() { m_r.isfx(); }
williamr@2
  1536
        operator bool() const { return m_ok; }
williamr@2
  1537
    };
williamr@2
  1538
williamr@2
  1539
template <typename Block, typename Alloc>
williamr@2
  1540
std::istream&
williamr@2
  1541
operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
williamr@2
  1542
{
williamr@2
  1543
williamr@2
  1544
// Extractor for classic IO streams (libstdc++ < 3.0)
williamr@2
  1545
// ----------------------------------------------------//
williamr@2
  1546
//  It's assumed that the stream buffer functions, and
williamr@2
  1547
//  the stream's setstate() _cannot_ throw.
williamr@2
  1548
williamr@2
  1549
williamr@2
  1550
    typedef dynamic_bitset<Block, Alloc> bitset_type;
williamr@2
  1551
    typedef typename bitset_type::size_type size_type;
williamr@2
  1552
williamr@2
  1553
    std::ios::iostate err = std::ios::goodbit; // gps
williamr@2
  1554
    pseudo_sentry cerberos(is); // skips whitespaces
williamr@2
  1555
    if(cerberos) {
williamr@2
  1556
williamr@2
  1557
        b.clear();
williamr@2
  1558
williamr@2
  1559
        const std::streamsize w = is.width();
williamr@2
  1560
        const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps
williamr@2
  1561
                                                         ? w : b.max_size();
williamr@2
  1562
        typename bitset_type::bit_appender appender(b);
williamr@2
  1563
        std::streambuf * buf = is.rdbuf();
williamr@2
  1564
        for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
williamr@2
  1565
williamr@2
  1566
            if (c == EOF) {
williamr@2
  1567
                err |= std::ios::eofbit; // G.P.S.
williamr@2
  1568
                break;
williamr@2
  1569
            }
williamr@2
  1570
            else if (char(c) != '0' && char(c) != '1')
williamr@2
  1571
                break; // non digit character
williamr@2
  1572
williamr@2
  1573
            else {
williamr@2
  1574
                try {
williamr@2
  1575
                    //throw std::bad_alloc(); // gps
williamr@2
  1576
                    appender.do_append(char(c) == '1');
williamr@2
  1577
                }
williamr@2
  1578
                catch(...) {
williamr@2
  1579
                    is.setstate(std::ios::failbit); // assume this can't throw
williamr@2
  1580
                    throw;
williamr@2
  1581
                }
williamr@2
  1582
            }
williamr@2
  1583
williamr@2
  1584
        } // for
williamr@2
  1585
    }
williamr@2
  1586
williamr@2
  1587
    is.width(0); // gps
williamr@2
  1588
    if (b.size() == 0)
williamr@2
  1589
        err |= std::ios::failbit;
williamr@2
  1590
    if (err != std::ios::goodbit) // gps
williamr@2
  1591
        is.setstate (err); // may throw
williamr@2
  1592
williamr@2
  1593
    return is;
williamr@2
  1594
}
williamr@2
  1595
williamr@2
  1596
#else // BOOST_OLD_IOSTREAMS
williamr@2
  1597
williamr@2
  1598
template <typename Ch, typename Tr, typename Block, typename Alloc>
williamr@2
  1599
std::basic_istream<Ch, Tr>&
williamr@2
  1600
operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
williamr@2
  1601
{
williamr@2
  1602
williamr@2
  1603
    using namespace std;
williamr@2
  1604
williamr@2
  1605
    typedef dynamic_bitset<Block, Alloc> bitset_type;
williamr@2
  1606
    typedef typename bitset_type::size_type size_type;
williamr@2
  1607
williamr@2
  1608
    const streamsize w = is.width();
williamr@2
  1609
    const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? // gps
williamr@2
  1610
                                         w : b.max_size();
williamr@2
  1611
williamr@2
  1612
    ios_base::iostate err = ios_base::goodbit; // gps
williamr@2
  1613
    typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
williamr@2
  1614
    if(cerberos) {
williamr@2
  1615
williamr@2
  1616
        // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
williamr@2
  1617
        BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
williamr@2
  1618
        const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
williamr@2
  1619
        const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
williamr@2
  1620
williamr@2
  1621
        b.clear();
williamr@2
  1622
        try {
williamr@2
  1623
            typename bitset_type::bit_appender appender(b);
williamr@2
  1624
            basic_streambuf <Ch, Tr> * buf = is.rdbuf();
williamr@2
  1625
            typename Tr::int_type c = buf->sgetc(); // G.P.S.
williamr@2
  1626
            for( ; appender.get_count() < limit; c = buf->snextc() ) {
williamr@2
  1627
williamr@2
  1628
                if (Tr::eq_int_type(Tr::eof(), c)) {
williamr@2
  1629
                    err |= ios_base::eofbit; // G.P.S.
williamr@2
  1630
                    break;
williamr@2
  1631
                }
williamr@2
  1632
                else {
williamr@2
  1633
                    const Ch to_c = Tr::to_char_type(c);
williamr@2
  1634
                    const bool is_one = Tr::eq(to_c, one);
williamr@2
  1635
williamr@2
  1636
                    if (!is_one && !Tr::eq(to_c, zero))
williamr@2
  1637
                        break; // non digit character
williamr@2
  1638
williamr@2
  1639
                    appender.do_append(is_one);
williamr@2
  1640
williamr@2
  1641
                }
williamr@2
  1642
williamr@2
  1643
            } // for
williamr@2
  1644
        }
williamr@2
  1645
        catch (...) {
williamr@2
  1646
            // catches from stream buf, or from vector:
williamr@2
  1647
            //
williamr@2
  1648
            // bits_stored bits have been extracted and stored, and
williamr@2
  1649
            // either no further character is extractable or we can't
williamr@2
  1650
            // append to the underlying vector (out of memory) gps
williamr@2
  1651
williamr@2
  1652
            bool rethrow = false;   // see std 27.6.1.1/4
williamr@2
  1653
            try { is.setstate(ios_base::badbit); }
williamr@2
  1654
            catch(...) { rethrow = true; }
williamr@2
  1655
williamr@2
  1656
            if (rethrow)
williamr@2
  1657
                throw;
williamr@2
  1658
williamr@2
  1659
        }
williamr@2
  1660
    }
williamr@2
  1661
williamr@2
  1662
    is.width(0); // gps
williamr@2
  1663
    if (b.size() == 0 /*|| !cerberos*/)
williamr@2
  1664
        err |= ios_base::failbit;
williamr@2
  1665
    if (err != ios_base::goodbit) // gps
williamr@2
  1666
        is.setstate (err); // may throw
williamr@2
  1667
williamr@2
  1668
    return is;
williamr@2
  1669
williamr@2
  1670
}
williamr@2
  1671
williamr@2
  1672
williamr@2
  1673
#endif
williamr@2
  1674
williamr@2
  1675
williamr@2
  1676
//-----------------------------------------------------------------------------
williamr@2
  1677
// bitset operations
williamr@2
  1678
williamr@2
  1679
template <typename Block, typename Allocator>
williamr@2
  1680
dynamic_bitset<Block, Allocator>
williamr@2
  1681
operator&(const dynamic_bitset<Block, Allocator>& x,
williamr@2
  1682
          const dynamic_bitset<Block, Allocator>& y)
williamr@2
  1683
{
williamr@2
  1684
    dynamic_bitset<Block, Allocator> b(x);
williamr@2
  1685
    return b &= y;
williamr@2
  1686
}
williamr@2
  1687
williamr@2
  1688
template <typename Block, typename Allocator>
williamr@2
  1689
dynamic_bitset<Block, Allocator>
williamr@2
  1690
operator|(const dynamic_bitset<Block, Allocator>& x,
williamr@2
  1691
          const dynamic_bitset<Block, Allocator>& y)
williamr@2
  1692
{
williamr@2
  1693
    dynamic_bitset<Block, Allocator> b(x);
williamr@2
  1694
    return b |= y;
williamr@2
  1695
}
williamr@2
  1696
williamr@2
  1697
template <typename Block, typename Allocator>
williamr@2
  1698
dynamic_bitset<Block, Allocator>
williamr@2
  1699
operator^(const dynamic_bitset<Block, Allocator>& x,
williamr@2
  1700
          const dynamic_bitset<Block, Allocator>& y)
williamr@2
  1701
{
williamr@2
  1702
    dynamic_bitset<Block, Allocator> b(x);
williamr@2
  1703
    return b ^= y;
williamr@2
  1704
}
williamr@2
  1705
williamr@2
  1706
template <typename Block, typename Allocator>
williamr@2
  1707
dynamic_bitset<Block, Allocator>
williamr@2
  1708
operator-(const dynamic_bitset<Block, Allocator>& x,
williamr@2
  1709
          const dynamic_bitset<Block, Allocator>& y)
williamr@2
  1710
{
williamr@2
  1711
    dynamic_bitset<Block, Allocator> b(x);
williamr@2
  1712
    return b -= y;
williamr@2
  1713
}
williamr@2
  1714
williamr@2
  1715
//-----------------------------------------------------------------------------
williamr@2
  1716
// namespace scope swap
williamr@2
  1717
williamr@2
  1718
template<typename Block, typename Allocator>
williamr@2
  1719
inline void
williamr@2
  1720
swap(dynamic_bitset<Block, Allocator>& left,
williamr@2
  1721
     dynamic_bitset<Block, Allocator>& right) // no throw
williamr@2
  1722
{
williamr@2
  1723
    left.swap(right); // gps
williamr@2
  1724
}
williamr@2
  1725
williamr@2
  1726
williamr@2
  1727
//-----------------------------------------------------------------------------
williamr@2
  1728
// private (on conforming compilers) member functions
williamr@2
  1729
williamr@2
  1730
williamr@2
  1731
template <typename Block, typename Allocator>
williamr@2
  1732
inline typename dynamic_bitset<Block, Allocator>::size_type
williamr@2
  1733
dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
williamr@2
  1734
{
williamr@2
  1735
    return num_bits / bits_per_block
williamr@2
  1736
           + static_cast<int>( num_bits % bits_per_block != 0 );
williamr@2
  1737
}
williamr@2
  1738
williamr@2
  1739
// gives a reference to the highest block
williamr@2
  1740
//
williamr@2
  1741
template <typename Block, typename Allocator>
williamr@2
  1742
inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
williamr@2
  1743
{
williamr@2
  1744
    return const_cast<Block &>
williamr@2
  1745
           (static_cast<const dynamic_bitset *>(this)->m_highest_block());
williamr@2
  1746
}
williamr@2
  1747
williamr@2
  1748
// gives a const-reference to the highest block
williamr@2
  1749
//
williamr@2
  1750
template <typename Block, typename Allocator>
williamr@2
  1751
inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
williamr@2
  1752
{
williamr@2
  1753
    assert(size() > 0 && num_blocks() > 0);
williamr@2
  1754
    return m_bits.back();
williamr@2
  1755
}
williamr@2
  1756
williamr@2
  1757
williamr@2
  1758
// If size() is not a multiple of bits_per_block
williamr@2
  1759
// then not all the bits in the last block are used.
williamr@2
  1760
// This function resets the unused bits (convenient
williamr@2
  1761
// for the implementation of many member functions)
williamr@2
  1762
//
williamr@2
  1763
template <typename Block, typename Allocator>
williamr@2
  1764
inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
williamr@2
  1765
{
williamr@2
  1766
    assert (num_blocks() == calc_num_blocks(m_num_bits));
williamr@2
  1767
williamr@2
  1768
    // if != 0 this is the number of bits used in the last block
williamr@2
  1769
    const block_width_type extra_bits = count_extra_bits();
williamr@2
  1770
williamr@2
  1771
    if (extra_bits != 0)
williamr@2
  1772
        m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
williamr@2
  1773
williamr@2
  1774
}
williamr@2
  1775
williamr@2
  1776
// check class invariants
williamr@2
  1777
template <typename Block, typename Allocator>
williamr@2
  1778
bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
williamr@2
  1779
{
williamr@2
  1780
    const block_width_type extra_bits = count_extra_bits();
williamr@2
  1781
    if (extra_bits > 0) {
williamr@2
  1782
        block_type const mask = (~static_cast<Block>(0) << extra_bits);
williamr@2
  1783
        if ((m_highest_block() & mask) != 0)
williamr@2
  1784
            return false;
williamr@2
  1785
    }
williamr@2
  1786
    if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
williamr@2
  1787
        return false;
williamr@2
  1788
williamr@2
  1789
    return true;
williamr@2
  1790
williamr@2
  1791
}
williamr@2
  1792
williamr@2
  1793
williamr@2
  1794
} // namespace boost
williamr@2
  1795
williamr@2
  1796
williamr@2
  1797
#undef BOOST_BITSET_CHAR
williamr@2
  1798
williamr@2
  1799
#endif // include guard
williamr@2
  1800