Changeset 2205:c20b0eb92a33 in lemon-0.x for test/unionfind_test.cc

Timestamp:

09/06/06 13:17:12 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2930

Message:

UnionFind?
Changing the representation of the union-find
it has the same running time but it takes just 2/3 space
! does not auto insert items /performance/

UnionFindEnum?
Changing the interface - more convenient to UnionFind?
Does not based on the stl data structures /it could be disadvantage/

=> does not use singular iterator assignment /not stl conform, but always work/

Just new iterator interface

MaxMatching? + UnionFindTest?
Using new iterator interface instead of the old

File:

• test/unionfind_test.cc (modified) (3 diffs)

test/unionfind_test.cc

@@ -26 +26 @@
 using namespace std;
 
-template <typename T>
-class BaseMap : public StdMap<int,T> {};
-
-typedef UnionFindEnum<int, BaseMap> UFE;
+typedef UnionFindEnum<int, StdMap<int, int> > UFE;
 
 void print(UFE const &ufe) {
-  UFE::ClassIt cit;
   cout << "Print the classes of the structure:" << endl;
   int i = 1;
-  for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
+  for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
     cout << "  " << i << " (" << cit << "):" << flush;
-    UFE::ItemIt iit;
-    for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
+    for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
       cout << " " << iit << flush;
     }
@@ -49 +44 @@
 
 int main() {
-  UFE::MapType base;
+  StdMap<int, int> base;
   UFE U(base);
 
@@ -76 +71 @@
   U.insert(9);
   U.insert(10,9);
+
   check(U.join(8,10),"Test failed.");