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

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