Changeset 2003:cf012a7c7f69 in lemon-0.x for lemon/unionfind.h

Timestamp:

03/10/06 19:06:26 (18 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

UnionFindEnum? revision:

• 0 is _not_ convertible to list<...>::iterator, so we have to use other means to define/check validity
• standard LEMON iterator interface for ClassIt? and ItemIt?

File:

• lemon/unionfind.h (modified) (18 diffs)

lemon/unionfind.h

@@ -258 +258 @@
     }
 
+    const ItemList& classOf(const T &a) const {
+      return *_find(m[a])->my_class;
+    }
+
   public:
     UnionFindEnum(MapType& _m) : m(_m) {}
@@ -344 +348 @@
 
         classes.erase(cb->my_class);
-        cb->my_class = 0;
+        // ehem: cb->my_class = 0;
       }
       else {
@@ -355 +359 @@
 
         classes.erase(ca->my_class);
-        ca->my_class = 0;
+        // ehem: ca->my_class = 0;
       }
 
@@ -417 +421 @@
 
       ia->my_class = la->my_class;
-      la->my_class = 0;
+      // ehem: la->my_class = 0;
 
       ia->size = la->size;
@@ -475 +479 @@
 
       ai->parent = clit;
-      ai->my_class = 0;
+      // ehem: ai->my_class = 0;
       ++clit->size;
 
@@ -484 +488 @@
     /**
      * \brief Removes the given element from the structure.
-     *
-     * Removes the given element from the structure.
      *
      * Removes the element from its component and if the component becomes
      * empty then removes that component from the component list.
+     *
+     * It is an error to remove an element which is not in the structure.
      */
     void erase(const T &a) {
 
       IIter ma = m[a];
-      if (ma == 0) return;
+      // ehem: if (ma == 0) return;
 
       IIter la = _find(ma);
@@ -499 +503 @@
         if (ma -> size == 1){
           classes.erase(ma->my_class);
-          m.set(a,0);
+          // ehem: m.set(a,0);
           return;
         }
@@ -513 +517 @@
       la->size--;
       la->my_class->erase(ma);
-      m.set(a,0);
+      // ehem: m.set(a,0);
     }
 
@@ -520 +524 @@
      *
      * Removes the component of the given element from the structure.
+     *
+     * It is an error to give an element which is not in the structure.
      */
 
     void eraseClass(const T &a) {
       IIter ma = m[a];
-      if (ma == 0) return;
-#     ifdef DEBUG
-      CIter c = _find(ma)->my_class;
-      for (IIter i=c->begin(); i!=c->end(); ++i)
-        m.set(i->me, 0);
-#     endif
+      // ehem: if (ma == 0) return;
+// #     ifdef DEBUG
+//       CIter c = _find(ma)->my_class;
+//       for (IIter i=c->begin(); i!=c->end(); ++i)
+//      m.set(i->me, 0);
+// #     endif
       classes.erase(_find(ma)->my_class);
     }
@@ -538 +544 @@
 
       CcIter i;
+      const ClassList *l;
+
     public:
-      ClassIt(Invalid): i(0) {}
+      ClassIt(Invalid): l(0) {}
       ClassIt() {}
+      ClassIt(UnionFindEnum const &ufe) {
+        l = &ufe.classes;
+        i = l->begin();
+      }
       
       operator const T& () const { 
         ItemList const &ll = *i;
-        return (ll.begin())->me; }
-      bool operator == (ClassIt it) const {
-        return (i == it.i);
-      }
-      bool operator != (ClassIt it) const {
-        return (i != it.i);
-      }
-      bool operator < (ClassIt it) const {
+        return (ll.begin())->me;
+      }
+      bool operator == (ClassIt const &it) const {
+        return (l==it.l && i==it.i) || (!valid() && !it.valid());
+      }
+      bool operator != (ClassIt const &it) const {
+        return !(*this == it);
+      }
+      bool operator < (ClassIt const &it) const {
         return (i < it.i);
       }
 
