--- jsr166/src/main/java/util/PriorityQueue.java 2003/08/12 11:11:58 1.27
+++ jsr166/src/main/java/util/PriorityQueue.java 2003/08/30 11:40:04 1.36
@@ -1,18 +1,15 @@
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.
+ * 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
+ * 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.
*
*
The {@link #remove()} and {@link #poll()} methods remove and
@@ -28,6 +25,18 @@
* 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()).
+ *
+ *
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
@@ -44,6 +53,8 @@
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 +147,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();
}
/**
@@ -177,7 +188,8 @@ public class PriorityQueue extends Ab
public PriorityQueue(Collection extends E> c) {
initializeArray(c);
if (c instanceof SortedSet) {
- SortedSet extends E> s = (SortedSet extends E>) c;
+ // @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) {
@@ -256,9 +268,8 @@ public class PriorityQueue extends Ab
queue = newQueue;
}
- // Queue Methods
-
+ // Queue Methods
/**
* Add the specified element to this priority queue.
@@ -287,7 +298,7 @@ public class PriorityQueue extends Ab
public E poll() {
if (size == 0)
return null;
- return (E) remove(1);
+ return remove();
}
public E peek() {
@@ -330,7 +341,7 @@ public class PriorityQueue extends Ab
}
- /**
+ /**
* 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 :
@@ -351,14 +362,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;
}
}
@@ -377,6 +388,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.
@@ -384,9 +396,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;
@@ -397,28 +409,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;
}
@@ -446,22 +499,51 @@ public class PriorityQueue extends Ab
}
/**
- * Removes and returns the ith element from queue. Recall
- * that queue is one-based, so 1 <= i <= size.
+ * Removes and returns the first element from queue.
+ */
+ public E remove() {
+ if (size == 0)
+ throw new NoSuchElementException();
+ 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.)
*
- * 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;
}
/**
@@ -484,7 +566,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;
@@ -505,17 +587,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;
@@ -525,6 +610,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
@@ -580,4 +673,3 @@ public class PriorityQueue extends Ab
}
}
-