BitsetTest.cpp

Go to the documentation of this file.
00001 //---------------------------------------------------------------------------
00002 /** @file
00003  */
00004 //---------------------------------------------------------------------------
00005 
00006 #include <boost/test/auto_unit_test.hpp>
00007 
00008 #include "Bitset.hpp"
00009 
00010 using namespace benzene;
00011 
00012 //---------------------------------------------------------------------------
00013 
00014 namespace {
00015 
00016 BOOST_AUTO_TEST_CASE(Bitset_Basics)
00017 {
00018     // sort of ridiculous, but in case someone switches
00019     // from stl to some other basis, we need these
00020     // operations to still work as expected
00021     bitset_t b1, b2;
00022     BOOST_REQUIRE(BITSETSIZE > 1);
00023     BOOST_CHECK_EQUAL(b1.count(), 0u);
00024     b1.flip();
00025     BOOST_CHECK_EQUAL(b1.count(), (std::size_t)BITSETSIZE);
00026     BOOST_CHECK(b1.test(0));
00027     BOOST_CHECK(b1.test(BITSETSIZE-1));
00028     BOOST_CHECK(!b2.test(0));
00029     BOOST_CHECK(!b2.test(BITSETSIZE-1));
00030     BOOST_CHECK(!b2.any());
00031     BOOST_CHECK(b2.none());
00032     BOOST_CHECK_EQUAL(b1.size(), (std::size_t)BITSETSIZE);
00033     BOOST_CHECK(!b1.none());
00034     b1.reset();
00035     BOOST_CHECK(b1.none());
00036     b1.set(0);
00037     BOOST_CHECK_EQUAL(b1.count(), 1u);
00038     b2.set(1);
00039     BOOST_CHECK_EQUAL(b2.count(), 1u);
00040     b2 |= b1;
00041     BOOST_CHECK_EQUAL(b2.count(), 2u);
00042     b1 ^= b2;
00043     BOOST_CHECK_EQUAL(b1.count(), 1u);
00044     BOOST_CHECK(!b1.test(0));
00045     BOOST_CHECK(b1.test(1));
00046     BOOST_CHECK(b2.test(0));
00047     BOOST_CHECK(b2.test(1));
00048     b2 &= b1;
00049     BOOST_CHECK_EQUAL(b1, b2);
00050     b1 ^= b2;
00051     BOOST_CHECK(b1.none());
00052 }
00053 
00054 BOOST_AUTO_TEST_CASE(Bitset_ConversionToBytes)
00055 {
00056     bitset_t b1, b2;
00057     byte byteArray[8];
00058     BOOST_REQUIRE(BITSETSIZE >= 64);
00059     int numBits = 64;
00060     BitsetUtil::BitsetToBytes(b1, byteArray, numBits);
00061     b2 = BitsetUtil::BytesToBitset(byteArray, numBits);
00062     BOOST_CHECK_EQUAL(b1, b2);
00063     BOOST_CHECK_EQUAL(byteArray[0], 0);
00064     BOOST_CHECK_EQUAL(byteArray[1], 0);
00065     b1.set(0);
00066     b1.set(3);
00067     BitsetUtil::BitsetToBytes(b1, byteArray, numBits);
00068     b2 = BitsetUtil::BytesToBitset(byteArray, numBits);
00069     BOOST_CHECK_EQUAL(b1, b2);
00070     BOOST_CHECK_EQUAL(byteArray[0], 9);
00071     BOOST_CHECK_EQUAL(byteArray[1], 0);
00072     b1.set(7);
00073     b1.set(8);
00074     BitsetUtil::BitsetToBytes(b1, byteArray, numBits);
00075     b2 = BitsetUtil::BytesToBitset(byteArray, numBits);
00076     BOOST_CHECK_EQUAL(b1, b2);
00077     BOOST_CHECK_EQUAL(byteArray[0], 137);
00078     BOOST_CHECK_EQUAL(byteArray[1], 1);
00079 }
00080 
00081 BOOST_AUTO_TEST_CASE(Bitset_ConversionToHex)
00082 {
00083     bitset_t b;
00084     std::string s;
00085     BOOST_REQUIRE(BITSETSIZE >= 128);
00086     s = BitsetUtil::BitsetToHex(b, 124);
00087     BOOST_CHECK_EQUAL(BitsetUtil::HexToBitset(s), b);
00088     BOOST_CHECK_EQUAL(s, "0000000000000000000000000000000");
00089     b.set(3);
00090     b.set(5);
00091     b.set(6);
00092     s = BitsetUtil::BitsetToHex(b, 124);
00093     BOOST_CHECK_EQUAL(BitsetUtil::HexToBitset(s), b);
00094     BOOST_CHECK_EQUAL(s, "8600000000000000000000000000000");
00095     b.set(4);
00096     b.flip(6);
00097     b.set(8);
00098     s = BitsetUtil::BitsetToHex(b, 64);
00099     BOOST_CHECK_EQUAL(BitsetUtil::HexToBitset(s), b);
00100     BOOST_CHECK_EQUAL(s, "8310000000000000");
00101     b.set(65);
00102     s = BitsetUtil::BitsetToHex(b, 64);
00103     BOOST_CHECK_EQUAL(s, "8310000000000000");
00104     BOOST_CHECK(BitsetUtil::HexToBitset(s) != b);
00105     BOOST_CHECK(BitsetUtil::IsSubsetOf(BitsetUtil::HexToBitset(s), b));
00106 }
00107 
00108 BOOST_AUTO_TEST_CASE(Bitset_Subtraction)
00109 {
00110     bitset_t b1, b2;
00111     BOOST_REQUIRE(BITSETSIZE > 2);
00112     b1.set(0);
00113     b2.set(1);
00114     BOOST_CHECK_EQUAL(BitsetUtil::Subtract(b1, b2), b1);
00115     BOOST_CHECK_EQUAL(b1 - b2, b1);
00116     BOOST_CHECK_EQUAL(BitsetUtil::Subtract(b2, b1), b2);
00117     BOOST_CHECK_EQUAL(b2 - b1, b2);
00118     b2 |= b1;
00119     // b1=100...0, b2=110...0
00120     BOOST_CHECK(BitsetUtil::Subtract(b1, b2).none());
00121     BOOST_CHECK((b1 - b2).none());
00122     BOOST_CHECK_EQUAL(BitsetUtil::Subtract(b2, b1).count(), 1u);
00123     BOOST_CHECK_EQUAL((b2 - b1).count(), 1u);
00124     b2 ^= b1;
00125     b1.flip();
00126     // b1=011...1, b2=010...0
00127     BOOST_CHECK(BitsetUtil::Subtract(b2, b1).none());
00128     BOOST_CHECK((b2 - b1).none());
00129     BOOST_CHECK_EQUAL(BitsetUtil::Subtract(b1, b2).count(), 
00130                       (std::size_t)(BITSETSIZE-2));
00131     BOOST_CHECK_EQUAL((b1 - b2).count(), (std::size_t)(BITSETSIZE-2));
00132     b2.flip();
00133     BOOST_CHECK_EQUAL(BitsetUtil::Subtract(b1, b2).count(), 1u);
00134     BOOST_CHECK_EQUAL((b1 - b2).count(), 1u);
00135     BOOST_CHECK(BitsetUtil::Subtract(b1, b2).test(1));
00136     BOOST_CHECK((b1 - b2).test(1));
00137     BOOST_CHECK_EQUAL(BitsetUtil::Subtract(b2, b1).count(), 1u);
00138     BOOST_CHECK_EQUAL((b2 - b1).count(), 1u);
00139     BOOST_CHECK(BitsetUtil::Subtract(b2, b1).test(0));
00140     BOOST_CHECK((b2 - b1).test(0));
00141 }
00142 
00143 BOOST_AUTO_TEST_CASE(Bitset_Comparison)
00144 {
00145     // Note: cannot assume any order for IsLessThan, so can only
00146     // check that it is transitive and non-reflexive
00147     bitset_t b1, b2, b3;
00148     bool order1, order2, order3, order4, order5, order6;
00149     BOOST_CHECK(!BitsetUtil::IsLessThan(b1, b2));
00150     BOOST_CHECK(BitsetUtil::IsSubsetOf(b1, b2));
00151     BOOST_REQUIRE(BITSETSIZE >= 8);
00152     b2.set(0);
00153     // b1 = 000...0, b2=100...0, b3=000...0
00154     BOOST_CHECK(BitsetUtil::IsLessThan(b1, b2) !=
00155         BitsetUtil::IsLessThan(b2, b1));
00156     BOOST_CHECK(BitsetUtil::IsSubsetOf(b1, b2));
00157     b1.set(1);
00158     BOOST_CHECK(BitsetUtil::IsLessThan(b1, b2) !=
00159         BitsetUtil::IsLessThan(b2, b1));
00160     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b1, b2));
00161     BOOST_CHECK(BitsetUtil::IsSubsetOf(b3, b1));
00162     BOOST_CHECK(BitsetUtil::IsSubsetOf(b3, b2));
00163     b3 = b2;
00164     b2.flip();
00165     // b1=010...0, b2=011...1, b3=100...0
00166     BOOST_CHECK(!BitsetUtil::IsLessThan(b1, b1));
00167     BOOST_CHECK(!BitsetUtil::IsLessThan(b2, b2));
00168     BOOST_CHECK(!BitsetUtil::IsLessThan(b3, b3));
00169     order1 = BitsetUtil::IsLessThan(b1, b2);
00170     order2 = BitsetUtil::IsLessThan(b1, b3);
00171     order3 = BitsetUtil::IsLessThan(b2, b1);
00172     order4 = BitsetUtil::IsLessThan(b2, b3);
00173     order5 = BitsetUtil::IsLessThan(b3, b1);
00174     order6 = BitsetUtil::IsLessThan(b3, b2);
00175     BOOST_CHECK(order1 != order3);
00176     BOOST_CHECK(order2 != order5);
00177     BOOST_CHECK(order4 != order6);
00178     BOOST_CHECK_EQUAL(order1 && order4 && order5, false);
00179     BOOST_CHECK_EQUAL(order2 && order3 && order6, false);
00180     BOOST_CHECK(BitsetUtil::IsSubsetOf(b1, b2));
00181     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b1, b3));
00182     b2.flip(1);
00183     // b1=010...0, b2=001...1, b3=100...0
00184     BOOST_CHECK(!BitsetUtil::IsLessThan(b1, b1));
00185     BOOST_CHECK(!BitsetUtil::IsLessThan(b2, b2));
00186     BOOST_CHECK(!BitsetUtil::IsLessThan(b3, b3));
00187     order1 = BitsetUtil::IsLessThan(b1, b2);
00188     order2 = BitsetUtil::IsLessThan(b1, b3);
00189     order3 = BitsetUtil::IsLessThan(b2, b1);
00190     order4 = BitsetUtil::IsLessThan(b2, b3);
00191     order5 = BitsetUtil::IsLessThan(b3, b1);
00192     order6 = BitsetUtil::IsLessThan(b3, b2);
00193     BOOST_CHECK(order1 != order3);
00194     BOOST_CHECK(order2 != order5);
00195     BOOST_CHECK(order4 != order6);
00196     BOOST_CHECK_EQUAL(order1 && order4 && order5, false);
00197     BOOST_CHECK_EQUAL(order2 && order3 && order6, false);
00198     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b1, b2));
00199     b1.flip();
00200     b3.flip(2);
00201     // b1=101...1, b2=001...1, b3=101...0
00202     BOOST_CHECK(!BitsetUtil::IsLessThan(b1, b1));
00203     BOOST_CHECK(!BitsetUtil::IsLessThan(b2, b2));
00204     BOOST_CHECK(!BitsetUtil::IsLessThan(b3, b3));
00205     order1 = BitsetUtil::IsLessThan(b1, b2);
00206     order2 = BitsetUtil::IsLessThan(b1, b3);
00207     order3 = BitsetUtil::IsLessThan(b2, b1);
00208     order4 = BitsetUtil::IsLessThan(b2, b3);
00209     order5 = BitsetUtil::IsLessThan(b3, b1);
00210     order6 = BitsetUtil::IsLessThan(b3, b2);
00211     BOOST_CHECK(order1 != order3);
00212     BOOST_CHECK(order2 != order5);
00213     BOOST_CHECK(order4 != order6);
00214     BOOST_CHECK_EQUAL(order1 && order4 && order5, false);
00215     BOOST_CHECK_EQUAL(order2 && order3 && order6, false);
00216     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b1, b2));
00217     BOOST_CHECK(BitsetUtil::IsSubsetOf(b2, b1));
00218     BOOST_CHECK(BitsetUtil::IsSubsetOf(b3, b1));
00219     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b3, b2));
00220     b2.flip();
00221     // b1=101...1, b2=110...0, b3=101...0
00222     BOOST_CHECK(!BitsetUtil::IsLessThan(b1, b1));
00223     BOOST_CHECK(!BitsetUtil::IsLessThan(b2, b2));
00224     BOOST_CHECK(!BitsetUtil::IsLessThan(b3, b3));
00225     order1 = BitsetUtil::IsLessThan(b1, b2);
00226     order2 = BitsetUtil::IsLessThan(b1, b3);
00227     order3 = BitsetUtil::IsLessThan(b2, b1);
00228     order4 = BitsetUtil::IsLessThan(b2, b3);
00229     order5 = BitsetUtil::IsLessThan(b3, b1);
00230     order6 = BitsetUtil::IsLessThan(b3, b2);
00231     BOOST_CHECK(order1 != order3);
00232     BOOST_CHECK(order2 != order5);
00233     BOOST_CHECK(order4 != order6);
00234     BOOST_CHECK_EQUAL(order1 && order4 && order5, false);
00235     BOOST_CHECK_EQUAL(order2 && order3 && order6, false);
00236     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b1, b2));
00237     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b2, b1));
00238     BOOST_CHECK(BitsetUtil::IsSubsetOf(b3, b1));
00239     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b3, b2));
00240     b1.set(1);
00241     b2.set();
00242     // b1=111...1, b2=111...1, b3=101...0
00243     BOOST_CHECK_EQUAL(b1, b2);
00244     BOOST_CHECK(!BitsetUtil::IsLessThan(b2, b1));
00245     BOOST_CHECK(!BitsetUtil::IsLessThan(b3, b3));
00246     order1 = BitsetUtil::IsLessThan(b1, b3);
00247     order2 = BitsetUtil::IsLessThan(b3, b1);
00248     BOOST_CHECK(order1 != order2);
00249     BOOST_CHECK(BitsetUtil::IsSubsetOf(b1, b2));
00250     BOOST_CHECK(BitsetUtil::IsSubsetOf(b2, b1));
00251     BOOST_CHECK(!BitsetUtil::IsSubsetOf(b2, b3));
00252     BOOST_CHECK(BitsetUtil::IsSubsetOf(b3, b2));
00253 }
00254 
00255 BOOST_AUTO_TEST_CASE(Bitset_ConversionToVector)
00256 {
00257     bitset_t b;
00258     std::vector<int> moves;
00259     BitsetUtil::BitsetToVector(b, moves);
00260     BOOST_CHECK(moves.empty());
00261     BOOST_REQUIRE(BITSETSIZE >= 16);
00262     b.set(1);
00263     BitsetUtil::BitsetToVector(b, moves);
00264     BOOST_CHECK_EQUAL(moves.size(), 1u);
00265     BOOST_CHECK_EQUAL(moves[0], 1);
00266     b.set(14);
00267     BitsetUtil::BitsetToVector(b, moves);
00268     BOOST_CHECK_EQUAL(moves.size(), 2u);
00269     BOOST_CHECK_EQUAL(moves[0], 1);
00270     BOOST_CHECK_EQUAL(moves[1], 14);
00271     b.flip();
00272     BitsetUtil::BitsetToVector(b, moves);
00273     BOOST_CHECK_EQUAL(moves.size(), (std::size_t)(BITSETSIZE-2));
00274     BOOST_CHECK_EQUAL(moves[moves.size()-1], BITSETSIZE-1);
00275 }
00276 
00277 BOOST_AUTO_TEST_CASE(Bitset_FindSingleton)
00278 {
00279     bitset_t b;
00280     BOOST_REQUIRE(BITSETSIZE > 2);
00281     b.set(0);
00282     BOOST_CHECK_EQUAL(BitsetUtil::FindSetBit(b), 0);
00283     b.flip(1);
00284     b.flip(0);
00285     BOOST_CHECK_EQUAL(BitsetUtil::FindSetBit(b), 1);
00286     b.reset();
00287     b.set(BITSETSIZE-1);
00288     BOOST_CHECK_EQUAL(BitsetUtil::FindSetBit(b), BITSETSIZE-1);
00289 }
00290 
00291 }
00292 
00293 //---------------------------------------------------------------------------