source: NonGTP/Boost/boost/dynamic_bitset/dynamic_bitset.hpp @ 857

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