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
reference(block_type & b,int pos)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
operator bool() const98 operator bool() const { return (m_block & m_mask) != 0; }
operator ~() const99 bool operator~() const { return (m_block & m_mask) == 0; }
100
flip()101 reference& flip() { do_flip(); return *this; }
102
operator =(bool x)103 reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x
operator =(const reference & rhs)104 reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
105
operator |=(bool x)106 reference& operator|=(bool x) { if (x) do_set(); return *this; }
operator &=(bool x)107 reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
operator ^=(bool x)108 reference& operator^=(bool x) { if (x) do_flip(); return *this; }
operator -=(bool x)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
do_set()115 void do_set() { m_block |= m_mask; }
do_reset()116 void do_reset() { m_block &= ~m_mask; }
do_flip()117 void do_flip() { m_block ^= m_mask; }
do_assign(bool x)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>
dynamic_bitset(const std::basic_string<CharT,Traits,Alloc> & s,typename std::basic_string<CharT,Traits,Alloc>::size_type pos,typename std::basic_string<CharT,Traits,Alloc>::size_type n,size_type num_bits=npos,const Allocator & alloc=Allocator ())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
dynamic_bitset(const std::basic_string<CharT,Traits,Alloc> & s,typename std::basic_string<CharT,Traits,Alloc>::size_type pos=0)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>
dynamic_bitset(BlockInputIterator first,BlockInputIterator last,const Allocator & alloc=Allocator ())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>
m_append(BlockInputIterator first,BlockInputIterator last,std::input_iterator_tag)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>
m_append(BlockInputIterator first,BlockInputIterator last,std::forward_iterator_tag)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>
append(BlockInputIterator first,BlockInputIterator last)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
operator [](size_type pos)256 reference operator[](size_type pos) {
257 return reference(m_bits[block_index(pos)], bit_index(pos));
258 }
operator [](size_type pos) const259 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
count_extra_bits() const321 block_width_type count_extra_bits() const { return bit_index(size()); }
block_index(size_type pos)322 static size_type block_index(size_type pos) { return pos / bits_per_block; }
bit_index(size_type pos)323 static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }
bit_mask(size_type pos)324 static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
325
326 template <typename CharT, typename Traits, typename Alloc>
init_from_string(const std::basic_string<CharT,Traits,Alloc> & s,typename std::basic_string<CharT,Traits,Alloc>::size_type pos,typename std::basic_string<CharT,Traits,Alloc>::size_type n,size_type num_bits,const Allocator & 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:
bit_appender(dynamic_bitset & r)391 bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
~bit_appender()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 }
do_append(bool value)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 }
get_count() const417 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
from_block_range(BlockIterator first,BlockIterator last,dynamic_bitset<B,A> & result)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>
dynamic_bitset(const Allocator & alloc)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>::
dynamic_bitset(size_type num_bits,unsigned long value,const Allocator & alloc)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>::
dynamic_bitset(const dynamic_bitset & b)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>::
~dynamic_bitset()565 ~dynamic_bitset()
566 {
567 assert(m_check_invariants());
568 }
569
570 template <typename Block, typename Allocator>
571 inline void dynamic_bitset<Block, Allocator>::
swap(dynamic_bitset<Block,Allocator> & b)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>::
operator =(const dynamic_bitset<Block,Allocator> & b)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
get_allocator() const595 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>::
resize(size_type num_bits,bool value)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>::
clear()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>::
push_back(bool bit)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>::
append(Block value)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>&
operator &=(const dynamic_bitset & rhs)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>&
operator |=(const dynamic_bitset & rhs)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>&
operator ^=(const dynamic_bitset & rhs)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>&
operator -=(const dynamic_bitset & rhs)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>&
operator <<=(size_type n)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>
operator >>=(size_type n)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>
operator <<(size_type n) const834 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>
operator >>(size_type n) const842 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>&
set(size_type pos,bool val)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>&
set()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>&
reset(size_type pos)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>&
reset()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>&
flip(size_type pos)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>&
flip()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>
m_unchecked_test(size_type pos) const926 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>
test(size_type pos) const932 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>
any() const939 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>
none() const948 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>
operator ~() const955 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
count() const1004 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>
to_string_helper(const dynamic_bitset<B,A> & b,stringT & s,bool dump_all)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
to_string(const dynamic_bitset<Block,Allocator> & b,stringT & s)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
dump_to_string(const dynamic_bitset<B,A> & b,stringT & s)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
to_block_range(const dynamic_bitset<Block,Allocator> & b,BlockOutputIterator result)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>::
to_ulong() const1089 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
size() const1126 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
num_blocks() const1133 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
max_size() const1140 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>
empty() const1160 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>::
is_subset_of(const dynamic_bitset<Block,Allocator> & a) const1192 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>::
is_proper_subset_of(const dynamic_bitset<Block,Allocator> & a) const1203 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>
intersects(const dynamic_bitset & b) const1218 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
m_do_find_from(size_type first_block) const1239 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
find_first() const1257 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
find_next(size_type pos) const1265 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>
operator ==(const dynamic_bitset<Block,Allocator> & a,const dynamic_bitset<Block,Allocator> & b)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>
operator !=(const dynamic_bitset<Block,Allocator> & a,const dynamic_bitset<Block,Allocator> & b)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>
operator <(const dynamic_bitset<Block,Allocator> & a,const dynamic_bitset<Block,Allocator> & b)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>
operator <=(const dynamic_bitset<Block,Allocator> & a,const dynamic_bitset<Block,Allocator> & b)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>
operator >(const dynamic_bitset<Block,Allocator> & a,const dynamic_bitset<Block,Allocator> & b)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>
operator >=(const dynamic_bitset<Block,Allocator> & a,const dynamic_bitset<Block,Allocator> & b)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&
operator <<(std::ostream & os,const dynamic_bitset<Block,Alloc> & b)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>&
operator <<(std::basic_ostream<Ch,Tr> & os,const dynamic_bitset<Block,Alloc> & b)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:
pseudo_sentry(std::istream & r)1516 explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
~pseudo_sentry()1517 ~pseudo_sentry() { m_r.isfx(); }
operator bool() const1518 operator bool() const { return m_ok; }
1519 };
1520
1521 template <typename Block, typename Alloc>
1522 std::istream&
operator >>(std::istream & is,dynamic_bitset<Block,Alloc> & b)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>&
operator >>(std::basic_istream<Ch,Tr> & is,dynamic_bitset<Block,Alloc> & b)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>
operator &(const dynamic_bitset<Block,Allocator> & x,const dynamic_bitset<Block,Allocator> & y)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>
operator |(const dynamic_bitset<Block,Allocator> & x,const dynamic_bitset<Block,Allocator> & y)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>
operator ^(const dynamic_bitset<Block,Allocator> & x,const dynamic_bitset<Block,Allocator> & y)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>
operator -(const dynamic_bitset<Block,Allocator> & x,const dynamic_bitset<Block,Allocator> & y)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
swap(dynamic_bitset<Block,Allocator> & left,dynamic_bitset<Block,Allocator> & right)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
calc_num_blocks(size_type num_bits)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>
m_highest_block()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>
m_highest_block() const1733 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>
m_zero_unused_bits()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>
m_check_invariants() const1760 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
1783