commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1357190 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
Date Wed, 04 Jul 2012 09:23:12 GMT
Author: simonetripodi
Date: Wed Jul  4 09:23:11 2012
New Revision: 1357190

URL: http://svn.apache.org/viewvc?rev=1357190&view=rev
Log:
added the FibonacciHeap#moveToRoot( FibonacciHeapNode<E> node ) method and fixed wrong
assumptions in add(), consolidate() and cut() methods

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=1357190&r1=1357189&r2=1357190&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
Wed Jul  4 09:23:11 2012
@@ -104,29 +104,15 @@ public final class FibonacciHeap<E>
     }
 
     /**
-     * {@inheritDoc}
+     * Moves the target node in the {@code H} root nodes.
      *
-     * <pre>FIB-HEAP-INSERT(H, x)
-     * 1  degree[x] &larr; 0
-     * 2  p[x] &larr; NIL
-     * 3  child[x] &larr; NIL
-     * 4  left[x] &larr; x
-     * 5  right[x] &larr; x
-     * 6  mark[x] &larr; FALSE
-     * 7  concatenate the root list containing x with root list H
-     * 8  if min[H] = NIL or key[x] &lt; key[min[H]]
-     * 9     then min[H] &larr; x
-     * 10  n[H] &larr; n[H] + 1</pre>
+     * @param node the node has to be moved in the {@code H} root nodes
+     * @see #add(Object)
+     * @see #consolidate()
+     * @see #cut(FibonacciHeapNode, FibonacciHeapNode)
      */
-    public boolean add( E e )
+    private void moveToRoot( FibonacciHeapNode<E> node )
     {
-        if ( e == null )
-        {
-            throw new NullPointerException();
-        }
-
-        // 1-6 performed in the node initialization
-        FibonacciHeapNode<E> node = new FibonacciHeapNode<E>( e );
         // 8'  if min[H] = NIL
         if ( isEmpty() )
         {
@@ -148,6 +134,35 @@ public final class FibonacciHeap<E>
                 minimumNode = node;
             }
         }
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * <pre>FIB-HEAP-INSERT(H, x)
+     * 1  degree[x] &larr; 0
+     * 2  p[x] &larr; NIL
+     * 3  child[x] &larr; NIL
+     * 4  left[x] &larr; x
+     * 5  right[x] &larr; x
+     * 6  mark[x] &larr; FALSE
+     * 7  concatenate the root list containing x with root list H
+     * 8  if min[H] = NIL or key[x] &lt; key[min[H]]
+     * 9     then min[H] &larr; x
+     * 10  n[H] &larr; n[H] + 1</pre>
+     */
+    public boolean add( E e )
+    {
+        if ( e == null )
+        {
+            throw new NullPointerException();
+        }
+
+        // 1-6 performed in the node initialization
+        FibonacciHeapNode<E> node = new FibonacciHeapNode<E>( e );
+
+        // 7-9 performed in the #moveToRoot( FibonacciHeapNode<E> ) method
+        moveToRoot( node );
 
         // 10  n[H] <- n[H] + 1
         size++;
@@ -504,12 +519,7 @@ public final class FibonacciHeap<E>
             // 16 if A[i] != NIL
             if ( pointer != null )
             {
-                // TODO 17            then add A[i] to the root list of H
-                // TODO 18                 if min[H] = NIL or key[A[i]] &le; key[min[H]]
-                // TODO 19                    then min[H] &larr; A[i]</pre>
-
-                // FIXME this should be wrong
-                add( pointer.getElement() );
+                moveToRoot( pointer );
             }
         }
     }
@@ -560,7 +570,7 @@ public final class FibonacciHeap<E>
         y.decraeseDegree();
 
         // add x to the root list of H
-        // TODO!!!
+        moveToRoot( x );
 
         // p[x] <- NIL
         x.setParent( null );



Mime
View raw message