12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454 |
- // -----------------------------------------------------------
- // Copyright (c) 2001 Jeremy Siek
- // Copyright (c) 2003-2006, 2008 Gennaro Prota
- // Copyright (c) 2014 Ahmed Charles
- // Copyright (c) 2014 Riccardo Marcangelo
- // Copyright (c) 2018 Evgeny Shulgin
- //
- // 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/core/lightweight_test.hpp>
- #include <boost/filesystem.hpp>
- template <typename Block>
- inline bool nth_bit(Block num, std::size_t n)
- {
- #ifndef NDEBUG
- #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);
- #endif
- 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);
- }
- class scoped_temp_file
- {
- public:
- scoped_temp_file()
- : m_path(boost::filesystem::unique_path())
- {
- }
- ~scoped_temp_file()
- {
- boost::filesystem::remove(m_path);
- }
- const boost::filesystem::path& path() const
- {
- return m_path;
- }
- private:
- boost::filesystem::path m_path;
- };
- #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(static_cast<typename Bitset::size_type>(num_bits), static_cast<unsigned long>(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_TEST(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_TEST(b.test(i) == nth_bit(static_cast<unsigned long>(num), i));
- for ( ; i < sz; ++i)
- BOOST_TEST(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_TEST(b.size() == actual_size);
- std::size_t m = (std::min)(num_bits, rlen);
- std::size_t j;
- for (j = 0; j < m; ++j)
- BOOST_TEST(b[j] == (str[pos + m - 1 - j] == '1'));
- // If M < N, remaining bit positions are zero
- for (; j < actual_size; ++j)
- BOOST_TEST(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_TEST(v[i] == sentinel);
- BOOST_TEST(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_TEST(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_TEST(bset[bit] == nth_bit(blocks[b], i));
- }
- }
- BOOST_TEST(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_TEST(bset[bit] == nth_bit(blocks[b], i));
- }
- }
- BOOST_TEST(n <= bset.num_blocks());
- }
- }
- // copy constructor (absent from std::bitset)
- static void copy_constructor(const Bitset& b)
- {
- Bitset copy(b);
- BOOST_TEST(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_TEST(copy[pos] != b[pos]);
- }
- }
- // copy assignment operator (absent from std::bitset)
- static void copy_assignment_operator(const Bitset& lhs, const Bitset& rhs)
- {
- Bitset b(lhs);
- b = rhs;
- b = b; // self assignment check
- BOOST_TEST(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_TEST(b[pos] != rhs[pos]);
- }
- }
- static void max_size(const Bitset& b)
- {
- BOOST_TEST(b.max_size() > 0);
- }
- #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
- // move constructor (absent from std::bitset)
- static void move_constructor(const Bitset& b)
- {
- Bitset copy(boost::move(b));
- BOOST_TEST(b == copy);
- }
- // move assignment operator (absent from std::bitset)
- static void move_assignment_operator(const Bitset& lhs, const Bitset& rhs)
- {
- Bitset b(lhs);
- Bitset c(rhs);
- b = boost::move(c);
- b = boost::move(b); // self assignment check
- BOOST_TEST(b == rhs);
- }
- #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
- static void swap(const Bitset& lhs, const Bitset& rhs)
- {
- // bitsets must be swapped
- Bitset copy1(lhs);
- Bitset copy2(rhs);
- copy1.swap(copy2);
- BOOST_TEST(copy1 == rhs);
- BOOST_TEST(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_TEST(b2[i] == x); // now it must be equal..
- b2.flip(i);
- BOOST_TEST(ref == b2[i]); // .. and ref must be into b2
- BOOST_TEST(ref == !x);
- }
- }
- static void resize(const Bitset& lhs)
- {
- Bitset b(lhs);
- // Test no change in size
- b.resize(lhs.size());
- BOOST_TEST(b == lhs);
- // Test increase in size
- b.resize(lhs.size() * 2, true);
- std::size_t i;
- for (i = 0; i < lhs.size(); ++i)
- BOOST_TEST(b[i] == lhs[i]);
- for (; i < b.size(); ++i)
- BOOST_TEST(b[i] == true);
- // Test decrease in size
- b.resize(lhs.size());
- for (i = 0; i < lhs.size(); ++i)
- BOOST_TEST(b[i] == lhs[i]);
- }
- static void clear(const Bitset& lhs)
- {
- Bitset b(lhs);
- b.clear();
- BOOST_TEST(b.size() == 0);
- }
- static void pop_back(const Bitset& lhs)
- {
- Bitset b(lhs);
- b.pop_back();
- BOOST_TEST(b.size() == lhs.size() - 1);
- for (std::size_t i = 0; i < b.size(); ++i)
- BOOST_TEST(b[i] == lhs[i]);
- b.pop_back();
- BOOST_TEST(b.size() == lhs.size() - 2);
- for (std::size_t j = 0; j < b.size(); ++j)
- BOOST_TEST(b[j] == lhs[j]);
- }
- static void append_bit(const Bitset& lhs)
- {
- Bitset b(lhs);
- b.push_back(true);
- BOOST_TEST(b.size() == lhs.size() + 1);
- BOOST_TEST(b[b.size() - 1] == true);
- for (std::size_t i = 0; i < lhs.size(); ++i)
- BOOST_TEST(b[i] == lhs[i]);
- b.push_back(false);
- BOOST_TEST(b.size() == lhs.size() + 2);
- BOOST_TEST(b[b.size() - 1] == false);
- BOOST_TEST(b[b.size() - 2] == true);
- for (std::size_t j = 0; j < lhs.size(); ++j)
- BOOST_TEST(b[j] == lhs[j]);
- }
- static void append_block(const Bitset& lhs)
- {
- Bitset b(lhs);
- Block value(128);
- b.append(value);
- BOOST_TEST(b.size() == lhs.size() + bits_per_block);
- for (typename Bitset::block_width_type i = 0; i < bits_per_block; ++i)
- BOOST_TEST(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_TEST(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_TEST(x == bit_vec[i]);
- x = ~b[i];
- BOOST_TEST(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_TEST(b[k] == x);
- else
- BOOST_TEST(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_TEST(b[j] == prev[j]);
- else
- BOOST_TEST(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_TEST(b[j] == prev[j]);
- else
- BOOST_TEST(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_TEST(lhs[I] == 0);
- else
- BOOST_TEST(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_TEST(lhs[I] == 1);
- else
- BOOST_TEST(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_TEST(lhs[I] == !prev[I]);
- else
- BOOST_TEST(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_TEST(lhs[I] == 0);
- else
- BOOST_TEST(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_TEST(lhs[I] == 0);
- else
- BOOST_TEST(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_TEST(lhs[I] == 0);
- else
- BOOST_TEST(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_TEST(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_TEST(lhs[pos] == value);
- // All other values of lhs remain unchanged
- for (std::size_t I = 0; I < N; ++I)
- if (I != pos)
- BOOST_TEST(lhs[I] == prev[I]);
- } else {
- // Not in range, doesn't satisfy precondition.
- }
- }
- static void set_segment(const Bitset& b, std::size_t pos,
- std::size_t len, bool value)
- {
- Bitset lhs(b);
- std::size_t N = lhs.size();
- Bitset prev(lhs);
- lhs.set(pos, len, value);
- for (std::size_t I = 0; I < N; ++I)
- {
- if (I < pos || I >= pos + len)
- BOOST_TEST(lhs[I] == prev[I]);
- else
- BOOST_TEST(lhs[I] == value);
- }
- }
- 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_TEST(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_TEST(lhs[pos] == 0);
- // All other values of lhs remain unchanged
- for (std::size_t I = 0; I < N; ++I)
- if (I != pos)
- BOOST_TEST(lhs[I] == prev[I]);
- } else {
- // Not in range, doesn't satisfy precondition.
- }
- }
- static void reset_segment(const Bitset& b, std::size_t pos,
- std::size_t len)
- {
- Bitset lhs(b);
- std::size_t N = lhs.size();
- Bitset prev(lhs);
- lhs.reset(pos, len);
- for (std::size_t I = 0; I < N; ++I)
- {
- if (I < pos || I >= pos + len)
- BOOST_TEST(lhs[I] == prev[I]);
- else
- BOOST_TEST(!lhs[I]);
- }
- }
- static void operator_flip(const Bitset& b)
- {
- Bitset lhs(b);
- Bitset x(lhs);
- BOOST_TEST(~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_TEST(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_TEST(lhs[pos] == !prev[pos]);
- // All other values of lhs remain unchanged
- for (std::size_t I = 0; I < N; ++I)
- if (I != pos)
- BOOST_TEST(lhs[I] == prev[I]);
- } else {
- // Not in range, doesn't satisfy precondition.
- }
- }
- static void flip_segment(const Bitset& b, std::size_t pos,
- std::size_t len)
- {
- Bitset lhs(b);
- std::size_t N = lhs.size();
- Bitset prev(lhs);
- lhs.flip(pos, len);
- for (std::size_t I = 0; I < N; ++I)
- {
- if (I < pos || I >= pos + len)
- BOOST_TEST(lhs[I] == prev[I]);
- else
- BOOST_TEST(lhs[I] != prev[I]);
- }
- }
- // empty
- static void empty(const Bitset& b)
- {
- BOOST_TEST(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_TEST(false); // It should have thrown an exception
- } catch (std::overflow_error & ex) {
- // Good!
- BOOST_TEST(!!ex.what());
- } catch (...) {
- BOOST_TEST(false); // threw the wrong exception
- }
- } else {
- result_type num = lhs.to_ulong();
- // Be sure the number is right
- if (sz == 0)
- BOOST_TEST(num == 0);
- else {
- for (std::size_t i = 0; i < sz; ++i)
- BOOST_TEST(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_TEST(str.size() == b.size());
- for (std::size_t i = 0; i < b.size(); ++i)
- BOOST_TEST(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_TEST(c == actual);
- }
- static void size(const Bitset& b)
- {
- BOOST_TEST(Bitset(b).set().count() == b.size());
- }
- static void capacity_test_one(const Bitset& lhs)
- {
- //empty bitset
- Bitset b(lhs);
- BOOST_TEST(b.capacity() == 0);
- }
- static void capacity_test_two(const Bitset& lhs)
- {
- //bitset constructed with size "100"
- Bitset b(lhs);
- BOOST_TEST(b.capacity() >= 100);
- b.resize(200);
- BOOST_TEST(b.capacity() >= 200);
- }
- static void reserve_test_one(const Bitset& lhs)
- {
- //empty bitset
- Bitset b(lhs);
- b.reserve(16);
- BOOST_TEST(b.capacity() >= 16);
- }
- static void reserve_test_two(const Bitset& lhs)
- {
- //bitset constructed with size "100"
- Bitset b(lhs);
- BOOST_TEST(b.capacity() >= 100);
- b.reserve(60);
- BOOST_TEST(b.size() == 100);
- BOOST_TEST(b.capacity() >= 100);
- b.reserve(160);
- BOOST_TEST(b.size() == 100);
- BOOST_TEST(b.capacity() >= 160);
- }
- static void shrink_to_fit_test_one(const Bitset& lhs)
- {
- //empty bitset
- Bitset b(lhs);
- b.shrink_to_fit();
- BOOST_TEST(b.size() == 0);
- BOOST_TEST(b.capacity() == 0);
- }
- static void shrink_to_fit_test_two(const Bitset& lhs)
- {
- //bitset constructed with size "100"
- Bitset b(lhs);
- b.shrink_to_fit();
- BOOST_TEST(b.capacity() >= 100);
- BOOST_TEST(b.size() == 100);
- b.reserve(200);
- BOOST_TEST(b.capacity() >= 200);
- BOOST_TEST(b.size() == 100);
- b.shrink_to_fit();
- BOOST_TEST(b.capacity() < 200);
- BOOST_TEST(b.size() == 100);
- }
- static void all(const Bitset& b)
- {
- BOOST_TEST(b.all() == (b.count() == b.size()));
- bool result = true;
- for(std::size_t i = 0; i < b.size(); ++i)
- if(!b[i]) {
- result = false;
- break;
- }
- BOOST_TEST(b.all() == result);
- }
- static void any(const Bitset& b)
- {
- BOOST_TEST(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_TEST(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_TEST(b.none() == result);
- // sanity
- BOOST_TEST(b.none() == !b.any());
- BOOST_TEST(b.none() == (b.count() == 0));
- }
- static void subset(const Bitset& a, const Bitset& b)
- {
- BOOST_TEST(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_TEST(a.count() == 0);
- BOOST_TEST(a.any() == false);
- //is_subset = (a.any() == false);
- }
- BOOST_TEST(a.is_subset_of(b) == is_subset);
- }
- static void proper_subset(const Bitset& a, const Bitset& b)
- {
- // PRE: a.size() == b.size()
- BOOST_TEST(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_TEST(a.count() < b.count());
- BOOST_TEST(b.any());
- }
- }
- }
- BOOST_TEST(a.is_proper_subset_of(b) == is_proper);
- if (is_proper)
- BOOST_TEST(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_TEST(a.intersects(b) == have_intersection);
- // also check commutativity
- BOOST_TEST(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_TEST(b.find_first() == Bitset::npos); // not found;
- else {
- BOOST_TEST(b.find_first() == i);
- BOOST_TEST(b.test(i) == true);
- }
- }
- static void find_next(const Bitset& b, typename Bitset::size_type prev)
- {
- BOOST_TEST(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_TEST(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_TEST(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_TEST(diff);
- }
- } else {
- for (std::size_t I = 0; I < a.size(); ++I)
- BOOST_TEST(a[I] == b[I]);
- }
- }
- static bool less_than(const Bitset& a, const Bitset& b)
- {
-
- typedef BOOST_DEDUCED_TYPENAME Bitset::size_type size_type;
-
- size_type asize(a.size());
- size_type bsize(b.size());
-
- if (!bsize)
- {
- return false;
- }
- else if (!asize)
- {
- return true;
- }
- else
- {
-
- // Compare from most significant to least.
-
- size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize));
- size_type I;
- for (I = 0; I < leqsize; ++I,--asize,--bsize)
- {
-
- size_type i = asize-1;
- size_type j = bsize-1;
-
- if (a[i] < b[j])
- return true;
- else if (a[i] > b[j])
- return false;
- // if (a[i] = b[j]) skip to next
- }
- return (a.size() < b.size());
- }
- }
- 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_TEST(a < b);
- else
- BOOST_TEST(!(a < b));
- }
- static void operator_greater_than(const Bitset& a, const Bitset& b)
- {
- if (less_than(a, b) || a == b)
- BOOST_TEST(!(a > b));
- else
- BOOST_TEST(a > b);
- }
- static void operator_less_than_eq(const Bitset& a, const Bitset& b)
- {
- if (less_than(a, b) || a == b)
- BOOST_TEST(a <= b);
- else
- BOOST_TEST(!(a <= b));
- }
- static void operator_greater_than_eq(const Bitset& a, const Bitset& b)
- {
- if (less_than(a, b))
- BOOST_TEST(!(a >= b));
- else
- BOOST_TEST(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_TEST(lhs.test(pos) == lhs[pos]);
- } else {
- // Not in range, doesn't satisfy precondition.
- }
- }
- static void test_set_bit(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.
- BOOST_TEST(lhs.test_set(pos, value) == prev[pos]);
- BOOST_TEST(lhs[pos] == value);
- // All other values of lhs remain unchanged
- for (std::size_t I = 0; I < N; ++I)
- if (I != pos)
- BOOST_TEST(lhs[I] == prev[I]);
- } else {
- // Not in range, doesn't satisfy precondition.
- }
- }
- static void operator_shift_left(const Bitset& lhs, std::size_t pos)
- {
- Bitset x(lhs);
- BOOST_TEST((lhs << pos) == (x <<= pos));
- }
- static void operator_shift_right(const Bitset& lhs, std::size_t pos)
- {
- Bitset x(lhs);
- BOOST_TEST((lhs >> pos) == (x >>= pos));
- }
- // operator|
- static
- void operator_or(const Bitset& lhs, const Bitset& rhs)
- {
- Bitset x(lhs);
- BOOST_TEST((lhs | rhs) == (x |= rhs));
- }
- // operator&
- static
- void operator_and(const Bitset& lhs, const Bitset& rhs)
- {
- Bitset x(lhs);
- BOOST_TEST((lhs & rhs) == (x &= rhs));
- }
- // operator^
- static
- void operator_xor(const Bitset& lhs, const Bitset& rhs)
- {
- Bitset x(lhs);
- BOOST_TEST((lhs ^ rhs) == (x ^= rhs));
- }
- // operator-
- static
- void operator_sub(const Bitset& lhs, const Bitset& rhs)
- {
- Bitset x(lhs);
- BOOST_TEST((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_TEST(false);
- }
- #else
- catch (const std::ios_base::failure &) {
- BOOST_TEST((except & s.rdstate()) != 0);
- did_throw = true;
- } catch (...) {
- did_throw = true;
- }
- #endif
- BOOST_TEST(did_throw || !stream_was_good || (s.width() == 0));
- if (!stream_was_good) {
- BOOST_TEST(s.good() == false);
- // this should actually be oldstate == s.rdstate()
- // but some implementations add badbit in the
- // sentry constructor
- //
- BOOST_TEST((oldstate & s.rdstate()) == oldstate);
- BOOST_TEST(s.width() == w);
- }
- else {
- if(!did_throw)
- BOOST_TEST(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 || static_cast<size_type>(w) < b.size()? b.size() : static_cast<size_type>(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_TEST(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_TEST(except == is.exceptions()); // paranoid
- #endif
- //------------------------------------------------------------------
- // postconditions
- BOOST_TEST(b.size() <= b.max_size());
- if(w > 0)
- BOOST_TEST(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_TEST(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_TEST(has_flags(is, std::ios::failbit));
- BOOST_TEST(b == a_copy);
- BOOST_TEST(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()
- ? static_cast<typename Bitset::size_type>(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_TEST(has_flags(is, std::ios::eofbit));
- else
- BOOST_TEST(!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_TEST(did_throw);
- }
- else {
- BOOST_TEST(has_flags(is, std::ios::failbit));
- }
- }
- else
- BOOST_TEST(!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_TEST(b == a_copy);
- #else
- BOOST_TEST(b.empty() == true);
- #endif
- }
- else {
- String sub = str.substr(after_spaces, num_digits);
- BOOST_TEST(b == Bitset(sub));
- }
- // check width
- BOOST_TEST(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_TEST(remainder == str.substr(after_digits));
- else
- BOOST_TEST(remainder == str);
- }
- };
- #endif // include guard
|