Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/test/unionfind_test.cc
changeset 774 4297098d9677
parent 542 69bde1d90c04
child 793 9cd0aeea47b0
equal deleted inserted replaced
1:efdede6546b9 2:c928d85d327d 
     1 #include <iostream>
 
     1 #include <iostream>
 
     2 
     2 
     3 #include <hugo/maps.h>
 
     3 #include <hugo/maps.h>
 
     4 #include <hugo/unionfind.h>
 
     4 #include <hugo/unionfind.h>
 
       
     5 #include "test_tools.h"
 
     5 
     6 
     6 using namespace hugo;
 
     7 using namespace hugo;
 
     7 using namespace std;
 
     8 using namespace std;
 
     8 
       
     9 bool passed = true;
 
       
    10 
       
    11 void check(bool rc) {
 
       
    12   passed = passed && rc;
 
       
    13   if(!rc) {
 
       
    14     cout << "Test failed!" << endl;
 
       
    15   }
 
       
    16 }
 
       
    17 
     9 
    18 template <typename T>
 
    10 template <typename T>
 
    19 class BaseMap : public StdMap<int,T> {};
 
    11 class BaseMap : public StdMap<int,T> {};
 
    20 
    12 
    21 typedef UnionFindEnum<int, BaseMap> UFE;
 
    13 typedef UnionFindEnum<int, BaseMap> UFE;
 
    22 
    14 
    23 void print(UFE const &ufe) {
 
    15 void print(UFE const &ufe) {
 
    24   UFE::ClassIt cit;
 
    16   UFE::ClassIt cit;
 
    25   cout << "printing the classes of the structure:" << endl;
 
    17   cout << "Print the classes of the structure:" << endl;
 
    26   int i = 1;
 
    18   int i = 1;
 
    27   for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
 
    19   for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
 
    28     cout << "  " << i << " (" << cit << "):" << flush;
 
    20     cout << "  " << i << " (" << cit << "):" << flush;
 
    29     UFE::ItemIt iit;
 
    21     UFE::ItemIt iit;
 
    30     for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
 
    22     for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
 
    39 
    31 
    40 int main() {
 
    32 int main() {
 
    41   UFE::MapType base;
 
    33   UFE::MapType base;
 
    42   UFE U(base);
 
    34   UFE U(base);
 
    43 
    35 
    44   print(U);
 
    36 //   print(U);
 
    45 
    37 
    46   cout << "Inserting 1..." << endl;
 
    38   cout << "Insert 1..." << endl;
 
    47   U.insert(1);
 
    39   U.insert(1);
 
    48   print(U);
 
    40 //   print(U);
 
    49   
    41   
    50   cout << "Inserting 2..." << endl;
 
    42   cout << "Insert 2..." << endl;
 
    51   U.insert(2);
 
    43   U.insert(2);
 
    52   print(U);
 
    44 //   print(U);
 
    53   
    45   
    54   cout << "Joining 1 and 2..." << endl;
 
    46   cout << "Join 1 and 2..." << endl;
 
    55   check(U.join(1,2));
 
    47   check(U.join(1,2),"Test failed.");
 
    56   print(U);
 
    48 //   print(U);
 
    57 
    49 
    58   cout << "Inserting 3, 4, 5, 6, 7..." << endl;
 
    50   cout << "Insert 3, 4, 5, 6, 7..." << endl;
 
    59   U.insert(3);
 
    51   U.insert(3);
 
    60   U.insert(4);
 
    52   U.insert(4);
 
    61   U.insert(5);
 
    53   U.insert(5);
 
    62   U.insert(6);
 
    54   U.insert(6);
 
    63   U.insert(7);
 
    55   U.insert(7);
 
    64   print (U);
 
    56 //   print (U);
 
    65 
    57 
    66   cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
 
    58   cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
 
    67   check(U.join(1,4));
 
    59   check(U.join(1,4),"Test failed.");
 
    68   check(!U.join(2,4));
 
    60   check(!U.join(2,4),"Test failed.");
 
    69   check(U.join(3,5));
 
    61   check(U.join(3,5),"Test failed.");
 
    70   print(U);
 
    62 //   print(U);
 
    71 
    63 
    72   cout << "Inserting 8 to the component of 5 ..." << endl;
 
    64   cout << "Insert 8 to the component of 5 ..." << endl;
 
    73   U.insert(8,5);
 
    65   U.insert(8,5);
 
    74   print(U);
 
    66 //   print(U);
 
    75 
    67 
    76   cout << "size of the class of 4: " << U.size(4) << endl;
 
    68   cout << "Size of the class of 4: " << U.size(4) << endl;
 
    77   check(U.size(4) == 3);
 
    69   check(U.size(4) == 3,"Test failed.");
 
    78   cout << "size of the class of 5: " << U.size(5) << endl;
 
    70   cout << "Size of the class of 5: " << U.size(5) << endl;
 
    79   check(U.size(5) == 3);
 
    71   check(U.size(5) == 3,"Test failed.");
 
    80   cout << "size of the class of 6: " << U.size(6) << endl;
 
    72   cout << "Size of the class of 6: " << U.size(6) << endl;
 
    81   check(U.size(6) == 1);
 
    73   check(U.size(6) == 1,"Test failed.");
 
    82   cout << "size of the class of 2: " << U.size(2) << endl;
 
    74   cout << "Size of the class of 2: " << U.size(2) << endl;
 
    83   check(U.size(2) == 3);
 
    75   check(U.size(2) == 3,"Test failed.");
 
    84 
    76 
    85   cout << "Inserting 9 ..." << endl;
 
    77   cout << "Insert 9 ..." << endl;
 
    86   U.insert(9);
 
    78   U.insert(9);
 
    87   print(U);
 
    79 //   print(U);
 
    88   cout << "Inserting 10 to the component of 9 ..." << endl;
 
    80   cout << "Insert 10 to the component of 9 ..." << endl;
 
    89   U.insert(10,9);
 
    81   U.insert(10,9);
 
    90   print(U);
 
    82 //   print(U);
 
    91 
    83 
    92   cout << "Joining 8 and 10..." << endl;
 
    84   cout << "Join 8 and 10..." << endl;
 
    93   check(U.join(8,10));
 
    85   check(U.join(8,10),"Test failed.");
 
    94   print(U);
 
    86 //   print(U);
 
    95 
    87 
    96   cout << "Move 9 to the class of 4 ..." << endl;
 
    88   cout << "Move 9 to the class of 4 ..." << endl;
 
    97   check(U.move(9,4));
 
    89   check(U.move(9,4),"Test failed.");
 
    98   print(U);
 
    90 //   print(U);
 
    99 
    91 
   100   cout << "Move 9 to the class of 2 ..." << endl;
 
    92   cout << "Move 9 to the class of 2 ..." << endl;
 
   101   check(!U.move(9,2));
 
    93   check(!U.move(9,2),"Test failed.");
 
   102   print(U);
 
    94 //   print(U);
 
   103 
    95 
   104   cout << "size of the class of 4: " << U.size(4) << endl;
 
    96   cout << "Size of the class of 4: " << U.size(4) << endl;
 
   105   check(U.size(4) == 4);
 
    97   check(U.size(4) == 4,"Test failed.");
 
   106   cout << "size of the class of 9: " << U.size(9) << endl;
 
    98   cout << "Size of the class of 9: " << U.size(9) << endl;
 
   107   check(U.size(9) == 4);
 
    99   check(U.size(9) == 4,"Test failed.");
 
   108   
   100   
   109   cout << "Move 5 to the class of 6 ..." << endl;
 
   101   cout << "Move 5 to the class of 6 ..." << endl;
 
   110   check(U.move(5,6));
 
   102   check(U.move(5,6),"Test failed.");
 
   111   print(U);
 
   103 //   print(U);
 
   112 
   104 
   113   cout << "size of the class of 5: " << U.size(5) << endl;
 
   105   cout << "Size of the class of 5: " << U.size(5) << endl;
 
   114   check(U.size(5) == 2);
 
   106   check(U.size(5) == 2,"Test failed.");
 
   115   cout << "size of the class of 8: " << U.size(8) << endl;
 
   107   cout << "Size of the class of 8: " << U.size(8) << endl;
 
   116   check(U.size(8) == 3);
 
   108   check(U.size(8) == 3,"Test failed.");
 
   117 
   109 
   118   cout << "Move 7 to the class of 10 ..." << endl;
 
   110   cout << "Move 7 to the class of 10 ..." << endl;
 
   119   check(U.move(7,10));
 
   111   check(U.move(7,10),"Test failed.");
 
   120   print(U);
 
   112 //   print(U);
 
   121 
   113 
   122   cout << "size of the class of 7: " << U.size(7) << endl;
 
   114   cout << "Size of the class of 7: " << U.size(7) << endl;
 
   123   check(U.size(7) == 4);
 
   115   check(U.size(7) == 4,"Test failed.");
 
   124 
   116 
   125   cout <<"erase 9: " << endl;
 
   117   cout <<"Erase 9... " << endl;
 
   126   U.erase(9);
 
   118   U.erase(9);
 
   127   print(U);
 
   119 //   print(U);
 
   128 
   120 
   129   cout <<"erase 1: " << endl;
 
   121   cout <<"Erase 1... " << endl;
 
   130   U.erase(1);
 
   122   U.erase(1);
 
   131   print(U);
 
   123 //   print(U);
 
   132 
   124 
   133   cout << "size of the class of 4: " << U.size(4) << endl;
 
   125   cout << "Size of the class of 4: " << U.size(4) << endl;
 
   134   check(U.size(4) == 2);
 
   126   check(U.size(4) == 2,"Test failed.");
 
   135   cout << "size of the class of 2: " << U.size(2) << endl;
 
   127   cout << "Size of the class of 2: " << U.size(2) << endl;
 
   136   check(U.size(2) == 2);
 
   128   check(U.size(2) == 2,"Test failed.");
 
   137 
   129 
   138 
   130 
   139   cout <<"erase 1: " << endl;
 
   131   cout <<"Erase 1... " << endl;
 
   140   U.erase(1);
 
   132   U.erase(1);
 
   141   print(U);
 
   133 //   print(U);
 
   142 
   134 
   143   cout <<"erase 6: " << endl;
 
   135   cout <<"Erase 6... " << endl;
 
   144   U.erase(6);
 
   136   U.erase(6);
 
   145   print(U);
 
   137 //   print(U);
 
   146 
   138 
   147   cout << "split the class of 8: " << endl;
 
   139   cout << "Split the class of 8... " << endl;
 
   148   U.split(8);
 
   140   U.split(8);
 
   149   print(U);
 
   141 //   print(U);
 
   150 
   142 
   151 
   143 
   152   cout << "size of the class of 4: " << U.size(4) << endl;
 
   144   cout << "Size of the class of 4: " << U.size(4) << endl;
 
   153   check(U.size(4) == 2);
 
   145   check(U.size(4) == 2,"Test failed.");
 
   154   cout << "size of the class of 3: " << U.size(3) << endl;
 
   146   cout << "Size of the class of 3: " << U.size(3) << endl;
 
   155   check(U.size(3) == 1);
 
   147   check(U.size(3) == 1,"Test failed.");
 
   156   cout << "size of the class of 2: " << U.size(2) << endl;
 
   148   cout << "Size of the class of 2: " << U.size(2) << endl;
 
   157   check(U.size(2) == 2);
 
   149   check(U.size(2) == 2,"Test failed.");
 
   158 
   150 
   159 
   151 
   160   cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
 
   152   cout << "Join 3 - 4 and 2 - 4 ..." << endl;
 
   161   check(U.join(3,4));
 
   153   check(U.join(3,4),"Test failed.");
 
   162   check(!U.join(2,4));
 
   154   check(!U.join(2,4),"Test failed.");
 
   163   print(U);
 
   155 //   print(U);
 
   164 
   156 
   165 
   157 
   166   cout << "size of the class of 4: " << U.size(4) << endl;
 
   158   cout << "Size of the class of 4: " << U.size(4) << endl;
 
   167   check(U.size(4) == 3);
 
   159   check(U.size(4) == 3,"Test failed.");
 
   168   cout << "size of the class of 3: " << U.size(3) << endl;
 
   160   cout << "Size of the class of 3: " << U.size(3) << endl;
 
   169   check(U.size(3) == 3);
 
   161   check(U.size(3) == 3,"Test failed.");
 
   170   cout << "size of the class of 2: " << U.size(2) << endl;
 
   162   cout << "Size of the class of 2: " << U.size(2) << endl;
 
   171   check(U.size(2) == 3);
 
   163   check(U.size(2) == 3,"Test failed.");
 
   172 
   164 
   173   cout << "makeRep(4)" << endl;
 
   165   cout << "makeRep(4)..." << endl;
 
   174   U.makeRep(4);
 
   166   U.makeRep(4);
 
   175   print(U);
 
   167 //   print(U);
 
   176   cout << "makeRep(3)" << endl;
 
   168   cout << "makeRep(3)..." << endl;
 
   177   U.makeRep(3);
 
   169   U.makeRep(3);
 
   178   print(U);
 
   170 //   print(U);
 
   179   cout << "makeRep(2)" << endl;
 
   171   cout << "makeRep(2)..." << endl;
 
   180   U.makeRep(2);
 
   172   U.makeRep(2);
 
   181   print(U);
 
   173 //   print(U);
 
   182 
   174 
   183   cout << "size of the class of 4: " << U.size(4) << endl;
 
   175   cout << "Size of the class of 4: " << U.size(4) << endl;
 
   184   check(U.size(4) == 3);
 
   176   check(U.size(4) == 3,"Test failed.");
 
   185   cout << "size of the class of 3: " << U.size(3) << endl;
 
   177   cout << "Size of the class of 3: " << U.size(3) << endl;
 
   186   check(U.size(3) == 3);
 
   178   check(U.size(3) == 3,"Test failed.");
 
   187   cout << "size of the class of 2: " << U.size(2) << endl;
 
   179   cout << "Size of the class of 2: " << U.size(2) << endl;
 
   188   check(U.size(2) == 3);
 
   180   check(U.size(2) == 3,"Test failed.");
 
   189 
   181 
   190 
   182 
   191   cout << "eraseClass 4 ..." << endl;
 
   183   cout << "eraseClass 4 ..." << endl;
 
   192   U.eraseClass(4);
 
   184   U.eraseClass(4);
 
   193   print(U);
 
   185 //   print(U);
 
   194 
   186 
   195   cout << "eraseClass 7 ..." << endl;
 
   187   cout << "eraseClass 7 ..." << endl;
 
   196   U.eraseClass(7);
 
   188   U.eraseClass(7);
 
   197   print(U);
 
   189 //   print(U);
 
   198 
   190 
   199   cout << "done" << endl;
 
   191   cout << "done." << endl;
 
   200 
       
   201   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
 
       
   202        << endl;
 
       
   203 
       
   204   return passed ? 0 : 1;
 
       
   205 }
 
   192 }
lemon-0.x