--- jsr166/src/main/java/util/PriorityQueue.java 2003/08/27 01:33:50 1.34
+++ jsr166/src/main/java/util/PriorityQueue.java 2004/06/02 23:45:46 1.50
@@ -1,34 +1,42 @@
- package java.util;
+/*
+ * %W% %E%
+ *
+ * Copyright 2004 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.
- *
- *
The {@link #remove()} and {@link #poll()} methods remove and
- * return the head of the queue.
+ * 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).
*
- *
The {@link #element()} and {@link #peek()} methods return, but do
- * not delete, 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.
*
- *
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.
+ *
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 Iterator provided in method {@link #iterator()} is not
+ *
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()).
@@ -51,10 +59,12 @@
*
* Java Collections Framework.
* @since 1.5
+ * @version %I%, %G%
* @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;
@@ -150,22 +160,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();
}
/**
@@ -191,8 +201,7 @@ public class PriorityQueue extends Ab
public PriorityQueue(Collection extends E> c) {
initializeArray(c);
if (c instanceof SortedSet) {
- // @fixme double-cast workaround for compiler
- SortedSet extends E> s = (SortedSet extends E>) (SortedSet)c;
+ SortedSet extends E> s = (SortedSet extends E>)c;
comparator = (Comparator super E>)s.comparator();
fillFromSorted(s);
} else if (c instanceof PriorityQueue) {
@@ -271,12 +280,9 @@ public class PriorityQueue extends Ab
queue = newQueue;
}
- // Queue Methods
-
-
/**
- * 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
@@ -299,13 +305,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];
}
@@ -316,48 +318,18 @@ 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);
}
-
/**
- * 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.
- */
- public boolean addAll(Collection extends E> 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.
- *
+ * queue, if it is present.
*/
public boolean remove(Object o) {
if (o == null)
@@ -366,14 +338,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;
}
}
@@ -392,6 +364,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.
@@ -399,9 +372,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;
@@ -412,27 +385,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);
- 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,7 +462,8 @@ public class PriorityQueue extends Ab
}
/**
- * Remove all elements from the priority queue.
+ * Removes all elements from the priority queue.
+ * The queue will be empty after this call returns.
*/
public void clear() {
modCount++;
@@ -459,21 +475,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.)
*
+ * 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;
}
/**
@@ -496,7 +540,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;
@@ -518,8 +562,10 @@ 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)
break;
Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
@@ -527,7 +573,8 @@ public class PriorityQueue extends Ab
}
} else {
while ((j = k << 1) <= size && (j > 0)) {
- if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
+ if (j 0)
j++; // j indexes smallest kid
if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
break;
@@ -537,6 +584,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
@@ -568,7 +623,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