Changeset 481:54d8feda437b in lemon-0.x for src/work/johanna/unionfind.h

Timestamp:

04/29/04 18:45:40 (20 years ago)

Author:

beckerjc

Branch:

default

Phase:

public

Convert:

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

Message:

Three new methods in UnionFindEnum?.
UnionFindEnum? completed.

File:

• src/work/johanna/unionfind.h (modified) (2 diffs)

src/work/johanna/unionfind.h

@@ -265 +265 @@
 
     /**
+     * \brief Insert the given element into the component of the others.
+     *
+     * This methods insert the element \e a into the component of the
+     * element \e comp. 
+     */
+
+    void insert(const T &a, const T &comp) {
+      
+      IIter clit = _find(m[comp]);
+      ItemList &c = *clit->my_class;
+      c.push_back(ItemType(a,0));
+      IIter ai = c.end();
+      --ai;
+      ai->parent = clit;
+      m.set(a, ai);
+      ++clit->size;
+    }
+
+
+    /**
      * \brief Find the leader of the component of the given element.
      *
@@ -384 +404 @@
       ia->parent = ia;
       la->parent = ia;
+    }
+
+    /**
+     * \brief Move the given element to an other component.
+     *
+     * This method moves the element \e a from its component
+     * to the component of \e comp.
+     * If \e a and \e comp are in the same component then
+     * it returns false otherwise it returns true.
+     */
+
+    bool move(const T &a, const T &comp) {
+
+      IIter ai = m[a];
+      IIter lai = _find(ai);
+      IIter clit = _find(m[comp]);
+
+      if (lai == clit)
+        return false;
+
+      ItemList &c = *clit->my_class;
+
+      bool is_leader = (lai == ai);
+      bool singleton = false;
+
+      if (is_leader) {
+        ++lai;
+      }
+
+      c.splice(c.end(), *lai->my_class, ai);
+
+      if (is_leader) {
+        if (ai->size == 1) {
+          classes.erase(ai->my_class);
+          singleton = true;
+        }
+        else {
+          lai->size = ai->size; 
+          lai->my_class = ai->my_class; 
+        }
+      }
+      if (!singleton) {
+        for (IIter i = lai; i != lai->my_class->end(); ++i)
+          i->parent = lai;
+        --lai->size;
+      }
+
+      ai->parent = clit;
+      ai->my_class = 0;
+      ++clit->size;
+
+      return true;
     }