1	// -----------------------------------------------------------
2	//
3	// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
4	// Copyright (c) 2003-2006, 2008 Gennaro Prota
5	// Copyright (c) 2014 Ahmed Charles
6	//
7	// Copyright (c) 2014 Glen Joseph Fernandes
8	// (glenjofe@gmail.com)
9	//
10	// Copyright (c) 2014 Riccardo Marcangelo
11	// Copyright (c) 2018 Evgeny Shulgin
12	//
13	// Distributed under the Boost Software License, Version 1.0.
14	// (See accompanying file LICENSE_1_0.txt or copy at
15	// http://www.boost.org/LICENSE_1_0.txt)
16	//
17	// -----------------------------------------------------------
18
19	#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
20	#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
21
22	#include <assert.h>
23	#include <string>
24	#include <stdexcept>
25	#include <algorithm>
26	#include <iterator> // used to implement append(Iter, Iter)
27	#include <vector>
28	#include <climits> // for CHAR_BIT
29
30	#include "boost/dynamic_bitset/config.hpp"
31
32	#ifndef BOOST_NO_STD_LOCALE
33	# include <locale>
34	#endif
35
36	#if defined(BOOST_OLD_IOSTREAMS)
37	# include <iostream.h>
38	# include <ctype.h> // for isspace
39	#else
40	# include <istream>
41	# include <ostream>
42	#endif
43
44	#include "boost/dynamic_bitset_fwd.hpp"
45	#include "boost/dynamic_bitset/detail/dynamic_bitset.hpp"
46	#include "boost/dynamic_bitset/detail/lowest_bit.hpp"
47	#include "boost/move/move.hpp"
48	#include "boost/limits.hpp"
49	#include "boost/static_assert.hpp"
50	#include "boost/core/addressof.hpp"
51	#include "boost/core/no_exceptions_support.hpp"
52	#include "boost/throw_exception.hpp"
53	#include "boost/functional/hash/hash.hpp"
54
55
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
92	reference(block_type & b, block_width_type pos)
93	:m_block(b),
94	m_mask( (assert(pos < bits_per_block),
95	block_type(1) << pos )
96	)
97	{ }
98
99	void operator&(); // left undefined
100
101	public:
102
103	// copy constructor: compiler generated
104
105	operator bool() const { return (m_block & m_mask) != 0; }
106	bool operator~() const { return (m_block & m_mask) == 0; }
107
108	reference& flip() { do_flip(); return *this; }
109
110	reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x
111	reference& operator=(const reference& rhs) { do_assign(x: rhs); return *this; } // for b[i] = b[j]
112
113	reference& operator|=(bool x) { if (x) do_set(); return *this; }
114	reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
115	reference& operator^=(bool x) { if (x) do_flip(); return *this; }
116	reference& operator-=(bool x) { if (x) do_reset(); return *this; }
117
118	private:
119	block_type & m_block;
120	const block_type m_mask;
121
122	void do_set() { m_block |= m_mask; }
123	void do_reset() { m_block &= ~m_mask; }
124	void do_flip() { m_block ^= m_mask; }
125	void do_assign(bool x) { x? do_set() : do_reset(); }
126	};
127
128	typedef bool const_reference;
129
130	// constructors, etc.
131	dynamic_bitset() : m_num_bits(0) {}
132
133	explicit
134	dynamic_bitset(const Allocator& alloc);
135
136	explicit
137	dynamic_bitset(size_type num_bits, unsigned long value = 0,
138	const Allocator& alloc = Allocator());
139
140
141	// WARNING: you should avoid using this constructor.
142	//
143	// A conversion from string is, in most cases, formatting,
144	// and should be performed by using operator>>.
145	//
146	// NOTE:
147	// Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
148	// g++ 3.2 requires them and probably the standard will - see core issue 325
149	// NOTE 2:
150	// split into two constructors because of bugs in MSVC 6.0sp5 with STLport
151
152	template <typename CharT, typename Traits, typename Alloc>
153	dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
154	typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
155	typename std::basic_string<CharT, Traits, Alloc>::size_type n,
156	size_type num_bits = npos,
157	const Allocator& alloc = Allocator())
158
159	:m_bits(alloc),
160	m_num_bits(0)
161	{
162	init_from_string(s, pos, n, num_bits);
163	}
164
165	template <typename CharT, typename Traits, typename Alloc>
166	explicit
167	dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
168	typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
169
170	:m_bits(Allocator()),
171	m_num_bits(0)
172	{
173	init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
174	npos);
175	}
176
177	// The first bit in *first is the least significant bit, and the
178	// last bit in the block just before *last is the most significant bit.
179	template <typename BlockInputIterator>
180	dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
181	const Allocator& alloc = Allocator())
182
183	:m_bits(alloc),
184	m_num_bits(0)
185	{
186	using boost::detail::dynamic_bitset_impl::value_to_type;
187	using boost::detail::dynamic_bitset_impl::is_numeric;
188
189	const value_to_type<
190	is_numeric<BlockInputIterator>::value> selector;
191
192	dispatch_init(first, last, selector);
193	}
194
195	template <typename T>
196	void dispatch_init(T num_bits, unsigned long value,
197	detail::dynamic_bitset_impl::value_to_type<true>)
198	{
199	init_from_unsigned_long(num_bits: static_cast<size_type>(num_bits), value);
200	}
201
202	template <typename T>
203	void dispatch_init(T first, T last,
204	detail::dynamic_bitset_impl::value_to_type<false>)
205	{
206	init_from_block_range(first, last);
207	}
208
209	template <typename BlockIter>
210	void init_from_block_range(BlockIter first, BlockIter last)
211	{
212	assert(m_bits.size() == 0);
213	m_bits.insert(m_bits.end(), first, last);
214	m_num_bits = m_bits.size() * bits_per_block;
215	}
216
217	// copy constructor
218	dynamic_bitset(const dynamic_bitset& b);
219
220	~dynamic_bitset();
221
222	void swap(dynamic_bitset& b);
223	dynamic_bitset& operator=(const dynamic_bitset& b);
224
225	#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
226	dynamic_bitset(dynamic_bitset&& src);
227	dynamic_bitset& operator=(dynamic_bitset&& src);
228	#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
229
230	allocator_type get_allocator() const;
231
232	// size changing operations
233	void resize(size_type num_bits, bool value = false);
234	void clear();
235	void push_back(bool bit);
236	void pop_back();
237	void append(Block block);
238
239	template <typename BlockInputIterator>
240	void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
241	{
242	std::vector<Block, Allocator> v(first, last);
243	m_append(v.begin(), v.end(), std::random_access_iterator_tag());
244	}
245	template <typename BlockInputIterator>
246	void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
247	{
248	assert(first != last);
249	block_width_type r = count_extra_bits();
250	std::size_t d = std::distance(first, last);
251	m_bits.reserve(num_blocks() + d);
252	if (r == 0) {
253	for( ; first != last; ++first)
254	m_bits.push_back(*first); // could use vector<>::insert()
255	}
256	else {
257	m_highest_block() |= (*first << r);
258	do {
259	Block b = *first >> (bits_per_block - r);
260	++first;
261	m_bits.push_back(b | (first==last? 0 : *first << r));
262	} while (first != last);
263	}
264	m_num_bits += bits_per_block * d;
265	}
266	template <typename BlockInputIterator>
267	void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
268	{
269	if (first != last) {
270	typename std::iterator_traits<BlockInputIterator>::iterator_category cat;
271	m_append(first, last, cat);
272	}
273	}
274
275
276	// bitset operations
277	dynamic_bitset& operator&=(const dynamic_bitset& b);
278	dynamic_bitset& operator|=(const dynamic_bitset& b);
279	dynamic_bitset& operator^=(const dynamic_bitset& b);
280	dynamic_bitset& operator-=(const dynamic_bitset& b);
281	dynamic_bitset& operator<<=(size_type n);
282	dynamic_bitset& operator>>=(size_type n);
283	dynamic_bitset operator<<(size_type n) const;
284	dynamic_bitset operator>>(size_type n) const;
285
286	// basic bit operations
287	dynamic_bitset& set(size_type n, size_type len, bool val /* = true */); // default would make it ambiguous
288	dynamic_bitset& set(size_type n, bool val = true);
289	dynamic_bitset& set();
290	dynamic_bitset& reset(size_type n, size_type len);
291	dynamic_bitset& reset(size_type n);
292	dynamic_bitset& reset();
293	dynamic_bitset& flip(size_type n, size_type len);
294	dynamic_bitset& flip(size_type n);
295	dynamic_bitset& flip();
296	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
305	reference operator[](size_type pos) {
306	return reference(m_bits[block_index(pos)], bit_index(pos));
307	}
308	bool operator[](size_type pos) const { return test(n: 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	static bool m_not_empty(Block x){ return x != Block(0); };
379	size_type m_do_find_from(size_type first_block) const;
380
381	block_width_type count_extra_bits() const BOOST_NOEXCEPT { return bit_index(pos: size()); }
382	static size_type block_index(size_type pos) BOOST_NOEXCEPT { return pos / bits_per_block; }
383	static block_width_type bit_index(size_type pos) BOOST_NOEXCEPT { return static_cast<block_width_type>(pos % bits_per_block); }
384	static Block bit_mask(size_type pos) BOOST_NOEXCEPT { return Block(1) << bit_index(pos); }
385	static Block bit_mask(size_type first, size_type last) BOOST_NOEXCEPT
386	{
387	Block res = (last == bits_per_block - 1)
388	? detail::dynamic_bitset_impl::max_limit<Block>::value
389	: ((Block(1) << (last + 1)) - 1);
390	res ^= (Block(1) << first) - 1;
391	return res;
392	}
393	static Block set_block_bits(Block block, size_type first,
394	size_type last, bool val) BOOST_NOEXCEPT
395	{
396	if (val)
397	return block | bit_mask(first, last);
398	else
399	return block & static_cast<Block>(~bit_mask(first, last));
400	}
401
402	// Functions for operations on ranges
403	inline static Block set_block_partial(Block block, size_type first,
404	size_type last) BOOST_NOEXCEPT
405	{
406	return set_block_bits(block, first, last, val: true);
407	}
408	inline static Block set_block_full(Block) BOOST_NOEXCEPT
409	{
410	return detail::dynamic_bitset_impl::max_limit<Block>::value;
411	}
412	inline static Block reset_block_partial(Block block, size_type first,
413	size_type last) BOOST_NOEXCEPT
414	{
415	return set_block_bits(block, first, last, val: false);
416	}
417	inline static Block reset_block_full(Block) BOOST_NOEXCEPT
418	{
419	return 0;
420	}
421	inline static Block flip_block_partial(Block block, size_type first,
422	size_type last) BOOST_NOEXCEPT
423	{
424	return block ^ bit_mask(first, last);
425	}
426	inline static Block flip_block_full(Block block) BOOST_NOEXCEPT
427	{
428	return ~block;
429	}
430
431	template <typename CharT, typename Traits, typename Alloc>
432	void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
433	typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
434	typename std::basic_string<CharT, Traits, Alloc>::size_type n,
435	size_type num_bits)
436	{
437	assert(pos <= s.size());
438
439	typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
440	typedef typename StrT::traits_type Tr;
441
442	const typename StrT::size_type rlen = (std::min)(n, s.size() - pos);
443	const size_type sz = ( num_bits != npos? num_bits : rlen);
444	m_bits.resize(calc_num_blocks(num_bits: sz));
445	m_num_bits = sz;
446
447
448	BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
449	const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
450
451	const size_type m = num_bits < rlen ? num_bits : rlen;
452	typename StrT::size_type i = 0;
453	for( ; i < m; ++i) {
454
455	const CharT c = s[(pos + m - 1) - i];
456
457	assert( Tr::eq(c, one)
458	|| Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
459
460	if (Tr::eq(c, one))
461	set(i);
462
463	}
464
465	}
466
467	void init_from_unsigned_long(size_type num_bits,
468	unsigned long value/*,
469	const Allocator& alloc*/)
470	{
471
472	assert(m_bits.size() == 0);
473
474	m_bits.resize(calc_num_blocks(num_bits));
475	m_num_bits = num_bits;
476
477	typedef unsigned long num_type;
478	typedef boost::detail::dynamic_bitset_impl
479	::shifter<num_type, bits_per_block, ulong_width> shifter;
480
481	//if (num_bits == 0)
482	// return;
483
484	// zero out all bits at pos >= num_bits, if any;
485	// note that: num_bits == 0 implies value == 0
486	if (num_bits < static_cast<size_type>(ulong_width)) {
487	const num_type mask = (num_type(1) << num_bits) - 1;
488	value &= mask;
489	}
490
491	typename buffer_type::iterator it = m_bits.begin();
492	for( ; value; shifter::left_shift(value), ++it) {
493	*it = static_cast<block_type>(value);
494	}
495
496	}
497
498
499
500	BOOST_DYNAMIC_BITSET_PRIVATE:
501
502	bool m_unchecked_test(size_type pos) const;
503	static size_type calc_num_blocks(size_type num_bits);
504
505	Block& m_highest_block();
506	const Block& m_highest_block() const;
507
508	buffer_type m_bits;
509	size_type m_num_bits;
510
511
512	class bit_appender;
513	friend class bit_appender;
514	class bit_appender {
515	// helper for stream >>
516	// Supplies to the lack of an efficient append at the less
517	// significant end: bits are actually appended "at left" but
518	// rearranged in the destructor. From the perspective of
519	// client code everything works *as if* dynamic_bitset<> had
520	// an append_at_right() function (eventually throwing the same
521	// exceptions as push_back) except that the function is in fact
522	// called bit_appender::do_append().
523	//
524	dynamic_bitset & bs;
525	size_type n;
526	Block mask;
527	Block * current;
528
529	// not implemented
530	bit_appender(const bit_appender &);
531	bit_appender & operator=(const bit_appender &);
532
533	public:
534	bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
535	~bit_appender() {
536	// reverse the order of blocks, shift
537	// if needed, and then resize
538	//
539	std::reverse(bs.m_bits.begin(), bs.m_bits.end());
540	const block_width_type offs = bit_index(pos: n);
541	if (offs)
542	bs >>= (bits_per_block - offs);
543	bs.resize(n); // doesn't enlarge, so can't throw
544	assert(bs.m_check_invariants());
545	}
546	inline void do_append(bool value) {
547
548	if (mask == 0) {
549	bs.append(Block(0));
550	current = &bs.m_highest_block();
551	mask = Block(1) << (bits_per_block - 1);
552	}
553
554	if(value)
555	*current |= mask;
556
557	mask /= 2;
558	++n;
559	}
560	size_type get_count() const { return n; }
561	};
562
563	};
564
565	#if !defined BOOST_NO_INCLASS_MEMBER_INITIALIZATION
566
567	template <typename Block, typename Allocator>
568	const typename dynamic_bitset<Block, Allocator>::block_width_type
569	dynamic_bitset<Block, Allocator>::bits_per_block;
570
571	template <typename Block, typename Allocator>
572	const typename dynamic_bitset<Block, Allocator>::size_type
573	dynamic_bitset<Block, Allocator>::npos;
574
575	template <typename Block, typename Allocator>
576	const typename dynamic_bitset<Block, Allocator>::block_width_type
577	dynamic_bitset<Block, Allocator>::ulong_width;
578
579	#endif
580
581	// Global Functions:
582
583	// comparison
584	template <typename Block, typename Allocator>
585	bool operator!=(const dynamic_bitset<Block, Allocator>& a,
586	const dynamic_bitset<Block, Allocator>& b);
587
588	template <typename Block, typename Allocator>
589	bool operator<=(const dynamic_bitset<Block, Allocator>& a,
590	const dynamic_bitset<Block, Allocator>& b);
591
592	template <typename Block, typename Allocator>
593	bool operator>(const dynamic_bitset<Block, Allocator>& a,
594	const dynamic_bitset<Block, Allocator>& b);
595
596	template <typename Block, typename Allocator>
597	bool operator>=(const dynamic_bitset<Block, Allocator>& a,
598	const dynamic_bitset<Block, Allocator>& b);
599
600	// stream operators
601	#ifdef BOOST_OLD_IOSTREAMS
602	template <typename Block, typename Allocator>
603	std::ostream& operator<<(std::ostream& os,
604	const dynamic_bitset<Block, Allocator>& b);
605
606	template <typename Block, typename Allocator>
607	std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
608	#else
609	template <typename CharT, typename Traits, typename Block, typename Allocator>
610	std::basic_ostream<CharT, Traits>&
611	operator<<(std::basic_ostream<CharT, Traits>& os,
612	const dynamic_bitset<Block, Allocator>& b);
613
614	template <typename CharT, typename Traits, typename Block, typename Allocator>
615	std::basic_istream<CharT, Traits>&
616	operator>>(std::basic_istream<CharT, Traits>& is,
617	dynamic_bitset<Block, Allocator>& b);
618	#endif
619
620	// bitset operations
621	template <typename Block, typename Allocator>
622	dynamic_bitset<Block, Allocator>
623	operator&(const dynamic_bitset<Block, Allocator>& b1,
624	const dynamic_bitset<Block, Allocator>& b2);
625
626	template <typename Block, typename Allocator>
627	dynamic_bitset<Block, Allocator>
628	operator|(const dynamic_bitset<Block, Allocator>& b1,
629	const dynamic_bitset<Block, Allocator>& b2);
630
631	template <typename Block, typename Allocator>
632	dynamic_bitset<Block, Allocator>
633	operator^(const dynamic_bitset<Block, Allocator>& b1,
634	const dynamic_bitset<Block, Allocator>& b2);
635
636	template <typename Block, typename Allocator>
637	dynamic_bitset<Block, Allocator>
638	operator-(const dynamic_bitset<Block, Allocator>& b1,
639	const dynamic_bitset<Block, Allocator>& b2);
640
641	// namespace scope swap
642	template<typename Block, typename Allocator>
643	void swap(dynamic_bitset<Block, Allocator>& b1,
644	dynamic_bitset<Block, Allocator>& b2);
645
646
647	template <typename Block, typename Allocator, typename stringT>
648	void
649	to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s);
650
651	template <typename Block, typename Allocator, typename BlockOutputIterator>
652	void
653	to_block_range(const dynamic_bitset<Block, Allocator>& b,
654	BlockOutputIterator result);
655
656
657	template <typename BlockIterator, typename B, typename A>
658	inline void
659	from_block_range(BlockIterator first, BlockIterator last,
660	dynamic_bitset<B, A>& result)
661	{
662	// PRE: distance(first, last) <= numblocks()
663	std::copy (first, last, result.m_bits.begin());
664	}
665
666	//=============================================================================
667	// dynamic_bitset implementation
668
669
670	//-----------------------------------------------------------------------------
671	// constructors, etc.
672
673	template <typename Block, typename Allocator>
674	dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
675	: m_bits(alloc), m_num_bits(0)
676	{
677
678	}
679
680	template <typename Block, typename Allocator>
681	dynamic_bitset<Block, Allocator>::
682	dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
683	: m_bits(alloc),
684	m_num_bits(0)
685	{
686	init_from_unsigned_long(num_bits, value);
687	}
688
689	// copy constructor
690	template <typename Block, typename Allocator>
691	inline dynamic_bitset<Block, Allocator>::
692	dynamic_bitset(const dynamic_bitset& b)
693	: m_bits(b.m_bits), m_num_bits(b.m_num_bits)
694	{
695
696	}
697
698	template <typename Block, typename Allocator>
699	inline dynamic_bitset<Block, Allocator>::
700	~dynamic_bitset()
701	{
702	assert(m_check_invariants());
703	}
704
705	template <typename Block, typename Allocator>
706	inline void dynamic_bitset<Block, Allocator>::
707	swap(dynamic_bitset<Block, Allocator>& b) // no throw
708	{
709	std::swap(m_bits, b.m_bits);
710	std::swap(m_num_bits, b.m_num_bits);
711	}
712
713	template <typename Block, typename Allocator>
714	dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
715	operator=(const dynamic_bitset<Block, Allocator>& b)
716	{
717	m_bits = b.m_bits;
718	m_num_bits = b.m_num_bits;
719	return *this;
720	}
721
722	#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
723
724	template <typename Block, typename Allocator>
725	inline dynamic_bitset<Block, Allocator>::
726	dynamic_bitset(dynamic_bitset<Block, Allocator>&& b)
727	: m_bits(boost::move(b.m_bits)), m_num_bits(boost::move(b.m_num_bits))
728	{
729	// Required so that assert(m_check_invariants()); works.
730	assert((b.m_bits = buffer_type()).empty());
731	b.m_num_bits = 0;
732	}
733
734	template <typename Block, typename Allocator>
735	inline dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
736	operator=(dynamic_bitset<Block, Allocator>&& b)
737	{
738	if (boost::addressof(b) == this) { return *this; }
739
740	m_bits = boost::move(b.m_bits);
741	m_num_bits = boost::move(b.m_num_bits);
742	// Required so that assert(m_check_invariants()); works.
743	assert((b.m_bits = buffer_type()).empty());
744	b.m_num_bits = 0;
745	return *this;
746	}
747
748	#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
749
750	template <typename Block, typename Allocator>
751	inline typename dynamic_bitset<Block, Allocator>::allocator_type
752	dynamic_bitset<Block, Allocator>::get_allocator() const
753	{
754	return m_bits.get_allocator();
755	}
756
757	//-----------------------------------------------------------------------------
758	// size changing operations
759
760	template <typename Block, typename Allocator>
761	void dynamic_bitset<Block, Allocator>::
762	resize(size_type num_bits, bool value) // strong guarantee
763	{
764
765	const size_type old_num_blocks = num_blocks();
766	const size_type required_blocks = calc_num_blocks(num_bits);
767
768	const block_type v = value? detail::dynamic_bitset_impl::max_limit<Block>::value : Block(0);
769
770	if (required_blocks != old_num_blocks) {
771	m_bits.resize(required_blocks, v); // s.g. (copy)
772	}
773
774
775	// At this point:
776	//
777	// - if the buffer was shrunk, we have nothing more to do,
778	// except a call to m_zero_unused_bits()
779	//
780	// - if it was enlarged, all the (used) bits in the new blocks have
781	// the correct value, but we have not yet touched those bits, if
782	// any, that were 'unused bits' before enlarging: if value == true,
783	// they must be set.
784
785	if (value && (num_bits > m_num_bits)) {
786
787	const block_width_type extra_bits = count_extra_bits();
788	if (extra_bits) {
789	assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
790
791	// Set them.
792	m_bits[old_num_blocks - 1] |= (v << extra_bits);
793	}
794
795	}
796
797	m_num_bits = num_bits;
798	m_zero_unused_bits();
799
800	}
801
802	template <typename Block, typename Allocator>
803	void dynamic_bitset<Block, Allocator>::
804	clear() // no throw
805	{
806	m_bits.clear();
807	m_num_bits = 0;
808	}
809
810
811	template <typename Block, typename Allocator>
812	void dynamic_bitset<Block, Allocator>::
813	push_back(bool bit)
814	{
815	const size_type sz = size();
816	resize(num_bits: sz + 1);
817	set(sz, bit);
818	}
819
820	template <typename Block, typename Allocator>
821	void dynamic_bitset<Block, Allocator>::
822	pop_back()
823	{
824	const size_type old_num_blocks = num_blocks();
825	const size_type required_blocks = calc_num_blocks(num_bits: m_num_bits - 1);
826
827	if (required_blocks != old_num_blocks) {
828	m_bits.pop_back();
829	}
830
831	--m_num_bits;
832	m_zero_unused_bits();
833	}
834
835
836	template <typename Block, typename Allocator>
837	void dynamic_bitset<Block, Allocator>::
838	append(Block value) // strong guarantee
839	{
840	const block_width_type r = count_extra_bits();
841
842	if (r == 0) {
843	// the buffer is empty, or all blocks are filled
844	m_bits.push_back(value);
845	}
846	else {
847	m_bits.push_back(value >> (bits_per_block - r));
848	m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
849	}
850
851	m_num_bits += bits_per_block;
852	assert(m_check_invariants());
853
854	}
855
856
857	//-----------------------------------------------------------------------------
858	// bitset operations
859	template <typename Block, typename Allocator>
860	dynamic_bitset<Block, Allocator>&
861	dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
862	{
863	assert(size() == rhs.size());
864	for (size_type i = 0; i < num_blocks(); ++i)
865	m_bits[i] &= rhs.m_bits[i];
866	return *this;
867	}
868
869	template <typename Block, typename Allocator>
870	dynamic_bitset<Block, Allocator>&
871	dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
872	{
873	assert(size() == rhs.size());
874	for (size_type i = 0; i < num_blocks(); ++i)
875	m_bits[i] |= rhs.m_bits[i];
876	//m_zero_unused_bits();
877	return *this;
878	}
879
880	template <typename Block, typename Allocator>
881	dynamic_bitset<Block, Allocator>&
882	dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
883	{
884	assert(size() == rhs.size());
885	for (size_type i = 0; i < this->num_blocks(); ++i)
886	m_bits[i] ^= rhs.m_bits[i];
887	//m_zero_unused_bits();
888	return *this;
889	}
890
891	template <typename Block, typename Allocator>
892	dynamic_bitset<Block, Allocator>&
893	dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
894	{
895	assert(size() == rhs.size());
896	for (size_type i = 0; i < num_blocks(); ++i)
897	m_bits[i] &= ~rhs.m_bits[i];
898	//m_zero_unused_bits();
899	return *this;
900	}
901
902	//
903	// NOTE:
904	// Note that the 'if (r != 0)' is crucial to avoid undefined
905	// behavior when the left hand operand of >> isn't promoted to a
906	// wider type (because rs would be too large).
907	//
908	template <typename Block, typename Allocator>
909	dynamic_bitset<Block, Allocator>&
910	dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
911	{
912	if (n >= m_num_bits)
913	return reset();
914	//else
915	if (n > 0) {
916
917	size_type const last = num_blocks() - 1; // num_blocks() is >= 1
918	size_type const div = n / bits_per_block; // div is <= last
919	block_width_type const r = bit_index(pos: n);
920	block_type * const b = &m_bits[0];
921
922	if (r != 0) {
923
924	block_width_type const rs = bits_per_block - r;
925
926	for (size_type i = last-div; i>0; --i) {
927	b[i+div] = (b[i] << r) | (b[i-1] >> rs);
928	}
929	b[div] = b[0] << r;
930
931	}
932	else {
933	for (size_type i = last-div; i>0; --i) {
934	b[i+div] = b[i];
935	}
936	b[div] = b[0];
937	}
938
939	// zero out div blocks at the less significant end
940	std::fill_n(m_bits.begin(), div, static_cast<block_type>(0));
941
942	// zero out any 1 bit that flowed into the unused part
943	m_zero_unused_bits(); // thanks to Lester Gong
944
945	}
946
947	return *this;
948
949
950	}
951
952
953	//
954	// NOTE:
955	// see the comments to operator <<=
956	//
957	template <typename B, typename A>
958	dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
959	if (n >= m_num_bits) {
960	return reset();
961	}
962	//else
963	if (n>0) {
964
965	size_type const last = num_blocks() - 1; // num_blocks() is >= 1
966	size_type const div = n / bits_per_block; // div is <= last
967	block_width_type const r = bit_index(pos: n);
968	block_type * const b = &m_bits[0];
969
970
971	if (r != 0) {
972
973	block_width_type const ls = bits_per_block - r;
974
975	for (size_type i = div; i < last; ++i) {
976	b[i-div] = (b[i] >> r) | (b[i+1] << ls);
977	}
978	// r bits go to zero
979	b[last-div] = b[last] >> r;
980	}
981
982	else {
983	for (size_type i = div; i <= last; ++i) {
984	b[i-div] = b[i];
985	}
986	// note the '<=': the last iteration 'absorbs'
987	// b[last-div] = b[last] >> 0;
988	}
989
990
991
992	// div blocks are zero filled at the most significant end
993	std::fill_n(m_bits.begin() + (num_blocks()-div), div, static_cast<block_type>(0));
994	}
995
996	return *this;
997	}
998
999
1000	template <typename Block, typename Allocator>
1001	dynamic_bitset<Block, Allocator>
1002	dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
1003	{
1004	dynamic_bitset r(*this);
1005	return r <<= n;
1006	}
1007
1008	template <typename Block, typename Allocator>
1009	dynamic_bitset<Block, Allocator>
1010	dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
1011	{
1012	dynamic_bitset r(*this);
1013	return r >>= n;
1014	}
1015
1016
1017	//-----------------------------------------------------------------------------
1018	// basic bit operations
1019
1020	template <typename Block, typename Allocator>
1021	dynamic_bitset<Block, Allocator>&
1022	dynamic_bitset<Block, Allocator>::set(size_type pos,
1023	size_type len, bool val)
1024	{
1025	if (val)
1026	return range_operation(pos, len, partial_block_operation: set_block_partial, full_block_operation: set_block_full);
1027	else
1028	return range_operation(pos, len, partial_block_operation: reset_block_partial, full_block_operation: reset_block_full);
1029	}
1030
1031	template <typename Block, typename Allocator>
1032	dynamic_bitset<Block, Allocator>&
1033	dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
1034	{
1035	assert(pos < m_num_bits);
1036
1037	if (val)
1038	m_bits[block_index(pos)] |= bit_mask(pos);
1039	else
1040	reset(pos);
1041
1042	return *this;
1043	}
1044
1045	template <typename Block, typename Allocator>
1046	dynamic_bitset<Block, Allocator>&
1047	dynamic_bitset<Block, Allocator>::set()
1048	{
1049	std::fill(m_bits.begin(), m_bits.end(), detail::dynamic_bitset_impl::max_limit<Block>::value);
1050	m_zero_unused_bits();
1051	return *this;
1052	}
1053
1054	template <typename Block, typename Allocator>
1055	inline dynamic_bitset<Block, Allocator>&
1056	dynamic_bitset<Block, Allocator>::reset(size_type pos, size_type len)
1057	{
1058	return range_operation(pos, len, partial_block_operation: reset_block_partial, full_block_operation: reset_block_full);
1059	}
1060
1061	template <typename Block, typename Allocator>
1062	dynamic_bitset<Block, Allocator>&
1063	dynamic_bitset<Block, Allocator>::reset(size_type pos)
1064	{
1065	assert(pos < m_num_bits);
1066	#if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
1067	// CodeWarrior 8 generates incorrect code when the &=~ is compiled,
1068	// use the |^ variation instead.. <grafik>
1069	m_bits[block_index(pos)] |= bit_mask(pos);
1070	m_bits[block_index(pos)] ^= bit_mask(pos);
1071	#else
1072	m_bits[block_index(pos)] &= ~bit_mask(pos);
1073	#endif
1074	return *this;
1075	}
1076
1077	template <typename Block, typename Allocator>
1078	dynamic_bitset<Block, Allocator>&
1079	dynamic_bitset<Block, Allocator>::reset()
1080	{
1081	std::fill(m_bits.begin(), m_bits.end(), Block(0));
1082	return *this;
1083	}
1084
1085	template <typename Block, typename Allocator>
1086	dynamic_bitset<Block, Allocator>&
1087	dynamic_bitset<Block, Allocator>::flip(size_type pos, size_type len)
1088	{
1089	return range_operation(pos, len, partial_block_operation: flip_block_partial, full_block_operation: flip_block_full);
1090	}
1091
1092	template <typename Block, typename Allocator>
1093	dynamic_bitset<Block, Allocator>&
1094	dynamic_bitset<Block, Allocator>::flip(size_type pos)
1095	{
1096	assert(pos < m_num_bits);
1097	m_bits[block_index(pos)] ^= bit_mask(pos);
1098	return *this;
1099	}
1100
1101	template <typename Block, typename Allocator>
1102	dynamic_bitset<Block, Allocator>&
1103	dynamic_bitset<Block, Allocator>::flip()
1104	{
1105	for (size_type i = 0; i < num_blocks(); ++i)
1106	m_bits[i] = ~m_bits[i];
1107	m_zero_unused_bits();
1108	return *this;
1109	}
1110
1111	template <typename Block, typename Allocator>
1112	bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
1113	{
1114	return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
1115	}
1116
1117	template <typename Block, typename Allocator>
1118	bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
1119	{
1120	assert(pos < m_num_bits);
1121	return m_unchecked_test(pos);
1122	}
1123
1124	template <typename Block, typename Allocator>
1125	bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool val)
1126	{
1127	bool const b = test(pos);
1128	if (b != val) {
1129	set(pos, val);
1130	}
1131	return b;
1132	}
1133
1134	template <typename Block, typename Allocator>
1135	bool dynamic_bitset<Block, Allocator>::all() const
1136	{
1137	if (empty()) {
1138	return true;
1139	}
1140
1141	const block_width_type extra_bits = count_extra_bits();
1142	block_type const all_ones = detail::dynamic_bitset_impl::max_limit<Block>::value;
1143
1144	if (extra_bits == 0) {
1145	for (size_type i = 0, e = num_blocks(); i < e; ++i) {
1146	if (m_bits[i] != all_ones) {
1147	return false;
1148	}
1149	}
1150	} else {
1151	for (size_type i = 0, e = num_blocks() - 1; i < e; ++i) {
1152	if (m_bits[i] != all_ones) {
1153	return false;
1154	}
1155	}
1156	const block_type mask = (block_type(1) << extra_bits) - 1;
1157	if (m_highest_block() != mask) {
1158	return false;
1159	}
1160	}
1161	return true;
1162	}
1163
1164	template <typename Block, typename Allocator>
1165	bool dynamic_bitset<Block, Allocator>::any() const
1166	{
1167	for (size_type i = 0; i < num_blocks(); ++i)
1168	if (m_bits[i])
1169	return true;
1170	return false;
1171	}
1172
1173	template <typename Block, typename Allocator>
1174	inline bool dynamic_bitset<Block, Allocator>::none() const
1175	{
1176	return !any();
1177	}
1178
1179	template <typename Block, typename Allocator>
1180	dynamic_bitset<Block, Allocator>
1181	dynamic_bitset<Block, Allocator>::operator~() const
1182	{
1183	dynamic_bitset b(*this);
1184	b.flip();
1185	return b;
1186	}
1187
1188	template <typename Block, typename Allocator>
1189	typename dynamic_bitset<Block, Allocator>::size_type
1190	dynamic_bitset<Block, Allocator>::count() const BOOST_NOEXCEPT
1191	{
1192	using detail::dynamic_bitset_impl::table_width;
1193	using detail::dynamic_bitset_impl::access_by_bytes;
1194	using detail::dynamic_bitset_impl::access_by_blocks;
1195	using detail::dynamic_bitset_impl::value_to_type;
1196
1197	#if BOOST_WORKAROUND(__GNUC__, == 4) && (__GNUC_MINOR__ == 3) && (__GNUC_PATCHLEVEL__ == 3)
1198	// NOTE: Explicit qualification of "bits_per_block"
1199	// breaks compilation on gcc 4.3.3
1200	enum { no_padding = bits_per_block == CHAR_BIT * sizeof(Block) };
1201	#else
1202	// NOTE: Explicitly qualifying "bits_per_block" to workaround
1203	// regressions of gcc 3.4.x
1204	enum { no_padding =
1205	dynamic_bitset<Block, Allocator>::bits_per_block
1206	== CHAR_BIT * sizeof(Block) };
1207	#endif
1208
1209	enum { enough_table_width = table_width >= CHAR_BIT };
1210
1211	#if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
1212	// Windows popcount is effective starting from the unsigned short type
1213	enum { uneffective_popcount = sizeof(Block) < sizeof(unsigned short) };
1214	#elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
1215	// GCC popcount is effective starting from the unsigned int type
1216	enum { uneffective_popcount = sizeof(Block) < sizeof(unsigned int) };
1217	#else
1218	enum { uneffective_popcount = true };
1219	#endif
1220
1221	enum { mode = (no_padding && enough_table_width && uneffective_popcount)
1222	? access_by_bytes
1223	: access_by_blocks };
1224
1225	return do_count(m_bits.begin(), num_blocks(), Block(0),
1226	static_cast<value_to_type<(bool)mode> *>(0));
1227	}
1228
1229
1230	//-----------------------------------------------------------------------------
1231	// conversions
1232
1233
1234	template <typename B, typename A, typename stringT>
1235	void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
1236	bool dump_all)
1237	{
1238	typedef typename stringT::traits_type Tr;
1239	typedef typename stringT::value_type Ch;
1240
1241	BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
1242	const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1243	const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1244
1245	// Note that this function may access (when
1246	// dump_all == true) bits beyond position size() - 1
1247
1248	typedef typename dynamic_bitset<B, A>::size_type size_type;
1249
1250	const size_type len = dump_all?
1251	dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
1252	b.size();
1253	s.assign (len, zero);
1254
1255	for (size_type i = 0; i < len; ++i) {
1256	if (b.m_unchecked_test(i))
1257	Tr::assign(s[len - 1 - i], one);
1258
1259	}
1260
1261	}
1262
1263
1264	// A comment similar to the one about the constructor from
1265	// basic_string can be done here. Thanks to James Kanze for
1266	// making me (Gennaro) realize this important separation of
1267	// concerns issue, as well as many things about i18n.
1268	//
1269	template <typename Block, typename Allocator, typename stringT>
1270	inline void
1271	to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
1272	{
1273	to_string_helper(b, s, false);
1274	}
1275
1276
1277	// Differently from to_string this function dumps out
1278	// every bit of the internal representation (may be
1279	// useful for debugging purposes)
1280	//
1281	template <typename B, typename A, typename stringT>
1282	inline void
1283	dump_to_string(const dynamic_bitset<B, A>& b, stringT& s)
1284	{
1285	to_string_helper(b, s, true /* =dump_all*/);
1286	}
1287
1288	template <typename Block, typename Allocator, typename BlockOutputIterator>
1289	inline void
1290	to_block_range(const dynamic_bitset<Block, Allocator>& b,
1291	BlockOutputIterator result)
1292	{
1293	// note how this copies *all* bits, including the
1294	// unused ones in the last block (which are zero)
1295	std::copy(b.m_bits.begin(), b.m_bits.end(), result);
1296	}
1297
1298	template <typename Block, typename Allocator>
1299	unsigned long dynamic_bitset<Block, Allocator>::
1300	to_ulong() const
1301	{
1302
1303	if (m_num_bits == 0)
1304	return 0; // convention
1305
1306	// Check for overflows. This may be a performance burden on very
1307	// large bitsets but is required by the specification, sorry
1308	if (find_next(pos: ulong_width - 1) != npos)
1309	BOOST_THROW_EXCEPTION(std::overflow_error("boost::dynamic_bitset::to_ulong overflow"));
1310
1311
1312	// Ok, from now on we can be sure there's no "on" bit
1313	// beyond the "allowed" positions
1314	typedef unsigned long result_type;
1315
1316	const size_type maximum_size =
1317	(std::min)(a: m_num_bits, b: static_cast<size_type>(ulong_width));
1318
1319	const size_type last_block = block_index( pos: maximum_size - 1 );
1320
1321	assert((last_block * bits_per_block) < static_cast<size_type>(ulong_width));
1322
1323	result_type result = 0;
1324	for (size_type i = 0; i <= last_block; ++i) {
1325	const size_type offset = i * bits_per_block;
1326	result |= (static_cast<result_type>(m_bits[i]) << offset);
1327	}
1328
1329	return result;
1330	}
1331
1332	template <typename Block, typename Allocator>
1333	inline typename dynamic_bitset<Block, Allocator>::size_type
1334	dynamic_bitset<Block, Allocator>::size() const BOOST_NOEXCEPT
1335	{
1336	return m_num_bits;
1337	}
1338
1339	template <typename Block, typename Allocator>
1340	inline typename dynamic_bitset<Block, Allocator>::size_type
1341	dynamic_bitset<Block, Allocator>::num_blocks() const BOOST_NOEXCEPT
1342	{
1343	return m_bits.size();
1344	}
1345
1346	template <typename Block, typename Allocator>
1347	inline typename dynamic_bitset<Block, Allocator>::size_type
1348	dynamic_bitset<Block, Allocator>::max_size() const BOOST_NOEXCEPT
1349	{
1350	// Semantics of vector<>::max_size() aren't very clear
1351	// (see lib issue 197) and many library implementations
1352	// simply return dummy values, _unrelated_ to the underlying
1353	// allocator.
1354	//
1355	// Given these problems, I was tempted to not provide this
1356	// function at all but the user could need it if he provides
1357	// his own allocator.
1358	//
1359
1360	const size_type m = detail::dynamic_bitset_impl::
1361	vector_max_size_workaround(m_bits);
1362
1363	return m <= (size_type(-1)/bits_per_block) ?
1364	m * bits_per_block :
1365	size_type(-1);
1366	}
1367
1368	template <typename Block, typename Allocator>
1369	inline bool dynamic_bitset<Block, Allocator>::empty() const BOOST_NOEXCEPT
1370	{
1371	return size() == 0;
1372	}
1373
1374	template <typename Block, typename Allocator>
1375	inline typename dynamic_bitset<Block, Allocator>::size_type
1376	dynamic_bitset<Block, Allocator>::capacity() const BOOST_NOEXCEPT
1377	{
1378	return m_bits.capacity() * bits_per_block;
1379	}
1380
1381	template <typename Block, typename Allocator>
1382	inline void dynamic_bitset<Block, Allocator>::reserve(size_type num_bits)
1383	{
1384	m_bits.reserve(calc_num_blocks(num_bits));
1385	}
1386
1387	template <typename Block, typename Allocator>
1388	void dynamic_bitset<Block, Allocator>::shrink_to_fit()
1389	{
1390	if (m_bits.size() < m_bits.capacity()) {
1391	buffer_type(m_bits).swap(m_bits);
1392	}
1393	}
1394
1395	template <typename Block, typename Allocator>
1396	bool dynamic_bitset<Block, Allocator>::
1397	is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1398	{
1399	assert(size() == a.size());
1400	for (size_type i = 0; i < num_blocks(); ++i)
1401	if (m_bits[i] & ~a.m_bits[i])
1402	return false;
1403	return true;
1404	}
1405
1406	template <typename Block, typename Allocator>
1407	bool dynamic_bitset<Block, Allocator>::
1408	is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1409	{
1410	assert(size() == a.size());
1411	assert(num_blocks() == a.num_blocks());
1412
1413	bool proper = false;
1414	for (size_type i = 0; i < num_blocks(); ++i) {
1415	const Block & bt = m_bits[i];
1416	const Block & ba = a.m_bits[i];
1417
1418	if (bt & ~ba)
1419	return false; // not a subset at all
1420	if (ba & ~bt)
1421	proper = true;
1422	}
1423	return proper;
1424	}
1425
1426	template <typename Block, typename Allocator>
1427	bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
1428	{
1429	size_type common_blocks = num_blocks() < b.num_blocks()
1430	? num_blocks() : b.num_blocks();
1431
1432	for(size_type i = 0; i < common_blocks; ++i) {
1433	if(m_bits[i] & b.m_bits[i])
1434	return true;
1435	}
1436	return false;
1437	}
1438
1439	// --------------------------------
1440	// lookup
1441
1442	// look for the first bit "on", starting
1443	// from the block with index first_block
1444	//
1445
1446	template <typename Block, typename Allocator>
1447	typename dynamic_bitset<Block, Allocator>::size_type
1448	dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
1449	{
1450
1451	size_type i = std::distance(m_bits.begin(),
1452	std::find_if(m_bits.begin() + first_block, m_bits.end(), m_not_empty) );
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
1463	dynamic_bitset<Block, Allocator>::find_first() const
1464	{
1465	return m_do_find_from(first_block: 0);
1466	}
1467
1468
1469	template <typename Block, typename Allocator>
1470	typename dynamic_bitset<Block, Allocator>::size_type
1471	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(first_block: blk + 1);
1490
1491	}
1492
1493
1494
1495	//-----------------------------------------------------------------------------
1496	// comparison
1497
1498	template <typename Block, typename Allocator>
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>
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>
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>
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>
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>
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>
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>
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&
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>&
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:
1804	explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
1805	~pseudo_sentry() { m_r.isfx(); }
1806	operator bool() const { return m_ok; }
1807	};
1808
1809	template <typename Block, typename Alloc>
1810	std::istream&
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>&
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>
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>
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>
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>
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
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
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>
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>
2023	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>
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: pos + len - 1);
2049
2050	const size_type first_bit_index = bit_index(pos);
2051	const size_type last_bit_index = bit_index(pos: 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: 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>
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>
2106	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 = detail::dynamic_bitset_impl::max_limit<Block>::value << 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(num_bits: 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;
2136	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