# HG changeset patch
# User klao
# Date 1142013986 0
# Node ID cf012a7c7f695f6ef06f7239128271af83fc84bc
# Parent  9ff31b5090bd71c4678ea00c722b1432e86a0b4e
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

diff -r 9ff31b5090bd -r cf012a7c7f69 lemon/unionfind.h
--- a/lemon/unionfind.h	Wed Mar 08 13:10:43 2006 +0000
+++ b/lemon/unionfind.h	Fri Mar 10 18:06:26 2006 +0000
@@ -257,6 +257,10 @@
       return comp;
     }
 
+    const ItemList& classOf(const T &a) const {
+      return *_find(m[a])->my_class;
+    }
+
   public:
     UnionFindEnum(MapType& _m) : m(_m) {}
 
@@ -343,7 +347,7 @@
 	alist.splice(alist.end(),*cb->my_class);
 
 	classes.erase(cb->my_class);
-	cb->my_class = 0;
+	// ehem: cb->my_class = 0;
       }
       else {
 
@@ -354,7 +358,7 @@
 	blist.splice(blist.end(),*ca->my_class);
 
 	classes.erase(ca->my_class);
-	ca->my_class = 0;
+	// ehem: ca->my_class = 0;
       }
 
       return true;
@@ -416,7 +420,7 @@
       if (la == ia) return;
 
       ia->my_class = la->my_class;
-      la->my_class = 0;
+      // ehem: la->my_class = 0;
 
       ia->size = la->size;
 
@@ -474,7 +478,7 @@
       }
 
       ai->parent = clit;
-      ai->my_class = 0;
+      // ehem: ai->my_class = 0;
       ++clit->size;
 
       return true;
@@ -484,21 +488,21 @@
     /**
      * \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);
       if (la == ma) {
 	if (ma -> size == 1){
 	  classes.erase(ma->my_class);
-	  m.set(a,0);
+	  // ehem: m.set(a,0);
 	  return;
 	}
 	++la;
@@ -512,23 +516,25 @@
 
       la->size--;
       la->my_class->erase(ma);
-      m.set(a,0);
+      // ehem: m.set(a,0);
     }
 
     /**
      * \brief Removes the component of the given element from the structure.
      *
      * 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);
     }
 
@@ -537,34 +543,54 @@
       friend class UnionFindEnum;
 
       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);
+	return (ll.begin())->me;
       }
-      bool operator != (ClassIt it) const {
-	return (i != it.i);
+      bool operator == (ClassIt const &it) const {
+	return (l==it.l && i==it.i) || (!valid() && !it.valid());
       }
-      bool operator < (ClassIt it) const {
+      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;
+//       }
     };
 
     /**
@@ -583,10 +609,12 @@
      *    cout << iter << endl;
      *  }
      * \endcode
+     *
+     * \bug obsoleted, use the new LEMON iterator interface instead
      */
 
     ClassIt& first(ClassIt& it) const {
-      it.first(classes);
+      it = ClassIt(*this);
       return it;
     }
 
@@ -597,6 +625,8 @@
      *
      * 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
      */
 
     bool valid(ClassIt const &it) const {
@@ -613,8 +643,7 @@
      */
 
     ClassIt& next(ClassIt& it) const {
-      it.next(classes);
-      return it;
+      return ++it;
     }
 
 
@@ -624,31 +653,48 @@
       IcIter i;
       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 {
 	return (i < it.i);
       }
 
-      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;
+//       }
     };
 
 
@@ -673,10 +719,12 @@
      *     cout << iiter << endl;
      *   }
      * \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;
     }
 
@@ -690,10 +738,12 @@
      * and \ref next2 "next" methods you can
      * 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();
     }
 
     /**
@@ -706,11 +756,12 @@
      * and \ref next2 "next" methods you can
      * 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;
     }
     
   };