| // ----------------------------------------------------------- |
| // Copyright (c) 2001 Jeremy Siek |
| // Copyright (c) 2003-2006, 2008 Gennaro Prota |
| // |
| // Distributed under the Boost Software License, Version 1.0. |
| // (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // ----------------------------------------------------------- |
| |
| #ifndef BOOST_BITSET_TEST_HPP_GP_20040319 |
| #define BOOST_BITSET_TEST_HPP_GP_20040319 |
| |
| #include "boost/config.hpp" |
| #if !defined (BOOST_NO_STD_LOCALE) |
| # include <locale> |
| #endif |
| |
| #include <vector> |
| #include <fstream> // used for operator<< |
| #include <string> // for (basic_string and) getline() |
| #include <algorithm> // for std::min |
| #include <assert.h> // <cassert> is sometimes macro-guarded :-( |
| |
| #include "boost/limits.hpp" |
| #include "boost/dynamic_bitset/dynamic_bitset.hpp" |
| #include "boost/test/minimal.hpp" |
| |
| |
| template <typename Block> |
| inline bool nth_bit(Block num, std::size_t n) |
| { |
| #ifdef __BORLANDC__ |
| // Borland deduces Block as a const qualified type, |
| // and thus finds numeric_limits<Block> to be zero :( |
| // (though not directly relevant here, see also |
| // lib issue 559) |
| int block_width = sizeof(Block) * CHAR_BIT; |
| #else |
| int block_width = std::numeric_limits<Block>::digits; |
| #endif |
| |
| assert(n < (std::size_t) block_width); |
| return (num >> n) & 1; |
| } |
| |
| // A long, 'irregular', string useful for various tests |
| std::string get_long_string() |
| { |
| const char * const p = |
| // 6 5 4 3 2 1 |
| // 3210987654321098765432109876543210987654321098765432109876543210 |
| "1110011100011110000011110000011111110000000000000110101110000000" |
| "1010101000011100011101010111110000101011111000001111100011100011" |
| "0000000110000001000000111100000111100010101111111000000011100011" |
| "1111111111111111111111111111111111111111111111111111111111111100" |
| "1000001100000001111111111111110000000011111000111100001010100000" |
| "101000111100011010101110011011000000010"; |
| |
| return std::string(p); |
| } |
| |
| const char * test_file_name() |
| { |
| return "boost_dynamic_bitset_tests"; |
| } |
| |
| #if defined BOOST_OLD_IOSTREAMS || defined BOOST_NO_STD_LOCALE |
| template <typename Stream> |
| bool is_one_or_zero(const Stream & /*s*/, char c) |
| { |
| return c == '1' || c == '0'; |
| } |
| template <typename Stream> |
| bool is_white_space(const Stream & /*s*/, char c) |
| { |
| return std::isspace(c); |
| } |
| #else |
| template <typename Stream, typename Ch> |
| bool is_one_or_zero(const Stream& s, Ch c) |
| { |
| typedef typename Stream::traits_type Tr; |
| const Ch zero = s.widen('0'); |
| const Ch one = s.widen('1'); |
| |
| return Tr::eq(c, one) || Tr::eq(c, zero); |
| } |
| template <typename Stream, typename Ch> |
| bool is_white_space(const Stream & s, Ch c) |
| { |
| // NOTE: the using directive is to satisfy Borland 5.6.4 |
| // with its own library (STLport), which doesn't |
| // like std::isspace(c, loc) |
| using namespace std; |
| return isspace(c, s.getloc()); |
| } |
| #endif // defined BOOST_OLD_IOSTREAMS |
| |
| |
| template <typename Stream> |
| bool has_flags(const Stream& s, std::ios::iostate flags) |
| { |
| return (s.rdstate() & flags) != std::ios::goodbit; |
| } |
| |
| |
| // constructors |
| // default (can't do this generically) |
| |
| template <typename Bitset> |
| struct bitset_test { |
| |
| typedef typename Bitset::block_type Block; |
| BOOST_STATIC_CONSTANT(int, bits_per_block = Bitset::bits_per_block); |
| |
| // from unsigned long |
| // |
| // Note: this is templatized so that we check that the do-the-right-thing |
| // constructor dispatch is working correctly. |
| // |
| template <typename NumBits, typename Value> |
| static void from_unsigned_long(NumBits num_bits, Value num) |
| { |
| // An object of size sz = num_bits is constructed: |
| // - the first m bit positions are initialized to the corresponding |
| // bit values in num (m being the smaller of sz and ulong_width) |
| // |
| // - any remaining bit positions are initialized to zero |
| // |
| |
| Bitset b(num_bits, num); |
| |
| // OK, we can now cast to size_type |
| typedef typename Bitset::size_type size_type; |
| const size_type sz = static_cast<size_type>(num_bits); |
| |
| BOOST_CHECK(b.size() == sz); |
| |
| const std::size_t ulong_width = std::numeric_limits<unsigned long>::digits; |
| size_type m = sz; |
| if (ulong_width < sz) |
| m = ulong_width; |
| |
| size_type i = 0; |
| for ( ; i < m; ++i) |
| BOOST_CHECK(b.test(i) == nth_bit(static_cast<unsigned long>(num), i)); |
| for ( ; i < sz; ++i) |
| BOOST_CHECK(b.test(i) == 0); |
| } |
| |
| // from string |
| // |
| // Note: The corresponding function in dynamic_bitset (constructor |
| // from a string) has several default arguments. Actually we don't |
| // test the correct working of those defaults here (except for the |
| // default of num_bits). I'm not sure what to do in this regard. |
| // |
| // Note2: the default argument expression for num_bits doesn't use |
| // static_cast, to avoid a gcc 2.95.3 'sorry, not implemented' |
| // |
| template <typename Ch, typename Tr, typename Al> |
| static void from_string(const std::basic_string<Ch, Tr, Al>& str, |
| std::size_t pos, |
| std::size_t max_char, |
| std::size_t num_bits = (std::size_t)(-1)) |
| { |
| |
| std::size_t rlen = (std::min)(max_char, str.size() - pos); |
| |
| // The resulting size N of the bitset is num_bits, if |
| // that is different from the default arg, rlen otherwise. |
| // Put M = the smaller of N and rlen, then character |
| // position pos + M - 1 corresponds to bit position zero. |
| // Subsequent decreasing character positions correspond to |
| // increasing bit positions. |
| |
| const bool size_upon_string = num_bits == (std::size_t)(-1); |
| Bitset b = size_upon_string ? |
| Bitset(str, pos, max_char) |
| : Bitset(str, pos, max_char, num_bits); |
| |
| const std::size_t actual_size = size_upon_string? rlen : num_bits; |
| BOOST_CHECK(b.size() == actual_size); |
| std::size_t m = (std::min)(num_bits, rlen); |
| std::size_t j; |
| for (j = 0; j < m; ++j) |
| BOOST_CHECK(b[j] == (str[pos + m - 1 - j] == '1')); |
| // If M < N, remaining bit positions are zero |
| for (; j < actual_size; ++j) |
| BOOST_CHECK(b[j] == 0); |
| |
| |
| } |
| |
| static void to_block_range(const Bitset & b /*, BlockOutputIterator result*/) |
| { |
| typedef typename Bitset::size_type size_type; |
| |
| Block sentinel = 0xF0; |
| int s = 8; // number of sentinels (must be *even*) |
| int offset = s/2; |
| std::vector<Block> v(b.num_blocks() + s, sentinel); |
| |
| boost::to_block_range(b, v.begin() + offset); |
| |
| assert(v.size() >= (size_type)s && (s >= 2) && (s % 2 == 0)); |
| // check sentinels at both ends |
| for(int i = 0; i < s/2; ++i) { |
| BOOST_CHECK(v[i] == sentinel); |
| BOOST_CHECK(v[v.size()-1-i] == sentinel); |
| } |
| |
| typename std::vector<Block>::const_iterator p = v.begin() + offset; |
| for(size_type n = 0; n < b.num_blocks(); ++n, ++p) { |
| typename Bitset::block_width_type i = 0; |
| for(; i < bits_per_block; ++i) { |
| size_type bit = n * bits_per_block + i; |
| BOOST_CHECK(nth_bit(*p, i) == (bit < b.size()? b[bit] : 0)); |
| } |
| } |
| } |
| |
| // TODO from_block_range (below) should be splitted |
| |
| // PRE: std::equal(first1, last1, first2) == true |
| static void from_block_range(const std::vector<Block>& blocks) |
| { |
| { // test constructor from block range |
| Bitset bset(blocks.begin(), blocks.end()); |
| std::size_t n = blocks.size(); |
| for (std::size_t b = 0; b < n; ++b) { |
| typename Bitset::block_width_type i = 0; |
| for (; i < bits_per_block; ++i) { |
| std::size_t bit = b * bits_per_block + i; |
| BOOST_CHECK(bset[bit] == nth_bit(blocks[b], i)); |
| } |
| } |
| BOOST_CHECK(bset.size() == n * bits_per_block); |
| } |
| { // test boost::from_block_range |
| const typename Bitset::size_type n = blocks.size(); |
| Bitset bset(n * bits_per_block); |
| boost::from_block_range(blocks.begin(), blocks.end(), bset); |
| for (std::size_t b = 0; b < n; ++b) { |
| typename Bitset::block_width_type i = 0; |
| for (; i < bits_per_block; ++i) { |
| std::size_t bit = b * bits_per_block + i; |
| BOOST_CHECK(bset[bit] == nth_bit(blocks[b], i)); |
| } |
| } |
| BOOST_CHECK(n <= bset.num_blocks()); |
| } |
| } |
| |
| // copy constructor (absent from std::bitset) |
| static void copy_constructor(const Bitset& b) |
| { |
| Bitset copy(b); |
| BOOST_CHECK(b == copy); |
| |
| // Changes to the copy do not affect the original |
| if (b.size() > 0) { |
| std::size_t pos = copy.size() / 2; |
| copy.flip(pos); |
| BOOST_CHECK(copy[pos] != b[pos]); |
| } |
| } |
| |
| // assignment operator (absent from std::bitset) |
| static void assignment_operator(const Bitset& lhs, const Bitset& rhs) |
| { |
| Bitset b(lhs); |
| b = rhs; |
| BOOST_CHECK(b == rhs); |
| |
| // Changes to the copy do not affect the original |
| if (b.size() > 0) { |
| std::size_t pos = b.size() / 2; |
| b.flip(pos); |
| BOOST_CHECK(b[pos] != rhs[pos]); |
| } |
| } |
| |
| static void swap(const Bitset& lhs, const Bitset& rhs) |
| { |
| // bitsets must be swapped |
| Bitset copy1(lhs); |
| Bitset copy2(rhs); |
| copy1.swap(copy2); |
| |
| BOOST_CHECK(copy1 == rhs); |
| BOOST_CHECK(copy2 == lhs); |
| |
| // references must be stable under a swap |
| for(typename Bitset::size_type i = 0; i < lhs.size(); ++i) { |
| Bitset b1(lhs); |
| Bitset b2(rhs); |
| typename Bitset::reference ref = b1[i]; |
| bool x = ref; |
| if (i < b2.size()) |
| b2[i] = !x; // make sure b2[i] is different |
| b1.swap(b2); |
| BOOST_CHECK(b2[i] == x); // now it must be equal.. |
| b2.flip(i); |
| BOOST_CHECK(ref == b2[i]); // .. and ref must be into b2 |
| BOOST_CHECK(ref == !x); |
| } |
| |
| } |
| |
| static void resize(const Bitset& lhs) |
| { |
| Bitset b(lhs); |
| |
| // Test no change in size |
| b.resize(lhs.size()); |
| BOOST_CHECK(b == lhs); |
| |
| // Test increase in size |
| b.resize(lhs.size() * 2, true); |
| |
| std::size_t i; |
| for (i = 0; i < lhs.size(); ++i) |
| BOOST_CHECK(b[i] == lhs[i]); |
| for (; i < b.size(); ++i) |
| BOOST_CHECK(b[i] == true); |
| |
| // Test decrease in size |
| b.resize(lhs.size()); |
| for (i = 0; i < lhs.size(); ++i) |
| BOOST_CHECK(b[i] == lhs[i]); |
| } |
| |
| static void clear(const Bitset& lhs) |
| { |
| Bitset b(lhs); |
| b.clear(); |
| BOOST_CHECK(b.size() == 0); |
| } |
| |
| static void append_bit(const Bitset& lhs) |
| { |
| Bitset b(lhs); |
| b.push_back(true); |
| BOOST_CHECK(b.size() == lhs.size() + 1); |
| BOOST_CHECK(b[b.size() - 1] == true); |
| for (std::size_t i = 0; i < lhs.size(); ++i) |
| BOOST_CHECK(b[i] == lhs[i]); |
| |
| b.push_back(false); |
| BOOST_CHECK(b.size() == lhs.size() + 2); |
| BOOST_CHECK(b[b.size() - 1] == false); |
| BOOST_CHECK(b[b.size() - 2] == true); |
| for (std::size_t j = 0; j < lhs.size(); ++j) |
| BOOST_CHECK(b[j] == lhs[j]); |
| } |
| |
| static void append_block(const Bitset& lhs) |
| { |
| Bitset b(lhs); |
| Block value(128); |
| b.append(value); |
| BOOST_CHECK(b.size() == lhs.size() + bits_per_block); |
| for (typename Bitset::block_width_type i = 0; i < bits_per_block; ++i) |
| BOOST_CHECK(b[lhs.size() + i] == bool((value >> i) & 1)); |
| } |
| |
| static void append_block_range(const Bitset& lhs, const std::vector<Block>& blocks) |
| { |
| Bitset b(lhs), c(lhs); |
| b.append(blocks.begin(), blocks.end()); |
| for (typename std::vector<Block>::const_iterator i = blocks.begin(); |
| i != blocks.end(); ++i) |
| c.append(*i); |
| BOOST_CHECK(b == c); |
| } |
| |
| // operator[] and reference members |
| // PRE: b[i] == bit_vec[i] |
| static void operator_bracket(const Bitset& lhs, const std::vector<bool>& bit_vec) |
| { |
| Bitset b(lhs); |
| std::size_t i, j, k; |
| |
| // x = b[i] |
| // x = ~b[i] |
| for (i = 0; i < b.size(); ++i) { |
| bool x = b[i]; |
| BOOST_CHECK(x == bit_vec[i]); |
| x = ~b[i]; |
| BOOST_CHECK(x == !bit_vec[i]); |
| } |
| Bitset prev(b); |
| |
| // b[i] = x |
| for (j = 0; j < b.size(); ++j) { |
| bool x = !prev[j]; |
| b[j] = x; |
| for (k = 0; k < b.size(); ++k) |
| if (j == k) |
| BOOST_CHECK(b[k] == x); |
| else |
| BOOST_CHECK(b[k] == prev[k]); |
| b[j] = prev[j]; |
| } |
| b.flip(); |
| |
| // b[i] = b[j] |
| for (i = 0; i < b.size(); ++i) { |
| b[i] = prev[i]; |
| for (j = 0; j < b.size(); ++j) { |
| if (i == j) |
| BOOST_CHECK(b[j] == prev[j]); |
| else |
| BOOST_CHECK(b[j] == !prev[j]); |
| } |
| b[i] = !prev[i]; |
| } |
| |
| // b[i].flip() |
| for (i = 0; i < b.size(); ++i) { |
| b[i].flip(); |
| for (j = 0; j < b.size(); ++j) { |
| if (i == j) |
| BOOST_CHECK(b[j] == prev[j]); |
| else |
| BOOST_CHECK(b[j] == !prev[j]); |
| } |
| b[i].flip(); |
| } |
| } |
| |
| //=========================================================================== |
| // bitwise operators |
| |
| // bitwise and assignment |
| |
| // PRE: b.size() == rhs.size() |
| static void and_assignment(const Bitset& b, const Bitset& rhs) |
| { |
| Bitset lhs(b); |
| Bitset prev(lhs); |
| lhs &= rhs; |
| // Clears each bit in lhs for which the corresponding bit in rhs is |
| // clear, and leaves all other bits unchanged. |
| for (std::size_t I = 0; I < lhs.size(); ++I) |
| if (rhs[I] == 0) |
| BOOST_CHECK(lhs[I] == 0); |
| else |
| BOOST_CHECK(lhs[I] == prev[I]); |
| } |
| |
| // PRE: b.size() == rhs.size() |
| static void or_assignment(const Bitset& b, const Bitset& rhs) |
| { |
| Bitset lhs(b); |
| Bitset prev(lhs); |
| lhs |= rhs; |
| // Sets each bit in lhs for which the corresponding bit in rhs is set, and |
| // leaves all other bits unchanged. |
| for (std::size_t I = 0; I < lhs.size(); ++I) |
| if (rhs[I] == 1) |
| BOOST_CHECK(lhs[I] == 1); |
| else |
| BOOST_CHECK(lhs[I] == prev[I]); |
| } |
| |
| // PRE: b.size() == rhs.size() |
| static void xor_assignment(const Bitset& b, const Bitset& rhs) |
| { |
| Bitset lhs(b); |
| Bitset prev(lhs); |
| lhs ^= rhs; |
| // Flips each bit in lhs for which the corresponding bit in rhs is set, |
| // and leaves all other bits unchanged. |
| for (std::size_t I = 0; I < lhs.size(); ++I) |
| if (rhs[I] == 1) |
| BOOST_CHECK(lhs[I] == !prev[I]); |
| else |
| BOOST_CHECK(lhs[I] == prev[I]); |
| } |
| |
| // PRE: b.size() == rhs.size() |
| static void sub_assignment(const Bitset& b, const Bitset& rhs) |
| { |
| Bitset lhs(b); |
| Bitset prev(lhs); |
| lhs -= rhs; |
| // Resets each bit in lhs for which the corresponding bit in rhs is set, |
| // and leaves all other bits unchanged. |
| for (std::size_t I = 0; I < lhs.size(); ++I) |
| if (rhs[I] == 1) |
| BOOST_CHECK(lhs[I] == 0); |
| else |
| BOOST_CHECK(lhs[I] == prev[I]); |
| } |
| |
| static void shift_left_assignment(const Bitset& b, std::size_t pos) |
| { |
| Bitset lhs(b); |
| Bitset prev(lhs); |
| lhs <<= pos; |
| // Replaces each bit at position I in lhs with the following value: |
| // - If I < pos, the new value is zero |
| // - If I >= pos, the new value is the previous value of the bit at |
| // position I - pos |
| for (std::size_t I = 0; I < lhs.size(); ++I) |
| if (I < pos) |
| BOOST_CHECK(lhs[I] == 0); |
| else |
| BOOST_CHECK(lhs[I] == prev[I - pos]); |
| } |
| |
| static void shift_right_assignment(const Bitset& b, std::size_t pos) |
| { |
| Bitset lhs(b); |
| Bitset prev(lhs); |
| lhs >>= pos; |
| // Replaces each bit at position I in lhs with the following value: |
| // - If pos >= N - I, the new value is zero |
| // - If pos < N - I, the new value is the previous value of the bit at |
| // position I + pos |
| std::size_t N = lhs.size(); |
| for (std::size_t I = 0; I < N; ++I) |
| if (pos >= N - I) |
| BOOST_CHECK(lhs[I] == 0); |
| else |
| BOOST_CHECK(lhs[I] == prev[I + pos]); |
| } |
| |
| |
| static void set_all(const Bitset& b) |
| { |
| Bitset lhs(b); |
| lhs.set(); |
| for (std::size_t I = 0; I < lhs.size(); ++I) |
| BOOST_CHECK(lhs[I] == 1); |
| } |
| |
| static void set_one(const Bitset& b, std::size_t pos, bool value) |
| { |
| Bitset lhs(b); |
| std::size_t N = lhs.size(); |
| if (pos < N) { |
| Bitset prev(lhs); |
| // Stores a new value in the bit at position pos in lhs. |
| lhs.set(pos, value); |
| BOOST_CHECK(lhs[pos] == value); |
| |
| // All other values of lhs remain unchanged |
| for (std::size_t I = 0; I < N; ++I) |
| if (I != pos) |
| BOOST_CHECK(lhs[I] == prev[I]); |
| } else { |
| // Not in range, doesn't satisfy precondition. |
| } |
| } |
| |
| static void reset_all(const Bitset& b) |
| { |
| Bitset lhs(b); |
| // Resets all bits in lhs |
| lhs.reset(); |
| for (std::size_t I = 0; I < lhs.size(); ++I) |
| BOOST_CHECK(lhs[I] == 0); |
| } |
| |
| static void reset_one(const Bitset& b, std::size_t pos) |
| { |
| Bitset lhs(b); |
| std::size_t N = lhs.size(); |
| if (pos < N) { |
| Bitset prev(lhs); |
| lhs.reset(pos); |
| // Resets the bit at position pos in lhs |
| BOOST_CHECK(lhs[pos] == 0); |
| |
| // All other values of lhs remain unchanged |
| for (std::size_t I = 0; I < N; ++I) |
| if (I != pos) |
| BOOST_CHECK(lhs[I] == prev[I]); |
| } else { |
| // Not in range, doesn't satisfy precondition. |
| } |
| } |
| |
| static void operator_flip(const Bitset& b) |
| { |
| Bitset lhs(b); |
| Bitset x(lhs); |
| BOOST_CHECK(~lhs == x.flip()); |
| } |
| |
| static void flip_all(const Bitset& b) |
| { |
| Bitset lhs(b); |
| std::size_t N = lhs.size(); |
| Bitset prev(lhs); |
| lhs.flip(); |
| // Toggles all the bits in lhs |
| for (std::size_t I = 0; I < N; ++I) |
| BOOST_CHECK(lhs[I] == !prev[I]); |
| } |
| |
| static void flip_one(const Bitset& b, std::size_t pos) |
| { |
| Bitset lhs(b); |
| std::size_t N = lhs.size(); |
| if (pos < N) { |
| Bitset prev(lhs); |
| lhs.flip(pos); |
| // Toggles the bit at position pos in lhs |
| BOOST_CHECK(lhs[pos] == !prev[pos]); |
| |
| // All other values of lhs remain unchanged |
| for (std::size_t I = 0; I < N; ++I) |
| if (I != pos) |
| BOOST_CHECK(lhs[I] == prev[I]); |
| } else { |
| // Not in range, doesn't satisfy precondition. |
| } |
| } |
| |
| // empty |
| static void empty(const Bitset& b) |
| { |
| BOOST_CHECK(b.empty() == (b.size() == 0)); |
| } |
| |
| // to_ulong() |
| static void to_ulong(const Bitset& lhs) |
| { |
| typedef unsigned long result_type; |
| std::size_t n = std::numeric_limits<result_type>::digits; |
| std::size_t sz = lhs.size(); |
| |
| bool will_overflow = false; |
| for (std::size_t i = n; i < sz; ++i) { |
| if (lhs.test(i) != 0) { |
| will_overflow = true; |
| break; |
| } |
| } |
| if (will_overflow) { |
| try { |
| (void)lhs.to_ulong(); |
| BOOST_CHECK(false); // It should have thrown an exception |
| } catch (std::overflow_error & ex) { |
| // Good! |
| BOOST_CHECK(!!ex.what()); |
| } catch (...) { |
| BOOST_CHECK(false); // threw the wrong exception |
| } |
| } else { |
| result_type num = lhs.to_ulong(); |
| // Be sure the number is right |
| if (sz == 0) |
| BOOST_CHECK(num == 0); |
| else { |
| for (std::size_t i = 0; i < sz; ++i) |
| BOOST_CHECK(lhs[i] == (i < n ? nth_bit(num, i) : 0)); |
| } |
| } |
| } |
| |
| // to_string() |
| static void to_string(const Bitset& b) |
| { |
| std::string str; |
| boost::to_string(b, str); |
| BOOST_CHECK(str.size() == b.size()); |
| for (std::size_t i = 0; i < b.size(); ++i) |
| BOOST_CHECK(str[b.size() - 1 - i] ==(b.test(i)? '1':'0')); |
| } |
| |
| static void count(const Bitset& b) |
| { |
| std::size_t c = b.count(); |
| std::size_t actual = 0; |
| for (std::size_t i = 0; i < b.size(); ++i) |
| if (b[i]) |
| ++actual; |
| BOOST_CHECK(c == actual); |
| } |
| |
| static void size(const Bitset& b) |
| { |
| BOOST_CHECK(Bitset(b).set().count() == b.size()); |
| } |
| |
| static void any(const Bitset& b) |
| { |
| //BOOST_CHECK(b.any() == (b.count() > 0)); |
| bool result = false; |
| for(std::size_t i = 0; i < b.size(); ++i) |
| if(b[i]) { |
| result = true; |
| break; |
| } |
| BOOST_CHECK(b.any() == result); |
| } |
| |
| static void none(const Bitset& b) |
| { |
| bool result = true; |
| for(std::size_t i = 0; i < b.size(); ++i) { |
| if(b[i]) { |
| result = false; |
| break; |
| } |
| } |
| BOOST_CHECK(b.none() == result); |
| |
| // sanity |
| BOOST_CHECK(b.none() == !b.any()); |
| BOOST_CHECK(b.none() == (b.count() == 0)); |
| } |
| |
| static void subset(const Bitset& a, const Bitset& b) |
| { |
| BOOST_CHECK(a.size() == b.size()); // PRE |
| |
| bool is_subset = true; |
| if (b.size()) { // could use b.any() but let's be safe |
| for(std::size_t i = 0; i < a.size(); ++i) { |
| if(a.test(i) && !b.test(i)) { |
| is_subset = false; |
| break; |
| } |
| } |
| } |
| else { |
| // sanity |
| BOOST_CHECK(a.count() == 0); |
| BOOST_CHECK(a.any() == false); |
| |
| //is_subset = (a.any() == false); |
| } |
| |
| BOOST_CHECK(a.is_subset_of(b) == is_subset); |
| } |
| |
| static void proper_subset(const Bitset& a, const Bitset& b) |
| { |
| // PRE: a.size() == b.size() |
| BOOST_CHECK(a.size() == b.size()); |
| |
| bool is_proper = false; |
| |
| if (b.size() != 0) { |
| |
| // check it's a subset |
| subset(a, b); |
| |
| // is it proper? |
| for (std::size_t i = 0; i < a.size(); ++i) { |
| if (!a.test(i) && b.test(i)) { |
| is_proper = true; |
| // sanity |
| BOOST_CHECK(a.count() < b.count()); |
| BOOST_CHECK(b.any()); |
| } |
| } |
| } |
| |
| BOOST_CHECK(a.is_proper_subset_of(b) == is_proper); |
| if (is_proper) |
| BOOST_CHECK(b.is_proper_subset_of(a) != is_proper);// antisymmetry |
| } |
| |
| static void intersects(const Bitset& a, const Bitset& b) |
| { |
| bool have_intersection = false; |
| |
| typename Bitset::size_type m = a.size() < b.size() ? a.size() : b.size(); |
| for(typename Bitset::size_type i = 0; i < m && !have_intersection; ++i) |
| if(a[i] == true && b[i] == true) |
| have_intersection = true; |
| |
| BOOST_CHECK(a.intersects(b) == have_intersection); |
| // also check commutativity |
| BOOST_CHECK(b.intersects(a) == have_intersection); |
| } |
| |
| static void find_first(const Bitset& b) |
| { |
| // find first non-null bit, if any |
| typename Bitset::size_type i = 0; |
| while (i < b.size() && b[i] == 0) |
| ++i; |
| |
| if (i == b.size()) |
| BOOST_CHECK(b.find_first() == Bitset::npos); // not found; |
| else { |
| BOOST_CHECK(b.find_first() == i); |
| BOOST_CHECK(b.test(i) == true); |
| } |
| |
| } |
| |
| static void find_next(const Bitset& b, typename Bitset::size_type prev) |
| { |
| BOOST_CHECK(next_bit_on(b, prev) == b.find_next(prev)); |
| } |
| |
| static void operator_equal(const Bitset& a, const Bitset& b) |
| { |
| if (a == b) { |
| for (std::size_t I = 0; I < a.size(); ++I) |
| BOOST_CHECK(a[I] == b[I]); |
| } else { |
| if (a.size() == b.size()) { |
| bool diff = false; |
| for (std::size_t I = 0; I < a.size(); ++I) |
| if (a[I] != b[I]) { |
| diff = true; |
| break; |
| } |
| BOOST_CHECK(diff); |
| } |
| } |
| } |
| |
| static void operator_not_equal(const Bitset& a, const Bitset& b) |
| { |
| if (a != b) { |
| if (a.size() == b.size()) { |
| bool diff = false; |
| for (std::size_t I = 0; I < a.size(); ++I) |
| if (a[I] != b[I]) { |
| diff = true; |
| break; |
| } |
| BOOST_CHECK(diff); |
| } |
| } else { |
| for (std::size_t I = 0; I < a.size(); ++I) |
| BOOST_CHECK(a[I] == b[I]); |
| } |
| } |
| |
| static bool less_than(const Bitset& a, const Bitset& b) |
| { |
| // Compare from most significant to least. |
| // Careful, don't send unsigned int into negative territory! |
| if (a.size() == 0) |
| return false; |
| |
| std::size_t I; |
| for (I = a.size() - 1; I > 0; --I) |
| if (a[I] < b[I]) |
| return true; |
| else if (a[I] > b[I]) |
| return false; |
| // if (a[I] = b[I]) skip to next |
| |
| if (a[0] < b[0]) |
| return true; |
| else |
| return false; |
| } |
| |
| static typename Bitset::size_type next_bit_on(const Bitset& b, typename Bitset::size_type prev) |
| { |
| // helper function for find_next() |
| // |
| |
| if (b.none() == true || prev == Bitset::npos) |
| return Bitset::npos; |
| |
| ++prev; |
| |
| if (prev >= b.size()) |
| return Bitset::npos; |
| |
| typename Bitset::size_type i = prev; |
| while (i < b.size() && b[i] == 0) |
| ++i; |
| |
| return i==b.size() ? Bitset::npos : i; |
| |
| } |
| |
| static void operator_less_than(const Bitset& a, const Bitset& b) |
| { |
| if (less_than(a, b)) |
| BOOST_CHECK(a < b); |
| else |
| BOOST_CHECK(!(a < b)); |
| } |
| |
| static void operator_greater_than(const Bitset& a, const Bitset& b) |
| { |
| if (less_than(a, b) || a == b) |
| BOOST_CHECK(!(a > b)); |
| else |
| BOOST_CHECK(a > b); |
| } |
| |
| static void operator_less_than_eq(const Bitset& a, const Bitset& b) |
| { |
| if (less_than(a, b) || a == b) |
| BOOST_CHECK(a <= b); |
| else |
| BOOST_CHECK(!(a <= b)); |
| } |
| |
| static void operator_greater_than_eq(const Bitset& a, const Bitset& b) |
| { |
| if (less_than(a, b)) |
| BOOST_CHECK(!(a >= b)); |
| else |
| BOOST_CHECK(a >= b); |
| } |
| |
| static void test_bit(const Bitset& b, std::size_t pos) |
| { |
| Bitset lhs(b); |
| std::size_t N = lhs.size(); |
| if (pos < N) { |
| BOOST_CHECK(lhs.test(pos) == lhs[pos]); |
| } else { |
| // Not in range, doesn't satisfy precondition. |
| } |
| } |
| |
| static void operator_shift_left(const Bitset& lhs, std::size_t pos) |
| { |
| Bitset x(lhs); |
| BOOST_CHECK((lhs << pos) == (x <<= pos)); |
| } |
| |
| static void operator_shift_right(const Bitset& lhs, std::size_t pos) |
| { |
| Bitset x(lhs); |
| BOOST_CHECK((lhs >> pos) == (x >>= pos)); |
| } |
| |
| // operator| |
| static |
| void operator_or(const Bitset& lhs, const Bitset& rhs) |
| { |
| Bitset x(lhs); |
| BOOST_CHECK((lhs | rhs) == (x |= rhs)); |
| } |
| |
| // operator& |
| static |
| void operator_and(const Bitset& lhs, const Bitset& rhs) |
| { |
| Bitset x(lhs); |
| BOOST_CHECK((lhs & rhs) == (x &= rhs)); |
| } |
| |
| // operator^ |
| static |
| void operator_xor(const Bitset& lhs, const Bitset& rhs) |
| { |
| Bitset x(lhs); |
| BOOST_CHECK((lhs ^ rhs) == (x ^= rhs)); |
| } |
| |
| // operator- |
| static |
| void operator_sub(const Bitset& lhs, const Bitset& rhs) |
| { |
| Bitset x(lhs); |
| BOOST_CHECK((lhs - rhs) == (x -= rhs)); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // I/O TESTS |
| // The following tests assume the results of extraction (i.e.: contents, |
| // state and width of is, contents of b) only depend on input (the string |
| // str). In other words, they don't consider "unexpected" errors such as |
| // stream corruption or out of memory. The reason is simple: if e.g. the |
| // stream buffer throws, the stream layer may eat the exception and |
| // transform it into a badbit. But we can't trust the stream state here, |
| // because one of the things that we want to test is exactly whether it |
| // is set correctly. Similarly for insertion. |
| // |
| // To provide for these cases would require that the test functions know |
| // in advance whether the stream buffer and/or allocations will fail, and |
| // when; that is, we should write both a special allocator and a special |
| // stream buffer capable of throwing "on demand" and pass them here. |
| |
| // Seems overkill for these kinds of unit tests. |
| //------------------------------------------------------------------------- |
| |
| // operator<<( [basic_]ostream, |
| template <typename Stream> |
| static void stream_inserter(const Bitset & b, |
| Stream & s, |
| const char * file_name |
| ) |
| { |
| #if defined BOOST_OLD_IOSTREAMS |
| typedef char char_type; |
| typedef std::string string_type; |
| typedef ifstream corresponding_input_stream_type; |
| #else |
| typedef typename Stream::char_type char_type; |
| typedef std::basic_string<char_type> string_type; |
| typedef std::basic_ifstream<char_type> corresponding_input_stream_type; |
| |
| std::ios::iostate except = s.exceptions(); |
| #endif |
| |
| typedef typename Bitset::size_type size_type; |
| std::streamsize w = s.width(); |
| char_type fill_char = s.fill(); |
| std::ios::iostate oldstate = s.rdstate(); |
| bool stream_was_good = s.good(); |
| |
| bool did_throw = false; |
| try { |
| s << b; |
| } |
| #if defined BOOST_OLD_IOSTREAMS |
| catch(...) { |
| BOOST_CHECK(false); |
| } |
| #else |
| catch (const std::ios_base::failure &) { |
| BOOST_CHECK((except & s.rdstate()) != 0); |
| did_throw = true; |
| } catch (...) { |
| did_throw = true; |
| } |
| #endif |
| |
| BOOST_CHECK(did_throw || !stream_was_good || (s.width() == 0)); |
| |
| if (!stream_was_good) { |
| BOOST_CHECK(s.good() == false); |
| |
| // this should actually be oldstate == s.rdstate() |
| // but some implementations add badbit in the |
| // sentry constructor |
| // |
| BOOST_CHECK((oldstate & s.rdstate()) == oldstate); |
| BOOST_CHECK(s.width() == w); |
| } |
| else { |
| if(!did_throw) |
| BOOST_CHECK(s.width() == 0); |
| // This test require that os be an output _and_ input stream. |
| // Of course dynamic_bitset's operator << doesn't require that. |
| |
| size_type total_len = w <= 0 || (size_type)(w) < b.size()? b.size() : w; |
| const string_type padding (total_len - b.size(), fill_char); |
| string_type expected; |
| boost::to_string(b, expected); |
| if ((s.flags() & std::ios::adjustfield) != std::ios::left) |
| expected = padding + expected; |
| else |
| expected = expected + padding; |
| |
| assert(expected.length() == total_len); |
| |
| // close, and reopen the file stream to verify contents |
| s.close(); |
| corresponding_input_stream_type is(file_name); |
| string_type contents; |
| std::getline(is, contents, char_type()); |
| BOOST_CHECK(contents == expected); |
| } |
| } |
| |
| // operator>>( [basic_]istream |
| template <typename Stream, typename String> |
| static void stream_extractor(Bitset& b, |
| Stream& is, |
| String& str |
| ) |
| { |
| // save necessary info then do extraction |
| // |
| const std::streamsize w = is.width(); |
| Bitset a_copy(b); |
| bool stream_was_good = is.good(); |
| |
| bool did_throw = false; |
| |
| #if defined BOOST_OLD_IOSTREAMS |
| bool has_stream_exceptions = false; |
| is >> b; |
| #else |
| const std::ios::iostate except = is.exceptions(); |
| bool has_stream_exceptions = true; |
| try { |
| is >> b; |
| } |
| catch(const std::ios::failure &) { |
| did_throw = true; |
| } |
| |
| // postconditions |
| BOOST_CHECK(except == is.exceptions()); // paranoid |
| #endif |
| //------------------------------------------------------------------ |
| |
| // postconditions |
| BOOST_CHECK(b.size() <= b.max_size()); |
| if(w > 0) |
| BOOST_CHECK(b.size() <= static_cast<typename Bitset::size_type>(w)); |
| |
| // throw if and only if required |
| if(has_stream_exceptions) { |
| const bool exceptional_state = has_flags(is, is.exceptions()); |
| BOOST_CHECK(exceptional_state == did_throw); |
| } |
| |
| typedef typename String::size_type size_type; |
| typedef typename String::value_type Ch; |
| size_type after_digits = 0; |
| |
| if(!stream_was_good) { |
| BOOST_CHECK(has_flags(is, std::ios::failbit)); |
| BOOST_CHECK(b == a_copy); |
| BOOST_CHECK(is.width() == (did_throw ? w : 0)); |
| } |
| else { |
| // stream was good(), parse the string; |
| // it may contain three parts, all of which are optional |
| // {spaces} {digits} {non-digits} |
| // opt opt opt |
| // |
| // The values of b.max_size() and is.width() may lead to |
| // ignore part of the digits, if any. |
| |
| size_type pos = 0; |
| size_type len = str.length(); |
| // {spaces} |
| for( ; pos < len && is_white_space(is, str[pos]); ++pos) |
| {} |
| size_type after_spaces = pos; |
| // {digits} or part of them |
| const typename Bitset::size_type max_digits = |
| w > 0 && static_cast<typename Bitset::size_type>(w) < b.max_size() |
| ? w : b.max_size(); |
| |
| for( ; pos < len && (pos - after_spaces) < max_digits; ++pos) { |
| if(!is_one_or_zero(is, str[pos])) |
| break; |
| } |
| after_digits = pos; |
| size_type num_digits = after_digits - after_spaces; |
| |
| // eofbit |
| if((after_digits == len && max_digits > num_digits )) |
| BOOST_CHECK(has_flags(is, std::ios::eofbit)); |
| else |
| BOOST_CHECK(!has_flags(is, std::ios::eofbit)); |
| |
| // failbit <=> there are no digits, except for the library |
| // issue explained below. |
| // |
| if(num_digits == 0) { |
| if(after_digits == len && has_stream_exceptions && |
| (is.exceptions() & std::ios::eofbit) != std::ios::goodbit) { |
| // This is a special case related to library issue 195: |
| // reaching eof when skipping whitespaces in the sentry ctor. |
| // The resolution says the sentry constructor should set *both* |
| // eofbit and failbit; but many implementations deliberately |
| // set eofbit only. See for instance: |
| // http://gcc.gnu.org/ml/libstdc++/2000-q1/msg00086.html |
| // |
| BOOST_CHECK(did_throw); |
| |
| } |
| else { |
| BOOST_CHECK(has_flags(is, std::ios::failbit)); |
| } |
| } |
| else |
| BOOST_CHECK(!has_flags(is, std::ios::failbit)); |
| |
| |
| if(num_digits == 0 && after_digits == len) { |
| // The VC6 library has a bug/non-conformity in the sentry |
| // constructor. It uses code like |
| // // skip whitespaces... |
| // int_type _C = rdbuf()->sgetc(); |
| // while (!_Tr::eq_int_type(_Tr::eof(), _C) ... |
| // |
| // For an empty file the while statement is never "entered" |
| // and the stream remains in good() state; thus the sentry |
| // object gives "true" when converted to bool. This is worse |
| // than the case above, because not only failbit is not set, |
| // but no bit is set at all, end we end up clearing the |
| // bitset though there's nothing in the file to be extracted. |
| // Note that the dynamic_bitset docs say a sentry object is |
| // constructed and then converted to bool, thus we rely on |
| // what the underlying library does. |
| // |
| #if !defined(BOOST_DINKUMWARE_STDLIB) || (BOOST_DINKUMWARE_STDLIB >= 306) |
| BOOST_CHECK(b == a_copy); |
| #else |
| BOOST_CHECK(b.empty() == true); |
| #endif |
| } |
| else { |
| String sub = str.substr(after_spaces, num_digits); |
| BOOST_CHECK(b == Bitset(sub)); |
| } |
| |
| // check width |
| BOOST_CHECK(is.width() == 0 |
| || (after_digits == len && num_digits == 0 && did_throw)); |
| } |
| |
| |
| // clear the stream to allow further reading then |
| // retrieve any remaining chars with a single getline() |
| is.exceptions(std::ios::goodbit); |
| is.clear(); |
| String remainder; |
| std::getline(is, remainder, Ch()); |
| if(stream_was_good) |
| BOOST_CHECK(remainder == str.substr(after_digits)); |
| else |
| BOOST_CHECK(remainder == str); |
| |
| } |
| |
| |
| }; |
| |
| |
| |
| #endif // include guard |
