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/07/03 04:09:06 UTC
cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections TestBinaryHeap.java
mas 2002/07/02 19:09:06
Modified: collections/src/java/org/apache/commons/collections
ArrayStack.java BinaryHeap.java
collections/src/test/org/apache/commons/collections
TestBinaryHeap.java
Log:
ArrayStack and BinaryHeap now implement Buffer.
Submitted by: Paul Jack
Revision Changes Path
1.6 +40 -5 jakarta-commons/collections/src/java/org/apache/commons/collections/ArrayStack.java
Index: ArrayStack.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/ArrayStack.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- ArrayStack.java 12 Jun 2002 03:59:15 -0000 1.5
+++ ArrayStack.java 3 Jul 2002 02:09:06 -0000 1.6
@@ -74,15 +74,24 @@
* is therefore operates faster in environments where you do not need to
* worry about multiple thread contention.
*
+ * The removal order of an <Code>ArrayStack</Code> is based on insertion
+ * order: The most recently added element is removed first. The iteration
+ * order is <I>not</I> the same as the removal order. The iterator returns
+ * elements from the bottom up, whereas the {@link remove()} method removes
+ * them from the top down.
+ *
* @since 1.0
* @author Craig R. McClanahan
* @version $Revision$ $Date$
* @see java.util.Stack
*/
-public class ArrayStack extends ArrayList {
+public class ArrayStack extends ArrayList implements Buffer {
+ final private static long serialVersionUID = 2130079159931574599L;
+//, local class serialVersionUID = -3491241305852305742
+
// --------------------------------------------------------- Public Methods
@@ -187,5 +196,31 @@
}
+
+ /**
+ * Returns the element on the top of the stack.
+ *
+ * @return the element on the top of the stack
+ * @throws BufferUnderflowException if the stack is empty
+ */
+ public Object get() {
+ int size = size();
+ if (size == 0) throw new BufferUnderflowException();
+ return get(size - 1);
+ }
+
+
+
+ /**
+ * Removes the element on the top of the stack.
+ *
+ * @return the removed element
+ * @throws BufferUnderflowException if the stack is empty
+ */
+ public Object remove() {
+ int size = size();
+ if (size == 0) throw new BufferUnderflowException();
+ return remove(size - 1);
+ }
}
1.8 +128 -6 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.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- BinaryHeap.java 12 Jun 2002 03:59:15 -0000 1.7
+++ BinaryHeap.java 3 Jul 2002 02:09:06 -0000 1.8
@@ -60,19 +60,43 @@
*/
package org.apache.commons.collections;
+import java.util.AbstractCollection;
+import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Comparator;
/**
- * Binary heap implementation of {@link PriorityQueue}.
+ * Binary heap implementation of {@link PriorityQueue} and {@link Buffer}.
+ *
+ * The removal order of a binary heap is based on either the natural sort
+ * order of its elements or a specified {@link Comparator}. The
+ * {@link remove()} method always returns the first element as determined
+ * by the sort order. (The <Code>isMinHeap</Code> flag in the constructors
+ * can be used to reverse the sort order, in which case {@link remove()}
+ * will always remove the last element.) The removal order is
+ * <I>not</I> the same as the order of iteration; elements are
+ * returned by the iterator in no particular order.<P>
+ *
+ * The {@link add(Object)} and {@link remove()} operations perform
+ * in logarithmic time. The {@link get()} operation performs in constant
+ * time. All other operations perform in linear time or worse.<P>
+ *
+ * Note that this implementation is not synchronized. Use
+ * {@link BufferUtils.synchronizedBuffer(Buffer)} to provide
+ * synchronized access to a <Code>BinaryHeap</Code>:
+ *
+ * <Pre>
+ * Buffer heap = BufferUtils.synchronizedBuffer(new BinaryHeap());
+ * </Pre>
*
* @since 1.0
* @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
* @author <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
* @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
+ * @author Paul Jack
*/
-public final class BinaryHeap
- implements PriorityQueue
+public final class BinaryHeap extends AbstractCollection
+ implements PriorityQueue, Buffer
{
protected final static int DEFAULT_CAPACITY = 13;
@@ -400,6 +424,104 @@
sb.append( " ]" );
return sb.toString();
+ }
+
+
+ /**
+ * Returns an iterator over this heap's elements.
+ *
+ * @return an iterator over this heap's elements
+ */
+ public Iterator iterator() {
+ return new Iterator() {
+
+ private int index = 1;
+ private int lastReturnedIndex = -1;
+
+ public boolean hasNext() {
+ return index <= m_size;
+ }
+
+ public Object next() {
+ if (!hasNext()) throw new NoSuchElementException();
+ lastReturnedIndex = index;
+ index++;
+ return m_elements[lastReturnedIndex];
+ }
+
+ public void remove() {
+ if (lastReturnedIndex == -1) throw new IllegalStateException();
+ m_elements[ lastReturnedIndex ] = m_elements[ m_size ];
+ m_elements[ m_size ] = null;
+ m_size--;
+ if( m_size != 0 )
+ {
+ //percolate top element to it's place in tree
+ if( m_isMinHeap ) percolateDownMinHeap( lastReturnedIndex );
+ else percolateDownMaxHeap( lastReturnedIndex );
+ }
+ index--;
+ lastReturnedIndex = -1;
+ }
+
+ };
+ }
+
+
+ /**
+ * Adds an object to this heap. Same as {@link insert(Object)}.
+ *
+ * @param o the object to add
+ * @return true, always
+ */
+ public boolean add(Object o) {
+ insert(o);
+ return true;
+ }
+
+
+ /**
+ * Returns the priority element. Same as {@link peek()}.
+ *
+ * @return the priority element
+ * @throws BufferUnderflowException if this heap is empty
+ */
+ public Object get() {
+ try {
+ return peek();
+ } catch (NoSuchElementException e) {
+ throw new BufferUnderflowException();
+ }
+ }
+
+
+ /**
+ * Removes the priority element. Same as {@link pop()}.
+ *
+ * @return the removed priority element
+ * @throws BufferUnderflowException if this heap is empty
+ */
+ public Object remove() {
+ try {
+ return pop();
+ } catch (NoSuchElementException e) {
+ throw new BufferUnderflowException();
+ }
+ }
+
+
+ /**
+ * Returns the number of elements in this heap.
+ *
+ * @return the number of elements in this heap
+ */
+ public int size() {
+ return m_size;
+ }
+
+
+ Comparator comparator() {
+ return m_comparator;
}
}
1.4 +55 -6 jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java
Index: TestBinaryHeap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestBinaryHeap.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- TestBinaryHeap.java 11 Jun 2002 02:41:47 -0000 1.3
+++ TestBinaryHeap.java 3 Jul 2002 02:09:06 -0000 1.4
@@ -62,6 +62,10 @@
package org.apache.commons.collections;
import junit.framework.*;
+import java.util.Arrays;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
@@ -74,7 +78,7 @@
* @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
* @version $Id$
*/
-public class TestBinaryHeap extends TestObject {
+public class TestBinaryHeap extends TestCollection {
public static Test suite() {
return new TestSuite(TestBinaryHeap.class);
@@ -87,10 +91,32 @@
/**
* Return a new, empty {@link Object} to used for testing.
*/
- public Object makeObject() {
+ public Collection makeCollection() {
return new BinaryHeap();
}
+
+ public Collection makeConfirmedCollection() {
+ return new ArrayList();
+ }
+
+ public Collection makeConfirmedFullCollection() {
+ ArrayList list = new ArrayList();
+ list.addAll(Arrays.asList(getFullElements()));
+ return list;
+ }
+
+ public Object[] getFullElements() {
+ return getFullNonNullStringElements();
+ }
+
+ public Object[] getOtherElements() {
+ return getOtherNonNullStringElements();
+ }
+
+ public void testCollectionIteratorFailFast() {
+ }
+
public void testBasicOps() {
BinaryHeap heap = new BinaryHeap();
@@ -240,6 +266,29 @@
} catch (NoSuchElementException e) {
// expected
}
+ }
+
+
+ public void verify() {
+ super.verify();
+ BinaryHeap heap = (BinaryHeap)collection;
+
+ Comparator c = heap.comparator();
+ if (c == null) c = ComparatorUtils.NATURAL;
+ if (!heap.m_isMinHeap) c = ComparatorUtils.reverse(c);
+
+ Object[] tree = heap.m_elements;
+ for (int i = 1; i <= heap.m_size; i++) {
+ Object parent = tree[i];
+ if (i * 2 <= heap.m_size) {
+ assertTrue("Parent is less than or equal to its left child",
+ c.compare(parent, tree[i * 2]) <= 0);
+ }
+ if (i * 2 + 1 < heap.m_size) {
+ assertTrue("Parent is less than or equal to its right child",
+ c.compare(parent, tree[i * 2 + 1]) <= 0);
+ }
+ }
}
}
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>