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 [EMAIL PROTECTED] * * 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 [EMAIL PROTECTED] 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 [EMAIL PROTECTED] org.apache.commons.collections.Buffer Buffer} and [EMAIL PROTECTED] org.apache.commons.collections.PriorityQueue PriorityQueue} interfaces. [EMAIL PROTECTED] 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 [EMAIL PROTECTED] * * 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 [EMAIL PROTECTED] Comparator}. The * [EMAIL PROTECTED] #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 [EMAIL PROTECTED] #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 [EMAIL PROTECTED] #add(Object)} and [EMAIL PROTECTED] #remove()} operations perform * in logarithmic time. The [EMAIL PROTECTED] #get()} operation performs in constant * time. All other operations perform in linear time or worse. * <p> * Note that this implementation is not synchronized. Use * [EMAIL PROTECTED] org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or * [EMAIL PROTECTED] 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: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]