Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/test/unionfind_test.cc
author jacint
Mon, 13 Sep 2004 10:50:28 +0000
changeset 833 512e5fd7d38b
parent 774 4297098d9677
child 906 17f31d280385
permissions -rw-r--r--
preflow test 
     1 #include <iostream>

     2 

     3 #include <hugo/maps.h>

     4 #include <hugo/unionfind.h>

     5 #include "test_tools.h"

     6 

     7 using namespace hugo;

     8 using namespace std;

     9 

    10 template <typename T>

    11 class BaseMap : public StdMap<int,T> {};

    12 

    13 typedef UnionFindEnum<int, BaseMap> UFE;

    14 

    15 void print(UFE const &ufe) {

    16   UFE::ClassIt cit;

    17   cout << "Print the classes of the structure:" << endl;

    18   int i = 1;

    19   for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {

    20     cout << "  " << i << " (" << cit << "):" << flush;

    21     UFE::ItemIt iit;

    22     for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {

    23       cout << " " << iit << flush;

    24     }

    25     cout << endl;

    26     i++;

    27   }

    28   cout << "done" << endl;

    29 }

    30 

    31 

    32 int main() {

    33   UFE::MapType base;

    34   UFE U(base);

    35 

    36 //   print(U);

    37 

    38   cout << "Insert 1..." << endl;

    39   U.insert(1);

    40 //   print(U);

    41   

    42   cout << "Insert 2..." << endl;

    43   U.insert(2);

    44 //   print(U);

    45   

    46   cout << "Join 1 and 2..." << endl;

    47   check(U.join(1,2),"Test failed.");

    48 //   print(U);

    49 

    50   cout << "Insert 3, 4, 5, 6, 7..." << endl;

    51   U.insert(3);

    52   U.insert(4);

    53   U.insert(5);

    54   U.insert(6);

    55   U.insert(7);

    56 //   print (U);

    57 

    58   cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl;

    59   check(U.join(1,4),"Test failed.");

    60   check(!U.join(2,4),"Test failed.");

    61   check(U.join(3,5),"Test failed.");

    62 //   print(U);

    63 

    64   cout << "Insert 8 to the component of 5 ..." << endl;

    65   U.insert(8,5);

    66 //   print(U);

    67 

    68   cout << "Size of the class of 4: " << U.size(4) << endl;

    69   check(U.size(4) == 3,"Test failed.");

    70   cout << "Size of the class of 5: " << U.size(5) << endl;

    71   check(U.size(5) == 3,"Test failed.");

    72   cout << "Size of the class of 6: " << U.size(6) << endl;

    73   check(U.size(6) == 1,"Test failed.");

    74   cout << "Size of the class of 2: " << U.size(2) << endl;

    75   check(U.size(2) == 3,"Test failed.");

    76 

    77   cout << "Insert 9 ..." << endl;

    78   U.insert(9);

    79 //   print(U);

    80   cout << "Insert 10 to the component of 9 ..." << endl;

    81   U.insert(10,9);

    82 //   print(U);

    83 

    84   cout << "Join 8 and 10..." << endl;

    85   check(U.join(8,10),"Test failed.");

    86 //   print(U);

    87 

    88   cout << "Move 9 to the class of 4 ..." << endl;

    89   check(U.move(9,4),"Test failed.");

    90 //   print(U);

    91 

    92   cout << "Move 9 to the class of 2 ..." << endl;

    93   check(!U.move(9,2),"Test failed.");

    94 //   print(U);

    95 

    96   cout << "Size of the class of 4: " << U.size(4) << endl;

    97   check(U.size(4) == 4,"Test failed.");

    98   cout << "Size of the class of 9: " << U.size(9) << endl;

    99   check(U.size(9) == 4,"Test failed.");

   100   

   101   cout << "Move 5 to the class of 6 ..." << endl;

   102   check(U.move(5,6),"Test failed.");

   103 //   print(U);

   104 

   105   cout << "Size of the class of 5: " << U.size(5) << endl;

   106   check(U.size(5) == 2,"Test failed.");

   107   cout << "Size of the class of 8: " << U.size(8) << endl;

   108   check(U.size(8) == 3,"Test failed.");

   109 

   110   cout << "Move 7 to the class of 10 ..." << endl;

   111   check(U.move(7,10),"Test failed.");

   112 //   print(U);

   113 

   114   cout << "Size of the class of 7: " << U.size(7) << endl;

   115   check(U.size(7) == 4,"Test failed.");

   116 

   117   cout <<"Erase 9... " << endl;

   118   U.erase(9);

   119 //   print(U);

   120 

   121   cout <<"Erase 1... " << endl;

   122   U.erase(1);

   123 //   print(U);

   124 

   125   cout << "Size of the class of 4: " << U.size(4) << endl;

   126   check(U.size(4) == 2,"Test failed.");

   127   cout << "Size of the class of 2: " << U.size(2) << endl;

   128   check(U.size(2) == 2,"Test failed.");

   129 

   130 

   131   cout <<"Erase 1... " << endl;

   132   U.erase(1);

   133 //   print(U);

   134 

   135   cout <<"Erase 6... " << endl;

   136   U.erase(6);

   137 //   print(U);

   138 

   139   cout << "Split the class of 8... " << endl;

   140   U.split(8);

   141 //   print(U);

   142 

   143 

   144   cout << "Size of the class of 4: " << U.size(4) << endl;

   145   check(U.size(4) == 2,"Test failed.");

   146   cout << "Size of the class of 3: " << U.size(3) << endl;

   147   check(U.size(3) == 1,"Test failed.");

   148   cout << "Size of the class of 2: " << U.size(2) << endl;

   149   check(U.size(2) == 2,"Test failed.");

   150 

   151 

   152   cout << "Join 3 - 4 and 2 - 4 ..." << endl;

   153   check(U.join(3,4),"Test failed.");

   154   check(!U.join(2,4),"Test failed.");

   155 //   print(U);

   156 

   157 

   158   cout << "Size of the class of 4: " << U.size(4) << endl;

   159   check(U.size(4) == 3,"Test failed.");

   160   cout << "Size of the class of 3: " << U.size(3) << endl;

   161   check(U.size(3) == 3,"Test failed.");

   162   cout << "Size of the class of 2: " << U.size(2) << endl;

   163   check(U.size(2) == 3,"Test failed.");

   164 

   165   cout << "Calling makeRep(4)..." << endl;

   166   U.makeRep(4);

   167 //   print(U);

   168   cout << "Calling makeRep(3)..." << endl;

   169   U.makeRep(3);

   170 //   print(U);

   171   cout << "Calling makeRep(2)..." << endl;

   172   U.makeRep(2);

   173 //   print(U);

   174 

   175   cout << "Size of the class of 4: " << U.size(4) << endl;

   176   check(U.size(4) == 3,"Test failed.");

   177   cout << "Size of the class of 3: " << U.size(3) << endl;

   178   check(U.size(3) == 3,"Test failed.");

   179   cout << "Size of the class of 2: " << U.size(2) << endl;

   180   check(U.size(2) == 3,"Test failed.");

   181 

   182 

   183   cout << "eraseClass 4 ..." << endl;

   184   U.eraseClass(4);

   185 //   print(U);

   186 

   187   cout << "eraseClass 7 ..." << endl;

   188   U.eraseClass(7);

   189 //   print(U);

   190 

   191   cout << "done." << endl;

   192 }
lemon-0.x