libs/dynamic_bitset/bitset_test.hpp

   1 // -----------------------------------------------------------
   2 //              Copyright (c) 2001 Jeremy Siek
   3 //        Copyright (c) 2003-2006, 2008 Gennaro Prota
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // -----------------------------------------------------------
  10
  11 #ifndef BOOST_BITSET_TEST_HPP_GP_20040319
  12 #define BOOST_BITSET_TEST_HPP_GP_20040319
  13
  14 #include "boost/config.hpp"
  15 #if !defined (BOOST_NO_STD_LOCALE)
  16 # include <locale>
  17 #endif
  18
  19 #include <vector>
  20 #include <fstream> // used for operator<<
  21 #include <string>    // for (basic_string and) getline()
  22 #include <algorithm> // for std::min
  23 #include <assert.h>  // <cassert> is sometimes macro-guarded :-(
  24
  25 #include "boost/limits.hpp"
  26 #include "boost/dynamic_bitset/dynamic_bitset.hpp"
  27 #include "boost/test/minimal.hpp"
  28
  29
  30 template <typename Block>
  31 inline bool nth_bit(Block num, std::size_t n)
  32 {
  33 #ifdef __BORLANDC__
  34   // Borland deduces Block as a const qualified type,
  35   // and thus finds numeric_limits<Block> to be zero :(
  36   //  (though not directly relevant here, see also
  37   //   lib issue 559)
  38   int block_width = sizeof(Block) * CHAR_BIT;
  39 #else
  40   int block_width = std::numeric_limits<Block>::digits;
  41 #endif
  42
  43   assert(n < (std::size_t) block_width);
  44   return (num >> n) & 1;
  45 }
  46
  47 // A long, 'irregular', string useful for various tests
  48 std::string get_long_string()
  49 {
  50   const char * const p =
  51   //    6         5         4         3         2         1
  52   // 3210987654321098765432109876543210987654321098765432109876543210
  53     "1110011100011110000011110000011111110000000000000110101110000000"
  54     "1010101000011100011101010111110000101011111000001111100011100011"
  55     "0000000110000001000000111100000111100010101111111000000011100011"
  56     "1111111111111111111111111111111111111111111111111111111111111100"
  57     "1000001100000001111111111111110000000011111000111100001010100000"
  58     "101000111100011010101110011011000000010";
  59
  60   return std::string(p);
  61 }
  62
  63 const char * test_file_name()
  64 {
  65   return "boost_dynamic_bitset_tests";
  66 }
  67
  68 #if defined BOOST_OLD_IOSTREAMS || defined BOOST_NO_STD_LOCALE
  69 template <typename Stream>
  70 bool is_one_or_zero(const Stream & /*s*/, char c)
  71 {
  72   return c == '1' || c == '0';
  73 }
  74 template <typename Stream>
  75 bool is_white_space(const Stream & /*s*/, char c)
  76 {
  77   return std::isspace(c);
  78 }
  79 #else
  80 template <typename Stream, typename Ch>
  81 bool is_one_or_zero(const Stream& s, Ch c)
  82 {
  83   typedef typename Stream::traits_type Tr;
  84   const Ch zero = s.widen('0');
  85   const Ch one  = s.widen('1');
  86
  87   return Tr::eq(c, one) || Tr::eq(c, zero);
  88 }
  89 template <typename Stream, typename Ch>
  90 bool is_white_space(const Stream & s, Ch c)
  91 {
  92   // NOTE: the using directive is to satisfy Borland 5.6.4
  93   //       with its own library (STLport), which doesn't
  94   //       like std::isspace(c, loc)
  95   using namespace std;
  96   return isspace(c, s.getloc());
  97 }
  98 #endif // defined BOOST_OLD_IOSTREAMS
  99
 100
 101 template <typename Stream>
 102 bool has_flags(const Stream& s, std::ios::iostate flags)
 103 {
 104   return (s.rdstate() & flags) != std::ios::goodbit;
 105 }
 106
 107
 108 // constructors
 109 //   default (can't do this generically)
 110
 111 template <typename Bitset>
 112 struct bitset_test {
 113
 114   typedef typename Bitset::block_type Block;
 115   BOOST_STATIC_CONSTANT(int, bits_per_block = Bitset::bits_per_block);
 116
 117   // from unsigned long
 118   //
 119   // Note: this is templatized so that we check that the do-the-right-thing
 120   // constructor dispatch is working correctly.
 121   //
 122   template <typename NumBits, typename Value>
 123   static void from_unsigned_long(NumBits num_bits, Value num)
 124   {
 125     // An object of size sz = num_bits is constructed:
 126     // - the first m bit positions are initialized to the corresponding
 127     //   bit values in num (m being the smaller of sz and ulong_width)
 128     //
 129     // - any remaining bit positions are initialized to zero
 130     //
 131
 132     Bitset b(num_bits, num);
 133
 134     // OK, we can now cast to size_type
 135     typedef typename Bitset::size_type size_type;
 136     const size_type sz = static_cast<size_type>(num_bits);
 137
 138     BOOST_CHECK(b.size() == sz);
 139
 140     const std::size_t ulong_width = std::numeric_limits<unsigned long>::digits;
 141     size_type m = sz;
 142     if (ulong_width < sz)
 143         m = ulong_width;
 144
 145     size_type i = 0;
 146     for ( ; i < m; ++i)
 147       BOOST_CHECK(b.test(i) == nth_bit(static_cast<unsigned long>(num), i));
 148     for ( ; i < sz; ++i)
 149       BOOST_CHECK(b.test(i) == 0);
 150   }
 151
 152   // from string
 153   //
 154   // Note: The corresponding function in dynamic_bitset (constructor
 155   // from a string) has several default arguments. Actually we don't
 156   // test the correct working of those defaults here (except for the
 157   // default of num_bits). I'm not sure what to do in this regard.
 158   //
 159   // Note2: the default argument expression for num_bits doesn't use
 160   //        static_cast, to avoid a gcc 2.95.3 'sorry, not implemented'
 161   //
 162   template <typename Ch, typename Tr, typename Al>
 163   static void from_string(const std::basic_string<Ch, Tr, Al>& str,
 164                           std::size_t pos,
 165                           std::size_t max_char,
 166                           std::size_t num_bits = (std::size_t)(-1))
 167   {
 168
 169       std::size_t rlen = (std::min)(max_char, str.size() - pos);
 170
 171       // The resulting size N of the bitset is num_bits, if
 172       // that is different from the default arg, rlen otherwise.
 173       // Put M = the smaller of N and rlen, then character
 174       // position pos + M - 1 corresponds to bit position zero.
 175       // Subsequent decreasing character positions correspond to
 176       // increasing bit positions.
 177
 178       const bool size_upon_string = num_bits == (std::size_t)(-1);
 179       Bitset b = size_upon_string ?
 180                     Bitset(str, pos, max_char)
 181                   : Bitset(str, pos, max_char, num_bits);
 182
 183       const std::size_t actual_size = size_upon_string? rlen : num_bits;
 184       BOOST_CHECK(b.size() == actual_size);
 185       std::size_t m = (std::min)(num_bits, rlen);
 186       std::size_t j;
 187       for (j = 0; j < m; ++j)
 188           BOOST_CHECK(b[j] == (str[pos + m - 1 - j] == '1'));
 189       // If M < N, remaining bit positions are zero
 190       for (; j < actual_size; ++j)
 191           BOOST_CHECK(b[j] == 0);
 192
 193
 194   }
 195
 196   static void to_block_range(const Bitset & b /*, BlockOutputIterator result*/)
 197   {
 198     typedef typename Bitset::size_type size_type;
 199
 200     Block sentinel = 0xF0;
 201     int s = 8; // number of sentinels (must be *even*)
 202     int offset = s/2;
 203     std::vector<Block> v(b.num_blocks() + s, sentinel);
 204
 205     boost::to_block_range(b, v.begin() + offset);
 206
 207     assert(v.size() >= (size_type)s && (s >= 2) && (s % 2 == 0));
 208     // check sentinels at both ends
 209     for(int i = 0; i < s/2; ++i) {
 210         BOOST_CHECK(v[i] == sentinel);
 211         BOOST_CHECK(v[v.size()-1-i] == sentinel);
 212     }
 213
 214     typename std::vector<Block>::const_iterator p = v.begin() + offset;
 215     for(size_type n = 0; n < b.num_blocks(); ++n, ++p) {
 216       typename Bitset::block_width_type i = 0;
 217       for(; i < bits_per_block; ++i) {
 218         size_type bit = n * bits_per_block + i;
 219         BOOST_CHECK(nth_bit(*p, i) == (bit < b.size()? b[bit] : 0));
 220       }
 221     }
 222   }
 223
 224   // TODO from_block_range (below) should be splitted
 225
 226   // PRE: std::equal(first1, last1, first2) == true
 227   static void from_block_range(const std::vector<Block>& blocks)
 228   {
 229     { // test constructor from block range
 230       Bitset bset(blocks.begin(), blocks.end());
 231       std::size_t n = blocks.size();
 232       for (std::size_t b = 0; b < n; ++b) {
 233         typename Bitset::block_width_type i = 0;
 234         for (; i < bits_per_block; ++i) {
 235           std::size_t bit = b * bits_per_block + i;
 236           BOOST_CHECK(bset[bit] == nth_bit(blocks[b], i));
 237         }
 238       }
 239       BOOST_CHECK(bset.size() == n * bits_per_block);
 240     }
 241     { // test boost::from_block_range
 242       const typename Bitset::size_type n = blocks.size();
 243       Bitset bset(n * bits_per_block);
 244       boost::from_block_range(blocks.begin(), blocks.end(), bset);
 245       for (std::size_t b = 0; b < n; ++b) {
 246         typename Bitset::block_width_type i = 0;
 247         for (; i < bits_per_block; ++i) {
 248           std::size_t bit = b * bits_per_block + i;
 249           BOOST_CHECK(bset[bit] == nth_bit(blocks[b], i));
 250         }
 251       }
 252       BOOST_CHECK(n <= bset.num_blocks());
 253     }
 254   }
 255
 256   // copy constructor (absent from std::bitset)
 257   static void copy_constructor(const Bitset& b)
 258   {
 259     Bitset copy(b);
 260     BOOST_CHECK(b == copy);
 261
 262     // Changes to the copy do not affect the original
 263     if (b.size() > 0) {
 264       std::size_t pos = copy.size() / 2;
 265       copy.flip(pos);
 266       BOOST_CHECK(copy[pos] != b[pos]);
 267     }
 268   }
 269
 270   // assignment operator (absent from std::bitset)
 271   static void assignment_operator(const Bitset& lhs, const Bitset& rhs)
 272   {
 273     Bitset b(lhs);
 274     b = rhs;
 275     BOOST_CHECK(b == rhs);
 276
 277     // Changes to the copy do not affect the original
 278     if (b.size() > 0) {
 279       std::size_t pos = b.size() / 2;
 280       b.flip(pos);
 281       BOOST_CHECK(b[pos] != rhs[pos]);
 282     }
 283   }
 284
 285   static void swap(const Bitset& lhs, const Bitset& rhs)
 286   {
 287     // bitsets must be swapped
 288     Bitset copy1(lhs);
 289     Bitset copy2(rhs);
 290     copy1.swap(copy2);
 291
 292     BOOST_CHECK(copy1 == rhs);
 293     BOOST_CHECK(copy2 == lhs);
 294
 295     // references must be stable under a swap
 296     for(typename Bitset::size_type i = 0; i < lhs.size(); ++i) {
 297       Bitset b1(lhs);
 298       Bitset b2(rhs);
 299       typename Bitset::reference ref = b1[i];
 300       bool x = ref;
 301       if (i < b2.size())
 302         b2[i] = !x; // make sure b2[i] is different
 303       b1.swap(b2);
 304       BOOST_CHECK(b2[i] == x); // now it must be equal..
 305       b2.flip(i);
 306       BOOST_CHECK(ref == b2[i]); // .. and ref must be into b2
 307       BOOST_CHECK(ref == !x);
 308     }
 309
 310   }
 311
 312   static void resize(const Bitset& lhs)
 313   {
 314     Bitset b(lhs);
 315
 316     // Test no change in size
 317     b.resize(lhs.size());
 318     BOOST_CHECK(b == lhs);
 319
 320     // Test increase in size
 321     b.resize(lhs.size() * 2, true);
 322
 323     std::size_t i;
 324     for (i = 0; i < lhs.size(); ++i)
 325       BOOST_CHECK(b[i] == lhs[i]);
 326     for (; i < b.size(); ++i)
 327       BOOST_CHECK(b[i] == true);
 328
 329     // Test decrease in size
 330     b.resize(lhs.size());
 331     for (i = 0; i < lhs.size(); ++i)
 332       BOOST_CHECK(b[i] == lhs[i]);
 333   }
 334
 335   static void clear(const Bitset& lhs)
 336   {
 337     Bitset b(lhs);
 338     b.clear();
 339     BOOST_CHECK(b.size() == 0);
 340   }
 341
 342   static void append_bit(const Bitset& lhs)
 343   {
 344     Bitset b(lhs);
 345     b.push_back(true);
 346     BOOST_CHECK(b.size() == lhs.size() + 1);
 347     BOOST_CHECK(b[b.size() - 1] == true);
 348     for (std::size_t i = 0; i < lhs.size(); ++i)
 349       BOOST_CHECK(b[i] == lhs[i]);
 350
 351     b.push_back(false);
 352     BOOST_CHECK(b.size() == lhs.size() + 2);
 353     BOOST_CHECK(b[b.size() - 1] == false);
 354     BOOST_CHECK(b[b.size() - 2] == true);
 355     for (std::size_t j = 0; j < lhs.size(); ++j)
 356       BOOST_CHECK(b[j] == lhs[j]);
 357   }
 358
 359   static void append_block(const Bitset& lhs)
 360   {
 361     Bitset b(lhs);
 362     Block value(128);
 363     b.append(value);
 364     BOOST_CHECK(b.size() == lhs.size() + bits_per_block);
 365     for (typename Bitset::block_width_type i = 0; i < bits_per_block; ++i)
 366       BOOST_CHECK(b[lhs.size() + i] == bool((value >> i) & 1));
 367   }
 368
 369   static void append_block_range(const Bitset& lhs, const std::vector<Block>& blocks)
 370   {
 371     Bitset b(lhs), c(lhs);
 372     b.append(blocks.begin(), blocks.end());
 373     for (typename std::vector<Block>::const_iterator i = blocks.begin();
 374          i != blocks.end(); ++i)
 375       c.append(*i);
 376     BOOST_CHECK(b == c);
 377   }
 378
 379   // operator[] and reference members
 380   // PRE: b[i] == bit_vec[i]
 381   static void operator_bracket(const Bitset& lhs, const std::vector<bool>& bit_vec)
 382   {
 383     Bitset b(lhs);
 384     std::size_t i, j, k;
 385
 386     // x = b[i]
 387     // x = ~b[i]
 388     for (i = 0; i < b.size(); ++i) {
 389       bool x = b[i];
 390       BOOST_CHECK(x == bit_vec[i]);
 391       x = ~b[i];
 392       BOOST_CHECK(x == !bit_vec[i]);
 393     }
 394     Bitset prev(b);
 395
 396     // b[i] = x
 397     for (j = 0; j < b.size(); ++j) {
 398       bool x = !prev[j];
 399       b[j] = x;
 400       for (k = 0; k < b.size(); ++k)
 401         if (j == k)
 402           BOOST_CHECK(b[k] == x);
 403         else
 404           BOOST_CHECK(b[k] == prev[k]);
 405       b[j] = prev[j];
 406     }
 407     b.flip();
 408
 409     // b[i] = b[j]
 410     for (i = 0; i < b.size(); ++i) {
 411       b[i] = prev[i];
 412       for (j = 0; j < b.size(); ++j) {
 413         if (i == j)
 414           BOOST_CHECK(b[j] == prev[j]);
 415         else
 416           BOOST_CHECK(b[j] == !prev[j]);
 417       }
 418       b[i] = !prev[i];
 419     }
 420
 421     // b[i].flip()
 422     for (i = 0; i < b.size(); ++i) {
 423       b[i].flip();
 424       for (j = 0; j < b.size(); ++j) {
 425         if (i == j)
 426           BOOST_CHECK(b[j] == prev[j]);
 427         else
 428           BOOST_CHECK(b[j] == !prev[j]);
 429       }
 430       b[i].flip();
 431     }
 432   }
 433
 434   //===========================================================================
 435   // bitwise operators
 436
 437   // bitwise and assignment
 438
 439   // PRE: b.size() == rhs.size()
 440   static void and_assignment(const Bitset& b, const Bitset& rhs)
 441   {
 442     Bitset lhs(b);
 443     Bitset prev(lhs);
 444     lhs &= rhs;
 445     // Clears each bit in lhs for which the corresponding bit in rhs is
 446     // clear, and leaves all other bits unchanged.
 447     for (std::size_t I = 0; I < lhs.size(); ++I)
 448       if (rhs[I] == 0)
 449         BOOST_CHECK(lhs[I] == 0);
 450       else
 451         BOOST_CHECK(lhs[I] == prev[I]);
 452   }
 453
 454   // PRE: b.size() == rhs.size()
 455   static void or_assignment(const Bitset& b, const Bitset& rhs)
 456   {
 457     Bitset lhs(b);
 458     Bitset prev(lhs);
 459     lhs |= rhs;
 460     // Sets each bit in lhs for which the corresponding bit in rhs is set, and
 461     // leaves all other bits unchanged.
 462     for (std::size_t I = 0; I < lhs.size(); ++I)
 463       if (rhs[I] == 1)
 464         BOOST_CHECK(lhs[I] == 1);
 465       else
 466         BOOST_CHECK(lhs[I] == prev[I]);
 467   }
 468
 469   // PRE: b.size() == rhs.size()
 470   static void xor_assignment(const Bitset& b, const Bitset& rhs)
 471   {
 472     Bitset lhs(b);
 473     Bitset prev(lhs);
 474     lhs ^= rhs;
 475     // Flips each bit in lhs for which the corresponding bit in rhs is set,
 476     // and leaves all other bits unchanged.
 477     for (std::size_t I = 0; I < lhs.size(); ++I)
 478       if (rhs[I] == 1)
 479         BOOST_CHECK(lhs[I] == !prev[I]);
 480       else
 481         BOOST_CHECK(lhs[I] == prev[I]);
 482   }
 483
 484   // PRE: b.size() == rhs.size()
 485   static void sub_assignment(const Bitset& b, const Bitset& rhs)
 486   {
 487     Bitset lhs(b);
 488     Bitset prev(lhs);
 489     lhs -= rhs;
 490     // Resets each bit in lhs for which the corresponding bit in rhs is set,
 491     // and leaves all other bits unchanged.
 492     for (std::size_t I = 0; I < lhs.size(); ++I)
 493       if (rhs[I] == 1)
 494         BOOST_CHECK(lhs[I] == 0);
 495       else
 496         BOOST_CHECK(lhs[I] == prev[I]);
 497   }
 498
 499   static void shift_left_assignment(const Bitset& b, std::size_t pos)
 500   {
 501     Bitset lhs(b);
 502     Bitset prev(lhs);
 503     lhs <<= pos;
 504     // Replaces each bit at position I in lhs with the following value:
 505     // - If I < pos, the new value is zero
 506     // - If I >= pos, the new value is the previous value of the bit at
 507     //   position I - pos
 508     for (std::size_t I = 0; I < lhs.size(); ++I)
 509       if (I < pos)
 510         BOOST_CHECK(lhs[I] == 0);
 511       else
 512         BOOST_CHECK(lhs[I] == prev[I - pos]);
 513   }
 514
 515   static void shift_right_assignment(const Bitset& b, std::size_t pos)
 516   {
 517     Bitset lhs(b);
 518     Bitset prev(lhs);
 519     lhs >>= pos;
 520     // Replaces each bit at position I in lhs with the following value:
 521     // - If pos >= N - I, the new value is zero
 522     // - If pos < N - I, the new value is the previous value of the bit at
 523     //    position I + pos
 524     std::size_t N = lhs.size();
 525     for (std::size_t I = 0; I < N; ++I)
 526       if (pos >= N - I)
 527         BOOST_CHECK(lhs[I] == 0);
 528       else
 529         BOOST_CHECK(lhs[I] == prev[I + pos]);
 530   }
 531
 532
 533   static void set_all(const Bitset& b)
 534   {
 535     Bitset lhs(b);
 536     lhs.set();
 537     for (std::size_t I = 0; I < lhs.size(); ++I)
 538       BOOST_CHECK(lhs[I] == 1);
 539   }
 540
 541   static void set_one(const Bitset& b, std::size_t pos, bool value)
 542   {
 543     Bitset lhs(b);
 544     std::size_t N = lhs.size();
 545     if (pos < N) {
 546       Bitset prev(lhs);
 547       // Stores a new value in the bit at position pos in lhs.
 548       lhs.set(pos, value);
 549       BOOST_CHECK(lhs[pos] == value);
 550
 551       // All other values of lhs remain unchanged
 552       for (std::size_t I = 0; I < N; ++I)
 553         if (I != pos)
 554           BOOST_CHECK(lhs[I] == prev[I]);
 555     } else {
 556       // Not in range, doesn't satisfy precondition.
 557     }
 558   }
 559
 560   static void reset_all(const Bitset& b)
 561   {
 562     Bitset lhs(b);
 563     // Resets all bits in lhs
 564     lhs.reset();
 565     for (std::size_t I = 0; I < lhs.size(); ++I)
 566       BOOST_CHECK(lhs[I] == 0);
 567   }
 568
 569   static void reset_one(const Bitset& b, std::size_t pos)
 570   {
 571     Bitset lhs(b);
 572     std::size_t N = lhs.size();
 573     if (pos < N) {
 574       Bitset prev(lhs);
 575       lhs.reset(pos);
 576       // Resets the bit at position pos in lhs
 577       BOOST_CHECK(lhs[pos] == 0);
 578
 579       // All other values of lhs remain unchanged
 580       for (std::size_t I = 0; I < N; ++I)
 581         if (I != pos)
 582           BOOST_CHECK(lhs[I] == prev[I]);
 583     } else {
 584       // Not in range, doesn't satisfy precondition.
 585     }
 586   }
 587
 588   static void operator_flip(const Bitset& b)
 589   {
 590     Bitset lhs(b);
 591     Bitset x(lhs);
 592     BOOST_CHECK(~lhs == x.flip());
 593   }
 594
 595   static void flip_all(const Bitset& b)
 596   {
 597     Bitset lhs(b);
 598     std::size_t N = lhs.size();
 599     Bitset prev(lhs);
 600     lhs.flip();
 601     // Toggles all the bits in lhs
 602     for (std::size_t I = 0; I < N; ++I)
 603       BOOST_CHECK(lhs[I] == !prev[I]);
 604   }
 605
 606   static void flip_one(const Bitset& b, std::size_t pos)
 607   {
 608     Bitset lhs(b);
 609     std::size_t N = lhs.size();
 610     if (pos < N) {
 611       Bitset prev(lhs);
 612       lhs.flip(pos);
 613       // Toggles the bit at position pos in lhs
 614       BOOST_CHECK(lhs[pos] == !prev[pos]);
 615
 616       // All other values of lhs remain unchanged
 617       for (std::size_t I = 0; I < N; ++I)
 618         if (I != pos)
 619           BOOST_CHECK(lhs[I] == prev[I]);
 620     } else {
 621       // Not in range, doesn't satisfy precondition.
 622     }
 623   }
 624
 625   // empty
 626   static void empty(const Bitset& b)
 627   {
 628     BOOST_CHECK(b.empty() == (b.size() == 0));
 629   }
 630
 631   // to_ulong()
 632   static void to_ulong(const Bitset& lhs)
 633   {
 634     typedef unsigned long result_type;
 635     std::size_t n = std::numeric_limits<result_type>::digits;
 636     std::size_t sz = lhs.size();
 637
 638     bool will_overflow = false;
 639     for (std::size_t i = n; i < sz; ++i) {
 640       if (lhs.test(i) != 0) {
 641         will_overflow = true;
 642         break;
 643       }
 644     }
 645     if (will_overflow) {
 646       try {
 647         (void)lhs.to_ulong();
 648         BOOST_CHECK(false); // It should have thrown an exception
 649       } catch (std::overflow_error & ex) {
 650         // Good!
 651         BOOST_CHECK(!!ex.what());
 652       } catch (...) {
 653         BOOST_CHECK(false); // threw the wrong exception
 654       }
 655     } else {
 656       result_type num = lhs.to_ulong();
 657       // Be sure the number is right
 658       if (sz == 0)
 659         BOOST_CHECK(num == 0);
 660       else {
 661         for (std::size_t i = 0; i < sz; ++i)
 662           BOOST_CHECK(lhs[i] == (i < n ? nth_bit(num, i) : 0));
 663       }
 664     }
 665   }
 666
 667   // to_string()
 668   static void to_string(const Bitset& b)
 669   {
 670     std::string str;
 671     boost::to_string(b, str);
 672     BOOST_CHECK(str.size() == b.size());
 673     for (std::size_t i = 0; i < b.size(); ++i)
 674       BOOST_CHECK(str[b.size() - 1 - i] ==(b.test(i)? '1':'0'));
 675   }
 676
 677   static void count(const Bitset& b)
 678   {
 679     std::size_t c = b.count();
 680     std::size_t actual = 0;
 681     for (std::size_t i = 0; i < b.size(); ++i)
 682       if (b[i])
 683         ++actual;
 684     BOOST_CHECK(c == actual);
 685   }
 686
 687   static void size(const Bitset& b)
 688   {
 689     BOOST_CHECK(Bitset(b).set().count() == b.size());
 690   }
 691
 692   static void any(const Bitset& b)
 693   {
 694     //BOOST_CHECK(b.any() == (b.count() > 0));
 695     bool result = false;
 696     for(std::size_t i = 0; i < b.size(); ++i)
 697       if(b[i]) {
 698         result = true;
 699         break;
 700       }
 701     BOOST_CHECK(b.any() == result);
 702   }
 703
 704   static void none(const Bitset& b)
 705   {
 706     bool result = true;
 707     for(std::size_t i = 0; i < b.size(); ++i) {
 708       if(b[i]) {
 709         result = false;
 710         break;
 711       }
 712     }
 713     BOOST_CHECK(b.none() == result);
 714
 715     // sanity
 716     BOOST_CHECK(b.none() == !b.any());
 717     BOOST_CHECK(b.none() == (b.count() == 0));
 718   }
 719
 720   static void subset(const Bitset& a, const Bitset& b)
 721   {
 722     BOOST_CHECK(a.size() == b.size()); // PRE
 723
 724     bool is_subset = true;
 725     if (b.size()) { // could use b.any() but let's be safe
 726       for(std::size_t i = 0; i < a.size(); ++i) {
 727         if(a.test(i) && !b.test(i)) {
 728           is_subset = false;
 729           break;
 730         }
 731       }
 732     }
 733     else {
 734       // sanity
 735       BOOST_CHECK(a.count() == 0);
 736       BOOST_CHECK(a.any() == false);
 737
 738       //is_subset = (a.any() == false);
 739     }
 740
 741     BOOST_CHECK(a.is_subset_of(b) == is_subset);
 742   }
 743
 744   static void proper_subset(const Bitset& a, const Bitset& b)
 745   {
 746     // PRE: a.size() == b.size()
 747     BOOST_CHECK(a.size() == b.size());
 748
 749     bool is_proper = false;
 750
 751     if (b.size() != 0) {
 752
 753       // check it's a subset
 754       subset(a, b);
 755
 756       // is it proper?
 757       for (std::size_t i = 0; i < a.size(); ++i) {
 758         if (!a.test(i) && b.test(i)) {
 759           is_proper = true;
 760           // sanity
 761           BOOST_CHECK(a.count() < b.count());
 762           BOOST_CHECK(b.any());
 763         }
 764       }
 765     }
 766
 767     BOOST_CHECK(a.is_proper_subset_of(b) == is_proper);
 768     if (is_proper)
 769       BOOST_CHECK(b.is_proper_subset_of(a) != is_proper);// antisymmetry
 770   }
 771
 772   static void intersects(const Bitset& a, const Bitset& b)
 773   {
 774     bool have_intersection = false;
 775
 776     typename Bitset::size_type m = a.size() < b.size() ? a.size() : b.size();
 777     for(typename Bitset::size_type i = 0; i < m && !have_intersection; ++i)
 778       if(a[i] == true && b[i] == true)
 779         have_intersection = true;
 780
 781     BOOST_CHECK(a.intersects(b) == have_intersection);
 782     // also check commutativity
 783     BOOST_CHECK(b.intersects(a) == have_intersection);
 784   }
 785
 786   static void find_first(const Bitset& b)
 787   {
 788       // find first non-null bit, if any
 789       typename Bitset::size_type i = 0;
 790       while (i < b.size() && b[i] == 0)
 791           ++i;
 792
 793       if (i == b.size())
 794         BOOST_CHECK(b.find_first() == Bitset::npos); // not found;
 795       else {
 796         BOOST_CHECK(b.find_first() == i);
 797         BOOST_CHECK(b.test(i) == true);
 798       }
 799
 800   }
 801
 802   static void find_next(const Bitset& b, typename Bitset::size_type prev)
 803   {
 804     BOOST_CHECK(next_bit_on(b, prev) == b.find_next(prev));
 805   }
 806
 807   static void operator_equal(const Bitset& a, const Bitset& b)
 808   {
 809     if (a == b) {
 810       for (std::size_t I = 0; I < a.size(); ++I)
 811         BOOST_CHECK(a[I] == b[I]);
 812     } else {
 813       if (a.size() == b.size()) {
 814         bool diff = false;
 815         for (std::size_t I = 0; I < a.size(); ++I)
 816           if (a[I] != b[I]) {
 817             diff = true;
 818             break;
 819           }
 820         BOOST_CHECK(diff);
 821       }
 822     }
 823   }
 824
 825   static void operator_not_equal(const Bitset& a, const Bitset& b)
 826   {
 827     if (a != b) {
 828       if (a.size() == b.size()) {
 829         bool diff = false;
 830         for (std::size_t I = 0; I < a.size(); ++I)
 831           if (a[I] != b[I]) {
 832             diff = true;
 833             break;
 834           }
 835         BOOST_CHECK(diff);
 836       }
 837     } else {
 838       for (std::size_t I = 0; I < a.size(); ++I)
 839         BOOST_CHECK(a[I] == b[I]);
 840     }
 841   }
 842
 843   static bool less_than(const Bitset& a, const Bitset& b)
 844   {
 845     // Compare from most significant to least.
 846     // Careful, don't send unsigned int into negative territory!
 847     if (a.size() == 0)
 848       return false;
 849
 850     std::size_t I;
 851     for (I = a.size() - 1; I > 0; --I)
 852       if (a[I] < b[I])
 853         return true;
 854       else if (a[I] > b[I])
 855         return false;
 856       // if (a[I] = b[I]) skip to next
 857
 858     if (a[0] < b[0])
 859       return true;
 860     else
 861       return false;
 862   }
 863
 864   static typename Bitset::size_type next_bit_on(const Bitset& b, typename Bitset::size_type prev)
 865   {
 866       // helper function for find_next()
 867       //
 868
 869       if (b.none() == true || prev == Bitset::npos)
 870           return Bitset::npos;
 871
 872       ++prev;
 873
 874       if (prev >= b.size())
 875           return Bitset::npos;
 876
 877       typename Bitset::size_type i = prev;
 878       while (i < b.size() && b[i] == 0)
 879           ++i;
 880
 881       return i==b.size() ? Bitset::npos : i;
 882
 883   }
 884
 885   static void operator_less_than(const Bitset& a, const Bitset& b)
 886   {
 887     if (less_than(a, b))
 888       BOOST_CHECK(a < b);
 889     else
 890       BOOST_CHECK(!(a < b));
 891   }
 892
 893   static void operator_greater_than(const Bitset& a, const Bitset& b)
 894   {
 895     if (less_than(a, b) || a == b)
 896       BOOST_CHECK(!(a > b));
 897     else
 898       BOOST_CHECK(a > b);
 899   }
 900
 901   static void operator_less_than_eq(const Bitset& a, const Bitset& b)
 902   {
 903     if (less_than(a, b) || a == b)
 904       BOOST_CHECK(a <= b);
 905     else
 906       BOOST_CHECK(!(a <= b));
 907   }
 908
 909   static void operator_greater_than_eq(const Bitset& a, const Bitset& b)
 910   {
 911     if (less_than(a, b))
 912       BOOST_CHECK(!(a >= b));
 913     else
 914       BOOST_CHECK(a >= b);
 915   }
 916
 917   static void test_bit(const Bitset& b, std::size_t pos)
 918   {
 919     Bitset lhs(b);
 920     std::size_t N = lhs.size();
 921     if (pos < N) {
 922       BOOST_CHECK(lhs.test(pos) == lhs[pos]);
 923     } else {
 924       // Not in range, doesn't satisfy precondition.
 925     }
 926   }
 927
 928   static void operator_shift_left(const Bitset& lhs, std::size_t pos)
 929   {
 930     Bitset x(lhs);
 931     BOOST_CHECK((lhs << pos) == (x <<= pos));
 932   }
 933
 934   static void operator_shift_right(const Bitset& lhs, std::size_t pos)
 935   {
 936     Bitset x(lhs);
 937     BOOST_CHECK((lhs >> pos) == (x >>= pos));
 938   }
 939
 940   // operator|
 941   static
 942   void operator_or(const Bitset& lhs, const Bitset& rhs)
 943   {
 944     Bitset x(lhs);
 945     BOOST_CHECK((lhs | rhs) == (x |= rhs));
 946   }
 947
 948   // operator&
 949   static
 950   void operator_and(const Bitset& lhs, const Bitset& rhs)
 951   {
 952     Bitset x(lhs);
 953     BOOST_CHECK((lhs & rhs) == (x &= rhs));
 954   }
 955
 956   // operator^
 957   static
 958   void operator_xor(const Bitset& lhs, const Bitset& rhs)
 959   {
 960     Bitset x(lhs);
 961     BOOST_CHECK((lhs ^ rhs) == (x ^= rhs));
 962   }
 963
 964   // operator-
 965   static
 966   void operator_sub(const Bitset& lhs, const Bitset& rhs)
 967   {
 968     Bitset x(lhs);
 969     BOOST_CHECK((lhs - rhs) == (x -= rhs));
 970   }
 971
 972 //------------------------------------------------------------------------------
 973 //                               I/O TESTS
 974    // The following tests assume the results of extraction (i.e.: contents,
 975    // state and width of is, contents of b) only depend on input (the string
 976    // str). In other words, they don't consider "unexpected" errors such as
 977    // stream corruption or out of memory. The reason is simple: if e.g. the
 978    // stream buffer throws, the stream layer may eat the exception and
 979    // transform it into a badbit. But we can't trust the stream state here,
 980    // because one of the things that we want to test is exactly whether it
 981    // is set correctly. Similarly for insertion.
 982    //
 983    // To provide for these cases would require that the test functions know
 984    // in advance whether the stream buffer and/or allocations will fail, and
 985    // when; that is, we should write both a special allocator and a special
 986    // stream buffer capable of throwing "on demand" and pass them here.
 987
 988    // Seems overkill for these kinds of unit tests.
 989   //-------------------------------------------------------------------------
 990
 991   // operator<<( [basic_]ostream,
 992   template <typename Stream>
 993   static void stream_inserter(const Bitset & b,
 994                               Stream & s,
 995                               const char * file_name
 996                               )
 997   {
 998 #if defined BOOST_OLD_IOSTREAMS
 999     typedef char char_type;
1000     typedef std::string string_type;
1001     typedef ifstream corresponding_input_stream_type;
1002 #else
1003     typedef typename Stream::char_type char_type;
1004     typedef std::basic_string<char_type> string_type;
1005     typedef std::basic_ifstream<char_type> corresponding_input_stream_type;
1006
1007     std::ios::iostate except = s.exceptions();
1008 #endif
1009
1010     typedef typename Bitset::size_type size_type;
1011     std::streamsize w = s.width();
1012     char_type fill_char = s.fill();
1013     std::ios::iostate oldstate = s.rdstate();
1014     bool stream_was_good = s.good();
1015
1016     bool did_throw = false;
1017     try {
1018       s << b;
1019     }
1020 #if defined BOOST_OLD_IOSTREAMS
1021     catch(...) {
1022       BOOST_CHECK(false);
1023     }
1024 #else
1025     catch (const std::ios_base::failure &) {
1026         BOOST_CHECK((except & s.rdstate()) != 0);
1027         did_throw = true;
1028     } catch (...) {
1029         did_throw = true;
1030     }
1031 #endif
1032
1033     BOOST_CHECK(did_throw || !stream_was_good || (s.width() == 0));
1034
1035     if (!stream_was_good) {
1036       BOOST_CHECK(s.good() == false);
1037
1038       // this should actually be oldstate == s.rdstate()
1039       // but some implementations add badbit in the
1040       // sentry constructor
1041       //
1042       BOOST_CHECK((oldstate & s.rdstate()) == oldstate);
1043       BOOST_CHECK(s.width() == w);
1044     }
1045     else {
1046       if(!did_throw)
1047         BOOST_CHECK(s.width() == 0);
1048       // This test require that os be an output _and_ input stream.
1049       // Of course dynamic_bitset's operator << doesn't require that.
1050
1051       size_type total_len = w <= 0 || (size_type)(w) < b.size()? b.size() : w;
1052       const string_type padding (total_len - b.size(), fill_char);
1053       string_type expected;
1054       boost::to_string(b, expected);
1055       if ((s.flags() & std::ios::adjustfield) != std::ios::left)
1056         expected = padding + expected;
1057       else
1058         expected = expected + padding;
1059
1060       assert(expected.length() == total_len);
1061
1062       // close, and reopen the file stream to verify contents
1063       s.close();
1064       corresponding_input_stream_type is(file_name);
1065       string_type contents;
1066       std::getline(is, contents, char_type());
1067       BOOST_CHECK(contents == expected);
1068     }
1069   }
1070
1071   // operator>>( [basic_]istream
1072   template <typename Stream, typename String>
1073   static void stream_extractor(Bitset& b,
1074                                Stream& is,
1075                                String& str
1076                               )
1077   {
1078     // save necessary info then do extraction
1079     //
1080     const std::streamsize w = is.width();
1081     Bitset a_copy(b);
1082     bool stream_was_good = is.good();
1083
1084     bool did_throw = false;
1085
1086 #if defined BOOST_OLD_IOSTREAMS
1087     bool has_stream_exceptions = false;
1088     is >> b;
1089 #else
1090     const std::ios::iostate except = is.exceptions();
1091     bool has_stream_exceptions = true;
1092     try {
1093       is >> b;
1094     }
1095     catch(const std::ios::failure &) {
1096       did_throw = true;
1097     }
1098
1099     // postconditions
1100     BOOST_CHECK(except == is.exceptions()); // paranoid
1101 #endif
1102     //------------------------------------------------------------------
1103
1104     // postconditions
1105     BOOST_CHECK(b.size() <= b.max_size());
1106     if(w > 0)
1107       BOOST_CHECK(b.size() <= static_cast<typename Bitset::size_type>(w));
1108
1109     // throw if and only if required
1110     if(has_stream_exceptions) {
1111         const bool exceptional_state = has_flags(is, is.exceptions());
1112         BOOST_CHECK(exceptional_state == did_throw);
1113     }
1114
1115     typedef typename String::size_type size_type;
1116     typedef typename String::value_type Ch;
1117     size_type after_digits = 0;
1118
1119     if(!stream_was_good) {
1120         BOOST_CHECK(has_flags(is, std::ios::failbit));
1121         BOOST_CHECK(b == a_copy);
1122         BOOST_CHECK(is.width() == (did_throw ? w : 0));
1123     }
1124     else {
1125       // stream was good(), parse the string;
1126       // it may contain three parts, all of which are optional
1127       // {spaces}   {digits}   {non-digits}
1128       //        opt        opt            opt
1129       //
1130       // The values of b.max_size() and is.width() may lead to
1131       // ignore part of the digits, if any.
1132
1133       size_type pos = 0;
1134       size_type len = str.length();
1135       // {spaces}
1136       for( ; pos < len && is_white_space(is, str[pos]); ++pos)
1137         {}
1138       size_type after_spaces = pos;
1139       // {digits} or part of them
1140       const typename Bitset::size_type max_digits =
1141             w > 0 && static_cast<typename Bitset::size_type>(w) < b.max_size()
1142                                ? w : b.max_size();
1143
1144       for( ; pos < len && (pos - after_spaces) < max_digits; ++pos) {
1145           if(!is_one_or_zero(is, str[pos]))
1146               break;
1147       }
1148       after_digits = pos;
1149       size_type num_digits = after_digits - after_spaces;
1150
1151       // eofbit
1152       if((after_digits == len && max_digits > num_digits ))
1153           BOOST_CHECK(has_flags(is, std::ios::eofbit));
1154       else
1155           BOOST_CHECK(!has_flags(is, std::ios::eofbit));
1156
1157       // failbit <=> there are no digits, except for the library
1158       // issue explained below.
1159       //
1160       if(num_digits == 0) {
1161         if(after_digits == len && has_stream_exceptions &&
1162             (is.exceptions() & std::ios::eofbit) != std::ios::goodbit) {
1163                 // This is a special case related to library issue 195:
1164                 // reaching eof when skipping whitespaces in the sentry ctor.
1165                 // The resolution says the sentry constructor should set *both*
1166                 // eofbit and failbit; but many implementations deliberately
1167                 // set eofbit only. See for instance:
1168                 //  http://gcc.gnu.org/ml/libstdc++/2000-q1/msg00086.html
1169                 //
1170                 BOOST_CHECK(did_throw);
1171
1172             }
1173         else {
1174             BOOST_CHECK(has_flags(is, std::ios::failbit));
1175         }
1176       }
1177       else
1178         BOOST_CHECK(!has_flags(is, std::ios::failbit));
1179
1180
1181       if(num_digits == 0 && after_digits == len) {
1182         // The VC6 library has a bug/non-conformity in the sentry
1183         // constructor. It uses code like
1184         //  // skip whitespaces...
1185         //  int_type _C = rdbuf()->sgetc();
1186         //  while (!_Tr::eq_int_type(_Tr::eof(), _C) ...
1187         //
1188         // For an empty file the while statement is never "entered"
1189         // and the stream remains in good() state; thus the sentry
1190         // object gives "true" when converted to bool. This is worse
1191         // than the case above, because not only failbit is not set,
1192         // but no bit is set at all, end we end up clearing the
1193         // bitset though there's nothing in the file to be extracted.
1194         // Note that the dynamic_bitset docs say a sentry object is
1195         // constructed and then converted to bool, thus we rely on
1196         // what the underlying library does.
1197         //
1198 #if !defined(BOOST_DINKUMWARE_STDLIB) || (BOOST_DINKUMWARE_STDLIB >= 306)
1199         BOOST_CHECK(b == a_copy);
1200 #else
1201         BOOST_CHECK(b.empty() == true);
1202 #endif
1203       }
1204       else {
1205         String sub = str.substr(after_spaces, num_digits);
1206         BOOST_CHECK(b == Bitset(sub));
1207       }
1208
1209       // check width
1210       BOOST_CHECK(is.width() == 0
1211                   || (after_digits == len && num_digits == 0 && did_throw));
1212     }
1213
1214
1215     // clear the stream to allow further reading then
1216     // retrieve any remaining chars with a single getline()
1217     is.exceptions(std::ios::goodbit);
1218     is.clear();
1219     String remainder;
1220     std::getline(is, remainder, Ch());
1221     if(stream_was_good)
1222       BOOST_CHECK(remainder == str.substr(after_digits));
1223     else
1224       BOOST_CHECK(remainder == str);
1225
1226   }
1227
1228
1229 };
1230
1231
1232
1233 #endif // include guard