--- jsr166/src/main/java/util/PriorityQueue.java 2003/08/04 01:48:39 1.18 +++ jsr166/src/main/java/util/PriorityQueue.java 2003/08/06 18:42:49 1.25 @@ -1,15 +1,16 @@ package java.util; /** - * A priority queue based on a priority heap. This queue orders + * An unbounded priority {@linkplain Queue queue} based on a priority heap. + * This queue orders * elements according to an order specified at construction time, which is - * specified in the same manner as {@link java.util.TreeSet} and + * specified in the same manner as {@link java.util.TreeSet} and * {@link java.util.TreeMap}: elements are ordered * either according to their natural order (see {@link Comparable}), or - * according to a {@link java.util.Comparator}, depending on which + * according to a {@link java.util.Comparator}, depending on which * constructor is used. - *

The head of this queue is the least element with - * respect to the specified ordering. + *

The head of this queue is the least element with + * respect to the specified ordering. * If multiple elements are tied for least value, the * head is one of those elements. A priority queue does not permit * null elements. @@ -22,7 +23,7 @@ * *

A priority queue has a capacity. The capacity is the * size of the array used internally to store the elements on the - * queue, and is limited to Integer.MAX_VALUE-1. + * queue. * It is always at least as large as the queue size. As * elements are added to a priority queue, its capacity grows * automatically. The details of the growth policy are not specified. @@ -41,7 +42,7 @@ * @author Josh Bloch */ public class PriorityQueue extends AbstractQueue - implements Sorted, Queue, java.io.Serializable { + implements Queue, java.io.Serializable { private static final int DEFAULT_INITIAL_CAPACITY = 11; @@ -78,27 +79,29 @@ public class PriorityQueue extends Ab private transient int modCount = 0; /** - * Create a PriorityQueue with the default initial capacity + * Creates a PriorityQueue with the default initial capacity * (11) that orders its elements according to their natural - * ordering (using Comparable.) + * ordering (using Comparable). */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } /** - * Create a PriorityQueue with the specified initial capacity + * Creates a PriorityQueue with the specified initial capacity * that orders its elements according to their natural ordering - * (using Comparable.) + * (using Comparable). * * @param initialCapacity the initial capacity for this priority queue. + * @throws IllegalArgumentException if initialCapacity is less + * than 1 */ public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } /** - * Create a PriorityQueue with the specified initial capacity + * Creates a PriorityQueue with the specified initial capacity * that orders its elements according to the specified comparator. * * @param initialCapacity the initial capacity for this priority queue. @@ -108,7 +111,8 @@ public class PriorityQueue extends Ab * @throws IllegalArgumentException if initialCapacity is less * than 1 */ - public PriorityQueue(int initialCapacity, Comparator comparator) { + public PriorityQueue(int initialCapacity, + Comparator comparator) { if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity + 1]; @@ -116,27 +120,10 @@ public class PriorityQueue extends Ab } /** - * Create a PriorityQueue containing the elements in the specified - * collection. The priority queue has an initial capacity of 110% of the - * size of the specified collection (bounded by - * Integer.MAX_VALUE-1); or 1 if the collection is empty. - * If the specified collection - * implements the {@link Sorted} interface, the priority queue will be - * sorted according to the same comparator, or according to its elements' - * natural order if the collection is sorted according to its elements' - * natural order. If the specified collection does not implement - * Sorted, the priority queue is ordered according to - * its elements' natural order. - * - * @param c the collection whose elements are to be placed - * into this priority queue. - * @throws ClassCastException if elements of the specified collection - * cannot be compared to one another according to the priority - * queue's ordering. - * @throws NullPointerException if c or any element within it - * is null + * Common code to initialize underlying queue array across + * constructors below. */ - public PriorityQueue(Collection c) { + private void initializeArray(Collection c) { int sz = c.size(); int initialCapacity = (int)Math.min((sz * 110L) / 100, Integer.MAX_VALUE - 1); @@ -144,22 +131,137 @@ public class PriorityQueue extends Ab initialCapacity = 1; this.queue = new Object[initialCapacity + 1]; + } - // FIXME: if c is larger than Integer.MAX_VALUE we'll - // overflow the array + /** + * Initially fill elements of the queue array under the + * knowledge that it is sorted or is another PQ, in which + * case we can just place the elements without fixups. + */ + private void fillFromSorted(Collection c) { + for (Iterator i = c.iterator(); i.hasNext(); ) + queue[++size] = i.next(); + } - if (c instanceof Sorted) { - comparator = ((Sorted)c).comparator(); - } else { - comparator = null; - } + /** + * Initially fill elements of the queue array that is + * not to our knowledge sorted, so we must add them + * one by one. + */ + private void fillFromUnsorted(Collection c) { for (Iterator i = c.iterator(); i.hasNext(); ) add(i.next()); } + /** + * Creates a PriorityQueue containing the elements in the + * specified collection. The priority queue has an initial + * capacity of 110% of the size of the specified collection or 1 + * if the collection is empty. If the specified collection is an + * instance of a {@link java.util.SortedSet} or is another + * PriorityQueue, the priority queue will be sorted + * according to the same comparator, or according to its elements' + * natural order if the collection is sorted according to its + * elements' natural order. Otherwise, the priority queue is + * ordered according to its elements' natural order. + * + * @param c the collection whose elements are to be placed + * into this priority queue. + * @throws ClassCastException if elements of the specified collection + * cannot be compared to one another according to the priority + * queue's ordering. + * @throws NullPointerException if c or any element within it + * is null + */ + public PriorityQueue(Collection c) { + initializeArray(c); + if (c instanceof SortedSet) { + SortedSet s = (SortedSet) c; + comparator = (Comparator)s.comparator(); + fillFromSorted(s); + } + else if (c instanceof PriorityQueue) { + PriorityQueue s = (PriorityQueue) c; + comparator = (Comparator)s.comparator(); + fillFromSorted(s); + } + else { + comparator = null; + fillFromUnsorted(c); + } + } + + /** + * Creates a PriorityQueue containing the elements in the + * specified collection. The priority queue has an initial + * capacity of 110% of the size of the specified collection or 1 + * if the collection is empty. This priority queue will be sorted + * according to the same comparator as the given collection, or + * according to its elements' natural order if the collection is + * sorted according to its elements' natural order. + * + * @param c the collection whose elements are to be placed + * into this priority queue. + * @throws ClassCastException if elements of the specified collection + * cannot be compared to one another according to the priority + * queue's ordering. + * @throws NullPointerException if c or any element within it + * is null + */ + public PriorityQueue(PriorityQueue c) { + initializeArray(c); + comparator = (Comparator)c.comparator(); + fillFromSorted(c); + } + + /** + * Creates a PriorityQueue containing the elements in the + * specified collection. The priority queue has an initial + * capacity of 110% of the size of the specified collection or 1 + * if the collection is empty. This priority queue will be sorted + * according to the same comparator as the given collection, or + * according to its elements' natural order if the collection is + * sorted according to its elements' natural order. + * + * @param c the collection whose elements are to be placed + * into this priority queue. + * @throws ClassCastException if elements of the specified collection + * cannot be compared to one another according to the priority + * queue's ordering. + * @throws NullPointerException if c or any element within it + * is null + */ + public PriorityQueue(SortedSet c) { + initializeArray(c); + comparator = (Comparator)c.comparator(); + fillFromSorted(c); + } + + /** + * Resize array, if necessary, to be able to hold given index + */ + private void grow(int index) { + int newlen = queue.length; + if (index < newlen) // don't need to grow + return; + if (index == Integer.MAX_VALUE) + throw new OutOfMemoryError(); + while (newlen <= index) { + if (newlen >= Integer.MAX_VALUE / 2) // avoid overflow + newlen = Integer.MAX_VALUE; + else + newlen <<= 2; + } + Object[] newQueue = new Object[newlen]; + System.arraycopy(queue, 0, newQueue, 0, queue.length); + queue = newQueue; + } + // Queue Methods + + /** * Add the specified element to this priority queue. * @@ -176,13 +278,8 @@ public class PriorityQueue extends Ab ++size; // Grow backing store if necessary - // FIXME: watch for overflow - // FIXME: what if we're full? - while (size >= queue.length) { - Object[] newQueue = new Object[2 * queue.length]; - System.arraycopy(queue, 0, newQueue, 0, queue.length); - queue = newQueue; - } + if (size >= queue.length) + grow(size); queue[size] = o; fixUp(size); @@ -199,12 +296,14 @@ public class PriorityQueue extends Ab return (E) queue[1]; } - // Collection Methods - - // these first two override just to get the throws docs + // Collection Methods - the first two override to update docs /** - * @throws NullPointerException if the specified element is null. + * Adds the specified element to this queue. + * @return true (as per the general contract of + * Collection.add). + * + * @throws NullPointerException {@inheritDoc} * @throws ClassCastException if the specified element cannot be compared * with elements currently in the priority queue according * to the priority queue's ordering. @@ -213,17 +312,40 @@ public class PriorityQueue extends Ab return super.add(o); } + /** + * Adds all of the elements in the specified collection to this queue. + * The behavior of this operation is undefined if + * the specified collection is modified while the operation is in + * progress. (This implies that the behavior of this call is undefined if + * the specified collection is this queue, and this queue is nonempty.) + *

+ * This implementation iterates over the specified collection, and adds + * each object returned by the iterator to this collection, in turn. + * @throws NullPointerException {@inheritDoc} * @throws ClassCastException if any element cannot be compared * with elements currently in the priority queue according * to the priority queue's ordering. - * @throws NullPointerException if c or any element in c - * is null */ public boolean addAll(Collection c) { return super.addAll(c); } + + /** + * Removes a single instance of the specified element from this + * queue, if it is present. More formally, + * removes an element e such that (o==null ? e==null : + * o.equals(e)), if the queue contains one or more such + * elements. Returns true if the queue contained the + * specified element (or equivalently, if the queue changed as a + * result of the call). + * + *

This implementation iterates over the queue looking for the + * specified element. If it finds the element, it removes the element + * from the queue using the iterator's remove method.

+ * + */ public boolean remove(Object o) { if (o == null) return false; @@ -246,6 +368,12 @@ public class PriorityQueue extends Ab return false; } + /** + * Returns an iterator over the elements in this queue. The iterator + * does not return the elements in any particular order. + * + * @return an iterator over the elements in this queue. + */ public Iterator iterator() { return new Itr(); } @@ -302,11 +430,6 @@ public class PriorityQueue extends Ab } } - /** - * Returns the number of elements in this priority queue. - * - * @return the number of elements in this priority queue. - */ public int size() { return size; } @@ -404,6 +527,15 @@ public class PriorityQueue extends Ab } } + + /** + * Returns the comparator used to order this collection, or null + * if this collection is sorted according to its elements natural ordering + * (using Comparable). + * + * @return the comparator used to order this collection, or null + * if this collection is sorted according to its elements natural ordering. + */ public Comparator comparator() { return comparator; } @@ -417,7 +549,7 @@ public class PriorityQueue extends Ab * Object) in the proper order. * @param s the stream */ - private synchronized void writeObject(java.io.ObjectOutputStream s) + private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff s.defaultWriteObject(); @@ -435,7 +567,7 @@ public class PriorityQueue extends Ab * deserialize it). * @param s the stream */ - private synchronized void readObject(java.io.ObjectInputStream s) + private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in size, and any hidden stuff s.defaultReadObject();