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

source code of boost/boost/dynamic_bitset/dynamic_bitset.hpp