Author: simonetripodi
Date: Thu Jun 28 12:40:16 2012
New Revision: 1354982
URL: http://svn.apache.org/viewvc?rev=1354982&view=rev
Log:
heap node initialization in the node itself (dropped the ugly 'reset degree'
method)
still working on the CONSOLIDATE method
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=1354982&r1=1354981&r2=1354982&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
Thu Jun 28 12:40:16 2012
@@ -105,6 +105,18 @@ public final class FibonacciHeap<E>
/**
* {@inheritDoc}
+ *
+ * <pre>FIB-HEAP-INSERT(H, x)
+ * 1 degree[x] ← 0
+ * 2 p[x] ← NIL
+ * 3 child[x] ← NIL
+ * 4 left[x] ← x
+ * 5 right[x] ← x
+ * 6 mark[x] ← FALSE
+ * 7 concatenate the root list containing x with root list H
+ * 8 if min[H] = NIL or key[x] < key[min[H]]
+ * 9 then min[H] ← x
+ * 10 n[H] ← n[H] + 1</pre>
*/
public boolean add( E e )
{
@@ -113,7 +125,32 @@ public final class FibonacciHeap<E>
throw new NullPointerException();
}
- insert( new FibonacciHeapNode<E>( e ) );
+ // 1-6 performed in the node initialization
+ FibonacciHeapNode<E> node = new FibonacciHeapNode<E>( e );
+ // 8' if min[H] = NIL
+ if ( isEmpty() )
+ {
+ // then min[H] <- x
+ minimumNode = node;
+ }
+ else
+ {
+ // 7 concatenate the root list containing x with root list H
+ minimumNode.getLeft().setRight( node );
+ node.setLeft( minimumNode.getLeft() );
+ node.setRight( minimumNode );
+ minimumNode.setLeft( node );
+
+ // 8'' if key[x] < key[min[H]]
+ if ( compare( node, minimumNode ) < 0 )
+ {
+ // 9 then min[H] <- x
+ minimumNode = node;
+ }
+ }
+
+ // 10 n[H] <- n[H] + 1
+ size++;
elementsIndex.add( e );
@@ -454,8 +491,12 @@ public final class FibonacciHeap<E>
// 16 if A[i] != NIL
if ( pointer != null )
{
- // FIXME this is totally wrong!!!
- insert( pointer );
+ // TODO 17 then add A[i] to the root list of H
+ // TODO 18 if min[H] = NIL or key[A[i]] ≤
key[min[H]]
+ // TODO 19 then min[H] ← A[i]</pre>
+
+ // FIXME this should be wrong
+ add( pointer.getElement() );
}
}
}
@@ -564,66 +605,6 @@ public final class FibonacciHeap<E>
}
/**
- * Adds a node in the current structure.
- *
- * <pre>FIB-HEAP-INSERT(H, x)
- * 1 degree[x] ← 0
- * 2 p[x] ← NIL
- * 3 child[x] ← NIL
- * 4 left[x] ← x
- * 5 right[x] ← x
- * 6 mark[x] ← FALSE
- * 7 concatenate the root list containing x with root list H
- * 8 if min[H] = NIL or key[x] < key[min[H]]
- * 9 then min[H] ← x
- * 10 n[H] ← n[H] + 1</pre>
- *
- * @param node the node has to be added.
- * @see #offer(Object)
- * @see #add(Object)
- */
- private void insert( FibonacciHeapNode<E> node )
- {
- // 1 degree[x] ← 0
- node.resetDegree();
- // 2 p[x] <- NIL
- node.setParent( null );
- // 3 child[x] <- NIL
- node.setChild( null );
- // 4 left[x] <- x
- node.setLeft( node );
- // 5 right[x] <- x
- node.setRight( node );
- // 6 mark[x] <- FALSE
- node.setMarked( false );
-
- // 8' if min[H] = NIL
- if ( isEmpty() )
- {
- // then min[H] <- x
- minimumNode = node;
- }
- else
- {
- // 7 concatenate the root list containing x with root list H
- minimumNode.getLeft().setRight( node );
- node.setLeft( minimumNode.getLeft() );
- node.setRight( minimumNode );
- minimumNode.setLeft( node );
-
- // 8'' if key[x] < key[min[H]]
- if ( compare( node, minimumNode ) < 0 )
- {
- // 9 then min[H] <- x
- minimumNode = node;
- }
- }
-
- // 10 n[H] <- n[H] + 1
- size++;
- }
-
- /**
* Compare the given objects according to to the specified comparator if
not null,
* according to their natural ordering otherwise.
*
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=1354982&r1=1354981&r2=1354982&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
Thu Jun 28 12:40:16 2012
@@ -55,13 +55,13 @@ final class FibonacciHeapNode<E>
/**
* The number of children in the child list of node {@code x} is stored in
{@code degree[x]}.
*/
- private int degree = 0;
+ private int degree;
/**
* {@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;
+ private boolean marked;
/**
* Build a new {@link FibonacciHeap} node with the given value.
@@ -70,6 +70,20 @@ final class FibonacciHeapNode<E>
*/
public FibonacciHeapNode( E element )
{
+ // 1 degree[x] ← 0
+ degree = 0;
+ // 2 p[x] <- NIL
+ setParent( null );
+ // 3 child[x] <- NIL
+ setChild( null );
+ // 4 left[x] <- x
+ setLeft( this );
+ // 5 right[x] <- x
+ setRight( this );
+ // 6 mark[x] <- FALSE
+ setMarked( false );
+
+ // set the adapted element
this.element = element;
}
@@ -164,14 +178,6 @@ final class FibonacciHeapNode<E>
}
/**
- * Sets the number of children in the child list to {@code 0}.
- */
- public void resetDegree()
- {
- degree = 0;
- }
-
- /**
* Increases the degree of current node.
*
* @see #getDegree()
