You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@avalon.apache.org by do...@apache.org on 2001/11/13 10:39:02 UTC
cvs commit: jakarta-avalon-excalibur/src/java/org/apache/avalon/excalibur/collections BinaryHeap.java PriorityQueue.java SynchronizedPriorityQueue.java
donaldp 01/11/13 01:39:02
Modified: src/java/org/apache/avalon/excalibur/collections
BinaryHeap.java PriorityQueue.java
SynchronizedPriorityQueue.java
Log:
Updated the BinaryHeap and PriorityQueue interface to work with objects rather than Comparables.
Optimized code to replace *2 and /2 by equivelent shifts.
Use Comparators inside BinaryHeap. This is to allow users to pass in Comparators that can sort other objects according to other schemes - and the objects added to heap no longer need to be Comparables.
Submitted By: "Chad Stansbury" <st...@earthlink.net>
Revision Changes Path
1.4 +101 -107 jakarta-avalon-excalibur/src/java/org/apache/avalon/excalibur/collections/BinaryHeap.java
Index: BinaryHeap.java
===================================================================
RCS file: /home/cvs/jakarta-avalon-excalibur/src/java/org/apache/avalon/excalibur/collections/BinaryHeap.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- BinaryHeap.java 2001/11/03 02:13:29 1.3
+++ BinaryHeap.java 2001/11/13 09:39:02 1.4
@@ -7,47 +7,111 @@
*/
package org.apache.avalon.excalibur.collections;
+import java.util.Comparator;
import java.util.NoSuchElementException;
/**
- * Iterface for priority queues.
- * This interface does not dictate whether it is min or max heap.
+ * BinaryHeap implementation of priority queue.
+ * The heap is either a minimum or maximum heap as determined
+ * by parameters passed to constructor.
*
* @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
* @author <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
- * @version CVS $Revision: 1.3 $ $Date: 2001/11/03 02:13:29 $
+ * @author <a href="mailto:stansburyc@earthlink.net">Chad Stansbury</a>
+ * @version CVS $Revision: 1.4 $ $Date: 2001/11/13 09:39:02 $
* @since 4.0
*/
public final class BinaryHeap
implements PriorityQueue
{
- private static final int DEFAULT_CAPACITY = 13;
+ private final static class MinComparator
+ implements Comparator
+ {
+ public final int compare( final Object lhs, final Object rhs )
+ {
+ return ((Comparable)lhs).compareTo(rhs);
+ }
+ }
+
+ private final static class MaxComparator
+ implements Comparator
+ {
+ public final int compare( final Object lhs, final Object rhs )
+ {
+ return ((Comparable)rhs).compareTo(lhs);
+ }
+ }
- private int m_size;
- private Comparable[] m_elements;
- private boolean m_isMinHeap;
+ private static final Comparator MIN_COMPARATOR = new MinComparator();
+ private static final Comparator MAX_COMPARATOR = new MaxComparator();
+ private static final int DEFAULT_CAPACITY = 13;
+ private static final Comparator DEFAULT_COMPARATOR = MIN_COMPARATOR;
+ private int m_size;
+ private Object[] m_elements;
+ private Comparator m_comparator;
+ /**
+ * Instantiates a new min binary heap with the default initial capacity.
+ */
public BinaryHeap()
{
- this( DEFAULT_CAPACITY, true );
+ this( DEFAULT_CAPACITY, DEFAULT_COMPARATOR );
}
+ /**
+ * Instantiates a new min binary heap with the given initial capacity.
+ */
public BinaryHeap( final int capacity )
+ {
+ this( capacity, DEFAULT_COMPARATOR );
+ }
+
+ /**
+ * Instantiates a new binary heap with the default initial capacity and
+ * ordered using the given Comparator.
+ */
+ public BinaryHeap( final Comparator comparator )
{
- this( capacity, true );
+ this( DEFAULT_CAPACITY, comparator );
}
+ /**
+ * Instantiates a new binary heap with the given initial capacity and
+ * ordered using the given Comparator.
+ */
+ public BinaryHeap( final int capacity, final Comparator comparator )
+ {
+ //+1 as 0 is noop
+ m_elements = new Object[ capacity + 1 ];
+ m_comparator = comparator;
+ }
+
+ /**
+ * Create a binary heap of Comparables. Takes a parameter
+ * to specify whether it is a minimum or maximum heap.
+ *
+ * @param isMinHeap true to make it a minimum heap, false to make it a max heap
+ */
public BinaryHeap( final boolean isMinHeap )
{
this( DEFAULT_CAPACITY, isMinHeap );
}
+ /**
+ * Create a binary heap of Comparables. Takes a parameter
+ * to specify whether it is a minimum or maximum heap and another
+ * parameter to specify the size of the heap.
+ *
+ * @param capacity the size of the heap
+ * @param isMinHeap true to make it a minimum heap, false to make it a max heap
+ */
public BinaryHeap( final int capacity, final boolean isMinHeap )
{
- m_isMinHeap = isMinHeap;
-
//+1 as 0 is noop
- m_elements = new Comparable[ capacity + 1 ];
+ m_elements = new Object[ capacity + 1 ];
+
+ if( isMinHeap ) m_comparator = MIN_COMPARATOR;
+ else m_comparator = MAX_COMPARATOR;
}
/**
@@ -84,22 +148,14 @@
*
* @param element the element to be inserted
*/
- public void insert( final Comparable element )
+ public void insert( final Object element )
{
if( isFull() )
{
grow();
}
- //percolate element to it's place in tree
- if( m_isMinHeap )
- {
- percolateUpMinHeap( element );
- }
- else
- {
- percolateUpMaxHeap( element );
- }
+ percolateUpHeap( element );
}
/**
@@ -108,7 +164,7 @@
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
- public Comparable peek() throws NoSuchElementException
+ public Object peek() throws NoSuchElementException
{
if( isEmpty() )
{
@@ -126,9 +182,9 @@
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
- public Comparable pop() throws NoSuchElementException
+ public Object pop() throws NoSuchElementException
{
- final Comparable result = peek();
+ final Object result = peek();
m_elements[ 1 ] = m_elements[ m_size-- ];
//set the unused element to 'null' so that the garbage collector
@@ -137,15 +193,7 @@
if( m_size != 0 )
{
- //percolate top element to it's place in tree
- if( m_isMinHeap )
- {
- percolateDownMinHeap( 1 );
- }
- else
- {
- percolateDownMaxHeap( 1 );
- }
+ percolateDownHeap( 1 );
}
return result;
@@ -153,73 +201,35 @@
/**
* Percolate element down heap from top.
- * Assume it is a maximum heap.
- *
- * @param element the element
- */
- private void percolateDownMinHeap( final int index )
- {
- final Comparable element = m_elements[ index ];
-
- int hole = index;
-
- while( (hole * 2) <= m_size )
- {
- int child = hole * 2;
-
- //if we have a right child and that child can not be percolated
- //up then move onto other child
- if( child != m_size &&
- m_elements[ child + 1 ].compareTo( m_elements[ child ] ) < 0 )
- {
- child++;
- }
-
- //if we found resting place of bubble then terminate search
- if( m_elements[ child ].compareTo( element ) >= 0 )
- {
- break;
- }
-
- m_elements[ hole ] = m_elements[ child ];
- hole = child;
- }
-
- m_elements[ hole ] = element;
- }
-
- /**
- * Percolate element down heap from top.
- * Assume it is a maximum heap.
*
* @param element the element
*/
- private void percolateDownMaxHeap( final int index )
+ private void percolateDownHeap( final int index )
{
- final Comparable element = m_elements[ index ];
+ final Object element = m_elements[ index ];
int hole = index;
+ int child = hole << 1;
- while( (hole * 2) <= m_size )
+ while( child <= m_size )
{
- int child = hole * 2;
-
//if we have a right child and that child can not be percolated
//up then move onto other child
if( child != m_size &&
- m_elements[ child + 1 ].compareTo( m_elements[ child ] ) > 0 )
+ m_comparator.compare( m_elements[ child + 1 ], m_elements[ child ] ) < 0 )
{
child++;
}
//if we found resting place of bubble then terminate search
- if( m_elements[ child ].compareTo( element ) <= 0 )
+ if( m_comparator.compare( m_elements[ child ], element ) >= 0 )
{
break;
}
m_elements[ hole ] = m_elements[ child ];
hole = child;
+ child = hole << 1;
}
m_elements[ hole ] = element;
@@ -227,60 +237,44 @@
/**
* Percolate element up heap from bottom.
- * Assume it is a maximum heap.
*
* @param element the element
*/
- private void percolateUpMinHeap( final Comparable element )
+ private void percolateUpHeap( final Object element )
{
int hole = ++m_size;
+ int next = hole >> 1;
m_elements[ hole ] = element;
while( hole > 1 &&
- element.compareTo( m_elements[ hole / 2 ] ) < 0 )
+ m_comparator.compare( element, m_elements[ next ] ) < 0 )
{
- //save element that is being pushed down
- //as the element "bubble" is percolated up
- final int next = hole / 2;
m_elements[ hole ] = m_elements[ next ];
hole = next;
+ next = hole >> 1;
}
m_elements[ hole ] = element;
}
/**
- * Percolate element up heap from bottom.
- * Assume it is a maximum heap.
- *
- * @param element the element
+ * Grows the heap by a factor of 2.
*/
- private void percolateUpMaxHeap( final Comparable element )
- {
- int hole = ++m_size;
-
- while( hole > 1 &&
- element.compareTo( m_elements[ hole / 2 ] ) > 0 )
- {
- //save element that is being pushed down
- //as the element "bubble" is percolated up
- final int next = hole / 2;
- m_elements[ hole ] = m_elements[ next ];
- hole = next;
- }
-
- m_elements[ hole ] = element;
- }
-
private void grow()
{
- final Comparable[] elements =
- new Comparable[ m_elements.length * 2 ];
+ final Object[] elements =
+ new Object[ m_elements.length * 2 ];
System.arraycopy( m_elements, 0, elements, 0, m_elements.length );
m_elements = elements;
}
+ /**
+ * Create a string representing heap
+ * and all elements in heap.
+ *
+ * @return the string representing heap
+ */
public String toString()
{
final StringBuffer sb = new StringBuffer();
1.3 +4 -4 jakarta-avalon-excalibur/src/java/org/apache/avalon/excalibur/collections/PriorityQueue.java
Index: PriorityQueue.java
===================================================================
RCS file: /home/cvs/jakarta-avalon-excalibur/src/java/org/apache/avalon/excalibur/collections/PriorityQueue.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- PriorityQueue.java 2001/08/07 10:57:04 1.2
+++ PriorityQueue.java 2001/11/13 09:39:02 1.3
@@ -14,7 +14,7 @@
* This interface does not dictate whether it is min or max heap.
*
* @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
- * @version CVS $Revision: 1.2 $ $Date: 2001/08/07 10:57:04 $
+ * @version CVS $Revision: 1.3 $ $Date: 2001/11/13 09:39:02 $
* @since 4.0
*/
public interface PriorityQueue
@@ -36,7 +36,7 @@
*
* @param element the element to be inserted
*/
- void insert( Comparable element );
+ void insert( Object element );
/**
* Return element on top of heap but don't remove it.
@@ -44,7 +44,7 @@
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
- Comparable peek() throws NoSuchElementException;
+ Object peek() throws NoSuchElementException;
/**
* Return element on top of heap and remove it.
@@ -52,6 +52,6 @@
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
- Comparable pop() throws NoSuchElementException;
+ Object pop() throws NoSuchElementException;
}
1.4 +5 -4 jakarta-avalon-excalibur/src/java/org/apache/avalon/excalibur/collections/SynchronizedPriorityQueue.java
Index: SynchronizedPriorityQueue.java
===================================================================
RCS file: /home/cvs/jakarta-avalon-excalibur/src/java/org/apache/avalon/excalibur/collections/SynchronizedPriorityQueue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- SynchronizedPriorityQueue.java 2001/08/29 15:57:28 1.3
+++ SynchronizedPriorityQueue.java 2001/11/13 09:39:02 1.4
@@ -15,7 +15,7 @@
* defined in the PriorityQueue interface.
*
* @author <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
- * @version CVS $Revision: 1.3 $ $Date: 2001/08/29 15:57:28 $
+ * @version CVS $Revision: 1.4 $ $Date: 2001/11/13 09:39:02 $
* @since 4.0
*/
public final class SynchronizedPriorityQueue
@@ -57,7 +57,7 @@
*
* @param element the element to be inserted
*/
- public void insert( final Comparable element )
+ public void insert( final Object element )
{
synchronized( m_priorityQueue )
{
@@ -71,7 +71,7 @@
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
- public Comparable peek() throws NoSuchElementException
+ public Object peek() throws NoSuchElementException
{
synchronized( m_priorityQueue )
{
@@ -85,7 +85,7 @@
* @return the element at top of heap
* @exception NoSuchElementException if isEmpty() == true
*/
- public Comparable pop() throws NoSuchElementException
+ public Object pop() throws NoSuchElementException
{
synchronized( m_priorityQueue )
{
@@ -101,3 +101,4 @@
}
}
}
+
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>