You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sc...@apache.org on 2004/01/02 03:14:29 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/buffer PriorityBuffer.java package.html BinaryBuffer.java
scolebourne 2004/01/01 18:14:29
Modified: collections/src/test/org/apache/commons/collections/buffer
TestAll.java
collections/src/java/org/apache/commons/collections
BinaryHeap.java
collections/src/java/org/apache/commons/collections/buffer
package.html
Added: collections/src/test/org/apache/commons/collections/buffer
TestPriorityBuffer.java
collections/src/java/org/apache/commons/collections/buffer
PriorityBuffer.java
Removed: collections/src/test/org/apache/commons/collections/buffer
TestBinaryBuffer.java
collections/src/java/org/apache/commons/collections/buffer
BinaryBuffer.java
Log:
Rename BinaryBuffer to PriorityBuffer
Revision Changes Path
1.4 +6 -5 jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestAll.java
Index: TestAll.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestAll.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- TestAll.java 1 Jan 2004 19:01:34 -0000 1.3
+++ TestAll.java 2 Jan 2004 02:14:28 -0000 1.4
@@ -83,14 +83,15 @@
public static Test suite() {
TestSuite suite = new TestSuite();
- suite.addTest(TestBinaryBuffer.suite());
- suite.addTest(TestBlockingBuffer.suite());
suite.addTest(TestBoundedFifoBuffer.suite());
suite.addTest(TestBoundedFifoBuffer2.suite());
suite.addTest(TestCircularFifoBuffer.suite());
+ suite.addTest(TestPriorityBuffer.suite());
+ suite.addTest(TestUnboundedFifoBuffer.suite());
+
+ suite.addTest(TestBlockingBuffer.suite());
suite.addTest(TestPredicatedBuffer.suite());
suite.addTest(TestTransformedBuffer.suite());
- suite.addTest(TestUnboundedFifoBuffer.suite());
return suite;
}
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestPriorityBuffer.java
Index: TestPriorityBuffer.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestPriorityBuffer.java,v 1.1 2004/01/02 02:14:28 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-2004 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 acknowledgement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgement may appear in the software itself,
* if and wherever such third-party acknowledgements 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 Software Foundation.
*
* 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.buffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Random;
import junit.framework.Test;
import junit.framework.TestSuite;
import org.apache.commons.collections.Buffer;
import org.apache.commons.collections.BufferUnderflowException;
import org.apache.commons.collections.ComparatorUtils;
import org.apache.commons.collections.collection.AbstractTestCollection;
import org.apache.commons.collections.comparators.ComparableComparator;
import org.apache.commons.collections.comparators.ReverseComparator;
/**
* Tests the PriorityBuffer.
*
* @version $Revision: 1.1 $ $Date: 2004/01/02 02:14:28 $
*
* @author Michael A. Smith
*/
public class TestPriorityBuffer extends AbstractTestCollection {
public static void main(String[] args) {
junit.textui.TestRunner.run(suite());
}
public static Test suite() {
return new TestSuite(TestPriorityBuffer.class);
}
public TestPriorityBuffer(String testName) {
super(testName);
}
//-----------------------------------------------------------------------
public void verify() {
super.verify();
PriorityBuffer heap = (PriorityBuffer) collection;
Comparator c = heap.comparator;
if (c == null) {
c = ComparatorUtils.naturalComparator();
}
if (!heap.ascendingOrder) {
c = ComparatorUtils.reversedComparator(c);
}
Object[] tree = heap.elements;
for (int i = 1; i <= heap.size; i++) {
Object parent = tree[i];
if (i * 2 <= heap.size) {
assertTrue("Parent is less than or equal to its left child", c.compare(parent, tree[i * 2]) <= 0);
}
if (i * 2 + 1 < heap.size) {
assertTrue("Parent is less than or equal to its right child", c.compare(parent, tree[i * 2 + 1]) <= 0);
}
}
}
//-----------------------------------------------------------------------
/**
* Overridden because BinaryBuffer isn't fail fast.
* @return false
*/
public boolean isFailFastSupported() {
return false;
}
//-----------------------------------------------------------------------
public Collection makeConfirmedCollection() {
return new ArrayList();
}
public Collection makeConfirmedFullCollection() {
ArrayList list = new ArrayList();
list.addAll(Arrays.asList(getFullElements()));
return list;
}
/**
* Return a new, empty {@link Object} to used for testing.
*/
public Collection makeCollection() {
return new PriorityBuffer();
}
//-----------------------------------------------------------------------
public Object[] getFullElements() {
return getFullNonNullStringElements();
}
public Object[] getOtherElements() {
return getOtherNonNullStringElements();
}
//-----------------------------------------------------------------------
public void testBufferEmpty() {
resetEmpty();
Buffer buffer = (Buffer) collection;
assertEquals(0, buffer.size());
assertEquals(true, buffer.isEmpty());
try {
buffer.get();
fail();
} catch (BufferUnderflowException ex) {}
try {
buffer.remove();
fail();
} catch (BufferUnderflowException ex) {}
}
public void testBasicOps() {
PriorityBuffer heap = new PriorityBuffer();
heap.add("a");
heap.add("c");
heap.add("e");
heap.add("b");
heap.add("d");
heap.add("n");
heap.add("m");
heap.add("l");
heap.add("k");
heap.add("j");
heap.add("i");
heap.add("h");
heap.add("g");
heap.add("f");
assertTrue("heap should not be empty after adds", !heap.isEmpty());
for (int i = 0; i < 14; i++) {
assertEquals(
"get using default constructor should return minimum value in the binary heap",
String.valueOf((char) ('a' + i)),
heap.get());
assertEquals(
"remove using default constructor should return minimum value in the binary heap",
String.valueOf((char) ('a' + i)),
heap.remove());
if (i + 1 < 14) {
assertTrue("heap should not be empty before all elements are removed", !heap.isEmpty());
} else {
assertTrue("heap should be empty after all elements are removed", heap.isEmpty());
}
}
try {
heap.get();
fail("NoSuchElementException should be thrown if get is called after all elements are removed");
} catch (BufferUnderflowException ex) {}
try {
heap.remove();
fail("NoSuchElementException should be thrown if remove is called after all elements are removed");
} catch (BufferUnderflowException ex) {}
}
public void testBasicComparatorOps() {
PriorityBuffer heap = new PriorityBuffer(new ReverseComparator(new ComparableComparator()));
assertTrue("heap should be empty after create", heap.isEmpty());
try {
heap.get();
fail("NoSuchElementException should be thrown if get is called before any elements are added");
} catch (BufferUnderflowException ex) {}
try {
heap.remove();
fail("NoSuchElementException should be thrown if remove is called before any elements are added");
} catch (BufferUnderflowException ex) {}
heap.add("a");
heap.add("c");
heap.add("e");
heap.add("b");
heap.add("d");
heap.add("n");
heap.add("m");
heap.add("l");
heap.add("k");
heap.add("j");
heap.add("i");
heap.add("h");
heap.add("g");
heap.add("f");
assertTrue("heap should not be empty after adds", !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(
"get using default constructor should return minimum value in the binary heap",
String.valueOf((char) ('n' - i)),
heap.get());
assertEquals(
"remove using default constructor should return minimum value in the binary heap",
String.valueOf((char) ('n' - i)),
heap.remove());
if (i + 1 < 14) {
assertTrue("heap should not be empty before all elements are removed", !heap.isEmpty());
} else {
assertTrue("heap should be empty after all elements are removed", heap.isEmpty());
}
}
try {
heap.get();
fail("NoSuchElementException should be thrown if get is called after all elements are removed");
} catch (BufferUnderflowException ex) {}
try {
heap.remove();
fail("NoSuchElementException should be thrown if remove is called after all elements are removed");
} catch (BufferUnderflowException ex) {}
}
/**
* Illustrates bad internal heap state reported in Bugzilla PR #235818.
*/
public void testAddRemove() {
resetEmpty();
PriorityBuffer heap = (PriorityBuffer) collection;
heap.add(new Integer(0));
heap.add(new Integer(2));
heap.add(new Integer(4));
heap.add(new Integer(3));
heap.add(new Integer(8));
heap.add(new Integer(10));
heap.add(new Integer(12));
heap.add(new Integer(3));
confirmed.addAll(heap);
// System.out.println(heap);
Object obj = new Integer(10);
heap.remove(obj);
confirmed.remove(obj);
// System.out.println(heap);
verify();
}
/**
* Generate heaps staring with Integers from 0 - heapSize - 1.
* Then perform random add / remove operations, checking
* heap order after modifications. Alternates minHeaps, maxHeaps.
*
* Based on code provided by Steve Phelps in PR #25818
*
*/
public void testRandom() {
int iterations = 500;
int heapSize = 100;
int operations = 20;
Random randGenerator = new Random();
PriorityBuffer h = null;
for(int i=0; i < iterations; i++) {
if (i < iterations / 2) {
h = new PriorityBuffer(true);
} else {
h = new PriorityBuffer(false);
}
for(int r = 0; r < heapSize; r++) {
h.add( new Integer( randGenerator.nextInt(heapSize)) );
}
for( int r = 0; r < operations; r++ ) {
h.remove(new Integer(r));
h.add(new Integer(randGenerator.nextInt(heapSize)));
}
checkOrder(h);
}
}
/**
* Pops all elements from the heap and verifies that the elements come off
* in the correct order. NOTE: this method empties the heap.
*/
protected void checkOrder(PriorityBuffer h) {
Integer lastNum = null;
Integer num = null;
boolean fail = false;
while (!h.isEmpty()) {
num = (Integer) h.remove();
if (h.ascendingOrder) {
assertTrue(lastNum == null || num.intValue() >= lastNum.intValue());
} else { // max heap
assertTrue(lastNum == null || num.intValue() <= lastNum.intValue());
}
lastNum = num;
num = null;
}
}
/**
* Returns a string showing the contents of the heap formatted as a tree.
* Makes no attempt at padding levels or handling wrapping.
*/
protected String showTree(PriorityBuffer h) {
int count = 1;
StringBuffer buffer = new StringBuffer();
for (int offset = 1; count < h.size() + 1; offset *= 2) {
for (int i = offset; i < offset * 2; i++) {
if (i < h.elements.length && h.elements[i] != null)
buffer.append(h.elements[i] + " ");
count++;
}
buffer.append('\n');
}
return buffer.toString();
}
}
1.19 +3 -3 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.18
retrieving revision 1.19
diff -u -r1.18 -r1.19
--- BinaryHeap.java 2 Jan 2004 01:36:51 -0000 1.18
+++ BinaryHeap.java 2 Jan 2004 02:14:28 -0000 1.19
@@ -68,7 +68,7 @@
* The <code>PriorityQueue</code> interface has now been replaced for most uses
* by the <code>Buffer</code> interface. This class and the interface are
* retained for backwards compatability. The intended replacement is
- * {@link org.apache.commons.collections.buffer.BinaryBuffer BinaryBuffer}.
+ * {@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
* <p>
* The removal order of a binary heap is based on either the natural sort
* order of its elements or a specified {@link Comparator}. The
1.7 +1 -1 jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/package.html
Index: package.html
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/package.html,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- package.html 1 Jan 2004 19:01:34 -0000 1.6
+++ package.html 2 Jan 2004 02:14:29 -0000 1.7
@@ -5,7 +5,7 @@
<p>
The following implementations are provided in the package:
<ul>
-<li>BinaryBuffer - provides for removal based on a comparator ordering (priority queue)
+<li>PriorityBuffer - provides for removal based on a comparator ordering
<li>BoundedFifoBuffer - implements a buffer with a fixed size that throws exceptions when full
<li>CircularFifoBuffer - implements a buffer with a fixed size that discards oldest when full
<li>UnboundedFifoBuffer - implements a buffer that grows in size if necessary
1.1 jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/PriorityBuffer.java
Index: PriorityBuffer.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/PriorityBuffer.java,v 1.1 2004/01/02 02:14:29 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-2004 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 acknowledgement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgement may appear in the software itself,
* if and wherever such third-party acknowledgements 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 Software Foundation.
*
* 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.buffer;
import java.util.AbstractCollection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import org.apache.commons.collections.Buffer;
import org.apache.commons.collections.BufferUnderflowException;
/**
* Binary heap implementation of <code>Buffer</code> that provides for
* removal based on <code>Comparator</code> ordering.
* <p>
* 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>ascendingOrder</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 org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or
* {@link org.apache.commons.collections.buffer.SynchronizedBuffer#decorate(Buffer)}
* to provide synchronized access to a <code>PriorityBuffer</code>:
*
* <pre>
* Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
* </pre>
*
* @since Commons Collections 3.0 (previously BinaryHeap v1.0)
* @version $Revision: 1.1 $ $Date: 2004/01/02 02:14:29 $
*
* @author Peter Donald
* @author Ram Chidambaram
* @author Michael A. Smith
* @author Paul Jack
* @author Stephen Colebourne
*/
public class PriorityBuffer extends AbstractCollection implements Buffer {
/**
* The default capacity for the buffer.
*/
private static final int DEFAULT_CAPACITY = 13;
/**
* The elements in this buffer.
*/
protected Object[] elements;
/**
* The number of elements currently in this buffer.
*/
protected int size;
/**
* If true, the first element as determined by the sort order will
* be returned. If false, the last element as determined by the
* sort order will be returned.
*/
protected boolean ascendingOrder;
/**
* The comparator used to order the elements
*/
protected Comparator comparator;
//-----------------------------------------------------------------------
/**
* Constructs a new empty buffer that sorts in ascending order by the
* natural order of the objects added.
*/
public PriorityBuffer() {
this(DEFAULT_CAPACITY, true, null);
}
/**
* Constructs a new empty buffer that sorts in ascending order using the
* specified comparator.
*
* @param comparator the comparator used to order the elements,
* null means use natural order
*/
public PriorityBuffer(Comparator comparator) {
this(DEFAULT_CAPACITY, true, comparator);
}
/**
* Constructs a new empty buffer specifying the sort order and using the
* natural order of the objects added.
*
* @param ascendingOrder if <code>true</code> the heap is created as a
* minimum heap; otherwise, the heap is created as a maximum heap
*/
public PriorityBuffer(boolean ascendingOrder) {
this(DEFAULT_CAPACITY, ascendingOrder, null);
}
/**
* Constructs a new empty buffer specifying the sort order and comparator.
*
* @param ascendingOrder true to use the order imposed by the given
* comparator; false to reverse that order
* @param comparator the comparator used to order the elements,
* null means use natural order
*/
public PriorityBuffer(boolean ascendingOrder, Comparator comparator) {
this(DEFAULT_CAPACITY, ascendingOrder, comparator);
}
/**
* Constructs a new empty buffer that sorts in ascending order by the
* natural order of the objects added, specifying an initial capacity.
*
* @param capacity the initial capacity for the buffer, greater than zero
* @throws IllegalArgumentException if <code>capacity</code> is <= <code>0</code>
*/
public PriorityBuffer(int capacity) {
this(capacity, true, null);
}
/**
* Constructs a new empty buffer that sorts in ascending order using the
* specified comparator and initial capacity.
*
* @param capacity the initial capacity for the buffer, greater than zero
* @param comparator the comparator used to order the elements,
* null means use natural order
* @throws IllegalArgumentException if <code>capacity</code> is <= <code>0</code>
*/
public PriorityBuffer(int capacity, Comparator comparator) {
this(capacity, true, comparator);
}
/**
* Constructs a new empty buffer that specifying initial capacity and
* sort order, using the natural order of the objects added.
*
* @param capacity the initial capacity for the buffer, greater than zero
* @param ascendingOrder if <code>true</code> the heap is created as a
* minimum heap; otherwise, the heap is created as a maximum heap.
* @throws IllegalArgumentException if <code>capacity</code> is <code><= 0</code>
*/
public PriorityBuffer(int capacity, boolean ascendingOrder) {
this(capacity, ascendingOrder, null);
}
/**
* Constructs a new empty buffer that specifying initial capacity,
* sort order and comparator.
*
* @param capacity the initial capacity for the buffer, greater than zero
* @param ascendingOrder true to use the order imposed by the given
* comparator; false to reverse that order
* @param comparator the comparator used to order the elements,
* null means use natural order
* @throws IllegalArgumentException if <code>capacity</code> is <code><= 0</code>
*/
public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator) {
super();
if (capacity <= 0) {
throw new IllegalArgumentException("invalid capacity");
}
this.ascendingOrder = ascendingOrder;
//+1 as 0 is noop
this.elements = new Object[capacity + 1];
this.comparator = comparator;
}
//-----------------------------------------------------------------------
/**
* Checks whether the heap is ascending or descending order.
*
* @return true if ascending order (a min heap)
*/
public boolean isAscendingOrder() {
return ascendingOrder;
}
/**
* Gets the comparator being used for this buffer, null is natural order.
*
* @return the comparator in use, null is natural order
*/
public Comparator comparator() {
return comparator;
}
//-----------------------------------------------------------------------
/**
* Returns the number of elements in this buffer.
*
* @return the number of elements in this buffer
*/
public int size() {
return size;
}
/**
* Clears all elements from the buffer.
*/
public void clear() {
elements = new Object[elements.length]; // for gc
size = 0;
}
/**
* Adds an element to the buffer.
* <p>
* The element added will be sorted according to the comparator in use.
*
* @param element the element to be added
*/
public boolean add(Object element) {
if (isAtCapacity()) {
grow();
}
// percolate element to it's place in tree
if (ascendingOrder) {
percolateUpMinHeap(element);
} else {
percolateUpMaxHeap(element);
}
return true;
}
/**
* Gets the next element to be removed without actually removing it (peek).
*
* @return the next element
* @throws BufferUnderflowException if the buffer is empty
*/
public Object get() {
if (isEmpty()) {
throw new BufferUnderflowException();
} else {
return elements[1];
}
}
/**
* Gets and removes the next element (pop).
*
* @return the next element
* @throws BufferUnderflowException if the buffer is empty
*/
public Object remove() {
final Object result = get();
elements[1] = elements[size--];
// set the unused element to 'null' so that the garbage collector
// can free the object if not used anywhere else.(remove reference)
elements[size + 1] = null;
if (size != 0) {
// percolate top element to it's place in tree
if (ascendingOrder) {
percolateDownMinHeap(1);
} else {
percolateDownMaxHeap(1);
}
}
return result;
}
//-----------------------------------------------------------------------
/**
* Tests if the buffer is at capacity.
*
* @return <code>true</code> if buffer is full; <code>false</code> otherwise.
*/
protected boolean isAtCapacity() {
//+1 as element 0 is noop
return elements.length == size + 1;
}
/**
* Percolates element down heap from the position given by the index.
* <p>
* Assumes it is a mimimum heap.
*
* @param index the index for the element
*/
protected void percolateDownMinHeap(final int index) {
final Object element = elements[index];
int hole = index;
while ((hole * 2) <= 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 != size && compare(elements[child + 1], elements[child]) < 0) {
child++;
}
// if we found resting place of bubble then terminate search
if (compare(elements[child], element) >= 0) {
break;
}
elements[hole] = elements[child];
hole = child;
}
elements[hole] = element;
}
/**
* Percolates element down heap from the position given by the index.
* <p>
* Assumes it is a maximum heap.
*
* @param index the index of the element
*/
protected void percolateDownMaxHeap(final int index) {
final Object element = elements[index];
int hole = index;
while ((hole * 2) <= 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 != size && compare(elements[child + 1], elements[child]) > 0) {
child++;
}
// if we found resting place of bubble then terminate search
if (compare(elements[child], element) <= 0) {
break;
}
elements[hole] = elements[child];
hole = child;
}
elements[hole] = element;
}
/**
* Percolates element up heap from the position given by the index.
* <p>
* Assumes it is a minimum heap.
*
* @param index the index of the element to be percolated up
*/
protected void percolateUpMinHeap(final int index) {
int hole = index;
Object element = elements[hole];
while (hole > 1 && compare(element, elements[hole / 2]) < 0) {
// save element that is being pushed down
// as the element "bubble" is percolated up
final int next = hole / 2;
elements[hole] = elements[next];
hole = next;
}
elements[hole] = element;
}
/**
* Percolates a new element up heap from the bottom.
* <p>
* Assumes it is a minimum heap.
*
* @param element the element
*/
protected void percolateUpMinHeap(final Object element) {
elements[++size] = element;
percolateUpMinHeap(size);
}
/**
* Percolates element up heap from from the position given by the index.
* <p>
* Assume it is a maximum heap.
*
* @param index the index of the element to be percolated up
*/
protected void percolateUpMaxHeap(final int index) {
int hole = index;
Object element = elements[hole];
while (hole > 1 && compare(element, elements[hole / 2]) > 0) {
// save element that is being pushed down
// as the element "bubble" is percolated up
final int next = hole / 2;
elements[hole] = elements[next];
hole = next;
}
elements[hole] = element;
}
/**
* Percolates a new element up heap from the bottom.
* <p>
* Assume it is a maximum heap.
*
* @param element the element
*/
protected void percolateUpMaxHeap(final Object element) {
elements[++size] = element;
percolateUpMaxHeap(size);
}
/**
* Compares two objects using the comparator if specified, or the
* natural order otherwise.
*
* @param a the first object
* @param b the second object
* @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
*/
protected int compare(Object a, Object b) {
if (comparator != null) {
return comparator.compare(a, b);
} else {
return ((Comparable) a).compareTo(b);
}
}
/**
* Increases the size of the heap to support additional elements
*/
protected void grow() {
final Object[] array = new Object[elements.length * 2];
System.arraycopy(elements, 0, array, 0, elements.length);
elements = array;
}
//-----------------------------------------------------------------------
/**
* 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 <= size;
}
public Object next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
lastReturnedIndex = index;
index++;
return elements[lastReturnedIndex];
}
public void remove() {
if (lastReturnedIndex == -1) {
throw new IllegalStateException();
}
elements[ lastReturnedIndex ] = elements[ size ];
elements[ size ] = null;
size--;
if( size != 0 && lastReturnedIndex <= size) {
int compareToParent = 0;
if (lastReturnedIndex > 1) {
compareToParent = compare(elements[lastReturnedIndex],
elements[lastReturnedIndex / 2]);
}
if (ascendingOrder) {
if (lastReturnedIndex > 1 && compareToParent < 0) {
percolateUpMinHeap(lastReturnedIndex);
} else {
percolateDownMinHeap(lastReturnedIndex);
}
} else { // max heap
if (lastReturnedIndex > 1 && compareToParent > 0) {
percolateUpMaxHeap(lastReturnedIndex);
} else {
percolateDownMaxHeap(lastReturnedIndex);
}
}
}
index--;
lastReturnedIndex = -1;
}
};
}
/**
* Returns a string representation of this heap. The returned string
* is similar to those produced by standard JDK collections.
*
* @return a string representation of this heap
*/
public String toString() {
final StringBuffer sb = new StringBuffer();
sb.append("[ ");
for (int i = 1; i < size + 1; i++) {
if (i != 1) {
sb.append(", ");
}
sb.append(elements[i]);
}
sb.append(" ]");
return sb.toString();
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org