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
6 // Copyright (c) 2018 Evgeny Shulgin
8 // Distributed under the Boost Software License, Version 1.0.
9 // (See accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
12 // -----------------------------------------------------------
14 #ifndef BOOST_BITSET_TEST_HPP_GP_20040319
15 #define BOOST_BITSET_TEST_HPP_GP_20040319
17 #include <boost/config.hpp>
18 #if !defined (BOOST_NO_STD_LOCALE)
23 #include <fstream> // used for operator<<
24 #include <string> // for (basic_string and) getline()
25 #include <algorithm> // for std::min
26 #include <assert.h> // <cassert> is sometimes macro-guarded :-(
28 #include <boost/limits.hpp>
29 #include <boost/dynamic_bitset/dynamic_bitset.hpp>
30 #include <boost/core/lightweight_test.hpp>
31 #include <boost/filesystem.hpp>
33 template <typename Block>
34 inline bool nth_bit(Block num, std::size_t n)
38 // Borland deduces Block as a const qualified type,
39 // and thus finds numeric_limits<Block> to be zero :(
40 // (though not directly relevant here, see also
42 int block_width = sizeof(Block) * CHAR_BIT;
44 int block_width = std::numeric_limits<Block>::digits;
46 assert(n < (std::size_t) block_width);
49 return (num >> n) & 1;
52 // A long, 'irregular', string useful for various tests
53 std::string get_long_string()
55 const char * const p =
57 // 3210987654321098765432109876543210987654321098765432109876543210
58 "1110011100011110000011110000011111110000000000000110101110000000"
59 "1010101000011100011101010111110000101011111000001111100011100011"
60 "0000000110000001000000111100000111100010101111111000000011100011"
61 "1111111111111111111111111111111111111111111111111111111111111100"
62 "1000001100000001111111111111110000000011111000111100001010100000"
63 "101000111100011010101110011011000000010";
65 return std::string(p);
68 class scoped_temp_file
72 : m_path(boost::filesystem::unique_path())
78 boost::filesystem::remove(m_path);
81 const boost::filesystem::path& path() const
87 boost::filesystem::path m_path;
90 #if defined BOOST_OLD_IOSTREAMS || defined BOOST_NO_STD_LOCALE
91 template <typename Stream>
92 bool is_one_or_zero(const Stream & /*s*/, char c)
94 return c == '1' || c == '0';
96 template <typename Stream>
97 bool is_white_space(const Stream & /*s*/, char c)
99 return std::isspace(c);
102 template <typename Stream, typename Ch>
103 bool is_one_or_zero(const Stream& s, Ch c)
105 typedef typename Stream::traits_type Tr;
106 const Ch zero = s.widen('0');
107 const Ch one = s.widen('1');
109 return Tr::eq(c, one) || Tr::eq(c, zero);
111 template <typename Stream, typename Ch>
112 bool is_white_space(const Stream & s, Ch c)
114 // NOTE: the using directive is to satisfy Borland 5.6.4
115 // with its own library (STLport), which doesn't
116 // like std::isspace(c, loc)
118 return isspace(c, s.getloc());
120 #endif // defined BOOST_OLD_IOSTREAMS
123 template <typename Stream>
124 bool has_flags(const Stream& s, std::ios::iostate flags)
126 return (s.rdstate() & flags) != std::ios::goodbit;
131 // default (can't do this generically)
133 template <typename Bitset>
136 typedef typename Bitset::block_type Block;
137 BOOST_STATIC_CONSTANT(int, bits_per_block = Bitset::bits_per_block);
139 // from unsigned long
141 // Note: this is templatized so that we check that the do-the-right-thing
142 // constructor dispatch is working correctly.
144 template <typename NumBits, typename Value>
145 static void from_unsigned_long(NumBits num_bits, Value num)
147 // An object of size sz = num_bits is constructed:
148 // - the first m bit positions are initialized to the corresponding
149 // bit values in num (m being the smaller of sz and ulong_width)
151 // - any remaining bit positions are initialized to zero
154 Bitset b(static_cast<typename Bitset::size_type>(num_bits), static_cast<unsigned long>(num));
156 // OK, we can now cast to size_type
157 typedef typename Bitset::size_type size_type;
158 const size_type sz = static_cast<size_type>(num_bits);
160 BOOST_TEST(b.size() == sz);
162 const std::size_t ulong_width = std::numeric_limits<unsigned long>::digits;
164 if (ulong_width < sz)
169 BOOST_TEST(b.test(i) == nth_bit(static_cast<unsigned long>(num), i));
171 BOOST_TEST(b.test(i) == 0);
176 // Note: The corresponding function in dynamic_bitset (constructor
177 // from a string) has several default arguments. Actually we don't
178 // test the correct working of those defaults here (except for the
179 // default of num_bits). I'm not sure what to do in this regard.
181 // Note2: the default argument expression for num_bits doesn't use
182 // static_cast, to avoid a gcc 2.95.3 'sorry, not implemented'
184 template <typename Ch, typename Tr, typename Al>
185 static void from_string(const std::basic_string<Ch, Tr, Al>& str,
187 std::size_t max_char,
188 std::size_t num_bits = (std::size_t)(-1))
191 std::size_t rlen = (std::min)(max_char, str.size() - pos);
193 // The resulting size N of the bitset is num_bits, if
194 // that is different from the default arg, rlen otherwise.
195 // Put M = the smaller of N and rlen, then character
196 // position pos + M - 1 corresponds to bit position zero.
197 // Subsequent decreasing character positions correspond to
198 // increasing bit positions.
200 const bool size_upon_string = num_bits == (std::size_t)(-1);
201 Bitset b = size_upon_string ?
202 Bitset(str, pos, max_char)
203 : Bitset(str, pos, max_char, num_bits);
205 const std::size_t actual_size = size_upon_string? rlen : num_bits;
206 BOOST_TEST(b.size() == actual_size);
207 std::size_t m = (std::min)(num_bits, rlen);
209 for (j = 0; j < m; ++j)
210 BOOST_TEST(b[j] == (str[pos + m - 1 - j] == '1'));
211 // If M < N, remaining bit positions are zero
212 for (; j < actual_size; ++j)
213 BOOST_TEST(b[j] == 0);
218 static void to_block_range(const Bitset & b /*, BlockOutputIterator result*/)
220 typedef typename Bitset::size_type size_type;
222 Block sentinel = 0xF0;
223 int s = 8; // number of sentinels (must be *even*)
225 std::vector<Block> v(b.num_blocks() + s, sentinel);
227 boost::to_block_range(b, v.begin() + offset);
229 assert(v.size() >= (size_type)s && (s >= 2) && (s % 2 == 0));
230 // check sentinels at both ends
231 for(int i = 0; i < s/2; ++i) {
232 BOOST_TEST(v[i] == sentinel);
233 BOOST_TEST(v[v.size()-1-i] == sentinel);
236 typename std::vector<Block>::const_iterator p = v.begin() + offset;
237 for(size_type n = 0; n < b.num_blocks(); ++n, ++p) {
238 typename Bitset::block_width_type i = 0;
239 for(; i < bits_per_block; ++i) {
240 size_type bit = n * bits_per_block + i;
241 BOOST_TEST(nth_bit(*p, i) == (bit < b.size()? b[bit] : 0));
246 // TODO from_block_range (below) should be splitted
248 // PRE: std::equal(first1, last1, first2) == true
249 static void from_block_range(const std::vector<Block>& blocks)
251 { // test constructor from block range
252 Bitset bset(blocks.begin(), blocks.end());
253 std::size_t n = blocks.size();
254 for (std::size_t b = 0; b < n; ++b) {
255 typename Bitset::block_width_type i = 0;
256 for (; i < bits_per_block; ++i) {
257 std::size_t bit = b * bits_per_block + i;
258 BOOST_TEST(bset[bit] == nth_bit(blocks[b], i));
261 BOOST_TEST(bset.size() == n * bits_per_block);
263 { // test boost::from_block_range
264 const typename Bitset::size_type n = blocks.size();
265 Bitset bset(n * bits_per_block);
266 boost::from_block_range(blocks.begin(), blocks.end(), bset);
267 for (std::size_t b = 0; b < n; ++b) {
268 typename Bitset::block_width_type i = 0;
269 for (; i < bits_per_block; ++i) {
270 std::size_t bit = b * bits_per_block + i;
271 BOOST_TEST(bset[bit] == nth_bit(blocks[b], i));
274 BOOST_TEST(n <= bset.num_blocks());
278 // copy constructor (absent from std::bitset)
279 static void copy_constructor(const Bitset& b)
282 BOOST_TEST(b == copy);
284 // Changes to the copy do not affect the original
286 std::size_t pos = copy.size() / 2;
288 BOOST_TEST(copy[pos] != b[pos]);
292 // copy assignment operator (absent from std::bitset)
293 static void copy_assignment_operator(const Bitset& lhs, const Bitset& rhs)
297 b = b; // self assignment check
298 BOOST_TEST(b == rhs);
300 // Changes to the copy do not affect the original
302 std::size_t pos = b.size() / 2;
304 BOOST_TEST(b[pos] != rhs[pos]);
308 static void max_size(const Bitset& b)
310 BOOST_TEST(b.max_size() > 0);
313 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
315 // move constructor (absent from std::bitset)
316 static void move_constructor(const Bitset& b)
318 Bitset copy(boost::move(b));
319 BOOST_TEST(b == copy);
322 // move assignment operator (absent from std::bitset)
323 static void move_assignment_operator(const Bitset& lhs, const Bitset& rhs)
328 b = boost::move(b); // self assignment check
329 BOOST_TEST(b == rhs);
332 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
334 static void swap(const Bitset& lhs, const Bitset& rhs)
336 // bitsets must be swapped
341 BOOST_TEST(copy1 == rhs);
342 BOOST_TEST(copy2 == lhs);
344 // references must be stable under a swap
345 for(typename Bitset::size_type i = 0; i < lhs.size(); ++i) {
348 typename Bitset::reference ref = b1[i];
351 b2[i] = !x; // make sure b2[i] is different
353 BOOST_TEST(b2[i] == x); // now it must be equal..
355 BOOST_TEST(ref == b2[i]); // .. and ref must be into b2
356 BOOST_TEST(ref == !x);
361 static void resize(const Bitset& lhs)
365 // Test no change in size
366 b.resize(lhs.size());
367 BOOST_TEST(b == lhs);
369 // Test increase in size
370 b.resize(lhs.size() * 2, true);
373 for (i = 0; i < lhs.size(); ++i)
374 BOOST_TEST(b[i] == lhs[i]);
375 for (; i < b.size(); ++i)
376 BOOST_TEST(b[i] == true);
378 // Test decrease in size
379 b.resize(lhs.size());
380 for (i = 0; i < lhs.size(); ++i)
381 BOOST_TEST(b[i] == lhs[i]);
384 static void clear(const Bitset& lhs)
388 BOOST_TEST(b.size() == 0);
391 static void pop_back(const Bitset& lhs)
395 BOOST_TEST(b.size() == lhs.size() - 1);
396 for (std::size_t i = 0; i < b.size(); ++i)
397 BOOST_TEST(b[i] == lhs[i]);
400 BOOST_TEST(b.size() == lhs.size() - 2);
401 for (std::size_t j = 0; j < b.size(); ++j)
402 BOOST_TEST(b[j] == lhs[j]);
405 static void append_bit(const Bitset& lhs)
409 BOOST_TEST(b.size() == lhs.size() + 1);
410 BOOST_TEST(b[b.size() - 1] == true);
411 for (std::size_t i = 0; i < lhs.size(); ++i)
412 BOOST_TEST(b[i] == lhs[i]);
415 BOOST_TEST(b.size() == lhs.size() + 2);
416 BOOST_TEST(b[b.size() - 1] == false);
417 BOOST_TEST(b[b.size() - 2] == true);
418 for (std::size_t j = 0; j < lhs.size(); ++j)
419 BOOST_TEST(b[j] == lhs[j]);
422 static void append_block(const Bitset& lhs)
427 BOOST_TEST(b.size() == lhs.size() + bits_per_block);
428 for (typename Bitset::block_width_type i = 0; i < bits_per_block; ++i)
429 BOOST_TEST(b[lhs.size() + i] == bool((value >> i) & 1));
432 static void append_block_range(const Bitset& lhs, const std::vector<Block>& blocks)
434 Bitset b(lhs), c(lhs);
435 b.append(blocks.begin(), blocks.end());
436 for (typename std::vector<Block>::const_iterator i = blocks.begin();
437 i != blocks.end(); ++i)
442 // operator[] and reference members
443 // PRE: b[i] == bit_vec[i]
444 static void operator_bracket(const Bitset& lhs, const std::vector<bool>& bit_vec)
451 for (i = 0; i < b.size(); ++i) {
453 BOOST_TEST(x == bit_vec[i]);
455 BOOST_TEST(x == !bit_vec[i]);
460 for (j = 0; j < b.size(); ++j) {
463 for (k = 0; k < b.size(); ++k)
465 BOOST_TEST(b[k] == x);
467 BOOST_TEST(b[k] == prev[k]);
473 for (i = 0; i < b.size(); ++i) {
475 for (j = 0; j < b.size(); ++j) {
477 BOOST_TEST(b[j] == prev[j]);
479 BOOST_TEST(b[j] == !prev[j]);
485 for (i = 0; i < b.size(); ++i) {
487 for (j = 0; j < b.size(); ++j) {
489 BOOST_TEST(b[j] == prev[j]);
491 BOOST_TEST(b[j] == !prev[j]);
497 //===========================================================================
500 // bitwise and assignment
502 // PRE: b.size() == rhs.size()
503 static void and_assignment(const Bitset& b, const Bitset& rhs)
508 // Clears each bit in lhs for which the corresponding bit in rhs is
509 // clear, and leaves all other bits unchanged.
510 for (std::size_t I = 0; I < lhs.size(); ++I)
512 BOOST_TEST(lhs[I] == 0);
514 BOOST_TEST(lhs[I] == prev[I]);
517 // PRE: b.size() == rhs.size()
518 static void or_assignment(const Bitset& b, const Bitset& rhs)
523 // Sets each bit in lhs for which the corresponding bit in rhs is set, and
524 // leaves all other bits unchanged.
525 for (std::size_t I = 0; I < lhs.size(); ++I)
527 BOOST_TEST(lhs[I] == 1);
529 BOOST_TEST(lhs[I] == prev[I]);
532 // PRE: b.size() == rhs.size()
533 static void xor_assignment(const Bitset& b, const Bitset& rhs)
538 // Flips each bit in lhs for which the corresponding bit in rhs is set,
539 // and leaves all other bits unchanged.
540 for (std::size_t I = 0; I < lhs.size(); ++I)
542 BOOST_TEST(lhs[I] == !prev[I]);
544 BOOST_TEST(lhs[I] == prev[I]);
547 // PRE: b.size() == rhs.size()
548 static void sub_assignment(const Bitset& b, const Bitset& rhs)
553 // Resets each bit in lhs for which the corresponding bit in rhs is set,
554 // and leaves all other bits unchanged.
555 for (std::size_t I = 0; I < lhs.size(); ++I)
557 BOOST_TEST(lhs[I] == 0);
559 BOOST_TEST(lhs[I] == prev[I]);
562 static void shift_left_assignment(const Bitset& b, std::size_t pos)
567 // Replaces each bit at position I in lhs with the following value:
568 // - If I < pos, the new value is zero
569 // - If I >= pos, the new value is the previous value of the bit at
571 for (std::size_t I = 0; I < lhs.size(); ++I)
573 BOOST_TEST(lhs[I] == 0);
575 BOOST_TEST(lhs[I] == prev[I - pos]);
578 static void shift_right_assignment(const Bitset& b, std::size_t pos)
583 // Replaces each bit at position I in lhs with the following value:
584 // - If pos >= N - I, the new value is zero
585 // - If pos < N - I, the new value is the previous value of the bit at
587 std::size_t N = lhs.size();
588 for (std::size_t I = 0; I < N; ++I)
590 BOOST_TEST(lhs[I] == 0);
592 BOOST_TEST(lhs[I] == prev[I + pos]);
596 static void set_all(const Bitset& b)
600 for (std::size_t I = 0; I < lhs.size(); ++I)
601 BOOST_TEST(lhs[I] == 1);
604 static void set_one(const Bitset& b, std::size_t pos, bool value)
607 std::size_t N = lhs.size();
610 // Stores a new value in the bit at position pos in lhs.
612 BOOST_TEST(lhs[pos] == value);
614 // All other values of lhs remain unchanged
615 for (std::size_t I = 0; I < N; ++I)
617 BOOST_TEST(lhs[I] == prev[I]);
619 // Not in range, doesn't satisfy precondition.
623 static void set_segment(const Bitset& b, std::size_t pos,
624 std::size_t len, bool value)
627 std::size_t N = lhs.size();
629 lhs.set(pos, len, value);
630 for (std::size_t I = 0; I < N; ++I)
632 if (I < pos || I >= pos + len)
633 BOOST_TEST(lhs[I] == prev[I]);
635 BOOST_TEST(lhs[I] == value);
639 static void reset_all(const Bitset& b)
642 // Resets all bits in lhs
644 for (std::size_t I = 0; I < lhs.size(); ++I)
645 BOOST_TEST(lhs[I] == 0);
648 static void reset_one(const Bitset& b, std::size_t pos)
651 std::size_t N = lhs.size();
655 // Resets the bit at position pos in lhs
656 BOOST_TEST(lhs[pos] == 0);
658 // All other values of lhs remain unchanged
659 for (std::size_t I = 0; I < N; ++I)
661 BOOST_TEST(lhs[I] == prev[I]);
663 // Not in range, doesn't satisfy precondition.
667 static void reset_segment(const Bitset& b, std::size_t pos,
671 std::size_t N = lhs.size();
674 for (std::size_t I = 0; I < N; ++I)
676 if (I < pos || I >= pos + len)
677 BOOST_TEST(lhs[I] == prev[I]);
683 static void operator_flip(const Bitset& b)
687 BOOST_TEST(~lhs == x.flip());
690 static void flip_all(const Bitset& b)
693 std::size_t N = lhs.size();
696 // Toggles all the bits in lhs
697 for (std::size_t I = 0; I < N; ++I)
698 BOOST_TEST(lhs[I] == !prev[I]);
701 static void flip_one(const Bitset& b, std::size_t pos)
704 std::size_t N = lhs.size();
708 // Toggles the bit at position pos in lhs
709 BOOST_TEST(lhs[pos] == !prev[pos]);
711 // All other values of lhs remain unchanged
712 for (std::size_t I = 0; I < N; ++I)
714 BOOST_TEST(lhs[I] == prev[I]);
716 // Not in range, doesn't satisfy precondition.
720 static void flip_segment(const Bitset& b, std::size_t pos,
724 std::size_t N = lhs.size();
727 for (std::size_t I = 0; I < N; ++I)
729 if (I < pos || I >= pos + len)
730 BOOST_TEST(lhs[I] == prev[I]);
732 BOOST_TEST(lhs[I] != prev[I]);
737 static void empty(const Bitset& b)
739 BOOST_TEST(b.empty() == (b.size() == 0));
743 static void to_ulong(const Bitset& lhs)
745 typedef unsigned long result_type;
746 std::size_t n = std::numeric_limits<result_type>::digits;
747 std::size_t sz = lhs.size();
749 bool will_overflow = false;
750 for (std::size_t i = n; i < sz; ++i) {
751 if (lhs.test(i) != 0) {
752 will_overflow = true;
758 (void)lhs.to_ulong();
759 BOOST_TEST(false); // It should have thrown an exception
760 } catch (std::overflow_error & ex) {
762 BOOST_TEST(!!ex.what());
764 BOOST_TEST(false); // threw the wrong exception
767 result_type num = lhs.to_ulong();
768 // Be sure the number is right
770 BOOST_TEST(num == 0);
772 for (std::size_t i = 0; i < sz; ++i)
773 BOOST_TEST(lhs[i] == (i < n ? nth_bit(num, i) : 0));
779 static void to_string(const Bitset& b)
782 boost::to_string(b, str);
783 BOOST_TEST(str.size() == b.size());
784 for (std::size_t i = 0; i < b.size(); ++i)
785 BOOST_TEST(str[b.size() - 1 - i] ==(b.test(i)? '1':'0'));
788 static void count(const Bitset& b)
790 std::size_t c = b.count();
791 std::size_t actual = 0;
792 for (std::size_t i = 0; i < b.size(); ++i)
795 BOOST_TEST(c == actual);
798 static void size(const Bitset& b)
800 BOOST_TEST(Bitset(b).set().count() == b.size());
803 static void capacity_test_one(const Bitset& lhs)
807 BOOST_TEST(b.capacity() == 0);
810 static void capacity_test_two(const Bitset& lhs)
812 //bitset constructed with size "100"
814 BOOST_TEST(b.capacity() >= 100);
816 BOOST_TEST(b.capacity() >= 200);
819 static void reserve_test_one(const Bitset& lhs)
824 BOOST_TEST(b.capacity() >= 16);
827 static void reserve_test_two(const Bitset& lhs)
829 //bitset constructed with size "100"
831 BOOST_TEST(b.capacity() >= 100);
833 BOOST_TEST(b.size() == 100);
834 BOOST_TEST(b.capacity() >= 100);
836 BOOST_TEST(b.size() == 100);
837 BOOST_TEST(b.capacity() >= 160);
840 static void shrink_to_fit_test_one(const Bitset& lhs)
845 BOOST_TEST(b.size() == 0);
846 BOOST_TEST(b.capacity() == 0);
849 static void shrink_to_fit_test_two(const Bitset& lhs)
851 //bitset constructed with size "100"
854 BOOST_TEST(b.capacity() >= 100);
855 BOOST_TEST(b.size() == 100);
857 BOOST_TEST(b.capacity() >= 200);
858 BOOST_TEST(b.size() == 100);
860 BOOST_TEST(b.capacity() < 200);
861 BOOST_TEST(b.size() == 100);
864 static void all(const Bitset& b)
866 BOOST_TEST(b.all() == (b.count() == b.size()));
868 for(std::size_t i = 0; i < b.size(); ++i)
873 BOOST_TEST(b.all() == result);
876 static void any(const Bitset& b)
878 BOOST_TEST(b.any() == (b.count() != 0));
880 for(std::size_t i = 0; i < b.size(); ++i)
885 BOOST_TEST(b.any() == result);
888 static void none(const Bitset& b)
891 for(std::size_t i = 0; i < b.size(); ++i) {
897 BOOST_TEST(b.none() == result);
900 BOOST_TEST(b.none() == !b.any());
901 BOOST_TEST(b.none() == (b.count() == 0));
904 static void subset(const Bitset& a, const Bitset& b)
906 BOOST_TEST(a.size() == b.size()); // PRE
908 bool is_subset = true;
909 if (b.size()) { // could use b.any() but let's be safe
910 for(std::size_t i = 0; i < a.size(); ++i) {
911 if(a.test(i) && !b.test(i)) {
919 BOOST_TEST(a.count() == 0);
920 BOOST_TEST(a.any() == false);
922 //is_subset = (a.any() == false);
925 BOOST_TEST(a.is_subset_of(b) == is_subset);
928 static void proper_subset(const Bitset& a, const Bitset& b)
930 // PRE: a.size() == b.size()
931 BOOST_TEST(a.size() == b.size());
933 bool is_proper = false;
937 // check it's a subset
941 for (std::size_t i = 0; i < a.size(); ++i) {
942 if (!a.test(i) && b.test(i)) {
945 BOOST_TEST(a.count() < b.count());
951 BOOST_TEST(a.is_proper_subset_of(b) == is_proper);
953 BOOST_TEST(b.is_proper_subset_of(a) != is_proper);// antisymmetry
956 static void intersects(const Bitset& a, const Bitset& b)
958 bool have_intersection = false;
960 typename Bitset::size_type m = a.size() < b.size() ? a.size() : b.size();
961 for(typename Bitset::size_type i = 0; i < m && !have_intersection; ++i)
962 if(a[i] == true && b[i] == true)
963 have_intersection = true;
965 BOOST_TEST(a.intersects(b) == have_intersection);
966 // also check commutativity
967 BOOST_TEST(b.intersects(a) == have_intersection);
970 static void find_first(const Bitset& b)
972 // find first non-null bit, if any
973 typename Bitset::size_type i = 0;
974 while (i < b.size() && b[i] == 0)
978 BOOST_TEST(b.find_first() == Bitset::npos); // not found;
980 BOOST_TEST(b.find_first() == i);
981 BOOST_TEST(b.test(i) == true);
986 static void find_next(const Bitset& b, typename Bitset::size_type prev)
988 BOOST_TEST(next_bit_on(b, prev) == b.find_next(prev));
991 static void operator_equal(const Bitset& a, const Bitset& b)
994 for (std::size_t I = 0; I < a.size(); ++I)
995 BOOST_TEST(a[I] == b[I]);
997 if (a.size() == b.size()) {
999 for (std::size_t I = 0; I < a.size(); ++I)
1009 static void operator_not_equal(const Bitset& a, const Bitset& b)
1012 if (a.size() == b.size()) {
1014 for (std::size_t I = 0; I < a.size(); ++I)
1022 for (std::size_t I = 0; I < a.size(); ++I)
1023 BOOST_TEST(a[I] == b[I]);
1027 static bool less_than(const Bitset& a, const Bitset& b)
1030 typedef BOOST_DEDUCED_TYPENAME Bitset::size_type size_type;
1032 size_type asize(a.size());
1033 size_type bsize(b.size());
1046 // Compare from most significant to least.
1048 size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize));
1050 for (I = 0; I < leqsize; ++I,--asize,--bsize)
1053 size_type i = asize-1;
1054 size_type j = bsize-1;
1058 else if (a[i] > b[j])
1060 // if (a[i] = b[j]) skip to next
1062 return (a.size() < b.size());
1066 static typename Bitset::size_type next_bit_on(const Bitset& b, typename Bitset::size_type prev)
1068 // helper function for find_next()
1071 if (b.none() == true || prev == Bitset::npos)
1072 return Bitset::npos;
1076 if (prev >= b.size())
1077 return Bitset::npos;
1079 typename Bitset::size_type i = prev;
1080 while (i < b.size() && b[i] == 0)
1083 return i==b.size() ? Bitset::npos : i;
1087 static void operator_less_than(const Bitset& a, const Bitset& b)
1089 if (less_than(a, b))
1092 BOOST_TEST(!(a < b));
1095 static void operator_greater_than(const Bitset& a, const Bitset& b)
1097 if (less_than(a, b) || a == b)
1098 BOOST_TEST(!(a > b));
1103 static void operator_less_than_eq(const Bitset& a, const Bitset& b)
1105 if (less_than(a, b) || a == b)
1108 BOOST_TEST(!(a <= b));
1111 static void operator_greater_than_eq(const Bitset& a, const Bitset& b)
1113 if (less_than(a, b))
1114 BOOST_TEST(!(a >= b));
1119 static void test_bit(const Bitset& b, std::size_t pos)
1122 std::size_t N = lhs.size();
1124 BOOST_TEST(lhs.test(pos) == lhs[pos]);
1126 // Not in range, doesn't satisfy precondition.
1130 static void test_set_bit(const Bitset& b, std::size_t pos, bool value)
1133 std::size_t N = lhs.size();
1136 // Stores a new value in the bit at position pos in lhs.
1137 BOOST_TEST(lhs.test_set(pos, value) == prev[pos]);
1138 BOOST_TEST(lhs[pos] == value);
1140 // All other values of lhs remain unchanged
1141 for (std::size_t I = 0; I < N; ++I)
1143 BOOST_TEST(lhs[I] == prev[I]);
1145 // Not in range, doesn't satisfy precondition.
1149 static void operator_shift_left(const Bitset& lhs, std::size_t pos)
1152 BOOST_TEST((lhs << pos) == (x <<= pos));
1155 static void operator_shift_right(const Bitset& lhs, std::size_t pos)
1158 BOOST_TEST((lhs >> pos) == (x >>= pos));
1163 void operator_or(const Bitset& lhs, const Bitset& rhs)
1166 BOOST_TEST((lhs | rhs) == (x |= rhs));
1171 void operator_and(const Bitset& lhs, const Bitset& rhs)
1174 BOOST_TEST((lhs & rhs) == (x &= rhs));
1179 void operator_xor(const Bitset& lhs, const Bitset& rhs)
1182 BOOST_TEST((lhs ^ rhs) == (x ^= rhs));
1187 void operator_sub(const Bitset& lhs, const Bitset& rhs)
1190 BOOST_TEST((lhs - rhs) == (x -= rhs));
1193 //------------------------------------------------------------------------------
1195 // The following tests assume the results of extraction (i.e.: contents,
1196 // state and width of is, contents of b) only depend on input (the string
1197 // str). In other words, they don't consider "unexpected" errors such as
1198 // stream corruption or out of memory. The reason is simple: if e.g. the
1199 // stream buffer throws, the stream layer may eat the exception and
1200 // transform it into a badbit. But we can't trust the stream state here,
1201 // because one of the things that we want to test is exactly whether it
1202 // is set correctly. Similarly for insertion.
1204 // To provide for these cases would require that the test functions know
1205 // in advance whether the stream buffer and/or allocations will fail, and
1206 // when; that is, we should write both a special allocator and a special
1207 // stream buffer capable of throwing "on demand" and pass them here.
1209 // Seems overkill for these kinds of unit tests.
1210 //-------------------------------------------------------------------------
1212 // operator<<( [basic_]ostream,
1213 template <typename Stream>
1214 static void stream_inserter(const Bitset & b,
1216 const char * file_name
1219 #if defined BOOST_OLD_IOSTREAMS
1220 typedef char char_type;
1221 typedef std::string string_type;
1222 typedef ifstream corresponding_input_stream_type;
1224 typedef typename Stream::char_type char_type;
1225 typedef std::basic_string<char_type> string_type;
1226 typedef std::basic_ifstream<char_type> corresponding_input_stream_type;
1228 std::ios::iostate except = s.exceptions();
1231 typedef typename Bitset::size_type size_type;
1232 std::streamsize w = s.width();
1233 char_type fill_char = s.fill();
1234 std::ios::iostate oldstate = s.rdstate();
1235 bool stream_was_good = s.good();
1237 bool did_throw = false;
1241 #if defined BOOST_OLD_IOSTREAMS
1246 catch (const std::ios_base::failure &) {
1247 BOOST_TEST((except & s.rdstate()) != 0);
1254 BOOST_TEST(did_throw || !stream_was_good || (s.width() == 0));
1256 if (!stream_was_good) {
1257 BOOST_TEST(s.good() == false);
1259 // this should actually be oldstate == s.rdstate()
1260 // but some implementations add badbit in the
1261 // sentry constructor
1263 BOOST_TEST((oldstate & s.rdstate()) == oldstate);
1264 BOOST_TEST(s.width() == w);
1268 BOOST_TEST(s.width() == 0);
1269 // This test require that os be an output _and_ input stream.
1270 // Of course dynamic_bitset's operator << doesn't require that.
1272 size_type total_len = w <= 0 || static_cast<size_type>(w) < b.size()? b.size() : static_cast<size_type>(w);
1273 const string_type padding (total_len - b.size(), fill_char);
1274 string_type expected;
1275 boost::to_string(b, expected);
1276 if ((s.flags() & std::ios::adjustfield) != std::ios::left)
1277 expected = padding + expected;
1279 expected = expected + padding;
1281 assert(expected.length() == total_len);
1283 // close, and reopen the file stream to verify contents
1285 corresponding_input_stream_type is(file_name);
1286 string_type contents;
1287 std::getline(is, contents, char_type());
1288 BOOST_TEST(contents == expected);
1292 // operator>>( [basic_]istream
1293 template <typename Stream, typename String>
1294 static void stream_extractor(Bitset& b,
1299 // save necessary info then do extraction
1301 const std::streamsize w = is.width();
1303 bool stream_was_good = is.good();
1305 bool did_throw = false;
1307 #if defined BOOST_OLD_IOSTREAMS
1308 bool has_stream_exceptions = false;
1311 const std::ios::iostate except = is.exceptions();
1312 bool has_stream_exceptions = true;
1316 catch(const std::ios::failure &) {
1321 BOOST_TEST(except == is.exceptions()); // paranoid
1323 //------------------------------------------------------------------
1326 BOOST_TEST(b.size() <= b.max_size());
1328 BOOST_TEST(b.size() <= static_cast<typename Bitset::size_type>(w));
1330 // throw if and only if required
1331 if(has_stream_exceptions) {
1332 const bool exceptional_state = has_flags(is, is.exceptions());
1333 BOOST_TEST(exceptional_state == did_throw);
1336 typedef typename String::size_type size_type;
1337 typedef typename String::value_type Ch;
1338 size_type after_digits = 0;
1340 if(!stream_was_good) {
1341 BOOST_TEST(has_flags(is, std::ios::failbit));
1342 BOOST_TEST(b == a_copy);
1343 BOOST_TEST(is.width() == (did_throw ? w : 0));
1346 // stream was good(), parse the string;
1347 // it may contain three parts, all of which are optional
1348 // {spaces} {digits} {non-digits}
1351 // The values of b.max_size() and is.width() may lead to
1352 // ignore part of the digits, if any.
1355 size_type len = str.length();
1357 for( ; pos < len && is_white_space(is, str[pos]); ++pos)
1359 size_type after_spaces = pos;
1360 // {digits} or part of them
1361 const typename Bitset::size_type max_digits =
1362 w > 0 && static_cast<typename Bitset::size_type>(w) < b.max_size()
1363 ? static_cast<typename Bitset::size_type>(w) : b.max_size();
1365 for( ; pos < len && (pos - after_spaces) < max_digits; ++pos) {
1366 if(!is_one_or_zero(is, str[pos]))
1370 size_type num_digits = after_digits - after_spaces;
1373 if((after_digits == len && max_digits > num_digits ))
1374 BOOST_TEST(has_flags(is, std::ios::eofbit));
1376 BOOST_TEST(!has_flags(is, std::ios::eofbit));
1378 // failbit <=> there are no digits, except for the library
1379 // issue explained below.
1381 if(num_digits == 0) {
1382 if(after_digits == len && has_stream_exceptions &&
1383 (is.exceptions() & std::ios::eofbit) != std::ios::goodbit) {
1384 // This is a special case related to library issue 195:
1385 // reaching eof when skipping whitespaces in the sentry ctor.
1386 // The resolution says the sentry constructor should set *both*
1387 // eofbit and failbit; but many implementations deliberately
1388 // set eofbit only. See for instance:
1389 // http://gcc.gnu.org/ml/libstdc++/2000-q1/msg00086.html
1391 BOOST_TEST(did_throw);
1395 BOOST_TEST(has_flags(is, std::ios::failbit));
1399 BOOST_TEST(!has_flags(is, std::ios::failbit));
1402 if(num_digits == 0 && after_digits == len) {
1403 // The VC6 library has a bug/non-conformity in the sentry
1404 // constructor. It uses code like
1405 // // skip whitespaces...
1406 // int_type _C = rdbuf()->sgetc();
1407 // while (!_Tr::eq_int_type(_Tr::eof(), _C) ...
1409 // For an empty file the while statement is never "entered"
1410 // and the stream remains in good() state; thus the sentry
1411 // object gives "true" when converted to bool. This is worse
1412 // than the case above, because not only failbit is not set,
1413 // but no bit is set at all, end we end up clearing the
1414 // bitset though there's nothing in the file to be extracted.
1415 // Note that the dynamic_bitset docs say a sentry object is
1416 // constructed and then converted to bool, thus we rely on
1417 // what the underlying library does.
1419 #if !defined(BOOST_DINKUMWARE_STDLIB) || (BOOST_DINKUMWARE_STDLIB >= 306)
1420 BOOST_TEST(b == a_copy);
1422 BOOST_TEST(b.empty() == true);
1426 String sub = str.substr(after_spaces, num_digits);
1427 BOOST_TEST(b == Bitset(sub));
1431 BOOST_TEST(is.width() == 0
1432 || (after_digits == len && num_digits == 0 && did_throw));
1436 // clear the stream to allow further reading then
1437 // retrieve any remaining chars with a single getline()
1438 is.exceptions(std::ios::goodbit);
1441 std::getline(is, remainder, Ch());
1443 BOOST_TEST(remainder == str.substr(after_digits));
1445 BOOST_TEST(remainder == str);
1454 #endif // include guard