← Back to branch summary

~twpol/dcplusplus/trunk

« back to all changes in this revision

Viewing changes to boost/boost/dynamic_bitset/dynamic_bitset.hpp

  • Committer: James Ross
  • Date: 2010-07-05 00:03:18 UTC
  • mfrom: (1524.1.650 dcplusplus)
  • Revision ID: silver@warwickcompsoc.co.uk-20100705000318-awwqm8ocpp5m47yz
Merged to trunk.

Show diffs side-by-side

added added

removed removed

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