commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1145486 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
Date Tue, 12 Jul 2011 08:23:30 GMT
Author: simonetripodi
Date: Tue Jul 12 08:23:30 2011
New Revision: 1145486

URL: http://svn.apache.org/viewvc?rev=1145486&view=rev
Log:
added inline comments in poll() method

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=1145486&r1=1145485&r2=1145486&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 08:23:30 2011
@@ -257,17 +257,21 @@ public final class FibonacciHeap<E>
      */
     public E poll()
     {
+        // FIB-HEAP-EXTRACT-MIN(H)
+
         if ( isEmpty() )
         {
             return null;
         }
 
+        // z <- min[H]
         FibonacciHeapNode<E> currentMinimum = minimumNode;
 
         int degree = currentMinimum.getDegree();
         FibonacciHeapNode<E> currentChild = currentMinimum.getChild();
         FibonacciHeapNode<E> pointer;
 
+        // for each child x of z
         while ( degree > 0 )
         {
             pointer = currentChild.getRight();
@@ -280,6 +284,7 @@ public final class FibonacciHeap<E>
             minimumNode.setRight( currentChild );
             currentChild.getRight().setLeft( currentChild );
 
+            // p[x] <- NIL
             currentChild.setParent( null );
             currentChild = pointer;
             degree--;
@@ -288,16 +293,23 @@ public final class FibonacciHeap<E>
         currentMinimum.getLeft().setRight( currentMinimum.getRight() );
         currentMinimum.getRight().setLeft( currentMinimum.getLeft() );
 
+        // remove z from the root list of H
+
+        // if z = right[z]
         if ( currentMinimum == currentMinimum.getRight() )
         {
+            // min[H] <- NIL
             minimumNode = null;
         }
         else
         {
+            // min[H] <- right[z]
             minimumNode = currentMinimum.getRight();
+            // CONSOLIDATE(H)
             consolidate();
         }
 
+        // n[H] <- n[H] - 1
         size--;
 
         return currentMinimum.getElement();



Mime
View raw message