Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / dynamic_bitset / dynamic_bitset.hpp
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
48 namespace boost {
49
50 template
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
59 class 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
67 public:
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
77 public:
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
312 private:
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
363 BOOST_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
425 template <typename Block, typename Allocator>
426 bool operator!=(const dynamic_bitset<Block, Allocator>& a,
427                 const dynamic_bitset<Block, Allocator>& b);
428
429 template <typename Block, typename Allocator>
430 bool operator<=(const dynamic_bitset<Block, Allocator>& a,
431                 const dynamic_bitset<Block, Allocator>& b);
432
433 template <typename Block, typename Allocator>
434 bool operator>(const dynamic_bitset<Block, Allocator>& a,
435                const dynamic_bitset<Block, Allocator>& b);
436
437 template <typename Block, typename Allocator>
438 bool operator>=(const dynamic_bitset<Block, Allocator>& a,
439                 const dynamic_bitset<Block, Allocator>& b);
440
441 // stream operators
442 #ifdef BOOST_OLD_IOSTREAMS
443 template <typename Block, typename Allocator>
444 std::ostream& operator<<(std::ostream& os,
445                          const dynamic_bitset<Block, Allocator>& b);
446
447 template <typename Block, typename Allocator>
448 std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
449 #else
450 template <typename CharT, typename Traits, typename Block, typename Allocator>
451 std::basic_ostream<CharT, Traits>&
452 operator<<(std::basic_ostream<CharT, Traits>& os,
453            const dynamic_bitset<Block, Allocator>& b);
454
455 template <typename CharT, typename Traits, typename Block, typename Allocator>
456 std::basic_istream<CharT, Traits>&
457 operator>>(std::basic_istream<CharT, Traits>& is,
458            dynamic_bitset<Block, Allocator>& b);
459 #endif
460
461 // bitset operations
462 template <typename Block, typename Allocator>
463 dynamic_bitset<Block, Allocator>
464 operator&(const dynamic_bitset<Block, Allocator>& b1,
465           const dynamic_bitset<Block, Allocator>& b2);
466
467 template <typename Block, typename Allocator>
468 dynamic_bitset<Block, Allocator>
469 operator|(const dynamic_bitset<Block, Allocator>& b1,
470           const dynamic_bitset<Block, Allocator>& b2);
471
472 template <typename Block, typename Allocator>
473 dynamic_bitset<Block, Allocator>
474 operator^(const dynamic_bitset<Block, Allocator>& b1,
475           const dynamic_bitset<Block, Allocator>& b2);
476
477 template <typename Block, typename Allocator>
478 dynamic_bitset<Block, Allocator>
479 operator-(const dynamic_bitset<Block, Allocator>& b1,
480           const dynamic_bitset<Block, Allocator>& b2);
481
482 // namespace scope swap
483 template<typename Block, typename Allocator>
484 void swap(dynamic_bitset<Block, Allocator>& b1,
485           dynamic_bitset<Block, Allocator>& b2);
486
487
488 template <typename Block, typename Allocator, typename stringT>
489 void
490 to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps
491
492 template <typename Block, typename Allocator, typename BlockOutputIterator>
493 void
494 to_block_range(const dynamic_bitset<Block, Allocator>& b,
495                BlockOutputIterator result);
496
497
498 // gps - check docs with Jeremy
499 //
500 template <typename BlockIterator, typename B, typename A>
501 inline void
502 from_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
516 template <typename Block, typename Allocator>
517 dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
518   : m_bits(alloc), m_num_bits(0)
519 {
520
521 }
522
523 template <typename Block, typename Allocator>
524 dynamic_bitset<Block, Allocator>::
525 dynamic_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
555 template <typename Block, typename Allocator>
556 inline dynamic_bitset<Block, Allocator>::
557 dynamic_bitset(const dynamic_bitset& b)
558   : m_bits(b.m_bits), m_num_bits(b.m_num_bits)  // [gps]
559 {
560
561 }
562
563 template <typename Block, typename Allocator>
564 inline dynamic_bitset<Block, Allocator>::
565 ~dynamic_bitset()
566 {
567     assert(m_check_invariants());
568 }
569
570 template <typename Block, typename Allocator>
571 inline void dynamic_bitset<Block, Allocator>::
572 swap(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
578 template <typename Block, typename Allocator>
579 dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
580 operator=(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
593 template <typename Block, typename Allocator>
594 inline typename dynamic_bitset<Block, Allocator>::allocator_type
595 dynamic_bitset<Block, Allocator>::get_allocator() const
596 {
597     return m_bits.get_allocator();
598 }
599
600 //-----------------------------------------------------------------------------
601 // size changing operations
602
603 template <typename Block, typename Allocator>
604 void dynamic_bitset<Block, Allocator>::
605 resize(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
647 template <typename Block, typename Allocator>
648 void dynamic_bitset<Block, Allocator>::
649 clear() // no throw
650 {
651   m_bits.clear();
652   m_num_bits = 0;
653 }
654
655
656 template <typename Block, typename Allocator>
657 void dynamic_bitset<Block, Allocator>::
658 push_back(bool bit)
659 {
660   resize(size() + 1);
661   set(size() - 1, bit);
662 }
663
664 template <typename Block, typename Allocator>
665 void dynamic_bitset<Block, Allocator>::
666 append(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
689 template <typename Block, typename Allocator>
690 dynamic_bitset<Block, Allocator>&
691 dynamic_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
699 template <typename Block, typename Allocator>
700 dynamic_bitset<Block, Allocator>&
701 dynamic_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
710 template <typename Block, typename Allocator>
711 dynamic_bitset<Block, Allocator>&
712 dynamic_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
721 template <typename Block, typename Allocator>
722 dynamic_bitset<Block, Allocator>&
723 dynamic_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 //
738 template <typename Block, typename Allocator>
739 dynamic_bitset<Block, Allocator>&
740 dynamic_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 //
789 template <typename B, typename A>
790 dynamic_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
832 template <typename Block, typename Allocator>
833 dynamic_bitset<Block, Allocator>
834 dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
835 {
836     dynamic_bitset r(*this);
837     return r <<= n;
838 }
839
840 template <typename Block, typename Allocator>
841 dynamic_bitset<Block, Allocator>
842 dynamic_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
852 template <typename Block, typename Allocator>
853 dynamic_bitset<Block, Allocator>&
854 dynamic_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
873 template <typename Block, typename Allocator>
874 dynamic_bitset<Block, Allocator>&
875 dynamic_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
882 template <typename Block, typename Allocator>
883 dynamic_bitset<Block, Allocator>&
884 dynamic_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
898 template <typename Block, typename Allocator>
899 dynamic_bitset<Block, Allocator>&
900 dynamic_bitset<Block, Allocator>::reset()
901 {
902   std::fill(m_bits.begin(), m_bits.end(), Block(0));
903   return *this;
904 }
905
906 template <typename Block, typename Allocator>
907 dynamic_bitset<Block, Allocator>&
908 dynamic_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
915 template <typename Block, typename Allocator>
916 dynamic_bitset<Block, Allocator>&
917 dynamic_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
925 template <typename Block, typename Allocator>
926 bool 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
931 template <typename Block, typename Allocator>
932 bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
933 {
934     assert(pos < m_num_bits);
935     return m_unchecked_test(pos);
936 }
937
938 template <typename Block, typename Allocator>
939 bool 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
947 template <typename Block, typename Allocator>
948 inline bool dynamic_bitset<Block, Allocator>::none() const
949 {
950     return !any();
951 }
952
953 template <typename Block, typename Allocator>
954 dynamic_bitset<Block, Allocator>
955 dynamic_bitset<Block, Allocator>::operator~() const
956 {
957     dynamic_bitset b(*this);
958     b.flip();
959     return b;
960 }
961
962
963 /*
964
965 The following is the straightforward implementation of count(), which
966 we leave here in a comment for documentation purposes.
967
968 template <typename Block, typename Allocator>
969 typename dynamic_bitset<Block, Allocator>::size_type
970 dynamic_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
979 The 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
1002 template <typename Block, typename Allocator>
1003 typename dynamic_bitset<Block, Allocator>::size_type
1004 dynamic_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
1023 template <typename B, typename A, typename stringT>
1024 void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
1025                       bool dump_all)
1026 {
1027     typedef typename stringT::traits_type Tr;
1028     typedef typename stringT::value_type  Ch;
1029
1030     BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
1031     const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1032     const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1033
1034     // Note that this function may access (when
1035     // dump_all == true) bits beyond position size() - 1
1036
1037     typedef typename dynamic_bitset<B, A>::size_type size_type;
1038
1039     const size_type len = dump_all?
1040          dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
1041          b.size();
1042     s.assign (len, zero);
1043
1044     for (size_type i = 0; i < len; ++i) {
1045         if (b.m_unchecked_test(i))
1046             Tr::assign(s[len - 1 - i], one);
1047
1048     }
1049
1050 }
1051
1052
1053 // A comment similar to the one about the constructor from
1054 // basic_string can be done here. Thanks to James Kanze for
1055 // making me (Gennaro) realize this important separation of
1056 // concerns issue, as well as many things about i18n.
1057 //
1058 template <typename Block, typename Allocator, typename stringT> // G.P.S.
1059 inline void
1060 to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
1061 {
1062     to_string_helper(b, s, false);
1063 }
1064
1065
1066 // Differently from to_string this function dumps out
1067 // every bit of the internal representation (may be
1068 // useful for debugging purposes)
1069 //
1070 template <typename B, typename A, typename stringT>
1071 inline void
1072 dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.
1073 {
1074     to_string_helper(b, s, true /* =dump_all*/);
1075 }
1076
1077 template <typename Block, typename Allocator, typename BlockOutputIterator>
1078 inline void
1079 to_block_range(const dynamic_bitset<Block, Allocator>& b,
1080                BlockOutputIterator result)
1081 {
1082     // note how this copies *all* bits, including the
1083     // unused ones in the last block (which are zero)
1084     std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]
1085 }
1086
1087 template <typename Block, typename Allocator>
1088 unsigned long dynamic_bitset<Block, Allocator>::
1089 to_ulong() const
1090 {
1091
1092   if (m_num_bits == 0)
1093       return 0; // convention
1094
1095   // Check for overflows. This may be a performance burden on very
1096   // large bitsets but is required by the specification, sorry
1097   if (find_next(ulong_width - 1) != npos)
1098     throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
1099
1100
1101   // Ok, from now on we can be sure there's no "on" bit 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
1124 template <typename Block, typename Allocator>
1125 inline typename dynamic_bitset<Block, Allocator>::size_type
1126 dynamic_bitset<Block, Allocator>::size() const
1127 {
1128     return m_num_bits;
1129 }
1130
1131 template <typename Block, typename Allocator>
1132 inline typename dynamic_bitset<Block, Allocator>::size_type
1133 dynamic_bitset<Block, Allocator>::num_blocks() const
1134 {
1135     return m_bits.size();
1136 }
1137
1138 template <typename Block, typename Allocator>
1139 inline typename dynamic_bitset<Block, Allocator>::size_type
1140 dynamic_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
1159 template <typename Block, typename Allocator>
1160 inline bool dynamic_bitset<Block, Allocator>::empty() const
1161 {
1162   return size() == 0;
1163 }
1164
1165 #if 0 // gps
1166 template <typename Block, typename Allocator>
1167 inline 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
1173 template <typename Block, typename Allocator>
1174 typename dynamic_bitset<Block, Allocator>::size_type
1175 dynamic_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
1190 template <typename Block, typename Allocator>
1191 bool dynamic_bitset<Block, Allocator>::
1192 is_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
1201 template <typename Block, typename Allocator>
1202 bool dynamic_bitset<Block, Allocator>::
1203 is_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
1217 template <typename Block, typename Allocator>
1218 bool 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 //
1237 template <typename Block, typename Allocator>
1238 typename dynamic_bitset<Block, Allocator>::size_type
1239 dynamic_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
1255 template <typename Block, typename Allocator>
1256 typename dynamic_bitset<Block, Allocator>::size_type
1257 dynamic_bitset<Block, Allocator>::find_first() const
1258 {
1259     return m_do_find_from(0);
1260 }
1261
1262
1263 template <typename Block, typename Allocator>
1264 typename dynamic_bitset<Block, Allocator>::size_type
1265 dynamic_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
1292 template <typename Block, typename Allocator>
1293 bool 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
1300 template <typename Block, typename Allocator>
1301 inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
1302                        const dynamic_bitset<Block, Allocator>& b)
1303 {
1304     return !(a == b);
1305 }
1306
1307 template <typename Block, typename Allocator>
1308 bool 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
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 template <typename Block, typename Allocator>
1341 inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
1342                       const dynamic_bitset<Block, Allocator>& b)
1343 {
1344     return b < a;
1345 }
1346
1347 template <typename Block, typename Allocator>
1348 inline 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
1358 template < typename Block, typename Alloc>
1359 std::ostream&
1360 operator<<(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
1427 template <typename Ch, typename Tr, typename Block, typename Alloc>
1428 std::basic_ostream<Ch, Tr>&
1429 operator<<(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
1521 template <typename Block, typename Alloc>
1522 std::istream&
1523 operator>>(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
1580 template <typename Ch, typename Tr, typename Block, typename Alloc>
1581 std::basic_istream<Ch, Tr>&
1582 operator>>(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
1661 template <typename Block, typename Allocator>
1662 dynamic_bitset<Block, Allocator>
1663 operator&(const dynamic_bitset<Block, Allocator>& x,
1664           const dynamic_bitset<Block, Allocator>& y)
1665 {
1666     dynamic_bitset<Block, Allocator> b(x);
1667     return b &= y;
1668 }
1669
1670 template <typename Block, typename Allocator>
1671 dynamic_bitset<Block, Allocator>
1672 operator|(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
1679 template <typename Block, typename Allocator>
1680 dynamic_bitset<Block, Allocator>
1681 operator^(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
1688 template <typename Block, typename Allocator>
1689 dynamic_bitset<Block, Allocator>
1690 operator-(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
1700 template<typename Block, typename Allocator>
1701 inline void
1702 swap(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
1713 template <typename Block, typename Allocator>
1714 inline typename dynamic_bitset<Block, Allocator>::size_type
1715 dynamic_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 //
1723 template <typename Block, typename Allocator>
1724 inline 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 //
1732 template <typename Block, typename Allocator>
1733 inline 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 //
1745 template <typename Block, typename Allocator>
1746 inline 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
1759 template <typename Block, typename Allocator>
1760 bool 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