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/01 20:01:34 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/buffer BinaryBuffer.java package.html BinaryHeap.java
scolebourne 2004/01/01 11:01:34
Modified: collections/src/test/org/apache/commons/collections/buffer
TestAll.java
collections/src/java/org/apache/commons/collections/buffer
package.html
Added: collections/src/test/org/apache/commons/collections/buffer
TestBinaryBuffer.java
collections/src/java/org/apache/commons/collections/buffer
BinaryBuffer.java
Removed: collections/src/test/org/apache/commons/collections/buffer
TestBinaryHeap.java
collections/src/java/org/apache/commons/collections/buffer
BinaryHeap.java
Log:
Rename BinaryHeap to BinaryBuffer
Remove PriorityQueue interface
Revision Changes Path
1.3 +3 -3 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.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- TestAll.java 29 Nov 2003 18:04:56 -0000 1.2
+++ TestAll.java 1 Jan 2004 19:01:34 -0000 1.3
@@ -83,7 +83,7 @@
public static Test suite() {
TestSuite suite = new TestSuite();
- suite.addTest(TestBinaryHeap.suite());
+ suite.addTest(TestBinaryBuffer.suite());
suite.addTest(TestBlockingBuffer.suite());
suite.addTest(TestBoundedFifoBuffer.suite());
suite.addTest(TestBoundedFifoBuffer2.suite());
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBinaryBuffer.java
Index: TestBinaryBuffer.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/buffer/TestBinaryBuffer.java,v 1.1 2004/01/01 19:01:34 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-2003 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 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 BinaryHeap.
*
* @version $Revision: 1.1 $ $Date: 2004/01/01 19:01:34 $
*
* @author Michael A. Smith
*/
public class TestBinaryBuffer extends AbstractTestCollection {
public static void main(String[] args) {
junit.textui.TestRunner.run(suite());
}
public static Test suite() {
return new TestSuite(TestBinaryBuffer.class);
}
public TestBinaryBuffer(String testName) {
super(testName);
}
//-----------------------------------------------------------------------
public void verify() {
super.verify();
BinaryBuffer heap = (BinaryBuffer) 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 BinaryBuffer();
}
//-----------------------------------------------------------------------
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() {
BinaryBuffer heap = new BinaryBuffer();
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() {
BinaryBuffer heap = new BinaryBuffer(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) {}
}
// public void testAddRemove() {
// resetEmpty();
// BinaryBuffer heap = (BinaryBuffer) 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();
// }
}
1.6 +5 -6 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.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- package.html 11 Dec 2003 23:15:12 -0000 1.5
+++ package.html 1 Jan 2004 19:01:34 -0000 1.6
@@ -1,15 +1,14 @@
<BODY>
<p>
This package contains implementations of the
-{@link org.apache.commons.collections.Buffer Buffer} and
-{@link org.apache.commons.collections.PriorityQueue PriorityQueue} interfaces.
+{@link org.apache.commons.collections.Buffer Buffer} interface.
<p>
The following implementations are provided in the package:
<ul>
-<li>BinaryHeap - implements both Buffer and PriorityQueue
-<li>BoundedBuffer - implements a buffer with a fixed size that throws exceptions when full
-<li>CircularBuffer - implements a buffer with a fixed size that discards oldest when full
-<li>UnboundedBuffer - implements a buffer that grows in size if necessary
+<li>BinaryBuffer - provides for removal based on a comparator ordering (priority queue)
+<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
</ul>
<p>
The following decorators are provided in the package:
1.1 jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryBuffer.java
Index: BinaryBuffer.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/buffer/BinaryBuffer.java,v 1.1 2004/01/01 19:01:34 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-2003 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>BinaryBuffer</code>:
*
* <pre>
* Buffer heap = SynchronizedBuffer.decorate(new BinaryBuffer());
* </pre>
*
* @since Commons Collections 3.0 (previously BinaryHeap v1.0)
* @version $Revision: 1.1 $ $Date: 2004/01/01 19:01:34 $
*
* @author Peter Donald
* @author Ram Chidambaram
* @author Michael A. Smith
* @author Paul Jack
* @author Stephen Colebourne
*/
public class BinaryBuffer extends AbstractCollection implements Buffer {
/**
* The default capacity for a binary heap.
*/
private static final int DEFAULT_CAPACITY = 13;
/**
* The elements in this heap.
*/
protected Object[] elements;
/**
* The number of elements currently in this heap.
*/
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 BinaryBuffer() {
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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 BinaryBuffer(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 top.
* Assume it is a minimum 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 top.
* Assume 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 bottom.
* Assume it is a minimum heap.
*
* @param element the element
*/
protected void percolateUpMinHeap(final Object element) {
int hole = ++size;
elements[hole] = element;
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 element up heap from bottom.
* Assume it is a maximum heap.
*
* @param element the element
*/
protected void percolateUpMaxHeap(final Object element) {
int hole = ++size;
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;
}
/**
* 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) {
//percolate top element to it's place in tree
if (ascendingOrder) {
percolateDownMinHeap(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