libs/dynamic_bitset/dyn_bitset_unit_tests3.cpp

   1 // -----------------------------------------------------------
   2 //              Copyright (c) 2001 Jeremy Siek
   3 //           Copyright (c) 2003-2006 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 #include <assert.h>
  12 #include "bitset_test.hpp"
  13 #include "boost/dynamic_bitset/dynamic_bitset.hpp"
  14 #include "boost/limits.hpp"
  15 #include "boost/config.hpp"
  16
  17
  18 template <typename Block>
  19 void run_test_cases( BOOST_EXPLICIT_TEMPLATE_TYPE(Block) )
  20 {
  21   // a bunch of typedefs which will be handy later on
  22   typedef boost::dynamic_bitset<Block> bitset_type;
  23   typedef bitset_test<bitset_type> Tests;
  24   // typedef typename bitset_type::size_type size_type; // unusable with Borland 5.5.1
  25
  26   std::string long_string = get_long_string();
  27   std::size_t ul_width = std::numeric_limits<unsigned long>::digits;
  28
  29   //=====================================================================
  30   // Test b.empty()
  31   {
  32     bitset_type b;
  33     Tests::empty(b);
  34   }
  35   {
  36     bitset_type b(1, 1ul);
  37     Tests::empty(b);
  38   }
  39   {
  40     bitset_type b(bitset_type::bits_per_block
  41                   + bitset_type::bits_per_block/2, 15ul);
  42     Tests::empty(b);
  43   }
  44   //=====================================================================
  45   // Test b.to_long()
  46   {
  47     boost::dynamic_bitset<Block> b;
  48     Tests::to_ulong(b);
  49   }
  50   {
  51     boost::dynamic_bitset<Block> b(std::string("1"));
  52     Tests::to_ulong(b);
  53   }
  54   {
  55     boost::dynamic_bitset<Block> b(bitset_type::bits_per_block,
  56                                    static_cast<unsigned long>(-1));
  57     Tests::to_ulong(b);
  58   }
  59   {
  60     std::string str(ul_width - 1, '1');
  61     boost::dynamic_bitset<Block> b(str);
  62     Tests::to_ulong(b);
  63   }
  64   {
  65     std::string ul_str(ul_width, '1');
  66     boost::dynamic_bitset<Block> b(ul_str);
  67     Tests::to_ulong(b);
  68   }
  69   { // case overflow
  70     boost::dynamic_bitset<Block> b(long_string);
  71     Tests::to_ulong(b);
  72   }
  73   //=====================================================================
  74   // Test to_string(b, str)
  75   {
  76     boost::dynamic_bitset<Block> b;
  77     Tests::to_string(b);
  78   }
  79   {
  80     boost::dynamic_bitset<Block> b(std::string("0"));
  81     Tests::to_string(b);
  82   }
  83   {
  84     boost::dynamic_bitset<Block> b(long_string);
  85     Tests::to_string(b);
  86   }
  87   //=====================================================================
  88   // Test b.count()
  89   {
  90     boost::dynamic_bitset<Block> b;
  91     Tests::count(b);
  92   }
  93   {
  94     boost::dynamic_bitset<Block> b(std::string("0"));
  95     Tests::count(b);
  96   }
  97   {
  98     boost::dynamic_bitset<Block> b(std::string("1"));
  99     Tests::count(b);
 100   }
 101   {
 102     boost::dynamic_bitset<Block> b(8, 255ul);
 103     Tests::count(b);
 104   }
 105   {
 106     boost::dynamic_bitset<Block> b(long_string);
 107     Tests::count(b);
 108   }
 109   //=====================================================================
 110   // Test b.size()
 111   {
 112     boost::dynamic_bitset<Block> b;
 113     Tests::size(b);
 114   }
 115   {
 116     boost::dynamic_bitset<Block> b(std::string("0"));
 117     Tests::size(b);
 118   }
 119   {
 120     boost::dynamic_bitset<Block> b(long_string);
 121     Tests::size(b);
 122   }
 123   //=====================================================================
 124   // Test b.any()
 125   {
 126     boost::dynamic_bitset<Block> b;
 127     Tests::any(b);
 128   }
 129   {
 130     boost::dynamic_bitset<Block> b(std::string("0"));
 131     Tests::any(b);
 132   }
 133   {
 134     boost::dynamic_bitset<Block> b(long_string);
 135     Tests::any(b);
 136   }
 137   //=====================================================================
 138   // Test b.none()
 139   {
 140     boost::dynamic_bitset<Block> b;
 141     Tests::none(b);
 142   }
 143   {
 144     boost::dynamic_bitset<Block> b(std::string("0"));
 145     Tests::none(b);
 146   }
 147   {
 148     boost::dynamic_bitset<Block> b(long_string);
 149     Tests::none(b);
 150   }
 151   //=====================================================================
 152   // Test a.is_subset_of(b)
 153   {
 154     boost::dynamic_bitset<Block> a, b;
 155     Tests::subset(a, b);
 156   }
 157   {
 158     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 159     Tests::subset(a, b);
 160   }
 161   {
 162     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 163     Tests::subset(a, b);
 164   }
 165   {
 166     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 167     Tests::subset(a, b);
 168   }
 169   {
 170     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 171     a[long_string.size()/2].flip();
 172     Tests::subset(a, b);
 173   }
 174   {
 175     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 176     b[long_string.size()/2].flip();
 177     Tests::subset(a, b);
 178   }
 179   //=====================================================================
 180   // Test a.is_proper_subset_of(b)
 181   {
 182     boost::dynamic_bitset<Block> a, b;
 183     Tests::proper_subset(a, b);
 184   }
 185   {
 186     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 187     Tests::proper_subset(a, b);
 188   }
 189   {
 190     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 191     Tests::proper_subset(a, b);
 192   }
 193   {
 194     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 195     Tests::proper_subset(a, b);
 196   }
 197   {
 198     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 199     a[long_string.size()/2].flip();
 200     Tests::proper_subset(a, b);
 201   }
 202   {
 203     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 204     b[long_string.size()/2].flip();
 205     Tests::proper_subset(a, b);
 206   }
 207   //=====================================================================
 208   // Test intersects
 209   {
 210     bitset_type a; // empty
 211     bitset_type b;
 212     Tests::intersects(a, b);
 213   }
 214   {
 215     bitset_type a;
 216     bitset_type b(5, 8ul);
 217     Tests::intersects(a, b);
 218   }
 219   {
 220     bitset_type a(8, 0ul);
 221     bitset_type b(15, 0ul);
 222     b[9] = 1;
 223     Tests::intersects(a, b);
 224   }
 225   {
 226     bitset_type a(15, 0ul);
 227     bitset_type b(22, 0ul);
 228     a[14] = b[14] = 1;
 229     Tests::intersects(a, b);
 230   }
 231   //=====================================================================
 232   // Test find_first
 233   {
 234       // empty bitset
 235       bitset_type b;
 236       Tests::find_first(b);
 237   }
 238   {
 239       // bitset of size 1
 240       bitset_type b(1, 1ul);
 241       Tests::find_first(b);
 242   }
 243   {
 244       // all-0s bitset
 245       bitset_type b(4 * bitset_type::bits_per_block, 0ul);
 246       Tests::find_first(b);
 247   }
 248   {
 249       // first bit on
 250       bitset_type b(1, 1ul);
 251       Tests::find_first(b);
 252   }
 253   {
 254       // last bit on
 255       bitset_type b(4 * bitset_type::bits_per_block - 1, 0ul);
 256       b.set(b.size() - 1);
 257       Tests::find_first(b);
 258   }
 259   //=====================================================================
 260   // Test find_next
 261   {
 262       // empty bitset
 263       bitset_type b;
 264
 265       // check
 266       Tests::find_next(b, 0);
 267       Tests::find_next(b, 1);
 268       Tests::find_next(b, 200);
 269       Tests::find_next(b, b.npos);
 270   }
 271   {
 272       // bitset of size 1 (find_next can never find)
 273       bitset_type b(1, 1ul);
 274
 275       // check
 276       Tests::find_next(b, 0);
 277       Tests::find_next(b, 1);
 278       Tests::find_next(b, 200);
 279       Tests::find_next(b, b.npos);
 280   }
 281   {
 282       // all-1s bitset
 283       bitset_type b(16 * bitset_type::bits_per_block);
 284       b.set();
 285
 286       // check
 287       const typename bitset_type::size_type larger_than_size = 5 + b.size();
 288       for(typename bitset_type::size_type i = 0; i <= larger_than_size; ++i) {
 289           Tests::find_next(b, i);
 290       }
 291       Tests::find_next(b, b.npos);
 292   }
 293   {
 294       // a bitset with 1s at block boundary only
 295       const int num_blocks = 32;
 296       const int block_width = bitset_type::bits_per_block;
 297
 298       bitset_type b(num_blocks * block_width);
 299       typename bitset_type::size_type i = block_width - 1;
 300       for ( ; i < b.size(); i += block_width) {
 301
 302         b.set(i);
 303         typename bitset_type::size_type first_in_block = i - (block_width - 1);
 304         b.set(first_in_block);
 305       }
 306
 307       // check
 308       const typename bitset_type::size_type larger_than_size = 5 + b.size();
 309       for (i = 0; i <= larger_than_size; ++i) {
 310           Tests::find_next(b, i);
 311       }
 312       Tests::find_next(b, b.npos);
 313
 314   }
 315   {
 316       // bitset with alternate 1s and 0s
 317       const typename bitset_type::size_type sz = 1000;
 318       bitset_type b(sz);
 319
 320       typename bitset_type::size_type i = 0;
 321       for ( ; i < sz; ++i) {
 322         b[i] = (i%2 == 0);
 323       }
 324
 325       // check
 326       const typename bitset_type::size_type larger_than_size = 5 + b.size();
 327       for (i = 0; i <= larger_than_size; ++i) {
 328           Tests::find_next(b, i);
 329       }
 330       Tests::find_next(b, b.npos);
 331
 332   }
 333   //=====================================================================
 334   // Test operator==
 335   {
 336     boost::dynamic_bitset<Block> a, b;
 337     Tests::operator_equal(a, b);
 338   }
 339   {
 340     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 341     Tests::operator_equal(a, b);
 342   }
 343   {
 344     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 345     Tests::operator_equal(a, b);
 346   }
 347   {
 348     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 349     Tests::operator_equal(a, b);
 350   }
 351   {
 352     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 353     a[long_string.size()/2].flip();
 354     Tests::operator_equal(a, b);
 355   }
 356   {
 357     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 358     b[long_string.size()/2].flip();
 359     Tests::operator_equal(a, b);
 360   }
 361   //=====================================================================
 362   // Test operator!=
 363   {
 364     boost::dynamic_bitset<Block> a, b;
 365     Tests::operator_not_equal(a, b);
 366   }
 367   {
 368     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 369     Tests::operator_not_equal(a, b);
 370   }
 371   {
 372     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 373     Tests::operator_not_equal(a, b);
 374   }
 375   {
 376     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 377     Tests::operator_not_equal(a, b);
 378   }
 379   {
 380     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 381     a[long_string.size()/2].flip();
 382     Tests::operator_not_equal(a, b);
 383   }
 384   {
 385     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 386     b[long_string.size()/2].flip();
 387     Tests::operator_not_equal(a, b);
 388   }
 389   //=====================================================================
 390   // Test operator<
 391   {
 392     boost::dynamic_bitset<Block> a, b;
 393     Tests::operator_less_than(a, b);
 394   }
 395   {
 396     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 397     Tests::operator_less_than(a, b);
 398   }
 399   {
 400     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 401     Tests::operator_less_than(a, b);
 402   }
 403   {
 404     boost::dynamic_bitset<Block> a(std::string("10")), b(std::string("11"));
 405     Tests::operator_less_than(a, b);
 406   }
 407   {
 408     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 409     Tests::operator_less_than(a, b);
 410   }
 411   {
 412     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 413     a[long_string.size()/2].flip();
 414     Tests::operator_less_than(a, b);
 415   }
 416   {
 417     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 418     b[long_string.size()/2].flip();
 419     Tests::operator_less_than(a, b);
 420   }
 421   // check for consistency with ulong behaviour
 422   {
 423     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
 424     assert(a < b);
 425   }
 426   {
 427     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
 428     assert(!(a < b));
 429   }
 430   {
 431     boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
 432     assert(!(a < b));
 433   }
 434   //=====================================================================
 435   // Test operator<=
 436   {
 437     boost::dynamic_bitset<Block> a, b;
 438     Tests::operator_less_than_eq(a, b);
 439   }
 440   {
 441     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 442     Tests::operator_less_than_eq(a, b);
 443   }
 444   {
 445     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 446     Tests::operator_less_than_eq(a, b);
 447   }
 448   {
 449     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 450     Tests::operator_less_than_eq(a, b);
 451   }
 452   {
 453     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 454     a[long_string.size()/2].flip();
 455     Tests::operator_less_than_eq(a, b);
 456   }
 457   {
 458     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 459     b[long_string.size()/2].flip();
 460     Tests::operator_less_than_eq(a, b);
 461   }
 462   // check for consistency with ulong behaviour
 463   {
 464     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
 465     assert(a <= b);
 466   }
 467   {
 468     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
 469     assert(a <= b);
 470   }
 471   {
 472     boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
 473     assert(!(a <= b));
 474   }
 475   //=====================================================================
 476   // Test operator>
 477   {
 478     boost::dynamic_bitset<Block> a, b;
 479     Tests::operator_greater_than(a, b);
 480   }
 481   {
 482     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 483     Tests::operator_greater_than(a, b);
 484   }
 485   {
 486     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 487     Tests::operator_greater_than(a, b);
 488   }
 489   {
 490     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 491     Tests::operator_greater_than(a, b);
 492   }
 493   {
 494     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 495     a[long_string.size()/2].flip();
 496     Tests::operator_greater_than(a, b);
 497   }
 498   {
 499     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 500     b[long_string.size()/2].flip();
 501     Tests::operator_greater_than(a, b);
 502   }
 503   // check for consistency with ulong behaviour
 504   {
 505     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
 506     assert(!(a > b));
 507   }
 508   {
 509     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
 510     assert(!(a > b));
 511   }
 512   {
 513     boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
 514     assert(a > b);
 515   }
 516   //=====================================================================
 517   // Test operator<=
 518   {
 519     boost::dynamic_bitset<Block> a, b;
 520     Tests::operator_greater_than_eq(a, b);
 521   }
 522   {
 523     boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
 524     Tests::operator_greater_than_eq(a, b);
 525   }
 526   {
 527     boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
 528     Tests::operator_greater_than_eq(a, b);
 529   }
 530   {
 531     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 532     Tests::operator_greater_than_eq(a, b);
 533   }
 534   {
 535     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 536     a[long_string.size()/2].flip();
 537     Tests::operator_greater_than_eq(a, b);
 538   }
 539   {
 540     boost::dynamic_bitset<Block> a(long_string), b(long_string);
 541     b[long_string.size()/2].flip();
 542     Tests::operator_greater_than_eq(a, b);
 543   }
 544   // check for consistency with ulong behaviour
 545   {
 546     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
 547     assert(!(a >= b));
 548   }
 549   {
 550     boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
 551     assert(a >= b);
 552   }
 553   {
 554     boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
 555     assert(a >= b);
 556   }
 557   //=====================================================================
 558   // Test b.test(pos)
 559   { // case pos >= b.size()
 560     boost::dynamic_bitset<Block> b;
 561     Tests::test_bit(b, 0);
 562   }
 563   { // case pos < b.size()
 564     boost::dynamic_bitset<Block> b(std::string("0"));
 565     Tests::test_bit(b, 0);
 566   }
 567   { // case pos == b.size() / 2
 568     boost::dynamic_bitset<Block> b(long_string);
 569     Tests::test_bit(b, long_string.size()/2);
 570   }
 571   //=====================================================================
 572   // Test b << pos
 573   { // case pos == 0
 574     std::size_t pos = 0;
 575     boost::dynamic_bitset<Block> b(std::string("1010"));
 576     Tests::operator_shift_left(b, pos);
 577   }
 578   { // case pos == size()/2
 579     std::size_t pos = long_string.size() / 2;
 580     boost::dynamic_bitset<Block> b(long_string);
 581     Tests::operator_shift_left(b, pos);
 582   }
 583   { // case pos >= n
 584     std::size_t pos = long_string.size();
 585     boost::dynamic_bitset<Block> b(long_string);
 586     Tests::operator_shift_left(b, pos);
 587   }
 588   //=====================================================================
 589   // Test b >> pos
 590   { // case pos == 0
 591     std::size_t pos = 0;
 592     boost::dynamic_bitset<Block> b(std::string("1010"));
 593     Tests::operator_shift_right(b, pos);
 594   }
 595   { // case pos == size()/2
 596     std::size_t pos = long_string.size() / 2;
 597     boost::dynamic_bitset<Block> b(long_string);
 598     Tests::operator_shift_right(b, pos);
 599   }
 600   { // case pos >= n
 601     std::size_t pos = long_string.size();
 602     boost::dynamic_bitset<Block> b(long_string);
 603     Tests::operator_shift_right(b, pos);
 604   }
 605   //=====================================================================
 606   // Test a & b
 607   {
 608     boost::dynamic_bitset<Block> lhs, rhs;
 609     Tests::operator_and(lhs, rhs);
 610   }
 611   {
 612     boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
 613     Tests::operator_and(lhs, rhs);
 614   }
 615   {
 616     boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
 617     Tests::operator_and(lhs, rhs);
 618   }
 619   {
 620     boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
 621     Tests::operator_and(lhs, rhs);
 622   }
 623   //=====================================================================
 624   // Test a | b
 625   {
 626     boost::dynamic_bitset<Block> lhs, rhs;
 627     Tests::operator_or(lhs, rhs);
 628   }
 629   {
 630     boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
 631     Tests::operator_or(lhs, rhs);
 632   }
 633   {
 634     boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
 635     Tests::operator_or(lhs, rhs);
 636   }
 637   {
 638     boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
 639     Tests::operator_or(lhs, rhs);
 640   }
 641   //=====================================================================
 642   // Test a^b
 643   {
 644     boost::dynamic_bitset<Block> lhs, rhs;
 645     Tests::operator_xor(lhs, rhs);
 646   }
 647   {
 648     boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
 649     Tests::operator_xor(lhs, rhs);
 650   }
 651   {
 652     boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
 653     Tests::operator_xor(lhs, rhs);
 654   }
 655   {
 656     boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
 657     Tests::operator_xor(lhs, rhs);
 658   }
 659   //=====================================================================
 660   // Test a-b
 661   {
 662     boost::dynamic_bitset<Block> lhs, rhs;
 663     Tests::operator_sub(lhs, rhs);
 664   }
 665   {
 666     boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
 667     Tests::operator_sub(lhs, rhs);
 668   }
 669   {
 670     boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
 671     Tests::operator_sub(lhs, rhs);
 672   }
 673   {
 674     boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
 675     Tests::operator_sub(lhs, rhs);
 676   }
 677 }
 678
 679 int
 680 test_main(int, char*[])
 681 {
 682   run_test_cases<unsigned char>();
 683   run_test_cases<unsigned short>();
 684   run_test_cases<unsigned int>();
 685   run_test_cases<unsigned long>();
 686 # ifdef BOOST_HAS_LONG_LONG
 687   run_test_cases< ::boost::ulong_long_type>();
 688 # endif
 689
 690   return 0;
 691 }