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