Changeset 438:81d40f1c850c in lemon-main

Timestamp:

12/21/08 20:45:25 (16 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Children:

439:1229dc2f1d36, 475:8b56605db6a8

Phase:

public

Message:

Bug fix in heap unionfind (ticket #197)

The previous bugfix set the minimum value in internal nodes
wrongly. It corrects the problem.

File:

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

lemon/unionfind.h

@@ -1178 +1178 @@
             if (nodes[nodes[jd].next].size < cmax) {
               pushLeft(nodes[jd].next, nodes[jd].left);
-              if (nodes[jd].item == nodes[pd].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;
@@ -1221 +1222 @@
             if (nodes[nodes[jd].prev].size < cmax) {
               pushRight(nodes[jd].prev, nodes[jd].right);
-              if (nodes[jd].item == nodes[pd].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;
@@ -1253 +1255 @@
       return comp(nodes[id].prio, nodes[jd].prio);
     }
-
-    bool equal(int id, int jd) const {
-      return !less(id, jd) && !less(jd, id);
-    }
-
 
   public: