1 // --------------------------------------------------
3 // (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.
4 // (C) Copyright Gennaro Prota 2003 - 2004.
6 // Distributed under the Boost Software License, Version 1.0.
7 // (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
10 // -----------------------------------------------------------
12 // See http://www.boost.org/libs/dynamic_bitset for documentation.
16 #ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
17 #define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
21 #include <stdexcept> // for std::overflow_error
22 #include <algorithm> // for std::swap, std::min, std::copy, std::fill
24 #include <climits> // for CHAR_BIT
26 #include "boost/dynamic_bitset/config.hpp"
28 #ifndef BOOST_NO_STD_LOCALE
29 # include <locale> // G.P.S
32 #if defined(BOOST_OLD_IOSTREAMS)
33 # include <iostream.h>
34 # include <ctype.h> // for isspace
40 #include "boost/dynamic_bitset_fwd.hpp"
41 #include "boost/detail/dynamic_bitset.hpp"
42 #include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
43 #include "boost/static_assert.hpp"
44 #include "boost/limits.hpp"
45 #include "boost/pending/lowest_bit.hpp" // used by find_first/next
52 #if defined(BOOST_MSVC) && BOOST_WORKAROUND(BOOST_MSVC, <= 1300) // 1300 == VC++ 7.0
53 // VC++ (up to 7.0) wants the default arguments again
54 <typename Block = unsigned long, typename Allocator = std::allocator<Block> >
56 <typename Block, typename Allocator>
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.
65 BOOST_STATIC_ASSERT(detail::dynamic_bitset_allowed_block_type<Block>::value);
68 typedef Block block_type;
69 typedef Allocator allocator_type;
70 typedef std::size_t size_type;
71 typedef int block_width_type; // gps
73 BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
74 BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
79 // A proxy class to simulate lvalues of bit type.
80 // Shouldn't it be private? [gps]
84 friend class dynamic_bitset<Block, Allocator>;
87 // the one and only non-copy ctor
88 reference(block_type & b, int pos)
89 :m_block(b), m_mask(block_type(1) << pos)
92 void operator&(); // left undefined
96 // copy constructor: compiler generated
98 operator bool() const { return (m_block & m_mask) != 0; }
99 bool operator~() const { return (m_block & m_mask) == 0; }
101 reference& flip() { do_flip(); return *this; }
103 reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x
104 reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
106 reference& operator|=(bool x) { if (x) do_set(); return *this; }
107 reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
108 reference& operator^=(bool x) { if (x) do_flip(); return *this; }
109 reference& operator-=(bool x) { if (x) do_reset(); return *this; }
112 block_type & m_block;
113 const block_type m_mask;
115 void do_set() { m_block |= m_mask; }
116 void do_reset() { m_block &= ~m_mask; }
117 void do_flip() { m_block ^= m_mask; }
118 void do_assign(bool x) { x? do_set() : do_reset(); }
121 typedef bool const_reference;
123 // constructors, etc.
125 dynamic_bitset(const Allocator& alloc = Allocator());
128 dynamic_bitset(size_type num_bits, unsigned long value = 0,
129 const Allocator& alloc = Allocator());
132 // The presence of this constructor is a concession to ease of
133 // use, especially for the novice user. A conversion from string
134 // is, in most cases, formatting, and should be done by the standard
135 // formatting convention: operator>>.
138 // Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
139 // g++ 3.2 requires them and probably the standard will - see core issue 325
141 // split into two constructors because of bugs in MSVC 6.0sp5 with STLport
143 template <typename CharT, typename Traits, typename Alloc>
144 dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
145 typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
146 typename std::basic_string<CharT, Traits, Alloc>::size_type n,
147 size_type num_bits = npos,
148 const Allocator& alloc = Allocator())
153 init_from_string(s, pos, n, num_bits, alloc);
156 template <typename CharT, typename Traits, typename Alloc>
158 dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
159 typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
161 :m_bits(Allocator()),
164 init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
168 // The first bit in *first is the least significant bit, and the
169 // last bit in the block just before *last is the most significant bit.
170 template <typename BlockInputIterator>
171 dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
172 const Allocator& alloc = Allocator())
174 :m_bits(first, last, alloc),
175 m_num_bits(m_bits.size() * bits_per_block)
180 dynamic_bitset(const dynamic_bitset& b);
184 void swap(dynamic_bitset& b);
185 dynamic_bitset& operator=(const dynamic_bitset& b);
187 allocator_type get_allocator() const;
189 // size changing operations
190 void resize(size_type num_bits, bool value = false);
192 void push_back(bool bit);
193 void append(Block block);
195 template <typename BlockInputIterator>
196 void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
198 std::vector<Block, Allocator> v(first, last);
199 m_append(v.begin(), v.end(), std::random_access_iterator_tag());
201 template <typename BlockInputIterator>
202 void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
204 assert(first != last);
205 block_width_type r = count_extra_bits();
206 std::size_t d = boost::detail::distance(first, last);
207 m_bits.reserve(num_blocks() + d);
209 for( ; first != last; ++first)
210 m_bits.push_back(*first); // could use vector<>::insert()
213 m_highest_block() |= (*first << r);
215 Block b = *first >> (bits_per_block - r);
217 m_bits.push_back(b | (first==last? 0 : *first << r));
218 } while (first != last);
220 m_num_bits += bits_per_block * d;
222 template <typename BlockInputIterator>
223 void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
226 typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
227 m_append(first, last, cat);
233 dynamic_bitset& operator&=(const dynamic_bitset& b);
234 dynamic_bitset& operator|=(const dynamic_bitset& b);
235 dynamic_bitset& operator^=(const dynamic_bitset& b);
236 dynamic_bitset& operator-=(const dynamic_bitset& b);
237 dynamic_bitset& operator<<=(size_type n);
238 dynamic_bitset& operator>>=(size_type n);
239 dynamic_bitset operator<<(size_type n) const;
240 dynamic_bitset operator>>(size_type n) const;
242 // basic bit operations
243 dynamic_bitset& set(size_type n, bool val = true);
244 dynamic_bitset& set();
245 dynamic_bitset& reset(size_type n);
246 dynamic_bitset& reset();
247 dynamic_bitset& flip(size_type n);
248 dynamic_bitset& flip();
249 bool test(size_type n) const;
252 dynamic_bitset operator~() const;
253 size_type count() const;
256 reference operator[](size_type pos) {
257 return reference(m_bits[block_index(pos)], bit_index(pos));
259 bool operator[](size_type pos) const { return test(pos); }
261 unsigned long to_ulong() const;
263 size_type size() const;
264 size_type num_blocks() const;
265 size_type max_size() const;
268 void reserve(size_type n);
269 size_type capacity() const;
272 bool is_subset_of(const dynamic_bitset& a) const;
273 bool is_proper_subset_of(const dynamic_bitset& a) const;
274 bool intersects(const dynamic_bitset & a) const;
277 size_type find_first() const;
278 size_type find_next(size_type pos) const;
281 #if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
282 // lexicographical comparison
283 template <typename B, typename A>
284 friend bool operator==(const dynamic_bitset<B, A>& a,
285 const dynamic_bitset<B, A>& b);
287 template <typename B, typename A>
288 friend bool operator<(const dynamic_bitset<B, A>& a,
289 const dynamic_bitset<B, A>& b);
292 template <typename B, typename A, typename BlockOutputIterator>
293 friend void to_block_range(const dynamic_bitset<B, A>& b,
294 BlockOutputIterator result);
296 template <typename BlockIterator, typename B, typename A>
297 friend void from_block_range(BlockIterator first, BlockIterator last,
298 dynamic_bitset<B, A>& result);
301 template <typename CharT, typename Traits, typename B, typename A>
302 friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
303 dynamic_bitset<B, A>& b);
305 template <typename B, typename A, typename stringT>
306 friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
313 BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
314 typedef std::vector<block_type, allocator_type> buffer_type;
316 void m_zero_unused_bits();
317 bool m_check_invariants() const;
319 size_type m_do_find_from(size_type first_block) const;
321 block_width_type count_extra_bits() const { return bit_index(size()); }
322 static size_type block_index(size_type pos) { return pos / bits_per_block; }
323 static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }
324 static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
326 template <typename CharT, typename Traits, typename Alloc>
327 void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
328 typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
329 typename std::basic_string<CharT, Traits, Alloc>::size_type n,
331 const Allocator& alloc)
333 assert(pos <= s.size());
335 typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
336 typedef typename StrT::traits_type Tr;
338 const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); // gps
339 const size_type sz = ( num_bits != npos? num_bits : rlen);
340 m_bits.resize(calc_num_blocks(sz));
344 BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
345 const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
347 const size_type m = num_bits < rlen ? num_bits : rlen; // [gps]
348 typename StrT::size_type i = 0;
351 const CharT c = s[(pos + m - 1) - i];
353 assert( Tr::eq(c, one)
354 || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
363 BOOST_DYNAMIC_BITSET_PRIVATE:
365 bool m_unchecked_test(size_type pos) const;
366 static size_type calc_num_blocks(size_type num_bits);
368 Block& m_highest_block();
369 const Block& m_highest_block() const;
371 buffer_type m_bits; // [gps] to be renamed
372 size_type m_num_bits;
376 friend class bit_appender;
378 // helper for stream >>
379 // Supplies to the lack of an efficient append at the less
380 // significant end: bits are actually appended "at left" but
381 // rearranged in the destructor. Everything works just as if
382 // dynamic_bitset<> had an append_at_right() function (which
383 // threw, in case, the same exceptions as push_back) except
384 // that the function is actually called bit_appender::do_append().
391 bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
393 // reverse the order of blocks, shift
394 // if needed, and then resize
396 std::reverse(bs.m_bits.begin(), bs.m_bits.end());
397 const block_width_type offs = bit_index(n);
399 bs >>= (bits_per_block - offs);
400 bs.resize(n); // doesn't enlarge, so can't throw
401 assert(bs.m_check_invariants());
403 inline void do_append(bool value) {
407 current = &bs.m_highest_block();
408 mask = Block(1) << (bits_per_block - 1);
417 size_type get_count() const { return n; }
422 #if BOOST_WORKAROUND( __IBMCPP__, <=600 )
424 // Workaround for IBM's AIX platform.
425 // See http://comments.gmane.org/gmane.comp.lib.boost.user/15331
427 template<typename Block, typename Allocator>
428 dynamic_bitset<Block, Allocator>::block_width_type const
429 dynamic_bitset<Block, Allocator>::bits_per_block;
431 template<typename Block, typename Allocator>
432 dynamic_bitset<Block, Allocator>::block_width_type const
433 dynamic_bitset<Block, Allocator>::ulong_width;
440 template <typename Block, typename Allocator>
441 bool operator!=(const dynamic_bitset<Block, Allocator>& a,
442 const dynamic_bitset<Block, Allocator>& b);
444 template <typename Block, typename Allocator>
445 bool operator<=(const dynamic_bitset<Block, Allocator>& a,
446 const dynamic_bitset<Block, Allocator>& b);
448 template <typename Block, typename Allocator>
449 bool operator>(const dynamic_bitset<Block, Allocator>& a,
450 const dynamic_bitset<Block, Allocator>& b);
452 template <typename Block, typename Allocator>
453 bool operator>=(const dynamic_bitset<Block, Allocator>& a,
454 const dynamic_bitset<Block, Allocator>& b);
457 #ifdef BOOST_OLD_IOSTREAMS
458 template <typename Block, typename Allocator>
459 std::ostream& operator<<(std::ostream& os,
460 const dynamic_bitset<Block, Allocator>& b);
462 template <typename Block, typename Allocator>
463 std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
465 // NOTE: Digital Mars wants the same template parameter names
466 // here and in the definition! [last tested: 8.48.10]
468 template <typename Ch, typename Tr, typename Block, typename Alloc>
469 std::basic_ostream<Ch, Tr>&
470 operator<<(std::basic_ostream<Ch, Tr>& os,
471 const dynamic_bitset<Block, Alloc>& b);
473 template <typename Ch, typename Tr, typename Block, typename Alloc>
474 std::basic_istream<Ch, Tr>&
475 operator>>(std::basic_istream<Ch, Tr>& is,
476 dynamic_bitset<Block, Alloc>& b);
480 template <typename Block, typename Allocator>
481 dynamic_bitset<Block, Allocator>
482 operator&(const dynamic_bitset<Block, Allocator>& b1,
483 const dynamic_bitset<Block, Allocator>& b2);
485 template <typename Block, typename Allocator>
486 dynamic_bitset<Block, Allocator>
487 operator|(const dynamic_bitset<Block, Allocator>& b1,
488 const dynamic_bitset<Block, Allocator>& b2);
490 template <typename Block, typename Allocator>
491 dynamic_bitset<Block, Allocator>
492 operator^(const dynamic_bitset<Block, Allocator>& b1,
493 const dynamic_bitset<Block, Allocator>& b2);
495 template <typename Block, typename Allocator>
496 dynamic_bitset<Block, Allocator>
497 operator-(const dynamic_bitset<Block, Allocator>& b1,
498 const dynamic_bitset<Block, Allocator>& b2);
500 // namespace scope swap
501 template<typename Block, typename Allocator>
502 void swap(dynamic_bitset<Block, Allocator>& b1,
503 dynamic_bitset<Block, Allocator>& b2);
506 template <typename Block, typename Allocator, typename stringT>
508 to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps
510 template <typename Block, typename Allocator, typename BlockOutputIterator>
512 to_block_range(const dynamic_bitset<Block, Allocator>& b,
513 BlockOutputIterator result);
516 // gps - check docs with Jeremy
518 template <typename BlockIterator, typename B, typename A>
520 from_block_range(BlockIterator first, BlockIterator last,
521 dynamic_bitset<B, A>& result)
523 // PRE: distance(first, last) <= numblocks()
524 std::copy (first, last, result.m_bits.begin()); //[gps]
527 //=============================================================================
528 // dynamic_bitset implementation
531 //-----------------------------------------------------------------------------
532 // constructors, etc.
534 template <typename Block, typename Allocator>
535 dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
536 : m_bits(alloc), m_num_bits(0)
541 template <typename Block, typename Allocator>
542 dynamic_bitset<Block, Allocator>::
543 dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
544 : m_bits(calc_num_blocks(num_bits), Block(0), alloc),
551 typedef unsigned long num_type;
553 // cut off all bits in value that have pos >= num_bits, if any
554 if (num_bits < static_cast<size_type>(ulong_width)) {
555 const num_type mask = (num_type(1) << num_bits) - 1;
559 if (bits_per_block >= ulong_width) {
560 m_bits[0] = static_cast<block_type>(value);
563 for(size_type i = 0; value != 0; ++i) {
565 m_bits[i] = static_cast<block_type>(value);
566 value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);
573 template <typename Block, typename Allocator>
574 inline dynamic_bitset<Block, Allocator>::
575 dynamic_bitset(const dynamic_bitset& b)
576 : m_bits(b.m_bits), m_num_bits(b.m_num_bits) // [gps]
581 template <typename Block, typename Allocator>
582 inline dynamic_bitset<Block, Allocator>::
585 assert(m_check_invariants());
588 template <typename Block, typename Allocator>
589 inline void dynamic_bitset<Block, Allocator>::
590 swap(dynamic_bitset<Block, Allocator>& b) // no throw
592 std::swap(m_bits, b.m_bits);
593 std::swap(m_num_bits, b.m_num_bits);
596 template <typename Block, typename Allocator>
597 dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
598 operator=(const dynamic_bitset<Block, Allocator>& b)
601 dynamic_bitset<Block, Allocator> tmp(b);
606 m_num_bits = b.m_num_bits;
611 template <typename Block, typename Allocator>
612 inline typename dynamic_bitset<Block, Allocator>::allocator_type
613 dynamic_bitset<Block, Allocator>::get_allocator() const
615 return m_bits.get_allocator();
618 //-----------------------------------------------------------------------------
619 // size changing operations
621 template <typename Block, typename Allocator>
622 void dynamic_bitset<Block, Allocator>::
623 resize(size_type num_bits, bool value) // strong guarantee
626 const size_type old_num_blocks = num_blocks();
627 const size_type required_blocks = calc_num_blocks(num_bits);
629 const block_type v = value? ~Block(0) : Block(0);
631 if (required_blocks != old_num_blocks) {
632 m_bits.resize(required_blocks, v); // s.g. (copy) [gps]
638 // - if the buffer was shrunk, there's nothing to do, except
639 // a call to m_zero_unused_bits()
641 // - if it it is enlarged, all the (used) bits in the new blocks have
642 // the correct value, but we should also take care of the bits,
643 // if any, that were 'unused bits' before enlarging: if value == true,
646 if (value && (num_bits > m_num_bits)) {
648 const size_type extra_bits = count_extra_bits(); // gps
650 assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
653 m_bits[old_num_blocks - 1] |= (v << extra_bits); // gps
660 m_num_bits = num_bits;
661 m_zero_unused_bits();
665 template <typename Block, typename Allocator>
666 void dynamic_bitset<Block, Allocator>::
674 template <typename Block, typename Allocator>
675 void dynamic_bitset<Block, Allocator>::
679 set(size() - 1, bit);
682 template <typename Block, typename Allocator>
683 void dynamic_bitset<Block, Allocator>::
684 append(Block value) // strong guarantee
686 // G.P.S. to be reviewed...
688 const block_width_type r = count_extra_bits();
691 // the buffer is empty, or all blocks are filled
692 m_bits.push_back(value);
695 m_bits.push_back(value >> (bits_per_block - r));
696 m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
699 m_num_bits += bits_per_block;
700 assert(m_check_invariants());
705 //-----------------------------------------------------------------------------
707 template <typename Block, typename Allocator>
708 dynamic_bitset<Block, Allocator>&
709 dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
711 assert(size() == rhs.size());
712 for (size_type i = 0; i < num_blocks(); ++i)
713 m_bits[i] &= rhs.m_bits[i];
717 template <typename Block, typename Allocator>
718 dynamic_bitset<Block, Allocator>&
719 dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
721 assert(size() == rhs.size());
722 for (size_type i = 0; i < num_blocks(); ++i)
723 m_bits[i] |= rhs.m_bits[i];
724 //m_zero_unused_bits();
728 template <typename Block, typename Allocator>
729 dynamic_bitset<Block, Allocator>&
730 dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
732 assert(size() == rhs.size());
733 for (size_type i = 0; i < this->num_blocks(); ++i)
734 m_bits[i] ^= rhs.m_bits[i];
735 //m_zero_unused_bits();
739 template <typename Block, typename Allocator>
740 dynamic_bitset<Block, Allocator>&
741 dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
743 assert(size() == rhs.size());
744 for (size_type i = 0; i < num_blocks(); ++i)
745 m_bits[i] &= ~rhs.m_bits[i];
746 //m_zero_unused_bits();
752 // Note that the 'if (r != 0)' is crucial to avoid undefined
753 // behavior when the left hand operand of >> isn't promoted to a
754 // wider type (because rs would be too large).
756 template <typename Block, typename Allocator>
757 dynamic_bitset<Block, Allocator>&
758 dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
765 size_type const last = num_blocks() - 1; // num_blocks() is >= 1
766 size_type const div = n / bits_per_block; // div is <= last
767 block_width_type const r = bit_index(n);
768 block_type * const b = &m_bits[0];
772 block_width_type const rs = bits_per_block - r;
774 for (size_type i = last-div; i>0; --i) {
775 b[i+div] = (b[i] << r) | (b[i-1] >> rs);
781 for (size_type i = last-div; i>0; --i) {
788 // zero out div blocks at the less significant end
789 std::fill_n(b, div, static_cast<block_type>(0));
791 // zero out any 1 bit that flowed into the unused part
792 m_zero_unused_bits(); // thanks to Lester Gong
805 // see the comments to operator <<=
807 template <typename B, typename A>
808 dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
809 if (n >= m_num_bits) {
815 size_type const last = num_blocks() - 1; // num_blocks() is >= 1
816 size_type const div = n / bits_per_block; // div is <= last
817 block_width_type const r = bit_index(n);
818 block_type * const b = &m_bits[0];
823 block_width_type const ls = bits_per_block - r;
825 for (size_type i = div; i < last; ++i) {
826 b[i-div] = (b[i] >> r) | (b[i+1] << ls);
829 b[last-div] = b[last] >> r;
833 for (size_type i = div; i <= last; ++i) {
836 // note the '<=': the last iteration 'absorbs'
837 // b[last-div] = b[last] >> 0;
842 // div blocks are zero filled at the most significant end
843 std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
850 template <typename Block, typename Allocator>
851 dynamic_bitset<Block, Allocator>
852 dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
854 dynamic_bitset r(*this);
858 template <typename Block, typename Allocator>
859 dynamic_bitset<Block, Allocator>
860 dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
862 dynamic_bitset r(*this);
867 //-----------------------------------------------------------------------------
868 // basic bit operations
870 template <typename Block, typename Allocator>
871 dynamic_bitset<Block, Allocator>&
872 dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
876 // Below we have no set(size_type) function to call when
877 // value == true; instead of using a helper, I think
878 // overloading set (rather than giving it a default bool
879 // argument) would be more elegant.
881 assert(pos < m_num_bits);
884 m_bits[block_index(pos)] |= bit_mask(pos);
891 template <typename Block, typename Allocator>
892 dynamic_bitset<Block, Allocator>&
893 dynamic_bitset<Block, Allocator>::set()
895 std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
896 m_zero_unused_bits();
900 template <typename Block, typename Allocator>
901 dynamic_bitset<Block, Allocator>&
902 dynamic_bitset<Block, Allocator>::reset(size_type pos)
904 assert(pos < m_num_bits);
905 #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
906 // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
907 // use the |^ variation instead.. <grafik>
908 m_bits[block_index(pos)] |= bit_mask(pos);
909 m_bits[block_index(pos)] ^= bit_mask(pos);
911 m_bits[block_index(pos)] &= ~bit_mask(pos);
916 template <typename Block, typename Allocator>
917 dynamic_bitset<Block, Allocator>&
918 dynamic_bitset<Block, Allocator>::reset()
920 std::fill(m_bits.begin(), m_bits.end(), Block(0));
924 template <typename Block, typename Allocator>
925 dynamic_bitset<Block, Allocator>&
926 dynamic_bitset<Block, Allocator>::flip(size_type pos)
928 assert(pos < m_num_bits);
929 m_bits[block_index(pos)] ^= bit_mask(pos);
933 template <typename Block, typename Allocator>
934 dynamic_bitset<Block, Allocator>&
935 dynamic_bitset<Block, Allocator>::flip()
937 for (size_type i = 0; i < num_blocks(); ++i)
938 m_bits[i] = ~m_bits[i];
939 m_zero_unused_bits();
943 template <typename Block, typename Allocator>
944 bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
946 return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
949 template <typename Block, typename Allocator>
950 bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
952 assert(pos < m_num_bits);
953 return m_unchecked_test(pos);
956 template <typename Block, typename Allocator>
957 bool dynamic_bitset<Block, Allocator>::any() const
959 for (size_type i = 0; i < num_blocks(); ++i)
965 template <typename Block, typename Allocator>
966 inline bool dynamic_bitset<Block, Allocator>::none() const
971 template <typename Block, typename Allocator>
972 dynamic_bitset<Block, Allocator>
973 dynamic_bitset<Block, Allocator>::operator~() const
975 dynamic_bitset b(*this);
983 The following is the straightforward implementation of count(), which
984 we leave here in a comment for documentation purposes.
986 template <typename Block, typename Allocator>
987 typename dynamic_bitset<Block, Allocator>::size_type
988 dynamic_bitset<Block, Allocator>::count() const
991 for (size_type i = 0; i != this->m_num_bits; ++i)
997 The actual algorithm uses a lookup table.
1000 The basic idea of the method is to pick up X bits at a time
1001 from the internal array of blocks and consider those bits as
1002 the binary representation of a number N. Then, to use a table
1003 of 1<<X elements where table[N] is the number of '1' digits
1004 in the binary representation of N (i.e. in our X bits).
1007 In this implementation X is 8 (but can be easily changed: you
1008 just have to modify the definition of table_width and shrink/enlarge
1009 the table accordingly - it could be useful, for instance, to expand
1010 the table to 512 elements on an implementation with 9-bit bytes) and
1011 the internal array of blocks is seen, if possible, as an array of bytes.
1012 In practice the "reinterpretation" as array of bytes is possible if and
1013 only if X >= CHAR_BIT and Block has no padding bits (that would be counted
1014 together with the "real ones" if we saw the array as array of bytes).
1015 Otherwise we simply 'extract' X bits at a time from each Block.
1020 template <typename Block, typename Allocator>
1021 typename dynamic_bitset<Block, Allocator>::size_type
1022 dynamic_bitset<Block, Allocator>::count() const
1024 using namespace detail::dynamic_bitset_count_impl;
1026 const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);
1027 const bool enough_table_width = table_width >= CHAR_BIT;
1029 typedef mode_to_type< (no_padding && enough_table_width ?
1030 access_by_bytes : access_by_blocks) > m;
1032 return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(0));
1037 //-----------------------------------------------------------------------------
1041 template <typename B, typename A, typename stringT>
1042 void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
1045 typedef typename stringT::traits_type Tr;
1046 typedef typename stringT::value_type Ch;
1048 BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
1049 const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1050 const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1052 // Note that this function may access (when
1053 // dump_all == true) bits beyond position size() - 1
1055 typedef typename dynamic_bitset<B, A>::size_type size_type;
1057 const size_type len = dump_all?
1058 dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
1060 s.assign (len, zero);
1062 for (size_type i = 0; i < len; ++i) {
1063 if (b.m_unchecked_test(i))
1064 Tr::assign(s[len - 1 - i], one);
1071 // A comment similar to the one about the constructor from
1072 // basic_string can be done here. Thanks to James Kanze for
1073 // making me (Gennaro) realize this important separation of
1074 // concerns issue, as well as many things about i18n.
1076 template <typename Block, typename Allocator, typename stringT> // G.P.S.
1078 to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
1080 to_string_helper(b, s, false);
1084 // Differently from to_string this function dumps out
1085 // every bit of the internal representation (may be
1086 // useful for debugging purposes)
1088 template <typename B, typename A, typename stringT>
1090 dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.
1092 to_string_helper(b, s, true /* =dump_all*/);
1095 template <typename Block, typename Allocator, typename BlockOutputIterator>
1097 to_block_range(const dynamic_bitset<Block, Allocator>& b,
1098 BlockOutputIterator result)
1100 // note how this copies *all* bits, including the
1101 // unused ones in the last block (which are zero)
1102 std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]
1105 template <typename Block, typename Allocator>
1106 unsigned long dynamic_bitset<Block, Allocator>::
1110 if (m_num_bits == 0)
1111 return 0; // convention
1113 // Check for overflows. This may be a performance burden on very
1114 // large bitsets but is required by the specification, sorry
1115 if (find_next(ulong_width - 1) != npos)
1116 throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
1119 // Ok, from now on we can be sure there's no "on" bit beyond
1120 // the allowed positions
1122 if (bits_per_block >= ulong_width)
1126 size_type last_block = block_index((std::min)(m_num_bits-1, // gps
1127 (size_type)(ulong_width-1)));
1128 unsigned long result = 0;
1129 for (size_type i = 0; i <= last_block; ++i) {
1131 assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps
1133 unsigned long piece = m_bits[i];
1134 result |= (piece << (bits_per_block * i));
1142 template <typename Block, typename Allocator>
1143 inline typename dynamic_bitset<Block, Allocator>::size_type
1144 dynamic_bitset<Block, Allocator>::size() const
1149 template <typename Block, typename Allocator>
1150 inline typename dynamic_bitset<Block, Allocator>::size_type
1151 dynamic_bitset<Block, Allocator>::num_blocks() const
1153 return m_bits.size();
1156 template <typename Block, typename Allocator>
1157 inline typename dynamic_bitset<Block, Allocator>::size_type
1158 dynamic_bitset<Block, Allocator>::max_size() const
1160 // Semantics of vector<>::max_size() aren't very clear
1161 // (see lib issue 197) and many library implementations
1162 // simply return dummy values, _unrelated_ to the underlying
1165 // Given these problems, I was tempted to not provide this
1166 // function at all but the user could need it if he provides
1167 // his own allocator.
1170 const size_type m = detail::vector_max_size_workaround(m_bits);
1172 return m <= (size_type(-1)/bits_per_block) ?
1173 m * bits_per_block :
1177 template <typename Block, typename Allocator>
1178 inline bool dynamic_bitset<Block, Allocator>::empty() const
1184 template <typename Block, typename Allocator>
1185 inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)
1187 assert(n <= max_size()); // PRE - G.P.S.
1188 m_bits.reserve(calc_num_blocks(n));
1191 template <typename Block, typename Allocator>
1192 typename dynamic_bitset<Block, Allocator>::size_type
1193 dynamic_bitset<Block, Allocator>::capacity() const
1195 // capacity is m_bits.capacity() * bits_per_block
1196 // unless that one overflows
1197 const size_type m = static_cast<size_type>(-1);
1198 const size_type q = m / bits_per_block;
1200 const size_type c = m_bits.capacity();
1203 c * bits_per_block :
1208 template <typename Block, typename Allocator>
1209 bool dynamic_bitset<Block, Allocator>::
1210 is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1212 assert(size() == a.size());
1213 for (size_type i = 0; i < num_blocks(); ++i)
1214 if (m_bits[i] & ~a.m_bits[i])
1219 template <typename Block, typename Allocator>
1220 bool dynamic_bitset<Block, Allocator>::
1221 is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1223 assert(size() == a.size());
1224 bool proper = false;
1225 for (size_type i = 0; i < num_blocks(); ++i) {
1226 Block bt = m_bits[i], ba = a.m_bits[i];
1235 template <typename Block, typename Allocator>
1236 bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
1238 size_type common_blocks = num_blocks() < b.num_blocks()
1239 ? num_blocks() : b.num_blocks();
1241 for(size_type i = 0; i < common_blocks; ++i) {
1242 if(m_bits[i] & b.m_bits[i])
1248 // --------------------------------
1252 // look for the first bit "on", starting
1253 // from the block with index first_block
1255 template <typename Block, typename Allocator>
1256 typename dynamic_bitset<Block, Allocator>::size_type
1257 dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
1259 size_type i = first_block;
1262 while (i < num_blocks() && m_bits[i] == 0)
1265 if (i >= num_blocks())
1266 return npos; // not found
1268 return i * bits_per_block + boost::lowest_bit(m_bits[i]);
1273 template <typename Block, typename Allocator>
1274 typename dynamic_bitset<Block, Allocator>::size_type
1275 dynamic_bitset<Block, Allocator>::find_first() const
1277 return m_do_find_from(0);
1281 template <typename Block, typename Allocator>
1282 typename dynamic_bitset<Block, Allocator>::size_type
1283 dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
1286 const size_type sz = size();
1287 if (pos >= (sz-1) || sz == 0)
1292 const size_type blk = block_index(pos);
1293 const block_width_type ind = bit_index(pos);
1295 // mask out bits before pos
1296 const Block fore = m_bits[blk] & ( ~Block(0) << ind );
1299 blk * bits_per_block + lowest_bit(fore)
1301 m_do_find_from(blk + 1);
1307 //-----------------------------------------------------------------------------
1310 template <typename Block, typename Allocator>
1311 bool operator==(const dynamic_bitset<Block, Allocator>& a,
1312 const dynamic_bitset<Block, Allocator>& b)
1314 return (a.m_num_bits == b.m_num_bits)
1315 && (a.m_bits == b.m_bits); // [gps]
1318 template <typename Block, typename Allocator>
1319 inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
1320 const dynamic_bitset<Block, Allocator>& b)
1325 template <typename Block, typename Allocator>
1326 bool operator<(const dynamic_bitset<Block, Allocator>& a,
1327 const dynamic_bitset<Block, Allocator>& b)
1329 assert(a.size() == b.size());
1330 typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
1335 // Since we are storing the most significant bit
1336 // at pos == size() - 1, we need to do the comparisons in reverse.
1338 // Compare a block at a time
1339 for (size_type i = a.num_blocks() - 1; i > 0; --i)
1340 if (a.m_bits[i] < b.m_bits[i])
1342 else if (a.m_bits[i] > b.m_bits[i])
1345 if (a.m_bits[0] < b.m_bits[0])
1351 template <typename Block, typename Allocator>
1352 inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
1353 const dynamic_bitset<Block, Allocator>& b)
1358 template <typename Block, typename Allocator>
1359 inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
1360 const dynamic_bitset<Block, Allocator>& b)
1365 template <typename Block, typename Allocator>
1366 inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
1367 const dynamic_bitset<Block, Allocator>& b)
1372 //-----------------------------------------------------------------------------
1373 // stream operations
1375 #ifdef BOOST_OLD_IOSTREAMS
1376 template < typename Block, typename Alloc>
1378 operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
1380 // NOTE: since this is aimed at "classic" iostreams, exception
1381 // masks on the stream are not supported. The library that
1382 // ships with gcc 2.95 has an exceptions() member function but
1383 // nothing is actually implemented; not even the class ios::failure.
1385 using namespace std;
1387 const ios::iostate ok = ios::goodbit;
1388 ios::iostate err = ok;
1390 if (os.opfx()) { // gps
1393 typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
1395 const bitsetsize_type sz = b.size();
1396 std::streambuf * buf = os.rdbuf();
1397 size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0)
1398 || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; //- gps
1400 const char fill_char = os.fill();
1401 const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
1403 // if needed fill at left; pad is decresed along the way
1404 if (adjustfield != ios::left) {
1405 for (; 0 < npad; --npad)
1406 if (fill_char != buf->sputc(fill_char)) {
1407 err |= ios::failbit; // gps
1413 // output the bitset
1414 for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
1415 const char dig = b.test(i-1)? '1' : '0';
1416 if (EOF == buf->sputc(dig)) { // ok?? gps
1417 err |= ios::failbit;
1424 // if needed fill at right
1425 for (; 0 < npad; --npad) {
1426 if (fill_char != buf->sputc(fill_char)) {
1427 err |= ios::failbit;
1439 os.setstate(err); // assume this does NOT throw - gps
1445 template <typename Ch, typename Tr, typename Block, typename Alloc>
1446 std::basic_ostream<Ch, Tr>&
1447 operator<<(std::basic_ostream<Ch, Tr>& os,
1448 const dynamic_bitset<Block, Alloc>& b)
1451 using namespace std;
1453 const ios_base::iostate ok = ios_base::goodbit;
1454 ios_base::iostate err = ok;
1456 typename basic_ostream<Ch, Tr>::sentry cerberos(os);
1459 BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
1460 const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1461 const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1465 typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
1466 typedef basic_streambuf<Ch, Tr> buffer_type; // G.P.S.
1468 buffer_type * buf = os.rdbuf();
1469 size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0)
1470 || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); //- G.P.S.
1472 const Ch fill_char = os.fill();
1473 const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
1475 // if needed fill at left; pad is decresed along the way
1476 if (adjustfield != ios_base::left) {
1477 for (; 0 < npad; --npad)
1478 if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1479 err |= ios_base::failbit; // G.P.S.
1485 // output the bitset
1486 for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
1487 typename buffer_type::int_type
1488 ret = buf->sputc(b.test(i-1)? one : zero);
1489 if (Tr::eq_int_type(Tr::eof(), ret)) {
1490 err |= ios_base::failbit;
1497 // if needed fill at right
1498 for (; 0 < npad; --npad) {
1499 if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1500 err |= ios_base::failbit;
1509 } catch (...) { // see std 27.6.1.1/4
1510 bool rethrow = false;
1511 try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
1519 os.setstate(err); // may throw exception
1526 #ifdef BOOST_OLD_IOSTREAMS
1528 // gps - A sentry-like class that calls isfx in its
1529 // destructor. Necessary because bit_appender::do_append may throw.
1530 class pseudo_sentry {
1534 explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
1535 ~pseudo_sentry() { m_r.isfx(); }
1536 operator bool() const { return m_ok; }
1539 template <typename Block, typename Alloc>
1541 operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
1544 // Extractor for classic IO streams (libstdc++ < 3.0)
1545 // ----------------------------------------------------//
1546 // It's assumed that the stream buffer functions, and
1547 // the stream's setstate() _cannot_ throw.
1550 typedef dynamic_bitset<Block, Alloc> bitset_type;
1551 typedef typename bitset_type::size_type size_type;
1553 std::ios::iostate err = std::ios::goodbit; // gps
1554 pseudo_sentry cerberos(is); // skips whitespaces
1559 const std::streamsize w = is.width();
1560 const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps
1562 typename bitset_type::bit_appender appender(b);
1563 std::streambuf * buf = is.rdbuf();
1564 for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
1567 err |= std::ios::eofbit; // G.P.S.
1570 else if (char(c) != '0' && char(c) != '1')
1571 break; // non digit character
1575 //throw std::bad_alloc(); // gps
1576 appender.do_append(char(c) == '1');
1579 is.setstate(std::ios::failbit); // assume this can't throw
1589 err |= std::ios::failbit;
1590 if (err != std::ios::goodbit) // gps
1591 is.setstate (err); // may throw
1596 #else // BOOST_OLD_IOSTREAMS
1598 template <typename Ch, typename Tr, typename Block, typename Alloc>
1599 std::basic_istream<Ch, Tr>&
1600 operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
1603 using namespace std;
1605 typedef dynamic_bitset<Block, Alloc> bitset_type;
1606 typedef typename bitset_type::size_type size_type;
1608 const streamsize w = is.width();
1609 const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? // gps
1612 ios_base::iostate err = ios_base::goodbit; // gps
1613 typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
1616 // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
1617 BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
1618 const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1619 const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1623 typename bitset_type::bit_appender appender(b);
1624 basic_streambuf <Ch, Tr> * buf = is.rdbuf();
1625 typename Tr::int_type c = buf->sgetc(); // G.P.S.
1626 for( ; appender.get_count() < limit; c = buf->snextc() ) {
1628 if (Tr::eq_int_type(Tr::eof(), c)) {
1629 err |= ios_base::eofbit; // G.P.S.
1633 const Ch to_c = Tr::to_char_type(c);
1634 const bool is_one = Tr::eq(to_c, one);
1636 if (!is_one && !Tr::eq(to_c, zero))
1637 break; // non digit character
1639 appender.do_append(is_one);
1646 // catches from stream buf, or from vector:
1648 // bits_stored bits have been extracted and stored, and
1649 // either no further character is extractable or we can't
1650 // append to the underlying vector (out of memory) gps
1652 bool rethrow = false; // see std 27.6.1.1/4
1653 try { is.setstate(ios_base::badbit); }
1654 catch(...) { rethrow = true; }
1663 if (b.size() == 0 /*|| !cerberos*/)
1664 err |= ios_base::failbit;
1665 if (err != ios_base::goodbit) // gps
1666 is.setstate (err); // may throw
1676 //-----------------------------------------------------------------------------
1677 // bitset operations
1679 template <typename Block, typename Allocator>
1680 dynamic_bitset<Block, Allocator>
1681 operator&(const dynamic_bitset<Block, Allocator>& x,
1682 const dynamic_bitset<Block, Allocator>& y)
1684 dynamic_bitset<Block, Allocator> b(x);
1688 template <typename Block, typename Allocator>
1689 dynamic_bitset<Block, Allocator>
1690 operator|(const dynamic_bitset<Block, Allocator>& x,
1691 const dynamic_bitset<Block, Allocator>& y)
1693 dynamic_bitset<Block, Allocator> b(x);
1697 template <typename Block, typename Allocator>
1698 dynamic_bitset<Block, Allocator>
1699 operator^(const dynamic_bitset<Block, Allocator>& x,
1700 const dynamic_bitset<Block, Allocator>& y)
1702 dynamic_bitset<Block, Allocator> b(x);
1706 template <typename Block, typename Allocator>
1707 dynamic_bitset<Block, Allocator>
1708 operator-(const dynamic_bitset<Block, Allocator>& x,
1709 const dynamic_bitset<Block, Allocator>& y)
1711 dynamic_bitset<Block, Allocator> b(x);
1715 //-----------------------------------------------------------------------------
1716 // namespace scope swap
1718 template<typename Block, typename Allocator>
1720 swap(dynamic_bitset<Block, Allocator>& left,
1721 dynamic_bitset<Block, Allocator>& right) // no throw
1723 left.swap(right); // gps
1727 //-----------------------------------------------------------------------------
1728 // private (on conforming compilers) member functions
1731 template <typename Block, typename Allocator>
1732 inline typename dynamic_bitset<Block, Allocator>::size_type
1733 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
1735 return num_bits / bits_per_block
1736 + static_cast<int>( num_bits % bits_per_block != 0 );
1739 // gives a reference to the highest block
1741 template <typename Block, typename Allocator>
1742 inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
1744 return const_cast<Block &>
1745 (static_cast<const dynamic_bitset *>(this)->m_highest_block());
1748 // gives a const-reference to the highest block
1750 template <typename Block, typename Allocator>
1751 inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
1753 assert(size() > 0 && num_blocks() > 0);
1754 return m_bits.back();
1758 // If size() is not a multiple of bits_per_block
1759 // then not all the bits in the last block are used.
1760 // This function resets the unused bits (convenient
1761 // for the implementation of many member functions)
1763 template <typename Block, typename Allocator>
1764 inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
1766 assert (num_blocks() == calc_num_blocks(m_num_bits));
1768 // if != 0 this is the number of bits used in the last block
1769 const block_width_type extra_bits = count_extra_bits();
1771 if (extra_bits != 0)
1772 m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
1776 // check class invariants
1777 template <typename Block, typename Allocator>
1778 bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
1780 const block_width_type extra_bits = count_extra_bits();
1781 if (extra_bits > 0) {
1782 block_type const mask = (~static_cast<Block>(0) << extra_bits);
1783 if ((m_highest_block() & mask) != 0)
1786 if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
1794 } // namespace boost
1797 #undef BOOST_BITSET_CHAR
1799 #endif // include guard