--- jsr166/src/main/java/util/PriorityQueue.java 2004/11/21 01:40:39 1.51 +++ jsr166/src/main/java/util/PriorityQueue.java 2005/11/22 11:44:47 1.52 @@ -1,22 +1,22 @@ /* - * %W% %E% + * @(#)PriorityQueue.java 1.8 05/08/27 * - * Copyright 2004 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 either according to their - * natural order (see {@link Comparable}), or according to a - * {@link java.util.Comparator}, 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). + * 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 head of this queue is the least element * with respect to the specified ordering. If multiple elements are @@ -34,12 +34,10 @@ package java.util; * *

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 PriorityQueue in any - * particular order. If you need ordered traversal, consider using - * Arrays.sort(pq.toArray()). + * 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 @@ -47,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 @@ -59,7 +56,7 @@ 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 */ @@ -103,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 */ @@ -128,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(); @@ -158,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(); + } } /** @@ -173,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(); } @@ -184,19 +189,17 @@ 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); @@ -216,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); @@ -239,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); @@ -261,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; @@ -275,32 +275,42 @@ public class PriorityQueue extends Ab else newlen <<= 2; } - Object[] newQueue = new Object[newlen]; - System.arraycopy(queue, 0, newQueue, 0, queue.length); - queue = newQueue; + queue = Arrays.copyOf(queue, newlen); } - /** * 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 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 offer(E o) { - if (o == null) + public boolean add(E e) { + return offer(e); + } + + /** + * Inserts the specified element into this priority queue. + * + * @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 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; } @@ -311,53 +321,100 @@ public class PriorityQueue extends Ab 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; + } + + /** + * 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). + * + * @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 remove(Object o) { + int i = indexOf(o); + if (i == -1) + return false; + else { + removeAt(i); + return true; + } + } /** - * Adds the specified element to this queue. - * @return true (as per the general contract of - * Collection.add). + * 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). * - * @throws NullPointerException if the specified element is null. - * @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 object to be checked for containment in this queue + * @return true if this queue contains the specified element */ - public boolean add(E o) { - return offer(o); + public boolean contains(Object o) { + return indexOf(o) != -1; } /** - * Removes a single instance of the specified element from this - * queue, if it is present. + * Returns an array containing all of the elements in this queue, + * The elements are in no particular order. + * + *

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(); @@ -420,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; @@ -462,7 +519,7 @@ public class PriorityQueue extends Ab } /** - * Removes 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() { @@ -502,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++; @@ -533,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; @@ -562,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) @@ -594,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; @@ -628,8 +686,8 @@ public class PriorityQueue extends Ab } /** - * Reconstitute the ArrayList 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)