You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by ma...@apache.org on 2002/03/19 05:34:18 UTC
cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections TestBinaryHeap.java TestAll.java
mas 02/03/18 20:34:18
Modified: collections RELEASE-NOTES-2.0.html
collections/src/java/org/apache/commons/collections
BinaryHeap.java PriorityQueue.java
collections/src/test/org/apache/commons/collections
TestAll.java
Added: collections/src/test/org/apache/commons/collections
TestBinaryHeap.java
Log:
Changed PriorityQueue and BinaryHeap to allow objects that do not
implement Comparable. BinaryHeap implements this by accepting an
optional Comparator in its constructor. If no comparator is specified,
the object's natural ordering is used (i.e. it is cast to a Comparable
and compared using its compareTo method)
Also added basic tests for BinaryHeap
Revision Changes Path
1.10 +48 -0 jakarta-commons/collections/RELEASE-NOTES-2.0.html
Index: RELEASE-NOTES-2.0.html
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/RELEASE-NOTES-2.0.html,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- RELEASE-NOTES-2.0.html 19 Mar 2002 00:11:56 -0000 1.9
+++ RELEASE-NOTES-2.0.html 19 Mar 2002 04:34:18 -0000 1.10
@@ -169,3 +169,51 @@
</ul>
+
+<p><u>PriorityQueue</u></p>
+
+<p>Changed to allow priority queue implementations that support determining
+priorities using means other than the object's natural ordering (i.e. a
+priority queue that does not depend on the object implementing the Comparable
+interface).</p>
+
+<p><i>PriorityQueue 2.0 compatibility changes:</i></p>
+
+<ul>
+
+ <li>The pop() and peek() methods were changed to return a generic Object
+ rather than a comparable.</li>
+
+ <li>The insert(Comparable) method was changed to take an Object argument
+ rather than a comparable.</li>
+
+</ul>
+
+
+<p><u>BinaryHeap</u></p>
+
+<p>Changed to allow the specification of a Comparator that should be used to
+compare objects to determine "priority" of the objects. If no comparator is
+specified, the object's natural ordering is used.</p>
+
+<p><i>BinaryHeap 2.0 compatibility changes:</i></p>
+
+<ul>
+
+ <li>The pop() and peek() methods were changed to return a generic Object
+ rather than a comparable.</li>
+
+ <li>The insert(Comparable) method was changed to take an Object argument
+ rather than a comparable.</li>
+
+</ul>
+
+<p><i>New features:</i></p>
+<ul>
+
+ <li>The BinaryHeap supports objects that do not implement Comparable. To use
+ such objects in the binary heap, a suitable Comparator must be provided in
+ the constructor so that the binary heap is capable of ordering elements in
+ their relative priorities.</li>
+
+</ul>
\ No newline at end of file
1.5 +56 -22 jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java
Index: BinaryHeap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- BinaryHeap.java 22 Feb 2002 04:16:19 -0000 1.4
+++ BinaryHeap.java 19 Mar 2002 04:34:18 -0000 1.5
@@ -1,7 +1,7 @@
/*
- * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java,v 1.4 2002/02/22 04:16:19 mas Exp $
- * $Revision: 1.4 $
- * $Date: 2002/02/22 04:16:19 $
+ * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java,v 1.5 2002/03/19 04:34:18 mas Exp $
+ * $Revision: 1.5 $
+ * $Date: 2002/03/19 04:34:18 $
*
* ====================================================================
*
@@ -61,6 +61,7 @@
package org.apache.commons.collections;
import java.util.NoSuchElementException;
+import java.util.Comparator;
/**
* Binary heap implementation of {@link PriorityQueue}.
@@ -74,8 +75,9 @@
protected final static int DEFAULT_CAPACITY = 13;
protected int m_size;
- protected Comparable[] m_elements;
+ protected Object[] m_elements;
protected boolean m_isMinHeap;
+ private Comparator m_comparator;
/**
* Create a new minimum binary heap.
@@ -85,6 +87,12 @@
this( DEFAULT_CAPACITY, true );
}
+ public BinaryHeap( Comparator comparator )
+ {
+ this();
+ m_comparator = comparator;
+ }
+
/**
* Create a new minimum binary heap with the specified initial capacity.
*
@@ -99,6 +107,12 @@
this( capacity, true );
}
+ public BinaryHeap( final int capacity, Comparator comparator )
+ {
+ this( capacity );
+ m_comparator = comparator;
+ }
+
/**
* Create a new minimum or maximum binary heap
*
@@ -110,6 +124,12 @@
this( DEFAULT_CAPACITY, isMinHeap );
}
+ public BinaryHeap( final boolean isMinHeap, Comparator comparator )
+ {
+ this( isMinHeap );
+ m_comparator = comparator;
+ }
+
/**
* Create a new minimum or maximum binary heap with the specified
* initial capacity.
@@ -131,7 +151,14 @@
m_isMinHeap = isMinHeap;
//+1 as 0 is noop
- m_elements = new Comparable[ capacity + 1 ];
+ m_elements = new Object[ capacity + 1 ];
+ }
+
+ public BinaryHeap( final int capacity, final boolean isMinHeap,
+ Comparator comparator )
+ {
+ this( capacity, isMinHeap );
+ m_comparator = comparator;
}
/**
@@ -170,7 +197,7 @@
*
* @param element the element to be inserted
*/
- public void insert( final Comparable element )
+ public void insert( final Object element )
{
if( isFull() ) grow();
@@ -185,7 +212,7 @@
* @return the element at top of heap
* @exception NoSuchElementException if <code>isEmpty() == true</code>
*/
- public Comparable peek() throws NoSuchElementException
+ public Object peek() throws NoSuchElementException
{
if( isEmpty() ) throw new NoSuchElementException();
else return m_elements[ 1 ];
@@ -197,9 +224,9 @@
* @return the element at top of heap
* @exception NoSuchElementException if <code>isEmpty() == true</code>
*/
- 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
@@ -224,7 +251,7 @@
*/
protected void percolateDownMinHeap( final int index )
{
- final Comparable element = m_elements[ index ];
+ final Object element = m_elements[ index ];
int hole = index;
@@ -234,14 +261,14 @@
//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 )
+ if( child != m_size &&
+ 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( compare( m_elements[ child ], element ) >= 0 )
{
break;
}
@@ -261,7 +288,7 @@
*/
protected void percolateDownMaxHeap( final int index )
{
- final Comparable element = m_elements[ index ];
+ final Object element = m_elements[ index ];
int hole = index;
@@ -272,13 +299,13 @@
//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 )
+ 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( compare( m_elements[ child ], element ) <= 0 )
{
break;
}
@@ -296,14 +323,14 @@
*
* @param element the element
*/
- protected void percolateUpMinHeap( final Comparable element )
+ protected void percolateUpMinHeap( final Object element )
{
int hole = ++m_size;
m_elements[ hole ] = element;
while( hole > 1 &&
- element.compareTo( m_elements[ hole / 2 ] ) < 0 )
+ compare( element, m_elements[ hole / 2 ] ) < 0 )
{
//save element that is being pushed down
//as the element "bubble" is percolated up
@@ -321,12 +348,12 @@
*
* @param element the element
*/
- protected void percolateUpMaxHeap( final Comparable element )
+ protected void percolateUpMaxHeap( final Object element )
{
int hole = ++m_size;
while( hole > 1 &&
- element.compareTo( m_elements[ hole / 2 ] ) > 0 )
+ compare( element, m_elements[ hole / 2 ] ) > 0 )
{
//save element that is being pushed down
//as the element "bubble" is percolated up
@@ -338,13 +365,20 @@
m_elements[ hole ] = element;
}
+ private int compare(Object a, Object b) {
+ if(m_comparator != null) {
+ return m_comparator.compare(a, b);
+ } else {
+ return ((Comparable)a).compareTo(b);
+ }
+ }
+
/**
* Increase the size of the heap to support additional elements
**/
protected 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;
}
1.4 +12 -8 jakarta-commons/collections/src/java/org/apache/commons/collections/PriorityQueue.java
Index: PriorityQueue.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/PriorityQueue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- PriorityQueue.java 10 Feb 2002 08:07:42 -0000 1.3
+++ PriorityQueue.java 19 Mar 2002 04:34:18 -0000 1.4
@@ -1,7 +1,7 @@
/*
- * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/PriorityQueue.java,v 1.3 2002/02/10 08:07:42 jstrachan Exp $
- * $Revision: 1.3 $
- * $Date: 2002/02/10 08:07:42 $
+ * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/PriorityQueue.java,v 1.4 2002/03/19 04:34:18 mas Exp $
+ * $Revision: 1.4 $
+ * $Date: 2002/03/19 04:34:18 $
*
* ====================================================================
*
@@ -86,23 +86,27 @@
* Insert an element into queue.
*
* @param element the element to be inserted
+ *
+ * @exception ClassCastException if the specified <code>element</code>'s
+ * type prevents it from being compared to other items in the queue to
+ * determine its relative priority.
*/
- void insert( Comparable element );
+ void insert( Object element );
/**
* Return element on top of heap but don't remove it.
*
* @return the element at top of heap
- * @exception NoSuchElementException if isEmpty() == true
+ * @exception NoSuchElementException if <code>isEmpty() == true</code>
*/
- Comparable peek() throws NoSuchElementException;
+ Object peek() throws NoSuchElementException;
/**
* Return element on top of heap and remove it.
*
* @return the element at top of heap
- * @exception NoSuchElementException if isEmpty() == true
+ * @exception NoSuchElementException if <code>isEmpty() == true</code>
*/
- Comparable pop() throws NoSuchElementException;
+ Object pop() throws NoSuchElementException;
}
1.24 +5 -4 jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java
Index: TestAll.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -r1.23 -r1.24
--- TestAll.java 1 Mar 2002 23:31:35 -0000 1.23
+++ TestAll.java 19 Mar 2002 04:34:18 -0000 1.24
@@ -1,7 +1,7 @@
/*
- * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java,v 1.23 2002/03/01 23:31:35 morgand Exp $
- * $Revision: 1.23 $
- * $Date: 2002/03/01 23:31:35 $
+ * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java,v 1.24 2002/03/19 04:34:18 mas Exp $
+ * $Revision: 1.24 $
+ * $Date: 2002/03/19 04:34:18 $
*
* ====================================================================
*
@@ -67,7 +67,7 @@
/**
* Entry point for all Collections tests.
* @author Rodney Waldhoff
- * @version $Id: TestAll.java,v 1.23 2002/03/01 23:31:35 morgand Exp $
+ * @version $Id: TestAll.java,v 1.24 2002/03/19 04:34:18 mas Exp $
*/
public class TestAll extends TestCase {
public TestAll(String testName) {
@@ -80,6 +80,7 @@
suite.addTest(TestArrayIterator2.suite());
suite.addTest(TestArrayStack.suite());
suite.addTest(TestBeanMap.suite());
+ suite.addTest(TestBinaryHeap.suite());
suite.addTest(TestCollectionUtils.suite());
suite.addTest(TestComparableComparator.suite());
suite.addTest(TestComparatorChain.suite());
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java
Index: TestBinaryHeap.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java,v 1.1 2002/03/19 04:34:18 mas Exp $
* $Revision: 1.1 $
* $Date: 2002/03/19 04:34:18 $
*
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999-2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowlegement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowlegement may appear in the software itself,
* if and wherever such third-party acknowlegements normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Group.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
*/
package org.apache.commons.collections;
import junit.framework.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
import org.apache.commons.collections.comparators.ComparableComparator;
import org.apache.commons.collections.comparators.ReverseComparator;
/**
* Tests the BinaryHeap.
*
* @author <a href="mas@apache.org">Michael A. Smith</a>
* @version $Id: TestBinaryHeap.java,v 1.1 2002/03/19 04:34:18 mas Exp $
*/
public class TestBinaryHeap extends TestObject {
public static Test suite() {
return new TestSuite(TestBinaryHeap.class);
}
public TestBinaryHeap(String testName) {
super(testName);
}
/**
* Return a new, empty {@link Object} to used for testing.
*/
public Object makeObject() {
return new BinaryHeap();
}
public void testBasicOps() {
BinaryHeap heap = new BinaryHeap();
assertTrue("heap should be empty after create", heap.isEmpty());
try {
heap.peek();
fail("NoSuchElementException should be thrown if peek is called " +
"before any elements are inserted");
} catch (NoSuchElementException e) {
// expected
}
try {
heap.pop();
fail("NoSuchElementException should be thrown if pop is called " +
"before any elements are inserted");
} catch (NoSuchElementException e) {
// expected
}
heap.insert("a");
heap.insert("c");
heap.insert("e");
heap.insert("b");
heap.insert("d");
heap.insert("n");
heap.insert("m");
heap.insert("l");
heap.insert("k");
heap.insert("j");
heap.insert("i");
heap.insert("h");
heap.insert("g");
heap.insert("f");
assertTrue("heap should not be empty after inserts", !heap.isEmpty());
for(int i = 0; i < 14; i++) {
assertEquals("peek using default constructor should return " +
"minimum value in the binary heap",
String.valueOf((char)('a' + i)), heap.peek());
assertEquals("pop using default constructor should return minimum " +
"value in the binary heap",
String.valueOf((char)('a' + i)), heap.pop());
if(i + 1 < 14) {
assertTrue("heap should not be empty before all elements are popped",
!heap.isEmpty());
} else {
assertTrue("heap should be empty after all elements are popped",
heap.isEmpty());
}
}
try {
heap.peek();
fail("NoSuchElementException should be thrown if peek is called " +
"after all elements are popped");
} catch (NoSuchElementException e) {
// expected
}
try {
heap.pop();
fail("NoSuchElementException should be thrown if pop is called " +
"after all elements are popped");
} catch (NoSuchElementException e) {
// expected
}
}
public void testBasicComparatorOps() {
BinaryHeap heap =
new BinaryHeap(new ReverseComparator(new ComparableComparator()));
assertTrue("heap should be empty after create", heap.isEmpty());
try {
heap.peek();
fail("NoSuchElementException should be thrown if peek is called " +
"before any elements are inserted");
} catch (NoSuchElementException e) {
// expected
}
try {
heap.pop();
fail("NoSuchElementException should be thrown if pop is called " +
"before any elements are inserted");
} catch (NoSuchElementException e) {
// expected
}
heap.insert("a");
heap.insert("c");
heap.insert("e");
heap.insert("b");
heap.insert("d");
heap.insert("n");
heap.insert("m");
heap.insert("l");
heap.insert("k");
heap.insert("j");
heap.insert("i");
heap.insert("h");
heap.insert("g");
heap.insert("f");
assertTrue("heap should not be empty after inserts", !heap.isEmpty());
for(int i = 0; i < 14; i++) {
// note: since we're using a comparator that reverses items, the
// "minimum" item is "n", and the "maximum" item is "a".
assertEquals("peek using default constructor should return " +
"minimum value in the binary heap",
String.valueOf((char)('n' - i)), heap.peek());
assertEquals("pop using default constructor should return minimum " +
"value in the binary heap",
String.valueOf((char)('n' - i)), heap.pop());
if(i + 1 < 14) {
assertTrue("heap should not be empty before all elements are popped",
!heap.isEmpty());
} else {
assertTrue("heap should be empty after all elements are popped",
heap.isEmpty());
}
}
try {
heap.peek();
fail("NoSuchElementException should be thrown if peek is called " +
"after all elements are popped");
} catch (NoSuchElementException e) {
// expected
}
try {
heap.pop();
fail("NoSuchElementException should be thrown if pop is called " +
"after all elements are popped");
} catch (NoSuchElementException e) {
// expected
}
}
}
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>