Merge c:/dyninst/pc_bluegene/dyninst into dyn_pc_integration
[dyninst.git] / external / 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(__IBMCPP__) && BOOST_WORKAROUND(__IBMCPP__, BOOST_TESTED_AT(600))
480
481 // Workaround for IBM's AIX platform.
482 // See http://comments.gmane.org/gmane.comp.lib.boost.user/15331
483 //
484 // NOTE:
485 //  The compiler is actually right, until core issue 454 will be settled:
486 //   <http://www.open-std.org/JTC1/SC22/WG21/docs/cwg_active.html#454>
487 //
488 //  It's arguable whether we want to mark this with BOOST_WORKAROUND or not.
489
490
491 template<typename Block, typename Allocator>
492 dynamic_bitset<Block, Allocator>::block_width_type const
493 dynamic_bitset<Block, Allocator>::bits_per_block;
494
495 template<typename Block, typename Allocator>
496 dynamic_bitset<Block, Allocator>::block_width_type const
497 dynamic_bitset<Block, Allocator>::ulong_width;
498
499 #endif
500
501 // Global Functions:
502
503 // comparison
504 template <typename Block, typename Allocator>
505 bool operator!=(const dynamic_bitset<Block, Allocator>& a,
506                 const dynamic_bitset<Block, Allocator>& b);
507
508 template <typename Block, typename Allocator>
509 bool operator<=(const dynamic_bitset<Block, Allocator>& a,
510                 const dynamic_bitset<Block, Allocator>& b);
511
512 template <typename Block, typename Allocator>
513 bool operator>(const dynamic_bitset<Block, Allocator>& a,
514                const dynamic_bitset<Block, Allocator>& b);
515
516 template <typename Block, typename Allocator>
517 bool operator>=(const dynamic_bitset<Block, Allocator>& a,
518                 const dynamic_bitset<Block, Allocator>& b);
519
520 // stream operators
521 #ifdef BOOST_OLD_IOSTREAMS
522 template <typename Block, typename Allocator>
523 std::ostream& operator<<(std::ostream& os,
524                          const dynamic_bitset<Block, Allocator>& b);
525
526 template <typename Block, typename Allocator>
527 std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
528 #else
529 template <typename CharT, typename Traits, typename Block, typename Allocator>
530 std::basic_ostream<CharT, Traits>&
531 operator<<(std::basic_ostream<CharT, Traits>& os,
532            const dynamic_bitset<Block, Allocator>& b);
533
534 template <typename CharT, typename Traits, typename Block, typename Allocator>
535 std::basic_istream<CharT, Traits>&
536 operator>>(std::basic_istream<CharT, Traits>& is,
537            dynamic_bitset<Block, Allocator>& b);
538 #endif
539
540 // bitset operations
541 template <typename Block, typename Allocator>
542 dynamic_bitset<Block, Allocator>
543 operator&(const dynamic_bitset<Block, Allocator>& b1,
544           const dynamic_bitset<Block, Allocator>& b2);
545
546 template <typename Block, typename Allocator>
547 dynamic_bitset<Block, Allocator>
548 operator|(const dynamic_bitset<Block, Allocator>& b1,
549           const dynamic_bitset<Block, Allocator>& b2);
550
551 template <typename Block, typename Allocator>
552 dynamic_bitset<Block, Allocator>
553 operator^(const dynamic_bitset<Block, Allocator>& b1,
554           const dynamic_bitset<Block, Allocator>& b2);
555
556 template <typename Block, typename Allocator>
557 dynamic_bitset<Block, Allocator>
558 operator-(const dynamic_bitset<Block, Allocator>& b1,
559           const dynamic_bitset<Block, Allocator>& b2);
560
561 // namespace scope swap
562 template<typename Block, typename Allocator>
563 void swap(dynamic_bitset<Block, Allocator>& b1,
564           dynamic_bitset<Block, Allocator>& b2);
565
566
567 template <typename Block, typename Allocator, typename stringT>
568 void
569 to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s);
570
571 template <typename Block, typename Allocator, typename BlockOutputIterator>
572 void
573 to_block_range(const dynamic_bitset<Block, Allocator>& b,
574                BlockOutputIterator result);
575
576
577 template <typename BlockIterator, typename B, typename A>
578 inline void
579 from_block_range(BlockIterator first, BlockIterator last,
580                  dynamic_bitset<B, A>& result)
581 {
582     // PRE: distance(first, last) <= numblocks()
583     std::copy (first, last, result.m_bits.begin());
584 }
585
586 //=============================================================================
587 // dynamic_bitset implementation
588
589
590 //-----------------------------------------------------------------------------
591 // constructors, etc.
592
593 template <typename Block, typename Allocator>
594 dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
595   : m_bits(alloc), m_num_bits(0)
596 {
597
598 }
599
600 template <typename Block, typename Allocator>
601 dynamic_bitset<Block, Allocator>::
602 dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
603     : m_bits(alloc),
604       m_num_bits(0)
605 {
606     init_from_unsigned_long(num_bits, value);
607 }
608
609 // copy constructor
610 template <typename Block, typename Allocator>
611 inline dynamic_bitset<Block, Allocator>::
612 dynamic_bitset(const dynamic_bitset& b)
613   : m_bits(b.m_bits), m_num_bits(b.m_num_bits)
614 {
615
616 }
617
618 template <typename Block, typename Allocator>
619 inline dynamic_bitset<Block, Allocator>::
620 ~dynamic_bitset()
621 {
622     assert(m_check_invariants());
623 }
624
625 template <typename Block, typename Allocator>
626 inline void dynamic_bitset<Block, Allocator>::
627 swap(dynamic_bitset<Block, Allocator>& b) // no throw
628 {
629     std::swap(m_bits, b.m_bits);
630     std::swap(m_num_bits, b.m_num_bits);
631 }
632
633 template <typename Block, typename Allocator>
634 dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
635 operator=(const dynamic_bitset<Block, Allocator>& b)
636 {
637     m_bits = b.m_bits;
638     m_num_bits = b.m_num_bits;
639     return *this;
640 }
641
642 template <typename Block, typename Allocator>
643 inline typename dynamic_bitset<Block, Allocator>::allocator_type
644 dynamic_bitset<Block, Allocator>::get_allocator() const
645 {
646     return m_bits.get_allocator();
647 }
648
649 //-----------------------------------------------------------------------------
650 // size changing operations
651
652 template <typename Block, typename Allocator>
653 void dynamic_bitset<Block, Allocator>::
654 resize(size_type num_bits, bool value) // strong guarantee
655 {
656
657   const size_type old_num_blocks = num_blocks();
658   const size_type required_blocks = calc_num_blocks(num_bits);
659
660   const block_type v = value? ~Block(0) : Block(0);
661
662   if (required_blocks != old_num_blocks) {
663     m_bits.resize(required_blocks, v); // s.g. (copy)
664   }
665
666
667   // At this point:
668   //
669   //  - if the buffer was shrunk, we have nothing more to do,
670   //    except a call to m_zero_unused_bits()
671   //
672   //  - if it was enlarged, all the (used) bits in the new blocks have
673   //    the correct value, but we have not yet touched those bits, if
674   //    any, that were 'unused bits' before enlarging: if value == true,
675   //    they must be set.
676
677   if (value && (num_bits > m_num_bits)) {
678
679     const size_type extra_bits = count_extra_bits();
680     if (extra_bits) {
681         assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
682
683         // Set them.
684         m_bits[old_num_blocks - 1] |= (v << extra_bits);
685     }
686
687   }
688
689   m_num_bits = num_bits;
690   m_zero_unused_bits();
691
692 }
693
694 template <typename Block, typename Allocator>
695 void dynamic_bitset<Block, Allocator>::
696 clear() // no throw
697 {
698   m_bits.clear();
699   m_num_bits = 0;
700 }
701
702
703 template <typename Block, typename Allocator>
704 void dynamic_bitset<Block, Allocator>::
705 push_back(bool bit)
706 {
707   const size_type sz = size();
708   resize(sz + 1);
709   set(sz, bit);
710 }
711
712 template <typename Block, typename Allocator>
713 void dynamic_bitset<Block, Allocator>::
714 append(Block value) // strong guarantee
715 {
716     const block_width_type r = count_extra_bits();
717
718     if (r == 0) {
719         // the buffer is empty, or all blocks are filled
720         m_bits.push_back(value);
721     }
722     else {
723         m_bits.push_back(value >> (bits_per_block - r));
724         m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
725     }
726
727     m_num_bits += bits_per_block;
728     assert(m_check_invariants());
729
730 }
731
732
733 //-----------------------------------------------------------------------------
734 // bitset operations
735 template <typename Block, typename Allocator>
736 dynamic_bitset<Block, Allocator>&
737 dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
738 {
739     assert(size() == rhs.size());
740     for (size_type i = 0; i < num_blocks(); ++i)
741         m_bits[i] &= rhs.m_bits[i];
742     return *this;
743 }
744
745 template <typename Block, typename Allocator>
746 dynamic_bitset<Block, Allocator>&
747 dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
748 {
749     assert(size() == rhs.size());
750     for (size_type i = 0; i < num_blocks(); ++i)
751         m_bits[i] |= rhs.m_bits[i];
752     //m_zero_unused_bits();
753     return *this;
754 }
755
756 template <typename Block, typename Allocator>
757 dynamic_bitset<Block, Allocator>&
758 dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
759 {
760     assert(size() == rhs.size());
761     for (size_type i = 0; i < this->num_blocks(); ++i)
762         m_bits[i] ^= rhs.m_bits[i];
763     //m_zero_unused_bits();
764     return *this;
765 }
766
767 template <typename Block, typename Allocator>
768 dynamic_bitset<Block, Allocator>&
769 dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
770 {
771     assert(size() == rhs.size());
772     for (size_type i = 0; i < num_blocks(); ++i)
773         m_bits[i] &= ~rhs.m_bits[i];
774     //m_zero_unused_bits();
775     return *this;
776 }
777
778 //
779 // NOTE:
780 //  Note that the 'if (r != 0)' is crucial to avoid undefined
781 //  behavior when the left hand operand of >> isn't promoted to a
782 //  wider type (because rs would be too large).
783 //
784 template <typename Block, typename Allocator>
785 dynamic_bitset<Block, Allocator>&
786 dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
787 {
788     if (n >= m_num_bits)
789         return reset();
790     //else
791     if (n > 0) {
792
793         size_type    const last = num_blocks() - 1;  // num_blocks() is >= 1
794         size_type    const div  = n / bits_per_block; // div is <= last
795         block_width_type const r = bit_index(n);
796         block_type * const b    = &m_bits[0];
797
798         if (r != 0) {
799
800             block_width_type const rs = bits_per_block - r;
801
802             for (size_type i = last-div; i>0; --i) {
803                 b[i+div] = (b[i] << r) | (b[i-1] >> rs);
804             }
805             b[div] = b[0] << r;
806
807         }
808         else {
809             for (size_type i = last-div; i>0; --i) {
810                 b[i+div] = b[i];
811             }
812             b[div] = b[0];
813         }
814
815         // zero out div blocks at the less significant end
816         std::fill_n(b, div, static_cast<block_type>(0));
817
818         // zero out any 1 bit that flowed into the unused part
819         m_zero_unused_bits(); // thanks to Lester Gong
820
821     }
822
823     return *this;
824
825
826 }
827
828
829 //
830 // NOTE:
831 //  see the comments to operator <<=
832 //
833 template <typename B, typename A>
834 dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
835     if (n >= m_num_bits) {
836         return reset();
837     }
838     //else
839     if (n>0) {
840
841         size_type  const last  = num_blocks() - 1; // num_blocks() is >= 1
842         size_type  const div   = n / bits_per_block;   // div is <= last
843         block_width_type const r     = bit_index(n);
844         block_type * const b   = &m_bits[0];
845
846
847         if (r != 0) {
848
849             block_width_type const ls = bits_per_block - r;
850
851             for (size_type i = div; i < last; ++i) {
852                 b[i-div] = (b[i] >> r) | (b[i+1]  << ls);
853             }
854             // r bits go to zero
855             b[last-div] = b[last] >> r;
856         }
857
858         else {
859             for (size_type i = div; i <= last; ++i) {
860                 b[i-div] = b[i];
861             }
862             // note the '<=': the last iteration 'absorbs'
863             // b[last-div] = b[last] >> 0;
864         }
865
866
867
868         // div blocks are zero filled at the most significant end
869         std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
870     }
871
872     return *this;
873 }
874
875
876 template <typename Block, typename Allocator>
877 dynamic_bitset<Block, Allocator>
878 dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
879 {
880     dynamic_bitset r(*this);
881     return r <<= n;
882 }
883
884 template <typename Block, typename Allocator>
885 dynamic_bitset<Block, Allocator>
886 dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
887 {
888     dynamic_bitset r(*this);
889     return r >>= n;
890 }
891
892
893 //-----------------------------------------------------------------------------
894 // basic bit operations
895
896 template <typename Block, typename Allocator>
897 dynamic_bitset<Block, Allocator>&
898 dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
899 {
900     assert(pos < m_num_bits);
901
902     if (val)
903         m_bits[block_index(pos)] |= bit_mask(pos);
904     else
905         reset(pos);
906
907     return *this;
908 }
909
910 template <typename Block, typename Allocator>
911 dynamic_bitset<Block, Allocator>&
912 dynamic_bitset<Block, Allocator>::set()
913 {
914   std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
915   m_zero_unused_bits();
916   return *this;
917 }
918
919 template <typename Block, typename Allocator>
920 dynamic_bitset<Block, Allocator>&
921 dynamic_bitset<Block, Allocator>::reset(size_type pos)
922 {
923     assert(pos < m_num_bits);
924 #if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
925     // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
926     // use the |^ variation instead.. <grafik>
927     m_bits[block_index(pos)] |= bit_mask(pos);
928     m_bits[block_index(pos)] ^= bit_mask(pos);
929 #else
930     m_bits[block_index(pos)] &= ~bit_mask(pos);
931 #endif
932     return *this;
933 }
934
935 template <typename Block, typename Allocator>
936 dynamic_bitset<Block, Allocator>&
937 dynamic_bitset<Block, Allocator>::reset()
938 {
939   std::fill(m_bits.begin(), m_bits.end(), Block(0));
940   return *this;
941 }
942
943 template <typename Block, typename Allocator>
944 dynamic_bitset<Block, Allocator>&
945 dynamic_bitset<Block, Allocator>::flip(size_type pos)
946 {
947     assert(pos < m_num_bits);
948     m_bits[block_index(pos)] ^= bit_mask(pos);
949     return *this;
950 }
951
952 template <typename Block, typename Allocator>
953 dynamic_bitset<Block, Allocator>&
954 dynamic_bitset<Block, Allocator>::flip()
955 {
956     for (size_type i = 0; i < num_blocks(); ++i)
957         m_bits[i] = ~m_bits[i];
958     m_zero_unused_bits();
959     return *this;
960 }
961
962 template <typename Block, typename Allocator>
963 bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
964 {
965     return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
966 }
967
968 template <typename Block, typename Allocator>
969 bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
970 {
971     assert(pos < m_num_bits);
972     return m_unchecked_test(pos);
973 }
974
975 template <typename Block, typename Allocator>
976 bool dynamic_bitset<Block, Allocator>::any() const
977 {
978     for (size_type i = 0; i < num_blocks(); ++i)
979         if (m_bits[i])
980             return true;
981     return false;
982 }
983
984 template <typename Block, typename Allocator>
985 inline bool dynamic_bitset<Block, Allocator>::none() const
986 {
987     return !any();
988 }
989
990 template <typename Block, typename Allocator>
991 dynamic_bitset<Block, Allocator>
992 dynamic_bitset<Block, Allocator>::operator~() const
993 {
994     dynamic_bitset b(*this);
995     b.flip();
996     return b;
997 }
998
999 template <typename Block, typename Allocator>
1000 typename dynamic_bitset<Block, Allocator>::size_type
1001 dynamic_bitset<Block, Allocator>::count() const
1002 {
1003     using detail::dynamic_bitset_impl::table_width;
1004     using detail::dynamic_bitset_impl::access_by_bytes;
1005     using detail::dynamic_bitset_impl::access_by_blocks;
1006     using detail::dynamic_bitset_impl::value_to_type;
1007
1008 #if BOOST_WORKAROUND(__GNUC__, == 4) && (__GNUC_MINOR__ == 3) && (__GNUC_PATCHLEVEL__ == 3)
1009     // NOTE: Explicit qualification of "bits_per_block"
1010     //       breaks compilation on gcc 4.3.3
1011     enum { no_padding = bits_per_block == CHAR_BIT * sizeof(Block) };
1012 #else
1013     // NOTE: Explicitly qualifying "bits_per_block" to workaround
1014     //       regressions of gcc 3.4.x
1015     enum { no_padding =
1016         dynamic_bitset<Block, Allocator>::bits_per_block
1017         == CHAR_BIT * sizeof(Block) };
1018 #endif
1019
1020     enum { enough_table_width = table_width >= CHAR_BIT };
1021
1022     enum { mode = (no_padding && enough_table_width)
1023                           ? access_by_bytes
1024                           : access_by_blocks };
1025
1026     return do_count(m_bits.begin(), num_blocks(), Block(0),
1027                     static_cast<value_to_type<(bool)mode> *>(0));
1028 }
1029
1030
1031 //-----------------------------------------------------------------------------
1032 // conversions
1033
1034
1035 template <typename B, typename A, typename stringT>
1036 void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
1037                       bool dump_all)
1038 {
1039     typedef typename stringT::traits_type Tr;
1040     typedef typename stringT::value_type  Ch;
1041
1042     BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
1043     const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1044     const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1045
1046     // Note that this function may access (when
1047     // dump_all == true) bits beyond position size() - 1
1048
1049     typedef typename dynamic_bitset<B, A>::size_type size_type;
1050
1051     const size_type len = dump_all?
1052          dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
1053          b.size();
1054     s.assign (len, zero);
1055
1056     for (size_type i = 0; i < len; ++i) {
1057         if (b.m_unchecked_test(i))
1058             Tr::assign(s[len - 1 - i], one);
1059
1060     }
1061
1062 }
1063
1064
1065 // A comment similar to the one about the constructor from
1066 // basic_string can be done here. Thanks to James Kanze for
1067 // making me (Gennaro) realize this important separation of
1068 // concerns issue, as well as many things about i18n.
1069 //
1070 template <typename Block, typename Allocator, typename stringT>
1071 inline void
1072 to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
1073 {
1074     to_string_helper(b, s, false);
1075 }
1076
1077
1078 // Differently from to_string this function dumps out
1079 // every bit of the internal representation (may be
1080 // useful for debugging purposes)
1081 //
1082 template <typename B, typename A, typename stringT>
1083 inline void
1084 dump_to_string(const dynamic_bitset<B, A>& b, stringT& s)
1085 {
1086     to_string_helper(b, s, true /* =dump_all*/);
1087 }
1088
1089 template <typename Block, typename Allocator, typename BlockOutputIterator>
1090 inline void
1091 to_block_range(const dynamic_bitset<Block, Allocator>& b,
1092                BlockOutputIterator result)
1093 {
1094     // note how this copies *all* bits, including the
1095     // unused ones in the last block (which are zero)
1096     std::copy(b.m_bits.begin(), b.m_bits.end(), result);
1097 }
1098
1099 template <typename Block, typename Allocator>
1100 unsigned long dynamic_bitset<Block, Allocator>::
1101 to_ulong() const
1102 {
1103
1104   if (m_num_bits == 0)
1105       return 0; // convention
1106
1107   // Check for overflows. This may be a performance burden on very
1108   // large bitsets but is required by the specification, sorry
1109   if (find_next(ulong_width - 1) != npos)
1110     throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
1111
1112
1113   // Ok, from now on we can be sure there's no "on" bit
1114   // beyond the "allowed" positions
1115   typedef unsigned long result_type;
1116
1117   const size_type max_size =
1118             (std::min)(m_num_bits, static_cast<size_type>(ulong_width));
1119
1120   const size_type last_block = block_index( max_size - 1 );
1121
1122   assert((last_block * bits_per_block) < static_cast<size_type>(ulong_width));
1123
1124   result_type result = 0;
1125   for (size_type i = 0; i <= last_block; ++i) {
1126     const size_type offset = i * bits_per_block;
1127     result |= (static_cast<result_type>(m_bits[i]) << offset);
1128   }
1129
1130   return result;
1131 }
1132
1133 template <typename Block, typename Allocator>
1134 inline typename dynamic_bitset<Block, Allocator>::size_type
1135 dynamic_bitset<Block, Allocator>::size() const
1136 {
1137     return m_num_bits;
1138 }
1139
1140 template <typename Block, typename Allocator>
1141 inline typename dynamic_bitset<Block, Allocator>::size_type
1142 dynamic_bitset<Block, Allocator>::num_blocks() const
1143 {
1144     return m_bits.size();
1145 }
1146
1147 template <typename Block, typename Allocator>
1148 inline typename dynamic_bitset<Block, Allocator>::size_type
1149 dynamic_bitset<Block, Allocator>::max_size() const
1150 {
1151     // Semantics of vector<>::max_size() aren't very clear
1152     // (see lib issue 197) and many library implementations
1153     // simply return dummy values, _unrelated_ to the underlying
1154     // allocator.
1155     //
1156     // Given these problems, I was tempted to not provide this
1157     // function at all but the user could need it if he provides
1158     // his own allocator.
1159     //
1160
1161     const size_type m = detail::dynamic_bitset_impl::
1162                         vector_max_size_workaround(m_bits);
1163
1164     return m <= (size_type(-1)/bits_per_block) ?
1165         m * bits_per_block :
1166         size_type(-1);
1167 }
1168
1169 template <typename Block, typename Allocator>
1170 inline bool dynamic_bitset<Block, Allocator>::empty() const
1171 {
1172   return size() == 0;
1173 }
1174
1175 template <typename Block, typename Allocator>
1176 bool dynamic_bitset<Block, Allocator>::
1177 is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1178 {
1179     assert(size() == a.size());
1180     for (size_type i = 0; i < num_blocks(); ++i)
1181         if (m_bits[i] & ~a.m_bits[i])
1182             return false;
1183     return true;
1184 }
1185
1186 template <typename Block, typename Allocator>
1187 bool dynamic_bitset<Block, Allocator>::
1188 is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1189 {
1190     assert(size() == a.size());
1191     assert(num_blocks() == a.num_blocks());
1192
1193     bool proper = false;
1194     for (size_type i = 0; i < num_blocks(); ++i) {
1195         const Block & bt =   m_bits[i];
1196         const Block & ba = a.m_bits[i];
1197
1198         if (bt & ~ba)
1199             return false; // not a subset at all
1200         if (ba & ~bt)
1201             proper = true;
1202     }
1203     return proper;
1204 }
1205
1206 template <typename Block, typename Allocator>
1207 bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
1208 {
1209     size_type common_blocks = num_blocks() < b.num_blocks()
1210                               ? num_blocks() : b.num_blocks();
1211
1212     for(size_type i = 0; i < common_blocks; ++i) {
1213         if(m_bits[i] & b.m_bits[i])
1214             return true;
1215     }
1216     return false;
1217 }
1218
1219 // --------------------------------
1220 // lookup
1221
1222
1223 // look for the first bit "on", starting
1224 // from the block with index first_block
1225 //
1226 template <typename Block, typename Allocator>
1227 typename dynamic_bitset<Block, Allocator>::size_type
1228 dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
1229 {
1230     size_type i = first_block;
1231
1232     // skip null blocks
1233     while (i < num_blocks() && m_bits[i] == 0)
1234         ++i;
1235
1236     if (i >= num_blocks())
1237         return npos; // not found
1238
1239     return i * bits_per_block + boost::lowest_bit(m_bits[i]);
1240
1241 }
1242
1243
1244 template <typename Block, typename Allocator>
1245 typename dynamic_bitset<Block, Allocator>::size_type
1246 dynamic_bitset<Block, Allocator>::find_first() const
1247 {
1248     return m_do_find_from(0);
1249 }
1250
1251
1252 template <typename Block, typename Allocator>
1253 typename dynamic_bitset<Block, Allocator>::size_type
1254 dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
1255 {
1256
1257     const size_type sz = size();
1258     if (pos >= (sz-1) || sz == 0)
1259         return npos;
1260
1261     ++pos;
1262
1263     const size_type blk = block_index(pos);
1264     const block_width_type ind = bit_index(pos);
1265
1266     // mask out bits before pos
1267     const Block fore = m_bits[blk] & ( ~Block(0) << ind );
1268
1269     return fore?
1270         blk * bits_per_block + lowest_bit(fore)
1271         :
1272         m_do_find_from(blk + 1);
1273
1274 }
1275
1276
1277
1278 //-----------------------------------------------------------------------------
1279 // comparison
1280
1281 template <typename Block, typename Allocator>
1282 bool operator==(const dynamic_bitset<Block, Allocator>& a,
1283                 const dynamic_bitset<Block, Allocator>& b)
1284 {
1285     return (a.m_num_bits == b.m_num_bits)
1286            && (a.m_bits == b.m_bits);
1287 }
1288
1289 template <typename Block, typename Allocator>
1290 inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
1291                        const dynamic_bitset<Block, Allocator>& b)
1292 {
1293     return !(a == b);
1294 }
1295
1296 template <typename Block, typename Allocator>
1297 bool operator<(const dynamic_bitset<Block, Allocator>& a,
1298                const dynamic_bitset<Block, Allocator>& b)
1299 {
1300     assert(a.size() == b.size());
1301     typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
1302
1303     //if (a.size() == 0)
1304     //  return false;
1305
1306     // Since we are storing the most significant bit
1307     // at pos == size() - 1, we need to do the comparisons in reverse.
1308     //
1309     for (size_type ii = a.num_blocks(); ii > 0; --ii) {
1310       size_type i = ii-1;
1311       if (a.m_bits[i] < b.m_bits[i])
1312         return true;
1313       else if (a.m_bits[i] > b.m_bits[i])
1314         return false;
1315     }
1316     return false;
1317 }
1318
1319 template <typename Block, typename Allocator>
1320 inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
1321                        const dynamic_bitset<Block, Allocator>& b)
1322 {
1323     return !(a > b);
1324 }
1325
1326 template <typename Block, typename Allocator>
1327 inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
1328                       const dynamic_bitset<Block, Allocator>& b)
1329 {
1330     return b < a;
1331 }
1332
1333 template <typename Block, typename Allocator>
1334 inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
1335                        const dynamic_bitset<Block, Allocator>& b)
1336 {
1337     return !(a < b);
1338 }
1339
1340 //-----------------------------------------------------------------------------
1341 // stream operations
1342
1343 #ifdef BOOST_OLD_IOSTREAMS
1344 template < typename Block, typename Alloc>
1345 std::ostream&
1346 operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
1347 {
1348     // NOTE: since this is aimed at "classic" iostreams, exception
1349     // masks on the stream are not supported. The library that
1350     // ships with gcc 2.95 has an exceptions() member function but
1351     // nothing is actually implemented; not even the class ios::failure.
1352
1353     using namespace std;
1354
1355     const ios::iostate ok = ios::goodbit;
1356     ios::iostate err = ok;
1357
1358     if (os.opfx()) {
1359
1360         //try
1361         typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
1362
1363         const bitsetsize_type sz = b.size();
1364         std::streambuf * buf = os.rdbuf();
1365         size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
1366             || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz;
1367
1368         const char fill_char = os.fill();
1369         const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
1370
1371         // if needed fill at left; pad is decresed along the way
1372         if (adjustfield != ios::left) {
1373             for (; 0 < npad; --npad)
1374                 if (fill_char != buf->sputc(fill_char)) {
1375                     err |= ios::failbit;
1376                     break;
1377                 }
1378         }
1379
1380         if (err == ok) {
1381             // output the bitset
1382             for (bitsetsize_type i = b.size(); 0 < i; --i) {
1383                 const char dig = b.test(i-1)? '1' : '0';
1384                 if (EOF == buf->sputc(dig)) {
1385                     err |= ios::failbit;
1386                     break;
1387                 }
1388             }
1389         }
1390
1391         if (err == ok) {
1392             // if needed fill at right
1393             for (; 0 < npad; --npad) {
1394                 if (fill_char != buf->sputc(fill_char)) {
1395                     err |= ios::failbit;
1396                     break;
1397                 }
1398             }
1399         }
1400
1401         os.osfx();
1402         os.width(0);
1403
1404     } // if opfx
1405
1406     if(err != ok)
1407         os.setstate(err); // assume this does NOT throw
1408     return os;
1409
1410 }
1411 #else
1412
1413 template <typename Ch, typename Tr, typename Block, typename Alloc>
1414 std::basic_ostream<Ch, Tr>&
1415 operator<<(std::basic_ostream<Ch, Tr>& os,
1416            const dynamic_bitset<Block, Alloc>& b)
1417 {
1418
1419     using namespace std;
1420
1421     const ios_base::iostate ok = ios_base::goodbit;
1422     ios_base::iostate err = ok;
1423
1424     typename basic_ostream<Ch, Tr>::sentry cerberos(os);
1425     if (cerberos) {
1426
1427         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
1428         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1429         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1430
1431         try {
1432
1433             typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
1434             typedef basic_streambuf<Ch, Tr> buffer_type;
1435
1436             buffer_type * buf = os.rdbuf();
1437             size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
1438                 || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size();
1439
1440             const Ch fill_char = os.fill();
1441             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
1442
1443             // if needed fill at left; pad is decresed along the way
1444             if (adjustfield != ios_base::left) {
1445                 for (; 0 < npad; --npad)
1446                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1447                           err |= ios_base::failbit;
1448                           break;
1449                     }
1450             }
1451
1452             if (err == ok) {
1453                 // output the bitset
1454                 for (bitsetsize_type i = b.size(); 0 < i; --i) {
1455                     typename buffer_type::int_type
1456                         ret = buf->sputc(b.test(i-1)? one : zero);
1457                     if (Tr::eq_int_type(Tr::eof(), ret)) {
1458                         err |= ios_base::failbit;
1459                         break;
1460                     }
1461                 }
1462             }
1463
1464             if (err == ok) {
1465                 // if needed fill at right
1466                 for (; 0 < npad; --npad) {
1467                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1468                         err |= ios_base::failbit;
1469                         break;
1470                     }
1471                 }
1472             }
1473
1474
1475             os.width(0);
1476
1477         } catch (...) { // see std 27.6.1.1/4
1478             bool rethrow = false;
1479             try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
1480
1481             if (rethrow)
1482                 throw;
1483         }
1484     }
1485
1486     if(err != ok)
1487         os.setstate(err); // may throw exception
1488     return os;
1489
1490 }
1491 #endif
1492
1493
1494 #ifdef BOOST_OLD_IOSTREAMS
1495
1496     // A sentry-like class that calls isfx in its destructor.
1497     // "Necessary" because bit_appender::do_append may throw.
1498     class pseudo_sentry {
1499         std::istream & m_r;
1500         const bool m_ok;
1501     public:
1502         explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
1503         ~pseudo_sentry() { m_r.isfx(); }
1504         operator bool() const { return m_ok; }
1505     };
1506
1507 template <typename Block, typename Alloc>
1508 std::istream&
1509 operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
1510 {
1511
1512 // Extractor for classic IO streams (libstdc++ < 3.0)
1513 // ----------------------------------------------------//
1514 //  It's assumed that the stream buffer functions, and
1515 //  the stream's setstate() _cannot_ throw.
1516
1517
1518     typedef dynamic_bitset<Block, Alloc> bitset_type;
1519     typedef typename bitset_type::size_type size_type;
1520
1521     std::ios::iostate err = std::ios::goodbit;
1522     pseudo_sentry cerberos(is); // skips whitespaces
1523     if(cerberos) {
1524
1525         b.clear();
1526
1527         const std::streamsize w = is.width();
1528         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()
1529                                                          ? w : b.max_size();
1530         typename bitset_type::bit_appender appender(b);
1531         std::streambuf * buf = is.rdbuf();
1532         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
1533
1534             if (c == EOF) {
1535                 err |= std::ios::eofbit;
1536                 break;
1537             }
1538             else if (char(c) != '0' && char(c) != '1')
1539                 break; // non digit character
1540
1541             else {
1542                 try {
1543                     appender.do_append(char(c) == '1');
1544                 }
1545                 catch(...) {
1546                     is.setstate(std::ios::failbit); // assume this can't throw
1547                     throw;
1548                 }
1549             }
1550
1551         } // for
1552     }
1553
1554     is.width(0);
1555     if (b.size() == 0)
1556         err |= std::ios::failbit;
1557     if (err != std::ios::goodbit)
1558         is.setstate (err); // may throw
1559
1560     return is;
1561 }
1562
1563 #else // BOOST_OLD_IOSTREAMS
1564
1565 template <typename Ch, typename Tr, typename Block, typename Alloc>
1566 std::basic_istream<Ch, Tr>&
1567 operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
1568 {
1569
1570     using namespace std;
1571
1572     typedef dynamic_bitset<Block, Alloc> bitset_type;
1573     typedef typename bitset_type::size_type size_type;
1574
1575     const streamsize w = is.width();
1576     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()?
1577                                          w : b.max_size();
1578
1579     ios_base::iostate err = ios_base::goodbit;
1580     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
1581     if(cerberos) {
1582
1583         // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
1584         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
1585         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1586         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1587
1588         b.clear();
1589         try {
1590             typename bitset_type::bit_appender appender(b);
1591             basic_streambuf <Ch, Tr> * buf = is.rdbuf();
1592             typename Tr::int_type c = buf->sgetc();
1593             for( ; appender.get_count() < limit; c = buf->snextc() ) {
1594
1595                 if (Tr::eq_int_type(Tr::eof(), c)) {
1596                     err |= ios_base::eofbit;
1597                     break;
1598                 }
1599                 else {
1600                     const Ch to_c = Tr::to_char_type(c);
1601                     const bool is_one = Tr::eq(to_c, one);
1602
1603                     if (!is_one && !Tr::eq(to_c, zero))
1604                         break; // non digit character
1605
1606                     appender.do_append(is_one);
1607
1608                 }
1609
1610             } // for
1611         }
1612         catch (...) {
1613             // catches from stream buf, or from vector:
1614             //
1615             // bits_stored bits have been extracted and stored, and
1616             // either no further character is extractable or we can't
1617             // append to the underlying vector (out of memory)
1618
1619             bool rethrow = false;   // see std 27.6.1.1/4
1620             try { is.setstate(ios_base::badbit); }
1621             catch(...) { rethrow = true; }
1622
1623             if (rethrow)
1624                 throw;
1625
1626         }
1627     }
1628
1629     is.width(0);
1630     if (b.size() == 0 /*|| !cerberos*/)
1631         err |= ios_base::failbit;
1632     if (err != ios_base::goodbit)
1633         is.setstate (err); // may throw
1634
1635     return is;
1636
1637 }
1638
1639
1640 #endif
1641
1642
1643 //-----------------------------------------------------------------------------
1644 // bitset operations
1645
1646 template <typename Block, typename Allocator>
1647 dynamic_bitset<Block, Allocator>
1648 operator&(const dynamic_bitset<Block, Allocator>& x,
1649           const dynamic_bitset<Block, Allocator>& y)
1650 {
1651     dynamic_bitset<Block, Allocator> b(x);
1652     return b &= y;
1653 }
1654
1655 template <typename Block, typename Allocator>
1656 dynamic_bitset<Block, Allocator>
1657 operator|(const dynamic_bitset<Block, Allocator>& x,
1658           const dynamic_bitset<Block, Allocator>& y)
1659 {
1660     dynamic_bitset<Block, Allocator> b(x);
1661     return b |= y;
1662 }
1663
1664 template <typename Block, typename Allocator>
1665 dynamic_bitset<Block, Allocator>
1666 operator^(const dynamic_bitset<Block, Allocator>& x,
1667           const dynamic_bitset<Block, Allocator>& y)
1668 {
1669     dynamic_bitset<Block, Allocator> b(x);
1670     return b ^= y;
1671 }
1672
1673 template <typename Block, typename Allocator>
1674 dynamic_bitset<Block, Allocator>
1675 operator-(const dynamic_bitset<Block, Allocator>& x,
1676           const dynamic_bitset<Block, Allocator>& y)
1677 {
1678     dynamic_bitset<Block, Allocator> b(x);
1679     return b -= y;
1680 }
1681
1682 //-----------------------------------------------------------------------------
1683 // namespace scope swap
1684
1685 template<typename Block, typename Allocator>
1686 inline void
1687 swap(dynamic_bitset<Block, Allocator>& left,
1688      dynamic_bitset<Block, Allocator>& right) // no throw
1689 {
1690     left.swap(right);
1691 }
1692
1693
1694 //-----------------------------------------------------------------------------
1695 // private (on conforming compilers) member functions
1696
1697
1698 template <typename Block, typename Allocator>
1699 inline typename dynamic_bitset<Block, Allocator>::size_type
1700 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
1701 {
1702     return num_bits / bits_per_block
1703            + static_cast<int>( num_bits % bits_per_block != 0 );
1704 }
1705
1706 // gives a reference to the highest block
1707 //
1708 template <typename Block, typename Allocator>
1709 inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
1710 {
1711     return const_cast<Block &>
1712            (static_cast<const dynamic_bitset *>(this)->m_highest_block());
1713 }
1714
1715 // gives a const-reference to the highest block
1716 //
1717 template <typename Block, typename Allocator>
1718 inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
1719 {
1720     assert(size() > 0 && num_blocks() > 0);
1721     return m_bits.back();
1722 }
1723
1724
1725 // If size() is not a multiple of bits_per_block
1726 // then not all the bits in the last block are used.
1727 // This function resets the unused bits (convenient
1728 // for the implementation of many member functions)
1729 //
1730 template <typename Block, typename Allocator>
1731 inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
1732 {
1733     assert (num_blocks() == calc_num_blocks(m_num_bits));
1734
1735     // if != 0 this is the number of bits used in the last block
1736     const block_width_type extra_bits = count_extra_bits();
1737
1738     if (extra_bits != 0)
1739         m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
1740
1741 }
1742
1743 // check class invariants
1744 template <typename Block, typename Allocator>
1745 bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
1746 {
1747     const block_width_type extra_bits = count_extra_bits();
1748     if (extra_bits > 0) {
1749         block_type const mask = (~static_cast<Block>(0) << extra_bits);
1750         if ((m_highest_block() & mask) != 0)
1751             return false;
1752     }
1753     if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
1754         return false;
1755
1756     return true;
1757
1758 }
1759
1760
1761 } // namespace boost
1762
1763
1764 #undef BOOST_BITSET_CHAR
1765
1766 #endif // include guard
1767