-      bool valid() const { return i != 0; }
+      bool operator==(Invalid) const {
+        return !valid();
+      }
+      bool operator!=(Invalid) const {
+        return valid();
+      }
+
+      ClassIt& operator++() {
+        ++i;
+        return *this;
+      }
+
+      // obsoleted:
+      bool valid() const { return l!=0 && i!=l->end(); }
     private:
-      void first(const ClassList &l) { i = l.begin(); validate(l); }
-      void next(const ClassList &l) {
-        ++i; 
-        validate(l);
-      }
-      void validate(const ClassList &l) {
-        if ( i == l.end() ) 
-          i = 0;
-      }
+      //void first(const ClassList &l) { i = l.begin(); validate(l); }
+//       void next(const ClassList &l) {
+//      ++i; 
+//      validate(l);
+//       }
+//       void validate(const ClassList &l) {
+//      if ( i == l.end() ) 
+//        i = 0;
+//       }
     };
 
@@ -584 +610 @@
      *  }
      * \endcode
+     *
+     * \bug obsoleted, use the new LEMON iterator interface instead
      */
 
     ClassIt& first(ClassIt& it) const {
-      it.first(classes);
+      it = ClassIt(*this);
       return it;
     }
@@ -598 +626 @@
      * With the \ref first, \ref valid and \ref next methods you can
      * iterate through the components. See the example here: \ref first.
+     *
+     * \bug obsoleted, use the new LEMON iterator interface instead
      */
 
@@ -614 +644 @@
 
     ClassIt& next(ClassIt& it) const {
-      it.next(classes);
-      return it;
+      return ++it;
     }
 
@@ -625 +654 @@
       const ItemList *l;
     public:
-      ItemIt(Invalid): i(0) {}
+      ItemIt(Invalid): l(0) {}
       ItemIt() {}
+      ItemIt(UnionFindEnum const &ufe, const T& a) {
+        l = &ufe.classOf(a);
+        i = l->begin();
+      }
       
       operator const T& () const { return i->me; }
       bool operator == (ItemIt it) const {
-        return (i == it.i);
+        return (l==it.l && i==it.i) || (!valid() && !it.valid());
       }
       bool operator != (ItemIt it) const {
-        return (i != it.i);
+        return !(*this == it);
       }
       bool operator < (ItemIt it) const {
@@ -639 +672 @@
       }
 
-      bool valid() const { return i != 0; }
+      bool operator==(Invalid) const {
+        return !valid();
+      }
+      bool operator!=(Invalid) const {
+        return valid();
+      }
+
+      ItemIt& operator++() {
+        ++i;
+        return *this;
+      }
+
+      // obsoleted:
+      bool valid() const { return l!=0 && i!=l->end(); }
     private:
-      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
-      void next() {
-        ++i; 
-        validate();
-      }
-      void validate() {
-        if ( i == l->end() ) 
-          i = 0;
-      }
+//       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
+//       void next() {
+//      ++i; 
+//      validate();
+//       }
+//       void validate() {
+//      if ( i == l->end() ) 
+//        i = 0;
+//       }
     };
 
@@ -674 +720 @@
      *   }
      * \endcode
+     *
+     * \bug obsoleted, use the new LEMON iterator interface instead
      */
     
     ItemIt& first(ItemIt& it, const T& a) const {
-      it.first( * _find(m[a])->my_class );
+      it = ItemIt(*this, a);
       return it;
     }
@@ -691 +739 @@
      * iterate through the elements of a component.
      * See the example here: \ref first2 "first".
+     *
+     * \bug obsoleted, use the new LEMON iterator interface instead
      */
 
     bool valid(ItemIt const &it) const {
-      return it.valid(); 
+      return it.valid();
     }
 
@@ -707 +757 @@
      * iterate through the elements of a component.
      * See the example here: \ref first2 "first".
+     *
+     * \bug obsoleted, use the new LEMON iterator interface instead
      */
 
     ItemIt& next(ItemIt& it) const {
-      it.next();
-      return it;
+      return ++it;
     }