commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1144042 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections: ./ FibonacciHeap.java FibonacciHeapNode.java FibonacciNumbers.java
Date Thu, 07 Jul 2011 21:16:03 GMT
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



Mime
View raw message