Mailing-List: contact commits-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@commons.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1145414 - in
 /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections:
 FibonacciHeap.java FibonacciHeapNode.java
Date: Tue, 12 Jul 2011 00:57:11 -0000
To: commits@commons.apache.org
From: simonetripodi@apache.org
Message-Id: <20110712005711.DBBB0238896F@eris.apache.org>

Author: simonetripodi
Date: Tue Jul 12 00:57:11 2011
New Revision: 1145414

URL: http://svn.apache.org/viewvc?rev=1145414&view=rev
Log:
adjusting FibonacciHeap implementation according to http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm
not completed yet, still a TODO

Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.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=1145414&r1=1145413&r2=1145414&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 00:57:11 2011
@@ -19,14 +19,17 @@ package org.apache.commons.graph.collect
  * under the License.
  */
 
+import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.Iterator;
+import java.util.List;
 import java.util.Queue;
 
 /**
  * A Fibonacci Heap implementation based on
- * <a href="http://www.cs.princeton.edu/~wayne/cs423/fibonacci/FibonacciHeapAlgorithm.html">Princeton</a> lesson.
+ * <a href="http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm">University of Science and Technology of
+ * China</a> lesson.
  */
 public final class FibonacciHeap<E>
     implements Queue<E>
@@ -38,11 +41,25 @@ public final class FibonacciHeap<E>
      */
     private final Comparator<? super E> comparator;
 
+    /**
+     * The number of nodes currently in {@code H} is kept in {@code n[H]}.
+     */
     private int size = 0;
 
+    /**
+     * {@code t(H)} the number of trees in the root list.
+     */
     private int trees = 0;
 
