--- jsr166/src/main/java/util/PriorityQueue.java 2003/09/01 12:23:28 1.38 +++ jsr166/src/main/java/util/PriorityQueue.java 2005/11/24 03:44:57 1.54 @@ -1,41 +1,43 @@ /* - * %W% %E% + * @(#)PriorityQueue.java 1.8 05/08/27 * - * Copyright 2003 Sun Microsystems, Inc. All rights reserved. + * Copyright 2005 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; +import java.util.*; // for javadoc (till 6280605 is fixed) /** - * 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 {@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 constructor is used. - *

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. + * An unbounded priority {@linkplain Queue queue} based on a priority + * heap. The elements of the priority queue are ordered according to + * their {@linkplain Comparable natural ordering}, or by a {@link + * Comparator} provided at queue construction time, depending on which + * constructor is used. A priority queue does not permit + * null elements. A priority queue relying on natural + * ordering also does not permit insertion of non-comparable objects + * (doing so may result in ClassCastException). * - *

The {@link #remove()} and {@link #poll()} methods remove and - * return the head of the queue. + *

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 -- ties are + * broken arbitrarily. The queue retrieval operations poll, + * remove, peek, and element access the + * element at the head of the queue. * - *

The {@link #element()} and {@link #peek()} methods return, but do - * not delete, the head of the queue. + *

A priority queue is unbounded, but has an internal + * capacity governing the size of an array used to store the + * elements on the 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. * - *

A priority queue has a capacity. The capacity is the - * size of the array used internally to store the elements on the - * 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. - * - *

The Iterator provided in method {@link #iterator()} is not - * guaranteed to traverse the elements of the PriorityQueue in any - * particular order. If you need ordered traversal, consider using - * Arrays.sort(pq.toArray()). + *

This class and its iterator implement all of the + * optional methods of the {@link Collection} and {@link + * Iterator} interfaces. The Iterator provided in method {@link + * #iterator()} is not guaranteed to traverse the elements of + * the priority queue in any particular order. If you need ordered + * traversal, consider using Arrays.sort(pq.toArray()). * *

Note that this implementation is not synchronized. * Multiple threads should not access a PriorityQueue @@ -43,7 +45,6 @@ package java.util; * structurally. Instead, use the thread-safe {@link * java.util.concurrent.PriorityBlockingQueue} class. * - * *

Implementation note: this implementation provides O(log(n)) time * for the insertion methods (offer, poll, * remove() and add) methods; linear time for the @@ -55,11 +56,12 @@ package java.util; * * Java Collections Framework. * @since 1.5 - * @version %I%, %G% + * @version 1.8, 08/27/05 * @author Josh Bloch + * @param the type of elements held in this collection */ public class PriorityQueue extends AbstractQueue - implements Queue, java.io.Serializable { + implements java.io.Serializable { private static final long serialVersionUID = -7720805057305804111L; @@ -98,20 +100,20 @@ public class PriorityQueue extends Ab private transient int modCount = 0; /** - * Creates a PriorityQueue with the default initial capacity - * (11) that orders its elements according to their natural - * ordering (using Comparable). + * Creates a PriorityQueue with the default initial + * capacity (11) that orders its elements according to their + * {@linkplain Comparable natural ordering}. */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } /** - * Creates a PriorityQueue with the specified initial capacity - * that orders its elements according to their natural ordering - * (using Comparable). + * Creates a PriorityQueue with the specified initial + * capacity that orders its elements according to their + * {@linkplain Comparable natural ordering}. * - * @param initialCapacity the initial capacity for this priority queue. + * @param initialCapacity the initial capacity for this priority queue * @throws IllegalArgumentException if initialCapacity is less * than 1 */ @@ -123,14 +125,14 @@ public class PriorityQueue extends Ab * 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. - * @param comparator the comparator used to order this priority queue. - * If null then the order depends on the elements' natural - * ordering. - * @throws IllegalArgumentException if initialCapacity is less - * than 1 + * @param initialCapacity the initial capacity for this priority queue + * @param comparator the comparator that will be used to order + * this priority queue. If null, the natural + * ordering of the elements will be used. + * @throws IllegalArgumentException if initialCapacity is + * less than 1 */ - public PriorityQueue(int initialCapacity, + public PriorityQueue(int initialCapacity, Comparator comparator) { if (initialCapacity < 1) throw new IllegalArgumentException(); @@ -153,13 +155,17 @@ public class PriorityQueue extends Ab } /** - * Initially fill elements of the queue array under the + * 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 in the order presented. */ private void fillFromSorted(Collection c) { - for (Iterator i = c.iterator(); i.hasNext(); ) - queue[++size] = i.next(); + for (Iterator i = c.iterator(); i.hasNext(); ) { + int k = ++size; + if (k >= queue.length) + grow(k); + queue[k] = i.next(); + } } /** @@ -168,8 +174,12 @@ public class PriorityQueue extends Ab * invariant. */ private void fillFromUnsorted(Collection c) { - for (Iterator i = c.iterator(); i.hasNext(); ) - queue[++size] = i.next(); + for (Iterator i = c.iterator(); i.hasNext(); ) { + int k = ++size; + if (k >= queue.length) + grow(k); + queue[k] = i.next(); + } heapify(); } @@ -179,25 +189,22 @@ public class PriorityQueue extends Ab * 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. + * PriorityQueue, the priority queue will be ordered + * according to the same ordering. Otherwise, this priority queue + * will be ordered according to the natural ordering of its elements. * - * @param c the collection whose elements are to be placed - * into this priority queue. + * @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 + * queue's ordering + * @throws NullPointerException if the specified collection or any + * of its elements are null */ public PriorityQueue(Collection c) { initializeArray(c); if (c instanceof SortedSet) { - // @fixme double-cast workaround for compiler - SortedSet s = (SortedSet) (SortedSet)c; + SortedSet s = (SortedSet)c; comparator = (Comparator)s.comparator(); fillFromSorted(s); } else if (c instanceof PriorityQueue) { @@ -212,20 +219,19 @@ public class PriorityQueue extends Ab /** * 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 + * specified priority queue. The priority queue has an initial + * capacity of 110% of the size of the specified priority queue or + * 1 if the priority queue is empty. This priority queue will be + * ordered according to the same ordering as the given priority + * queue. + * + * @param c the priority queue whose elements are to be placed + * into this priority queue + * @throws ClassCastException if elements of c cannot be + * compared to one another according to c's + * ordering + * @throws NullPointerException if the specified priority queue or any + * of its elements are null */ public PriorityQueue(PriorityQueue c) { initializeArray(c); @@ -235,20 +241,18 @@ public class PriorityQueue extends Ab /** * 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 + * specified sorted set. The priority queue has an initial + * capacity of 110% of the size of the specified sorted set or 1 + * if the sorted set is empty. This priority queue will be ordered + * according to the same ordering as the given sorted set. + * + * @param c the sorted set whose elements are to be placed + * into this priority queue. + * @throws ClassCastException if elements of the specified sorted + * set cannot be compared to one another according to the + * sorted set's ordering + * @throws NullPointerException if the specified sorted set or any + * of its elements are null */ public PriorityQueue(SortedSet c) { initializeArray(c); @@ -257,7 +261,7 @@ public class PriorityQueue extends Ab } /** - * Resize array, if necessary, to be able to hold given index + * Resize array, if necessary, to be able to hold given index. */ private void grow(int index) { int newlen = queue.length; @@ -269,127 +273,148 @@ public class PriorityQueue extends Ab if (newlen >= Integer.MAX_VALUE / 2) // avoid overflow newlen = Integer.MAX_VALUE; else - newlen <<= 2; + newlen <<= 1; } - Object[] newQueue = new Object[newlen]; - System.arraycopy(queue, 0, newQueue, 0, queue.length); - queue = newQueue; + queue = Arrays.copyOf(queue, newlen); } - - // Queue Methods + /** + * Inserts the specified element into this priority queue. + * + * @return true (as specified by {@link Collection#add}) + * @throws ClassCastException if the specified element cannot be + * compared with elements currently in this priority queue + * according to the priority queue's ordering + * @throws NullPointerException if the specified element is null + */ + public boolean add(E e) { + return offer(e); + } /** - * Add the specified element to this priority queue. + * Inserts the specified element into this priority queue. * - * @return true - * @throws ClassCastException if the specified element cannot be compared - * with elements currently in the priority queue according - * to the priority queue's ordering. - * @throws NullPointerException if the specified element is null. + * @return true (as specified by {@link Queue#offer}) + * @throws ClassCastException if the specified element cannot be + * compared with elements currently in this priority queue + * according to the priority queue's ordering + * @throws NullPointerException if the specified element is null */ - public boolean offer(E o) { - if (o == null) + public boolean offer(E e) { + if (e == null) throw new NullPointerException(); modCount++; ++size; // Grow backing store if necessary - if (size >= queue.length) + if (size >= queue.length) grow(size); - queue[size] = o; + queue[size] = e; fixUp(size); return true; } - public E poll() { + public E peek() { if (size == 0) return null; - return remove(); - } - - public E peek() { return (E) queue[1]; } - // Collection Methods - the first two override to update docs + private int indexOf(Object o) { + if (o == null) + return -1; + for (int i = 1; i <= size; i++) + if (o.equals(queue[i])) + return i; + return -1; + } /** - * Adds the specified element to this queue. - * @return true (as per the general contract of - * Collection.add). + * Removes a single instance of the specified element from this queue, + * if it is present. More formally, removes an element e such + * that o.equals(e), if this queue contains one or more such + * elements. Returns true if this queue contained the specified element + * (or equivalently, if this queue changed as a result of the call). * - * @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. + * @param o element to be removed from this queue, if present + * @return true if this queue changed as a result of the call */ - public boolean add(E o) { - return super.add(o); + public boolean remove(Object o) { + int i = indexOf(o); + if (i == -1) + return false; + else { + removeAt(i); + return true; + } } - /** - * 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. + * Returns true if this queue contains the specified element. + * More formally, returns true if and only if this queue contains + * at least one element e such that o.equals(e). + * + * @param o object to be checked for containment in this queue + * @return true if this queue contains the specified element */ - public boolean addAll(Collection c) { - return super.addAll(c); + public boolean contains(Object o) { + return indexOf(o) != -1; } - /** - * 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). + * Returns an array containing all of the elements in this queue, + * The elements are in no particular order. * - *

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.

+ *

The returned array will be "safe" in that no references to it are + * maintained by this list. (In other words, this method must allocate + * a new array). The caller is thus free to modify the returned array. * + * @return an array containing all of the elements in this queue. */ - public boolean remove(Object o) { - if (o == null) - return false; + public Object[] toArray() { + return Arrays.copyOfRange(queue, 1, size+1); + } - if (comparator == null) { - for (int i = 1; i <= size; i++) { - if (((Comparable)queue[i]).compareTo((E)o) == 0) { - removeAt(i); - return true; - } - } - } else { - for (int i = 1; i <= size; i++) { - if (comparator.compare((E)queue[i], (E)o) == 0) { - removeAt(i); - return true; - } - } - } - return false; + /** + * Returns an array containing all of the elements in this queue. + * The elements are in no particular order. The runtime type of + * the returned array is that of the specified array. If the queue + * fits in the specified array, it is returned therein. + * Otherwise, a new array is allocated with the runtime type of + * the specified array and the size of this queue. + * + *

If the queue fits in the specified array with room to spare + * (i.e., the array has more elements than the queue), the element in + * the array immediately following the end of the collection is set to + * null. (This is useful in determining the length of the + * queue only if the caller knows that the queue does not contain + * any null elements.) + * + * @param a the array into which the elements of the queue are to + * be stored, if it is big enough; otherwise, a new array of the + * same runtime type is allocated for this purpose. + * @return an array containing the elements of the queue + * @throws ArrayStoreException if the runtime type of the specified array + * is not a supertype of the runtime type of every element in + * this queue + * @throws NullPointerException if the specified array is null + */ + public T[] toArray(T[] a) { + if (a.length < size) + // Make a new array of a's runtime type, but my contents: + return (T[]) Arrays.copyOfRange(queue, 1, size+1, a.getClass()); + System.arraycopy(queue, 1, a, 0, size); + if (a.length > size) + a[size] = null; + return a; } /** * 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. + * @return an iterator over the elements in this queue */ public Iterator iterator() { return new Itr(); @@ -452,7 +477,7 @@ public class PriorityQueue extends Ab else { int remaining = forgetMeNot.size(); result = forgetMeNot.remove(remaining - 1); - if (remaining == 1) + if (remaining == 1) forgetMeNot = null; lastRet = 0; lastRetElt = result; @@ -494,7 +519,8 @@ public class PriorityQueue extends Ab } /** - * Remove all elements from the priority queue. + * Removes all of the elements from this priority queue. + * The queue will be empty after this call returns. */ public void clear() { modCount++; @@ -506,12 +532,9 @@ public class PriorityQueue extends Ab size = 0; } - /** - * Removes and returns the first element from queue. - */ - public E remove() { + public E poll() { if (size == 0) - throw new NoSuchElementException(); + return null; modCount++; E result = (E) queue[1]; @@ -536,7 +559,7 @@ public class PriorityQueue extends Ab * previously at the end of the list and is now at some position between * 2 and i-1 inclusive. */ - private E removeAt(int i) { + private E removeAt(int i) { assert i > 0 && i <= size; modCount++; @@ -567,7 +590,7 @@ public class PriorityQueue extends Ab if (comparator == null) { while (k > 1) { int j = k >> 1; - if (((Comparable)queue[j]).compareTo((E)queue[k]) <= 0) + if (((Comparable)queue[j]).compareTo((E)queue[k]) <= 0) break; Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; k = j; @@ -596,18 +619,18 @@ public class PriorityQueue extends Ab int j; if (comparator == null) { while ((j = k << 1) <= size && (j > 0)) { - if (j)queue[j]).compareTo((E)queue[j+1]) > 0) + if (j)queue[j]).compareTo((E)queue[j+1]) > 0) j++; // j indexes smallest kid - if (((Comparable)queue[k]).compareTo((E)queue[j]) <= 0) + if (((Comparable)queue[k]).compareTo((E)queue[j]) <= 0) break; Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; k = j; } } else { while ((j = k << 1) <= size && (j > 0)) { - if (j 0) j++; // j indexes smallest kid if (comparator.compare((E)queue[k], (E)queue[j]) <= 0) @@ -628,12 +651,13 @@ 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. + * Returns the comparator used to order the elements in this + * queue, or null if this queue is sorted according to + * the {@linkplain Comparable natural ordering} of its elements. + * + * @return the comparator used to order this queue, or + * null if this queue is sorted according to the + * natural ordering of its elements. */ public Comparator comparator() { return comparator; @@ -657,13 +681,13 @@ public class PriorityQueue extends Ab s.writeInt(queue.length); // Write out all elements in the proper order. - for (int i=0; iArrayList instance from a stream (that is, - * deserialize it). + * Reconstitute the PriorityQueue instance from a stream + * (that is, deserialize it). * @param s the stream */ private void readObject(java.io.ObjectInputStream s) @@ -676,7 +700,7 @@ public class PriorityQueue extends Ab queue = new Object[arrayLength]; // Read in all elements in the proper order. - for (int i=0; i