Author: simonetripodi
Date: Thu Jul 7 21:16:02 2011
New Revision: 1144042
URL: http://svn.apache.org/viewvc?rev=1144042&view=rev
Log:
started implementing a Fibonacci Heap data structure, useful to improve
algorithms performance that require storing data in a priority queue
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
(with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
(with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java
(with props)
Added:
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=1144042&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
(added)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
Thu Jul 7 21:16:02 2011
@@ -0,0 +1,208 @@
+package org.apache.commons.graph.collections;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+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.
+ */
+public final class FibonacciHeap<E>
+ implements Queue<E>
+{
+
+ /**
+ * The comparator, or null if priority queue uses elements'
+ * natural ordering.
+ */
+ private final Comparator<? super E> comparator;
+
+ private int size = 0;
+
+ private FibonacciHeapNode<E> root;
+
+ public FibonacciHeap()
+ {
+ this(null);
+ }
+
+ public FibonacciHeap( Comparator<? super E> comparator )
+ {
+ this.comparator = comparator;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean add( E e )
+ {
+ if ( e == null )
+ {
+ throw new NullPointerException();
+ }
+
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean addAll( Collection<? extends E> c )
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void clear()
+ {
+
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean contains( Object o )
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean containsAll( Collection<?> c )
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isEmpty()
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Iterator<E> iterator()
+ {
+ return null;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean remove( Object o )
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean removeAll( Collection<?> c )
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean retainAll( Collection<?> c )
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int size()
+ {
+ return size;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Object[] toArray()
+ {
+ return null;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public <T> T[] toArray( T[] a )
+ {
+ return null;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public E element()
+ {
+ return null;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean offer( E arg0 )
+ {
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public E peek()
+ {
+ if ( size == 0 )
+ {
+ return null;
+ }
+ return root.getValue();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public E poll()
+ {
+ return null;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public E remove()
+ {
+ return null;
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added:
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=1144042&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
(added)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
Thu Jul 7 21:16:02 2011
@@ -0,0 +1,109 @@
+package org.apache.commons.graph.collections;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+final class FibonacciHeapNode<T>
+{
+
+ private final T value;
+
+ private FibonacciHeapNode<T> parent;
+
+ private FibonacciHeapNode<T> previous;
+
+ private FibonacciHeapNode<T> next;
+
+ private FibonacciHeapNode<T> child;
+
+ private int degree = 0;
+
+ private boolean marked = false;
+
+ public FibonacciHeapNode( T value )
+ {
+ this.value = value;
+ }
+
+ public FibonacciHeapNode<T> getParent()
+ {
+ return parent;
+ }
+
+ public void setParent( FibonacciHeapNode<T> parent )
+ {
+ this.parent = parent;
+ }
+
+ public FibonacciHeapNode<T> getPrevious()
+ {
+ return previous;
+ }
+
+ public void setPrevious( FibonacciHeapNode<T> previous )
+ {
+ this.previous = previous;
+ }
+
+ public FibonacciHeapNode<T> getNext()
+ {
+ return next;
+ }
+
+ public void setNext( FibonacciHeapNode<T> next )
+ {
+ this.next = next;
+ }
+
+ public FibonacciHeapNode<T> getChild()
+ {
+ return child;
+ }
+
+ public void setChild( FibonacciHeapNode<T> child )
+ {
+ this.child = child;
+ }
+
+ public int getDegree()
+ {
+ return degree;
+ }
+
+ public void setDegree( int degree )
+ {
+ this.degree = degree;
+ }
+
+ public boolean isMarked()
+ {
+ return marked;
+ }
+
+ public void setMarked( boolean marked )
+ {
+ this.marked = marked;
+ }
+
+ public T getValue()
+ {
+ return value;
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java?rev=1144042&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java
(added)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java
Thu Jul 7 21:16:02 2011
@@ -0,0 +1,57 @@
+package org.apache.commons.graph.collections;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ *
+ */
+final class FibonacciNumbers
+{
+
+ private static final List<Integer> CACHE = new ArrayList<Integer>();
+
+ static
+ {
+ CACHE.add( 0 );
+ CACHE.add( 1 );
+ }
+
+ public static int fibonacci( int n )
+ {
+ if ( CACHE.size() <= n )
+ {
+ CACHE.add( n, fibonacci( n - 1 ) + fibonacci( n - 2 ) );
+ }
+
+ return CACHE.get( n );
+ }
+
+ /**
+ * This class cannot be instantiated.
+ */
+ private FibonacciNumbers()
+ {
+ // do nothing
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciNumbers.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