-    private FibonacciHeapNode<E> root;
+    /**
+     * {@code m(H)} the number of marked nodes in {@code H}.
+     */
+    private int markedNodes = 0;
+
+    /**
+     * The root of the tree containing a minimum key {@code min[H]}.
+     */
+    private FibonacciHeapNode<E> minimumNode;
 
     public FibonacciHeap()
     {
@@ -66,31 +83,20 @@ public final class FibonacciHeap<E>
 
         FibonacciHeapNode<E> node = new FibonacciHeapNode<E>( e );
 
-        if ( root == null )
+        if ( minimumNode == null )
         {
-            root = node;
+            minimumNode = node;
         }
         else
         {
-            node.setPrevious( root );
-            node.setNext( root.getNext() );
-            root.setNext( node );
-            node.getNext().setPrevious( root );
+            node.setLeft( minimumNode );
+            node.setRight( minimumNode.getRight() );
+            minimumNode.setRight( node );
+            node.getRight().setLeft( minimumNode );
 
-            int comparison;
-            if ( comparator != null )
+            if ( compare( minimumNode.getValue(), e ) < 0 )
             {
-                comparison = comparator.compare( root.getValue(), e );
-            }
-            else
-            {
-                Comparable<? super E> rootComparable = (Comparable<? super E>) root.getValue();
-                comparison = rootComparable.compareTo( e );
-            }
-
-            if ( comparison < 0 )
-            {
-                root = node;
+                minimumNode = node;
             }
         }
 
@@ -201,7 +207,11 @@ public final class FibonacciHeap<E>
      */
     public E element()
     {
-        return null;
+        if ( size == 0 )
+        {
+            return null;
+        }
+        return minimumNode.getValue();
     }
 
     /**
@@ -217,11 +227,7 @@ public final class FibonacciHeap<E>
      */
     public E peek()
     {
-        if ( size == 0 )
-        {
-            return null;
-        }
-        return root.getValue();
+        return element();
     }
 
     /**
@@ -229,7 +235,7 @@ public final class FibonacciHeap<E>
      */
     public E poll()
     {
-        return null;
+        return remove();
     }
 
     /**
@@ -237,12 +243,94 @@ public final class FibonacciHeap<E>
      */
     public E remove()
     {
-        return null;
+        if ( size == 0 )
+        {
+            return null;
+        }
+
+        FibonacciHeapNode<E> currentRoot = minimumNode;
+
+        int degree = currentRoot.getDegree();
+        FibonacciHeapNode<E> currentChild = currentRoot.getChild();
+        FibonacciHeapNode<E> pointer;
+
+        while ( degree > 0 )
+        {
+            pointer = currentChild.getRight();
+
+            currentChild.getLeft().setRight( currentChild.getRight() );
+            currentChild.getRight().setLeft( currentChild.getLeft() );
+
+            currentChild.setLeft( minimumNode );
+            currentChild.setRight( minimumNode.getRight() );
+            minimumNode.setRight( currentChild );
+            currentChild.getRight().setLeft( currentChild );
+
+            currentChild.setParent( null );
+            currentChild = pointer;
+            degree--;
+        }
+
+        currentRoot.getLeft().setRight( currentRoot.getRight() );
+        currentRoot.getRight().setLeft( currentRoot.getLeft() );
+
+        if ( currentRoot == currentRoot.getRight() )
+        {
+            minimumNode = null;
+        }
+        else
+        {
+            minimumNode = currentRoot.getRight();
+            consolidate();
+        }
+
+        size--;
+
+        return currentRoot.getValue();
     }
 
     private void consolidate()
     {
+        if ( minimumNode == null )
+        {
+            return;
+        }
+
+        List<FibonacciHeapNode<E>> nodeSequence = new ArrayList<FibonacciHeapNode<E>>();
+
+        FibonacciHeapNode<E> pointer = minimumNode.getRight();
+
+        while ( pointer != minimumNode )
+        {
+            int degree = pointer.getDegree();
+
+            
+
+            pointer = pointer.getRight();
+        }
+
         
     }
 
+    /**
+     * The potential of Fibonacci heap {@code H} is then defined by
+     * {@code t(H) + 2m(H)}.
+     *
+     * @return The potential of this Fibonacci heap.
+     */
+    public int potential()
+    {
+        return trees + 2 * markedNodes;
+    }
+
+    private int compare( E o1, E o2 )
+    {
+        if ( comparator != null )
+        {
+            return comparator.compare( o1, o2 );
+        }
+        Comparable<? super E> o1Comparable = (Comparable<? super E>) o1;
+        return o1Comparable.compareTo( o2 );
+    }
+
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java?rev=1145414&r1=1145413&r2=1145414&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java Tue Jul 12 00:57:11 2011
@@ -19,6 +19,9 @@ package org.apache.commons.graph.collect
  * under the License.
  */
 
+/**
+ * 
+ */
 final class FibonacciHeapNode<E>
 {
 
@@ -26,14 +29,27 @@ final class FibonacciHeapNode<E>
 
     private FibonacciHeapNode<E> parent;
 
-    private FibonacciHeapNode<E> previous;
-
-    private FibonacciHeapNode<E> next;
+    /**
+     * {@code left[x]}
+     */
+    private FibonacciHeapNode<E> left = this;
+
+    /**
+     * {@code right[x]}
+     */
+    private FibonacciHeapNode<E> right = this;
 
     private FibonacciHeapNode<E> child;
 
+    /**
+     * The number of children in the child list of node {@code x} is stored in {@code degree[x]}.
+     */
     private int degree = 0;
 
+    /**
+     * {@code mark[x]} indicates whether node {@code x} has lost a child since
+     * the last time {@code x} was made the child of another node.
+     */
     private boolean marked = false;
 
     public FibonacciHeapNode( E value )
@@ -51,24 +67,24 @@ final class FibonacciHeapNode<E>
         this.parent = parent;
     }
 
-    public FibonacciHeapNode<E> getPrevious()
+    public FibonacciHeapNode<E> getLeft()
     {
-        return previous;
+        return left;
     }
 
-    public void setPrevious( FibonacciHeapNode<E> previous )
+    public void setLeft( FibonacciHeapNode<E> left )
     {
-        this.previous = previous;
+        this.left = left;
     }
 
-    public FibonacciHeapNode<E> getNext()
+    public FibonacciHeapNode<E> getRight()
     {
-        return next;
+        return right;
     }
 
-    public void setNext( FibonacciHeapNode<E> next )
+    public void setRight( FibonacciHeapNode<E> right )
     {
-        this.next = next;
+        this.right = right;
     }
 
     public FibonacciHeapNode<E> getChild()