UnionFindTest.cpp

Go to the documentation of this file.
00001 //---------------------------------------------------------------------------
00002 /** @file UnionFindTest.cpp
00003  */
00004 //---------------------------------------------------------------------------
00005 
00006 #include <boost/test/auto_unit_test.hpp>
00007 
00008 #include "Hex.hpp"
00009 #include "UnionFind.hpp"
00010 
00011 using namespace benzene;
00012 
00013 //---------------------------------------------------------------------------
00014 
00015 namespace {
00016 
00017 BOOST_AUTO_TEST_CASE(UnionFind_AllTests)
00018 {
00019     UnionFind<14> uf;
00020     int root;
00021     
00022     // test that Clear method sets all elements to be their own root
00023     uf.Clear();
00024     BOOST_CHECK_EQUAL(uf.GetRoot(0), 0);
00025     BOOST_CHECK_EQUAL(uf.GetRoot(1), 1);
00026     BOOST_CHECK_EQUAL(uf.GetRoot(7), 7);
00027     BOOST_CHECK_EQUAL(uf.GetRoot(13), 13);
00028     BOOST_CHECK(uf.IsRoot(0));
00029     BOOST_CHECK(uf.IsRoot(1));
00030     BOOST_CHECK(uf.IsRoot(7));
00031     BOOST_CHECK(uf.IsRoot(13));
00032     
00033     // test UnionGroups merges two, no effect on others
00034     uf.UnionGroups(7, 12);
00035     BOOST_CHECK(uf.IsRoot(7) != uf.IsRoot(12));
00036     BOOST_CHECK_EQUAL(uf.GetRoot(7), uf.GetRoot(12));
00037     BOOST_CHECK(uf.IsRoot(0));
00038     BOOST_CHECK(uf.IsRoot(1));
00039     BOOST_CHECK(uf.IsRoot(13));
00040     
00041     uf.UnionGroups(0, 1);
00042     BOOST_CHECK(uf.IsRoot(0) != uf.IsRoot(1));
00043     BOOST_CHECK_EQUAL(uf.GetRoot(0), uf.GetRoot(1));
00044     BOOST_CHECK_EQUAL(uf.GetRoot(7), uf.GetRoot(12));
00045     BOOST_CHECK(uf.IsRoot(13));
00046     
00047     // test merging with self has no effect
00048     uf.UnionGroups(0, 1);
00049     BOOST_CHECK(uf.IsRoot(0) != uf.IsRoot(1));
00050     BOOST_CHECK_EQUAL(uf.GetRoot(0), uf.GetRoot(1));
00051     BOOST_CHECK_EQUAL(uf.GetRoot(7), uf.GetRoot(12));
00052     BOOST_CHECK(uf.IsRoot(13));
00053     
00054     // test merging of groups
00055     uf.UnionGroups(7, 1);
00056     root = uf.GetRoot(0);
00057     BOOST_CHECK_EQUAL(root, uf.GetRoot(1));
00058     BOOST_CHECK_EQUAL(root, uf.GetRoot(7));
00059     BOOST_CHECK_EQUAL(root, uf.GetRoot(12));
00060     BOOST_CHECK(0==root || 1==root || 7==root || 12==root);
00061     BOOST_CHECK(uf.IsRoot(6));
00062     BOOST_CHECK(uf.IsRoot(8));
00063     BOOST_CHECK(uf.IsRoot(13));
00064     
00065     // test that GetRoot does not affect group membership
00066     root = uf.GetRoot(12);
00067     root = uf.GetRoot(1);
00068     root = uf.GetRoot(13);
00069     root = uf.GetRoot(0);
00070     BOOST_CHECK_EQUAL(root, uf.GetRoot(1));
00071     BOOST_CHECK_EQUAL(root, uf.GetRoot(7));
00072     BOOST_CHECK_EQUAL(root, uf.GetRoot(12));
00073     BOOST_CHECK(0==root || 1==root || 7==root || 12==root);
00074     BOOST_CHECK(uf.IsRoot(6));
00075     BOOST_CHECK(uf.IsRoot(8));
00076     BOOST_CHECK(uf.IsRoot(13));
00077     
00078     // test Clear resets properly to individual sets
00079     uf.Clear();
00080     BOOST_CHECK(uf.IsRoot(0));
00081     BOOST_CHECK(uf.IsRoot(1));
00082     BOOST_CHECK(uf.IsRoot(7));
00083     BOOST_CHECK(uf.IsRoot(13));
00084     BOOST_CHECK(uf.GetRoot(7) != uf.GetRoot(12));
00085 }
00086 
00087 }
00088 
00089 //---------------------------------------------------------------------------