Author: simonetripodi
Date: Tue Jul 12 20:48:06 2011
New Revision: 1145763
URL: http://svn.apache.org/viewvc?rev=1145763&view=rev
Log:
added FIB-HEAP-LINK(H, y, x) implementation
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java?rev=1145763&r1=1145762&r2=1145763&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
(original)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
Tue Jul 12 20:48:06 2011
@@ -346,7 +346,8 @@ public final class FibonacciHeap<E>
x = pointer;
}
- // TODO FIB-HEAP-LINK(H,y,x)
+ // FIB-HEAP-LINK(H,y,x)
+ link( y, x );
// A[d] <- NIL
nodeSequence.set( degree, null );
@@ -374,6 +375,26 @@ public final class FibonacciHeap<E>
}
/**
+ * Implements the {@code FIB-HEAP-LINK(H, y, x)} function.
+ *
+ * @param y
+ * @param x
+ */
+ private void link( FibonacciHeapNode<E> y, FibonacciHeapNode<E> x )
+ {
+ // remove y from the root list of H
+ y.getLeft().setRight( y.getRight() );
+ y.getRight().setLeft( y.getLeft() );
+
+ // make y a child of x, incrementing degree[x]
+ x.setChild( y );
+ x.incraeseDegree();
+
+ // mark[y] <- FALSE
+ y.setMarked( false );
+ }
+
+ /**
* The potential of Fibonacci heap {@code H} is then defined by
* {@code t(H) + 2m(H)}.
*
