1 // -----------------------------------------------------------
2 // Copyright (c) 2001 Jeremy Siek
3 // Copyright (c) 2003-2006, 2008 Gennaro Prota
4 // Copyright (c) 2014 Ahmed Charles
5 // Copyright (c) 2014 Riccardo Marcangelo
7 // Distributed under the Boost Software License, Version 1.0.
8 // (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 // -----------------------------------------------------------
13 #ifndef BOOST_BITSET_TEST_HPP_GP_20040319
14 #define BOOST_BITSET_TEST_HPP_GP_20040319
16 #include "boost/config.hpp"
17 #if !defined (BOOST_NO_STD_LOCALE)
22 #include <fstream> // used for operator<<
23 #include <string> // for (basic_string and) getline()
24 #include <algorithm> // for std::min
25 #include <assert.h> // <cassert> is sometimes macro-guarded :-(
27 #include "boost/limits.hpp"
28 #include "boost/dynamic_bitset/dynamic_bitset.hpp"
29 #include "boost/test/minimal.hpp"
31 template <typename Block>
32 inline bool nth_bit(Block num, std::size_t n)
35 // Borland deduces Block as a const qualified type,
36 // and thus finds numeric_limits<Block> to be zero :(
37 // (though not directly relevant here, see also
39 int block_width = sizeof(Block) * CHAR_BIT;
41 int block_width = std::numeric_limits<Block>::digits;
44 assert(n < (std::size_t) block_width);
45 return (num >> n) & 1;
48 // A long, 'irregular', string useful for various tests
49 std::string get_long_string()
51 const char * const p =
53 // 3210987654321098765432109876543210987654321098765432109876543210
54 "1110011100011110000011110000011111110000000000000110101110000000"
55 "1010101000011100011101010111110000101011111000001111100011100011"
56 "0000000110000001000000111100000111100010101111111000000011100011"
57 "1111111111111111111111111111111111111111111111111111111111111100"
58 "1000001100000001111111111111110000000011111000111100001010100000"
59 "101000111100011010101110011011000000010";
61 return std::string(p);
64 const char * test_file_name()
66 return "boost_dynamic_bitset_tests";
69 #if defined BOOST_OLD_IOSTREAMS || defined BOOST_NO_STD_LOCALE
70 template <typename Stream>
71 bool is_one_or_zero(const Stream & /*s*/, char c)
73 return c == '1' || c == '0';
75 template <typename Stream>
76 bool is_white_space(const Stream & /*s*/, char c)
78 return std::isspace(c);
81 template <typename Stream, typename Ch>
82 bool is_one_or_zero(const Stream& s, Ch c)
84 typedef typename Stream::traits_type Tr;
85 const Ch zero = s.widen('0');
86 const Ch one = s.widen('1');
88 return Tr::eq(c, one) || Tr::eq(c, zero);
90 template <typename Stream, typename Ch>
91 bool is_white_space(const Stream & s, Ch c)
93 // NOTE: the using directive is to satisfy Borland 5.6.4
94 // with its own library (STLport), which doesn't
95 // like std::isspace(c, loc)
97 return isspace(c, s.getloc());
99 #endif // defined BOOST_OLD_IOSTREAMS
102 template <typename Stream>
103 bool has_flags(const Stream& s, std::ios::iostate flags)
105 return (s.rdstate() & flags) != std::ios::goodbit;
110 // default (can't do this generically)
112 template <typename Bitset>
115 typedef typename Bitset::block_type Block;
116 BOOST_STATIC_CONSTANT(int, bits_per_block = Bitset::bits_per_block);
118 // from unsigned long
120 // Note: this is templatized so that we check that the do-the-right-thing
121 // constructor dispatch is working correctly.
123 template <typename NumBits, typename Value>
124 static void from_unsigned_long(NumBits num_bits, Value num)
126 // An object of size sz = num_bits is constructed:
127 // - the first m bit positions are initialized to the corresponding
128 // bit values in num (m being the smaller of sz and ulong_width)
130 // - any remaining bit positions are initialized to zero
133 Bitset b(static_cast<typename Bitset::size_type>(num_bits), static_cast<unsigned long>(num));
135 // OK, we can now cast to size_type
136 typedef typename Bitset::size_type size_type;
137 const size_type sz = static_cast<size_type>(num_bits);
139 BOOST_CHECK(b.size() == sz);
141 const std::size_t ulong_width = std::numeric_limits<unsigned long>::digits;
143 if (ulong_width < sz)
148 BOOST_CHECK(b.test(i) == nth_bit(static_cast<unsigned long>(num), i));
150 BOOST_CHECK(b.test(i) == 0);
155 // Note: The corresponding function in dynamic_bitset (constructor
156 // from a string) has several default arguments. Actually we don't
157 // test the correct working of those defaults here (except for the
158 // default of num_bits). I'm not sure what to do in this regard.
160 // Note2: the default argument expression for num_bits doesn't use
161 // static_cast, to avoid a gcc 2.95.3 'sorry, not implemented'
163 template <typename Ch, typename Tr, typename Al>
164 static void from_string(const std::basic_string<Ch, Tr, Al>& str,
166 std::size_t max_char,
167 std::size_t num_bits = (std::size_t)(-1))
170 std::size_t rlen = (std::min)(max_char, str.size() - pos);
172 // The resulting size N of the bitset is num_bits, if
173 // that is different from the default arg, rlen otherwise.
174 // Put M = the smaller of N and rlen, then character
175 // position pos + M - 1 corresponds to bit position zero.
176 // Subsequent decreasing character positions correspond to
177 // increasing bit positions.
179 const bool size_upon_string = num_bits == (std::size_t)(-1);
180 Bitset b = size_upon_string ?
181 Bitset(str, pos, max_char)
182 : Bitset(str, pos, max_char, num_bits);
184 const std::size_t actual_size = size_upon_string? rlen : num_bits;
185 BOOST_CHECK(b.size() == actual_size);
186 std::size_t m = (std::min)(num_bits, rlen);
188 for (j = 0; j < m; ++j)
189 BOOST_CHECK(b[j] == (str[pos + m - 1 - j] == '1'));
190 // If M < N, remaining bit positions are zero
191 for (; j < actual_size; ++j)
192 BOOST_CHECK(b[j] == 0);
197 static void to_block_range(const Bitset & b /*, BlockOutputIterator result*/)
199 typedef typename Bitset::size_type size_type;
201 Block sentinel = 0xF0;
202 int s = 8; // number of sentinels (must be *even*)
204 std::vector<Block> v(b.num_blocks() + s, sentinel);
206 boost::to_block_range(b, v.begin() + offset);
208 assert(v.size() >= (size_type)s && (s >= 2) && (s % 2 == 0));
209 // check sentinels at both ends
210 for(int i = 0; i < s/2; ++i) {
211 BOOST_CHECK(v[i] == sentinel);
212 BOOST_CHECK(v[v.size()-1-i] == sentinel);
215 typename std::vector<Block>::const_iterator p = v.begin() + offset;
216 for(size_type n = 0; n < b.num_blocks(); ++n, ++p) {
217 typename Bitset::block_width_type i = 0;
218 for(; i < bits_per_block; ++i) {
219 size_type bit = n * bits_per_block + i;
220 BOOST_CHECK(nth_bit(*p, i) == (bit < b.size()? b[bit] : 0));
225 // TODO from_block_range (below) should be splitted
227 // PRE: std::equal(first1, last1, first2) == true
228 static void from_block_range(const std::vector<Block>& blocks)
230 { // test constructor from block range
231 Bitset bset(blocks.begin(), blocks.end());
232 std::size_t n = blocks.size();
233 for (std::size_t b = 0; b < n; ++b) {
234 typename Bitset::block_width_type i = 0;
235 for (; i < bits_per_block; ++i) {
236 std::size_t bit = b * bits_per_block + i;
237 BOOST_CHECK(bset[bit] == nth_bit(blocks[b], i));
240 BOOST_CHECK(bset.size() == n * bits_per_block);
242 { // test boost::from_block_range
243 const typename Bitset::size_type n = blocks.size();
244 Bitset bset(n * bits_per_block);
245 boost::from_block_range(blocks.begin(), blocks.end(), bset);
246 for (std::size_t b = 0; b < n; ++b) {
247 typename Bitset::block_width_type i = 0;
248 for (; i < bits_per_block; ++i) {
249 std::size_t bit = b * bits_per_block + i;
250 BOOST_CHECK(bset[bit] == nth_bit(blocks[b], i));
253 BOOST_CHECK(n <= bset.num_blocks());
257 // copy constructor (absent from std::bitset)
258 static void copy_constructor(const Bitset& b)
261 BOOST_CHECK(b == copy);
263 // Changes to the copy do not affect the original
265 std::size_t pos = copy.size() / 2;
267 BOOST_CHECK(copy[pos] != b[pos]);
271 // copy assignment operator (absent from std::bitset)
272 static void copy_assignment_operator(const Bitset& lhs, const Bitset& rhs)
276 b = b; // self assignment check
277 BOOST_CHECK(b == rhs);
279 // Changes to the copy do not affect the original
281 std::size_t pos = b.size() / 2;
283 BOOST_CHECK(b[pos] != rhs[pos]);
287 static void max_size(const Bitset& b)
289 BOOST_CHECK(b.max_size() > 0);
292 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
294 // move constructor (absent from std::bitset)
295 static void move_constructor(const Bitset& b)
297 Bitset copy(boost::move(b));
298 BOOST_CHECK(b == copy);
301 // move assignment operator (absent from std::bitset)
302 static void move_assignment_operator(const Bitset& lhs, const Bitset& rhs)
307 b = boost::move(b); // self assignment check
308 BOOST_CHECK(b == rhs);
311 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
313 static void swap(const Bitset& lhs, const Bitset& rhs)
315 // bitsets must be swapped
320 BOOST_CHECK(copy1 == rhs);
321 BOOST_CHECK(copy2 == lhs);
323 // references must be stable under a swap
324 for(typename Bitset::size_type i = 0; i < lhs.size(); ++i) {
327 typename Bitset::reference ref = b1[i];
330 b2[i] = !x; // make sure b2[i] is different
332 BOOST_CHECK(b2[i] == x); // now it must be equal..
334 BOOST_CHECK(ref == b2[i]); // .. and ref must be into b2
335 BOOST_CHECK(ref == !x);
340 static void resize(const Bitset& lhs)
344 // Test no change in size
345 b.resize(lhs.size());
346 BOOST_CHECK(b == lhs);
348 // Test increase in size
349 b.resize(lhs.size() * 2, true);
352 for (i = 0; i < lhs.size(); ++i)
353 BOOST_CHECK(b[i] == lhs[i]);
354 for (; i < b.size(); ++i)
355 BOOST_CHECK(b[i] == true);
357 // Test decrease in size
358 b.resize(lhs.size());
359 for (i = 0; i < lhs.size(); ++i)
360 BOOST_CHECK(b[i] == lhs[i]);
363 static void clear(const Bitset& lhs)
367 BOOST_CHECK(b.size() == 0);
370 static void pop_back(const Bitset& lhs)
374 BOOST_CHECK(b.size() == lhs.size() - 1);
375 for (std::size_t i = 0; i < b.size(); ++i)
376 BOOST_CHECK(b[i] == lhs[i]);
379 BOOST_CHECK(b.size() == lhs.size() - 2);
380 for (std::size_t j = 0; j < b.size(); ++j)
381 BOOST_CHECK(b[j] == lhs[j]);
384 static void append_bit(const Bitset& lhs)
388 BOOST_CHECK(b.size() == lhs.size() + 1);
389 BOOST_CHECK(b[b.size() - 1] == true);
390 for (std::size_t i = 0; i < lhs.size(); ++i)
391 BOOST_CHECK(b[i] == lhs[i]);
394 BOOST_CHECK(b.size() == lhs.size() + 2);
395 BOOST_CHECK(b[b.size() - 1] == false);
396 BOOST_CHECK(b[b.size() - 2] == true);
397 for (std::size_t j = 0; j < lhs.size(); ++j)
398 BOOST_CHECK(b[j] == lhs[j]);
401 static void append_block(const Bitset& lhs)
406 BOOST_CHECK(b.size() == lhs.size() + bits_per_block);
407 for (typename Bitset::block_width_type i = 0; i < bits_per_block; ++i)
408 BOOST_CHECK(b[lhs.size() + i] == bool((value >> i) & 1));
411 static void append_block_range(const Bitset& lhs, const std::vector<Block>& blocks)
413 Bitset b(lhs), c(lhs);
414 b.append(blocks.begin(), blocks.end());
415 for (typename std::vector<Block>::const_iterator i = blocks.begin();
416 i != blocks.end(); ++i)
421 // operator[] and reference members
422 // PRE: b[i] == bit_vec[i]
423 static void operator_bracket(const Bitset& lhs, const std::vector<bool>& bit_vec)
430 for (i = 0; i < b.size(); ++i) {
432 BOOST_CHECK(x == bit_vec[i]);
434 BOOST_CHECK(x == !bit_vec[i]);
439 for (j = 0; j < b.size(); ++j) {
442 for (k = 0; k < b.size(); ++k)
444 BOOST_CHECK(b[k] == x);
446 BOOST_CHECK(b[k] == prev[k]);
452 for (i = 0; i < b.size(); ++i) {
454 for (j = 0; j < b.size(); ++j) {
456 BOOST_CHECK(b[j] == prev[j]);
458 BOOST_CHECK(b[j] == !prev[j]);
464 for (i = 0; i < b.size(); ++i) {
466 for (j = 0; j < b.size(); ++j) {
468 BOOST_CHECK(b[j] == prev[j]);
470 BOOST_CHECK(b[j] == !prev[j]);
476 //===========================================================================
479 // bitwise and assignment
481 // PRE: b.size() == rhs.size()
482 static void and_assignment(const Bitset& b, const Bitset& rhs)
487 // Clears each bit in lhs for which the corresponding bit in rhs is
488 // clear, and leaves all other bits unchanged.
489 for (std::size_t I = 0; I < lhs.size(); ++I)
491 BOOST_CHECK(lhs[I] == 0);
493 BOOST_CHECK(lhs[I] == prev[I]);
496 // PRE: b.size() == rhs.size()
497 static void or_assignment(const Bitset& b, const Bitset& rhs)
502 // Sets each bit in lhs for which the corresponding bit in rhs is set, and
503 // leaves all other bits unchanged.
504 for (std::size_t I = 0; I < lhs.size(); ++I)
506 BOOST_CHECK(lhs[I] == 1);
508 BOOST_CHECK(lhs[I] == prev[I]);
511 // PRE: b.size() == rhs.size()
512 static void xor_assignment(const Bitset& b, const Bitset& rhs)
517 // Flips each bit in lhs for which the corresponding bit in rhs is set,
518 // and leaves all other bits unchanged.
519 for (std::size_t I = 0; I < lhs.size(); ++I)
521 BOOST_CHECK(lhs[I] == !prev[I]);
523 BOOST_CHECK(lhs[I] == prev[I]);
526 // PRE: b.size() == rhs.size()
527 static void sub_assignment(const Bitset& b, const Bitset& rhs)
532 // Resets each bit in lhs for which the corresponding bit in rhs is set,
533 // and leaves all other bits unchanged.
534 for (std::size_t I = 0; I < lhs.size(); ++I)
536 BOOST_CHECK(lhs[I] == 0);
538 BOOST_CHECK(lhs[I] == prev[I]);
541 static void shift_left_assignment(const Bitset& b, std::size_t pos)
546 // Replaces each bit at position I in lhs with the following value:
547 // - If I < pos, the new value is zero
548 // - If I >= pos, the new value is the previous value of the bit at
550 for (std::size_t I = 0; I < lhs.size(); ++I)
552 BOOST_CHECK(lhs[I] == 0);
554 BOOST_CHECK(lhs[I] == prev[I - pos]);
557 static void shift_right_assignment(const Bitset& b, std::size_t pos)
562 // Replaces each bit at position I in lhs with the following value:
563 // - If pos >= N - I, the new value is zero
564 // - If pos < N - I, the new value is the previous value of the bit at
566 std::size_t N = lhs.size();
567 for (std::size_t I = 0; I < N; ++I)
569 BOOST_CHECK(lhs[I] == 0);
571 BOOST_CHECK(lhs[I] == prev[I + pos]);
575 static void set_all(const Bitset& b)
579 for (std::size_t I = 0; I < lhs.size(); ++I)
580 BOOST_CHECK(lhs[I] == 1);
583 static void set_one(const Bitset& b, std::size_t pos, bool value)
586 std::size_t N = lhs.size();
589 // Stores a new value in the bit at position pos in lhs.
591 BOOST_CHECK(lhs[pos] == value);
593 // All other values of lhs remain unchanged
594 for (std::size_t I = 0; I < N; ++I)
596 BOOST_CHECK(lhs[I] == prev[I]);
598 // Not in range, doesn't satisfy precondition.
602 static void reset_all(const Bitset& b)
605 // Resets all bits in lhs
607 for (std::size_t I = 0; I < lhs.size(); ++I)
608 BOOST_CHECK(lhs[I] == 0);
611 static void reset_one(const Bitset& b, std::size_t pos)
614 std::size_t N = lhs.size();
618 // Resets the bit at position pos in lhs
619 BOOST_CHECK(lhs[pos] == 0);
621 // All other values of lhs remain unchanged
622 for (std::size_t I = 0; I < N; ++I)
624 BOOST_CHECK(lhs[I] == prev[I]);
626 // Not in range, doesn't satisfy precondition.
630 static void operator_flip(const Bitset& b)
634 BOOST_CHECK(~lhs == x.flip());
637 static void flip_all(const Bitset& b)
640 std::size_t N = lhs.size();
643 // Toggles all the bits in lhs
644 for (std::size_t I = 0; I < N; ++I)
645 BOOST_CHECK(lhs[I] == !prev[I]);
648 static void flip_one(const Bitset& b, std::size_t pos)
651 std::size_t N = lhs.size();
655 // Toggles the bit at position pos in lhs
656 BOOST_CHECK(lhs[pos] == !prev[pos]);
658 // All other values of lhs remain unchanged
659 for (std::size_t I = 0; I < N; ++I)
661 BOOST_CHECK(lhs[I] == prev[I]);
663 // Not in range, doesn't satisfy precondition.
668 static void empty(const Bitset& b)
670 BOOST_CHECK(b.empty() == (b.size() == 0));
674 static void to_ulong(const Bitset& lhs)
676 typedef unsigned long result_type;
677 std::size_t n = std::numeric_limits<result_type>::digits;
678 std::size_t sz = lhs.size();
680 bool will_overflow = false;
681 for (std::size_t i = n; i < sz; ++i) {
682 if (lhs.test(i) != 0) {
683 will_overflow = true;
689 (void)lhs.to_ulong();
690 BOOST_CHECK(false); // It should have thrown an exception
691 } catch (std::overflow_error & ex) {
693 BOOST_CHECK(!!ex.what());
695 BOOST_CHECK(false); // threw the wrong exception
698 result_type num = lhs.to_ulong();
699 // Be sure the number is right
701 BOOST_CHECK(num == 0);
703 for (std::size_t i = 0; i < sz; ++i)
704 BOOST_CHECK(lhs[i] == (i < n ? nth_bit(num, i) : 0));
710 static void to_string(const Bitset& b)
713 boost::to_string(b, str);
714 BOOST_CHECK(str.size() == b.size());
715 for (std::size_t i = 0; i < b.size(); ++i)
716 BOOST_CHECK(str[b.size() - 1 - i] ==(b.test(i)? '1':'0'));
719 static void count(const Bitset& b)
721 std::size_t c = b.count();
722 std::size_t actual = 0;
723 for (std::size_t i = 0; i < b.size(); ++i)
726 BOOST_CHECK(c == actual);
729 static void size(const Bitset& b)
731 BOOST_CHECK(Bitset(b).set().count() == b.size());
734 static void capacity_test_one(const Bitset& lhs)
738 BOOST_CHECK(b.capacity() == 0);
741 static void capacity_test_two(const Bitset& lhs)
743 //bitset constructed with size "100"
745 BOOST_CHECK(b.capacity() >= 100);
747 BOOST_CHECK(b.capacity() >= 200);
750 static void reserve_test_one(const Bitset& lhs)
755 BOOST_CHECK(b.capacity() >= 16);
758 static void reserve_test_two(const Bitset& lhs)
760 //bitset constructed with size "100"
762 BOOST_CHECK(b.capacity() >= 100);
764 BOOST_CHECK(b.size() == 100);
765 BOOST_CHECK(b.capacity() >= 100);
767 BOOST_CHECK(b.size() == 100);
768 BOOST_CHECK(b.capacity() >= 160);
771 static void shrink_to_fit_test_one(const Bitset& lhs)
776 BOOST_CHECK(b.size() == 0);
777 BOOST_CHECK(b.capacity() == 0);
780 static void shrink_to_fit_test_two(const Bitset& lhs)
782 //bitset constructed with size "100"
785 BOOST_CHECK(b.capacity() >= 100);
786 BOOST_CHECK(b.size() == 100);
788 BOOST_CHECK(b.capacity() >= 200);
789 BOOST_CHECK(b.size() == 100);
791 BOOST_CHECK(b.capacity() < 200);
792 BOOST_CHECK(b.size() == 100);
795 static void all(const Bitset& b)
797 BOOST_CHECK(b.all() == (b.count() == b.size()));
799 for(std::size_t i = 0; i < b.size(); ++i)
804 BOOST_CHECK(b.all() == result);
807 static void any(const Bitset& b)
809 BOOST_CHECK(b.any() == (b.count() != 0));
811 for(std::size_t i = 0; i < b.size(); ++i)
816 BOOST_CHECK(b.any() == result);
819 static void none(const Bitset& b)
822 for(std::size_t i = 0; i < b.size(); ++i) {
828 BOOST_CHECK(b.none() == result);
831 BOOST_CHECK(b.none() == !b.any());
832 BOOST_CHECK(b.none() == (b.count() == 0));
835 static void subset(const Bitset& a, const Bitset& b)
837 BOOST_CHECK(a.size() == b.size()); // PRE
839 bool is_subset = true;
840 if (b.size()) { // could use b.any() but let's be safe
841 for(std::size_t i = 0; i < a.size(); ++i) {
842 if(a.test(i) && !b.test(i)) {
850 BOOST_CHECK(a.count() == 0);
851 BOOST_CHECK(a.any() == false);
853 //is_subset = (a.any() == false);
856 BOOST_CHECK(a.is_subset_of(b) == is_subset);
859 static void proper_subset(const Bitset& a, const Bitset& b)
861 // PRE: a.size() == b.size()
862 BOOST_CHECK(a.size() == b.size());
864 bool is_proper = false;
868 // check it's a subset
872 for (std::size_t i = 0; i < a.size(); ++i) {
873 if (!a.test(i) && b.test(i)) {
876 BOOST_CHECK(a.count() < b.count());
877 BOOST_CHECK(b.any());
882 BOOST_CHECK(a.is_proper_subset_of(b) == is_proper);
884 BOOST_CHECK(b.is_proper_subset_of(a) != is_proper);// antisymmetry
887 static void intersects(const Bitset& a, const Bitset& b)
889 bool have_intersection = false;
891 typename Bitset::size_type m = a.size() < b.size() ? a.size() : b.size();
892 for(typename Bitset::size_type i = 0; i < m && !have_intersection; ++i)
893 if(a[i] == true && b[i] == true)
894 have_intersection = true;
896 BOOST_CHECK(a.intersects(b) == have_intersection);
897 // also check commutativity
898 BOOST_CHECK(b.intersects(a) == have_intersection);
901 static void find_first(const Bitset& b)
903 // find first non-null bit, if any
904 typename Bitset::size_type i = 0;
905 while (i < b.size() && b[i] == 0)
909 BOOST_CHECK(b.find_first() == Bitset::npos); // not found;
911 BOOST_CHECK(b.find_first() == i);
912 BOOST_CHECK(b.test(i) == true);
917 static void find_next(const Bitset& b, typename Bitset::size_type prev)
919 BOOST_CHECK(next_bit_on(b, prev) == b.find_next(prev));
922 static void operator_equal(const Bitset& a, const Bitset& b)
925 for (std::size_t I = 0; I < a.size(); ++I)
926 BOOST_CHECK(a[I] == b[I]);
928 if (a.size() == b.size()) {
930 for (std::size_t I = 0; I < a.size(); ++I)
940 static void operator_not_equal(const Bitset& a, const Bitset& b)
943 if (a.size() == b.size()) {
945 for (std::size_t I = 0; I < a.size(); ++I)
953 for (std::size_t I = 0; I < a.size(); ++I)
954 BOOST_CHECK(a[I] == b[I]);
958 static bool less_than(const Bitset& a, const Bitset& b)
961 typedef BOOST_DEDUCED_TYPENAME Bitset::size_type size_type;
963 size_type asize(a.size());
964 size_type bsize(b.size());
977 // Compare from most significant to least.
979 size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize));
981 for (I = 0; I < leqsize; ++I,--asize,--bsize)
984 size_type i = asize-1;
985 size_type j = bsize-1;
989 else if (a[i] > b[j])
991 // if (a[i] = b[j]) skip to next
993 return (a.size() < b.size());
997 static typename Bitset::size_type next_bit_on(const Bitset& b, typename Bitset::size_type prev)
999 // helper function for find_next()
1002 if (b.none() == true || prev == Bitset::npos)
1003 return Bitset::npos;
1007 if (prev >= b.size())
1008 return Bitset::npos;
1010 typename Bitset::size_type i = prev;
1011 while (i < b.size() && b[i] == 0)
1014 return i==b.size() ? Bitset::npos : i;
1018 static void operator_less_than(const Bitset& a, const Bitset& b)
1020 if (less_than(a, b))
1023 BOOST_CHECK(!(a < b));
1026 static void operator_greater_than(const Bitset& a, const Bitset& b)
1028 if (less_than(a, b) || a == b)
1029 BOOST_CHECK(!(a > b));
1034 static void operator_less_than_eq(const Bitset& a, const Bitset& b)
1036 if (less_than(a, b) || a == b)
1037 BOOST_CHECK(a <= b);
1039 BOOST_CHECK(!(a <= b));
1042 static void operator_greater_than_eq(const Bitset& a, const Bitset& b)
1044 if (less_than(a, b))
1045 BOOST_CHECK(!(a >= b));
1047 BOOST_CHECK(a >= b);
1050 static void test_bit(const Bitset& b, std::size_t pos)
1053 std::size_t N = lhs.size();
1055 BOOST_CHECK(lhs.test(pos) == lhs[pos]);
1057 // Not in range, doesn't satisfy precondition.
1061 static void test_set_bit(const Bitset& b, std::size_t pos, bool value)
1064 std::size_t N = lhs.size();
1067 // Stores a new value in the bit at position pos in lhs.
1068 BOOST_CHECK(lhs.test_set(pos, value) == prev[pos]);
1069 BOOST_CHECK(lhs[pos] == value);
1071 // All other values of lhs remain unchanged
1072 for (std::size_t I = 0; I < N; ++I)
1074 BOOST_CHECK(lhs[I] == prev[I]);
1076 // Not in range, doesn't satisfy precondition.
1080 static void operator_shift_left(const Bitset& lhs, std::size_t pos)
1083 BOOST_CHECK((lhs << pos) == (x <<= pos));
1086 static void operator_shift_right(const Bitset& lhs, std::size_t pos)
1089 BOOST_CHECK((lhs >> pos) == (x >>= pos));
1094 void operator_or(const Bitset& lhs, const Bitset& rhs)
1097 BOOST_CHECK((lhs | rhs) == (x |= rhs));
1102 void operator_and(const Bitset& lhs, const Bitset& rhs)
1105 BOOST_CHECK((lhs & rhs) == (x &= rhs));
1110 void operator_xor(const Bitset& lhs, const Bitset& rhs)
1113 BOOST_CHECK((lhs ^ rhs) == (x ^= rhs));
1118 void operator_sub(const Bitset& lhs, const Bitset& rhs)
1121 BOOST_CHECK((lhs - rhs) == (x -= rhs));
1124 //------------------------------------------------------------------------------
1126 // The following tests assume the results of extraction (i.e.: contents,
1127 // state and width of is, contents of b) only depend on input (the string
1128 // str). In other words, they don't consider "unexpected" errors such as
1129 // stream corruption or out of memory. The reason is simple: if e.g. the
1130 // stream buffer throws, the stream layer may eat the exception and
1131 // transform it into a badbit. But we can't trust the stream state here,
1132 // because one of the things that we want to test is exactly whether it
1133 // is set correctly. Similarly for insertion.
1135 // To provide for these cases would require that the test functions know
1136 // in advance whether the stream buffer and/or allocations will fail, and
1137 // when; that is, we should write both a special allocator and a special
1138 // stream buffer capable of throwing "on demand" and pass them here.
1140 // Seems overkill for these kinds of unit tests.
1141 //-------------------------------------------------------------------------
1143 // operator<<( [basic_]ostream,
1144 template <typename Stream>
1145 static void stream_inserter(const Bitset & b,
1147 const char * file_name
1150 #if defined BOOST_OLD_IOSTREAMS
1151 typedef char char_type;
1152 typedef std::string string_type;
1153 typedef ifstream corresponding_input_stream_type;
1155 typedef typename Stream::char_type char_type;
1156 typedef std::basic_string<char_type> string_type;
1157 typedef std::basic_ifstream<char_type> corresponding_input_stream_type;
1159 std::ios::iostate except = s.exceptions();
1162 typedef typename Bitset::size_type size_type;
1163 std::streamsize w = s.width();
1164 char_type fill_char = s.fill();
1165 std::ios::iostate oldstate = s.rdstate();
1166 bool stream_was_good = s.good();
1168 bool did_throw = false;
1172 #if defined BOOST_OLD_IOSTREAMS
1177 catch (const std::ios_base::failure &) {
1178 BOOST_CHECK((except & s.rdstate()) != 0);
1185 BOOST_CHECK(did_throw || !stream_was_good || (s.width() == 0));
1187 if (!stream_was_good) {
1188 BOOST_CHECK(s.good() == false);
1190 // this should actually be oldstate == s.rdstate()
1191 // but some implementations add badbit in the
1192 // sentry constructor
1194 BOOST_CHECK((oldstate & s.rdstate()) == oldstate);
1195 BOOST_CHECK(s.width() == w);
1199 BOOST_CHECK(s.width() == 0);
1200 // This test require that os be an output _and_ input stream.
1201 // Of course dynamic_bitset's operator << doesn't require that.
1203 size_type total_len = w <= 0 || static_cast<size_type>(w) < b.size()? b.size() : static_cast<size_type>(w);
1204 const string_type padding (total_len - b.size(), fill_char);
1205 string_type expected;
1206 boost::to_string(b, expected);
1207 if ((s.flags() & std::ios::adjustfield) != std::ios::left)
1208 expected = padding + expected;
1210 expected = expected + padding;
1212 assert(expected.length() == total_len);
1214 // close, and reopen the file stream to verify contents
1216 corresponding_input_stream_type is(file_name);
1217 string_type contents;
1218 std::getline(is, contents, char_type());
1219 BOOST_CHECK(contents == expected);
1223 // operator>>( [basic_]istream
1224 template <typename Stream, typename String>
1225 static void stream_extractor(Bitset& b,
1230 // save necessary info then do extraction
1232 const std::streamsize w = is.width();
1234 bool stream_was_good = is.good();
1236 bool did_throw = false;
1238 #if defined BOOST_OLD_IOSTREAMS
1239 bool has_stream_exceptions = false;
1242 const std::ios::iostate except = is.exceptions();
1243 bool has_stream_exceptions = true;
1247 catch(const std::ios::failure &) {
1252 BOOST_CHECK(except == is.exceptions()); // paranoid
1254 //------------------------------------------------------------------
1257 BOOST_CHECK(b.size() <= b.max_size());
1259 BOOST_CHECK(b.size() <= static_cast<typename Bitset::size_type>(w));
1261 // throw if and only if required
1262 if(has_stream_exceptions) {
1263 const bool exceptional_state = has_flags(is, is.exceptions());
1264 BOOST_CHECK(exceptional_state == did_throw);
1267 typedef typename String::size_type size_type;
1268 typedef typename String::value_type Ch;
1269 size_type after_digits = 0;
1271 if(!stream_was_good) {
1272 BOOST_CHECK(has_flags(is, std::ios::failbit));
1273 BOOST_CHECK(b == a_copy);
1274 BOOST_CHECK(is.width() == (did_throw ? w : 0));
1277 // stream was good(), parse the string;
1278 // it may contain three parts, all of which are optional
1279 // {spaces} {digits} {non-digits}
1282 // The values of b.max_size() and is.width() may lead to
1283 // ignore part of the digits, if any.
1286 size_type len = str.length();
1288 for( ; pos < len && is_white_space(is, str[pos]); ++pos)
1290 size_type after_spaces = pos;
1291 // {digits} or part of them
1292 const typename Bitset::size_type max_digits =
1293 w > 0 && static_cast<typename Bitset::size_type>(w) < b.max_size()
1294 ? static_cast<typename Bitset::size_type>(w) : b.max_size();
1296 for( ; pos < len && (pos - after_spaces) < max_digits; ++pos) {
1297 if(!is_one_or_zero(is, str[pos]))
1301 size_type num_digits = after_digits - after_spaces;
1304 if((after_digits == len && max_digits > num_digits ))
1305 BOOST_CHECK(has_flags(is, std::ios::eofbit));
1307 BOOST_CHECK(!has_flags(is, std::ios::eofbit));
1309 // failbit <=> there are no digits, except for the library
1310 // issue explained below.
1312 if(num_digits == 0) {
1313 if(after_digits == len && has_stream_exceptions &&
1314 (is.exceptions() & std::ios::eofbit) != std::ios::goodbit) {
1315 // This is a special case related to library issue 195:
1316 // reaching eof when skipping whitespaces in the sentry ctor.
1317 // The resolution says the sentry constructor should set *both*
1318 // eofbit and failbit; but many implementations deliberately
1319 // set eofbit only. See for instance:
1320 // http://gcc.gnu.org/ml/libstdc++/2000-q1/msg00086.html
1322 BOOST_CHECK(did_throw);
1326 BOOST_CHECK(has_flags(is, std::ios::failbit));
1330 BOOST_CHECK(!has_flags(is, std::ios::failbit));
1333 if(num_digits == 0 && after_digits == len) {
1334 // The VC6 library has a bug/non-conformity in the sentry
1335 // constructor. It uses code like
1336 // // skip whitespaces...
1337 // int_type _C = rdbuf()->sgetc();
1338 // while (!_Tr::eq_int_type(_Tr::eof(), _C) ...
1340 // For an empty file the while statement is never "entered"
1341 // and the stream remains in good() state; thus the sentry
1342 // object gives "true" when converted to bool. This is worse
1343 // than the case above, because not only failbit is not set,
1344 // but no bit is set at all, end we end up clearing the
1345 // bitset though there's nothing in the file to be extracted.
1346 // Note that the dynamic_bitset docs say a sentry object is
1347 // constructed and then converted to bool, thus we rely on
1348 // what the underlying library does.
1350 #if !defined(BOOST_DINKUMWARE_STDLIB) || (BOOST_DINKUMWARE_STDLIB >= 306)
1351 BOOST_CHECK(b == a_copy);
1353 BOOST_CHECK(b.empty() == true);
1357 String sub = str.substr(after_spaces, num_digits);
1358 BOOST_CHECK(b == Bitset(sub));
1362 BOOST_CHECK(is.width() == 0
1363 || (after_digits == len && num_digits == 0 && did_throw));
1367 // clear the stream to allow further reading then
1368 // retrieve any remaining chars with a single getline()
1369 is.exceptions(std::ios::goodbit);
1372 std::getline(is, remainder, Ch());
1374 BOOST_CHECK(remainder == str.substr(after_digits));
1376 BOOST_CHECK(remainder == str);
1385 #endif // include guard