--- jsr166/src/main/java/util/PriorityQueue.java 2003/08/06 18:22:09 1.24
+++ jsr166/src/main/java/util/PriorityQueue.java 2003/09/13 18:51:06 1.41
@@ -1,33 +1,49 @@
- package java.util;
+/*
+ * %W% %E%
+ *
+ * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
+ * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
+ */
+
+package java.util;
/**
- * 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. 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.
+ *
+ *
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 {@link #remove()} and {@link #poll()}
+ * methods remove and return the head of the queue, and the {@link
+ * #element()} and {@link #peek()} methods return, but do not delete,
+ * the head of the queue.
*
- *
The {@link #remove()} and {@link #poll()} methods remove and
- * return 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.
*
- *
The {@link #element()} and {@link #peek()} methods return, but do
- * not delete, the head of the queue.
+ *
This class implements 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()).
*
- *
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.
+ *
Note that this implementation is not synchronized.
+ * Multiple threads should not access a PriorityQueue
+ * instance concurrently if any of the threads modifies the list
+ * 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
@@ -39,11 +55,14 @@
*
* Java Collections Framework.
* @since 1.5
+ * @version %I%, %G%
* @author Josh Bloch
*/
public class PriorityQueue extends AbstractQueue
implements Queue, java.io.Serializable {
+ private static final long serialVersionUID = -7720805057305804111L;
+
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
@@ -136,22 +155,22 @@ public class PriorityQueue extends Ab
/**
* 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.
+ * case we can just place the elements in the order presented.
*/
private void fillFromSorted(Collection extends E> c) {
for (Iterator extends E> i = c.iterator(); i.hasNext(); )
queue[++size] = i.next();
}
-
/**
- * Initially fill elements of the queue array that is
- * not to our knowledge sorted, so we must add them
- * one by one.
+ * Initially fill elements of the queue array that is not to our knowledge
+ * sorted, so we must rearrange the elements to guarantee the heap
+ * invariant.
*/
private void fillFromUnsorted(Collection extends E> c) {
for (Iterator extends E> i = c.iterator(); i.hasNext(); )
- add(i.next());
+ queue[++size] = i.next();
+ heapify();
}
/**
@@ -159,7 +178,7 @@ public class PriorityQueue extends Ab
* 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 SortedSet} or is another
+ * 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
@@ -176,17 +195,16 @@ public class PriorityQueue extends Ab
*/
public PriorityQueue(Collection extends E> c) {
initializeArray(c);
- if (c instanceof SortedSet extends E>) {
- SortedSet extends E> s = (SortedSet extends E>) c;
+ if (c instanceof SortedSet) {
+ // @fixme double-cast workaround for compiler
+ SortedSet extends E> s = (SortedSet extends E>) (SortedSet)c;
comparator = (Comparator super E>)s.comparator();
fillFromSorted(s);
- }
- else if (c instanceof PriorityQueue extends E>) {
+ } else if (c instanceof PriorityQueue) {
PriorityQueue extends E> s = (PriorityQueue extends E>) c;
comparator = (Comparator super E>)s.comparator();
fillFromSorted(s);
- }
- else {
+ } else {
comparator = null;
fillFromUnsorted(c);
}
@@ -258,12 +276,9 @@ public class PriorityQueue extends Ab
queue = newQueue;
}
- // Queue Methods
-
-
/**
- * Add the specified element to this priority queue.
+ * Inserts the specified element to this priority queue.
*
* @return true
* @throws ClassCastException if the specified element cannot be compared
@@ -286,13 +301,9 @@ public class PriorityQueue extends Ab
return true;
}
- public E poll() {
+ public E peek() {
if (size == 0)
return null;
- return (E) remove(1);
- }
-
- public E peek() {
return (E) queue[1];
}
@@ -303,13 +314,13 @@ public class PriorityQueue extends Ab
* @return true (as per the general contract of
* Collection.add).
*
- * @throws NullPointerException {@inheritDoc}
+ * @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.
*/
public boolean add(E o) {
- return super.add(o);
+ return offer(o);
}
@@ -322,7 +333,11 @@ public class PriorityQueue extends Ab
*
* This implementation iterates over the specified collection, and adds
* each object returned by the iterator to this collection, in turn.
- * @throws NullPointerException {@inheritDoc}
+ * @param c collection whose elements are to be added to this queue
+ * @return true if this queue changed as a result of the
+ * call.
+ * @throws NullPointerException if c or any element in c
+ * is null
* @throws ClassCastException if any element cannot be compared
* with elements currently in the priority queue according
* to the priority queue's ordering.
@@ -331,21 +346,6 @@ public class PriorityQueue extends Ab
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;
@@ -353,14 +353,14 @@ public class PriorityQueue extends Ab
if (comparator == null) {
for (int i = 1; i <= size; i++) {
if (((Comparable)queue[i]).compareTo((E)o) == 0) {
- remove(i);
+ removeAt(i);
return true;
}
}
} else {
for (int i = 1; i <= size; i++) {
if (comparator.compare((E)queue[i], (E)o) == 0) {
- remove(i);
+ removeAt(i);
return true;
}
}
@@ -379,6 +379,7 @@ public class PriorityQueue extends Ab
}
private class Itr implements Iterator {
+
/**
* Index (into queue array) of element to be returned by
* subsequent call to next.
@@ -386,9 +387,9 @@ public class PriorityQueue extends Ab
private int cursor = 1;
/**
- * Index of element returned by most recent call to next or
- * previous. Reset to 0 if this element is deleted by a call
- * to remove.
+ * Index of element returned by most recent call to next,
+ * unless that element came from the forgetMeNot list.
+ * Reset to 0 if element is deleted by a call to remove.
*/
private int lastRet = 0;
@@ -399,28 +400,69 @@ public class PriorityQueue extends Ab
*/
private int expectedModCount = modCount;
+ /**
+ * A list of elements that were moved from the unvisited portion of
+ * the heap into the visited portion as a result of "unlucky" element
+ * removals during the iteration. (Unlucky element removals are those
+ * that require a fixup instead of a fixdown.) We must visit all of
+ * the elements in this list to complete the iteration. We do this
+ * after we've completed the "normal" iteration.
+ *
+ * We expect that most iterations, even those involving removals,
+ * will not use need to store elements in this field.
+ */
+ private ArrayList forgetMeNot = null;
+
+ /**
+ * Element returned by the most recent call to next iff that
+ * element was drawn from the forgetMeNot list.
+ */
+ private Object lastRetElt = null;
+
public boolean hasNext() {
- return cursor <= size;
+ return cursor <= size || forgetMeNot != null;
}
public E next() {
checkForComodification();
- if (cursor > size)
+ E result;
+ if (cursor <= size) {
+ result = (E) queue[cursor];
+ lastRet = cursor++;
+ }
+ else if (forgetMeNot == null)
throw new NoSuchElementException();
- E result = (E) queue[cursor];
- lastRet = cursor++;
+ else {
+ int remaining = forgetMeNot.size();
+ result = forgetMeNot.remove(remaining - 1);
+ if (remaining == 1)
+ forgetMeNot = null;
+ lastRet = 0;
+ lastRetElt = result;
+ }
return result;
}
public void remove() {
- if (lastRet == 0)
- throw new IllegalStateException();
checkForComodification();
- PriorityQueue.this.remove(lastRet);
- if (lastRet < cursor)
- cursor--;
- lastRet = 0;
+ if (lastRet != 0) {
+ E moved = PriorityQueue.this.removeAt(lastRet);
+ lastRet = 0;
+ if (moved == null) {
+ cursor--;
+ } else {
+ if (forgetMeNot == null)
+ forgetMeNot = new ArrayList();
+ forgetMeNot.add(moved);
+ }
+ } else if (lastRetElt != null) {
+ PriorityQueue.this.remove(lastRetElt);
+ lastRetElt = null;
+ } else {
+ throw new IllegalStateException();
+ }
+
expectedModCount = modCount;
}
@@ -447,23 +489,49 @@ public class PriorityQueue extends Ab
size = 0;
}
+ public E poll() {
+ if (size == 0)
+ return null;
+ modCount++;
+
+ E result = (E) queue[1];
+ queue[1] = queue[size];
+ queue[size--] = null; // Drop extra ref to prevent memory leak
+ if (size > 1)
+ fixDown(1);
+
+ return result;
+ }
+
/**
- * Removes and returns the ith element from queue. Recall
- * that queue is one-based, so 1 <= i <= size.
+ * Removes and returns the ith element from queue. (Recall that queue
+ * is one-based, so 1 <= i <= size.)
*
- * XXX: Could further special-case i==size, but is it worth it?
- * XXX: Could special-case i==0, but is it worth it?
+ * Normally this method leaves the elements at positions from 1 up to i-1,
+ * inclusive, untouched. Under these circumstances, it returns null.
+ * Occasionally, in order to maintain the heap invariant, it must move
+ * the last element of the list to some index in the range [2, i-1],
+ * and move the element previously at position (i/2) to position i.
+ * Under these circumstances, this method returns the element that was
+ * previously at the end of the list and is now at some position between
+ * 2 and i-1 inclusive.
*/
- private E remove(int i) {
- assert i <= size;
+ private E removeAt(int i) {
+ assert i > 0 && i <= size;
modCount++;
- E result = (E) queue[i];
- queue[i] = queue[size];
+ E moved = (E) queue[size];
+ queue[i] = moved;
queue[size--] = null; // Drop extra ref to prevent memory leak
- if (i <= size)
+ if (i <= size) {
fixDown(i);
- return result;
+ if (queue[i] == moved) {
+ fixUp(i);
+ if (queue[i] != moved)
+ return moved;
+ }
+ }
+ return null;
}
/**
@@ -486,7 +554,7 @@ public class PriorityQueue extends Ab
}
} else {
while (k > 1) {
- int j = k >> 1;
+ int j = k >>> 1;
if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
break;
Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
@@ -507,17 +575,20 @@ public class PriorityQueue extends Ab
private void fixDown(int k) {
int j;
if (comparator == null) {
- while ((j = k << 1) <= size) {
- if (j)queue[j]).compareTo((E)queue[j+1]) > 0)
+ while ((j = k << 1) <= size && (j > 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)
break;
Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
k = j;
}
} else {
- while ((j = k << 1) <= size) {
- if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
+ 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)
break;
@@ -527,6 +598,14 @@ public class PriorityQueue extends Ab
}
}
+ /**
+ * Establishes the heap invariant (described above) in the entire tree,
+ * assuming nothing about the order of the elements prior to the call.
+ */
+ private void heapify() {
+ for (int i = size/2; i >= 1; i--)
+ fixDown(i);
+ }
/**
* Returns the comparator used to order this collection, or null
@@ -558,7 +637,7 @@ public class PriorityQueue extends Ab
s.writeInt(queue.length);
// Write out all elements in the proper order.
- for (int i=0; i extends Ab
queue = new Object[arrayLength];
// Read in all elements in the proper order.
- for (int i=0; i