Changes in lemon/unionfind.h [236:da953e387d31:440:88ed40ad0d4f] in lemon-1.2

File:

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

lemon/unionfind.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -1178 +1178 @@
             if (nodes[nodes[jd].next].size < cmax) {
               pushLeft(nodes[jd].next, nodes[jd].left);
-              if (less(nodes[jd].left, nodes[jd].next)) {
-                nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
-                nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
+              if (less(jd, nodes[jd].next) ||
+                  nodes[jd].item == nodes[pd].item) {
+                nodes[nodes[jd].next].prio = nodes[jd].prio;
+                nodes[nodes[jd].next].item = nodes[jd].item;
               }
               popLeft(pd);
@@ -1189 +1190 @@
               popLeft(nodes[jd].next);
               pushRight(jd, ld);
-              if (less(ld, nodes[jd].left)) {
+              if (less(ld, nodes[jd].left) ||
+                  nodes[ld].item == nodes[pd].item) {
                 nodes[jd].item = nodes[ld].item;
-                nodes[jd].prio = nodes[jd].prio;
+                nodes[jd].prio = nodes[ld].prio;
               }
               if (nodes[nodes[jd].next].item == nodes[ld].item) {
@@ -1220 +1222 @@
             if (nodes[nodes[jd].prev].size < cmax) {
               pushRight(nodes[jd].prev, nodes[jd].right);
-              if (less(nodes[jd].right, nodes[jd].prev)) {
-                nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
-                nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
+              if (less(jd, nodes[jd].prev) ||
+                  nodes[jd].item == nodes[pd].item) {
+                nodes[nodes[jd].prev].prio = nodes[jd].prio;
+                nodes[nodes[jd].prev].item = nodes[jd].item;
               }
               popRight(pd);
@@ -1231 +1234 @@
               popRight(nodes[jd].prev);
               pushLeft(jd, ld);
-              if (less(ld, nodes[jd].right)) {
+              if (less(ld, nodes[jd].right) ||
+                  nodes[ld].item == nodes[pd].item) {
                 nodes[jd].item = nodes[ld].item;
-                nodes[jd].prio = nodes[jd].prio;
+                nodes[jd].prio = nodes[ld].prio;
               }
               if (nodes[nodes[jd].prev].item == nodes[ld].item) {
@@ -1251 +1255 @@
       return comp(nodes[id].prio, nodes[jd].prio);
     }
-
-    bool equal(int id, int jd) const {
-      return !less(id, jd) && !less(jd, id);
-    }
-
 
   public:
@@ -1401 +1400 @@
               push(new_id, right_id);
               pushRight(new_id, ~(classes[r].parent));
-              setPrio(new_id);
+
+              if (less(~classes[r].parent, right_id)) {
+                nodes[new_id].item = nodes[~classes[r].parent].item;
+                nodes[new_id].prio = nodes[~classes[r].parent].prio;
+              } else {
+                nodes[new_id].item = nodes[right_id].item;
+                nodes[new_id].prio = nodes[right_id].prio;
+              }
 
               id = nodes[id].parent;
@@ -1441 +1447 @@
               push(new_id, left_id);
               pushLeft(new_id, ~(classes[l].parent));
-              setPrio(new_id);
+
+              if (less(~classes[l].parent, left_id)) {
+                nodes[new_id].item = nodes[~classes[l].parent].item;
+                nodes[new_id].prio = nodes[~classes[l].parent].prio;
+              } else {
+                nodes[new_id].item = nodes[left_id].item;
+                nodes[new_id].prio = nodes[left_id].prio;
+              }
 
               id = nodes[id].parent;