java/util/PriorityQueue.java

 package java.util;

/**
 * A priority 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 <i>natural order</i> (see {@link Comparable}), or
 * according to a {@link java.util.Comparator}, depending on which
 * constructor is used.
 * <p>The <em>head</em> of this queue is the <em>least</em> 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
 * <tt>null</tt> elements.
 *
 * <p>The {@link #remove()} and {@link #poll()} methods remove and
 * return the head of the queue.
 *
 * <p>The {@link #element()} and {@link #peek()} methods return, but do
 * not delete, the head of the queue.
 *
 * <p>A priority queue has a <i>capacity</i>.  The capacity is the
 * size of the array used internally to store the elements on the
 * queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.
 * 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.
 *
 * <p>Implementation note: this implementation provides O(log(n)) time
 * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
 * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
 * <tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
 * constant time for the retrieval methods (<tt>peek</tt>,
 * <tt>element</tt>, and <tt>size</tt>).
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 * @since 1.5
 * @author Josh Bloch
 */
public class PriorityQueue<E> extends AbstractQueue<E>
    implements Sorted, Queue<E>, java.io.Serializable {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * Priority queue represented as a balanced binary heap: the two children
     * of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is
     * ordered by comparator, or by the elements' natural ordering, if
     * comparator is null:  For each node n in the heap and each descendant d
     * of n, n <= d.
     *
     * The element with the lowest value is in queue[1], assuming the queue is
     * nonempty.  (A one-based array is used in preference to the traditional
     * zero-based array to simplify parent and child calculations.)
     *
     * queue.length must be >= 2, even if size == 0.
     */
    private transient Object[] queue;

    /**
     * The number of elements in the priority queue.
     */
    private int size = 0;

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     */
    private final Comparator<? super E> comparator;

    /**
     * The number of times this priority queue has been
     * <i>structurally modified</i>.  See AbstractList for gory details.
     */
    private transient int modCount = 0;

    /**
     * Create a <tt>PriorityQueue</tt> with the default initial capacity
     * (11) that orders its elements according to their natural
     * ordering (using <tt>Comparable</tt>.)
     */
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    /**
     * Create a <tt>PriorityQueue</tt> with the specified initial capacity
     * that orders its elements according to their natural ordering
     * (using <tt>Comparable</tt>.)
     *
     * @param initialCapacity the initial capacity for this priority queue.
     */
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    /**
     * Create a <tt>PriorityQueue</tt> 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 <tt>null</tt> then the order depends on the elements' natural
     * ordering.
     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
     * than 1
     */
    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity + 1];
        this.comparator = comparator;
    }

    /**
     * Create a <tt>PriorityQueue</tt> containing the elements in the specified
     * collection.  The priority queue has an initial capacity of 110% of the
     * size of the specified collection (bounded by
     * <tt>Integer.MAX_VALUE-1</tt>); or 1 if the collection is empty.
     * If the specified collection
     * implements the {@link Sorted} interface, 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.  If the specified collection does not implement
     * <tt>Sorted</tt>, the priority queue is ordered 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 <tt>c</tt> or any element within it
     * is <tt>null</tt>
     */
    public PriorityQueue(Collection<? extends E> c) {
        int sz = c.size();
        int initialCapacity = (int)Math.min((sz * 110L) / 100,
                                            Integer.MAX_VALUE - 1);
        if (initialCapacity < 1)
            initialCapacity = 1;

        this.queue = new Object[initialCapacity + 1];

        // FIXME: if c is larger than Integer.MAX_VALUE we'll
        // overflow the array

        if (c instanceof Sorted) {
            comparator = (Comparator<? super E>)((Sorted)c).comparator();
        } else {
            comparator = null;
        }

        for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
            add(i.next());
    }

    // Queue Methods

    /**
     * Add the specified element to this priority queue.
     *
     * @return <tt>true</tt>
     * @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 <tt>null</tt>.
     */
    public boolean offer(E o) {
        if (o == null)
            throw new NullPointerException();
        modCount++;
        ++size;

        // Grow backing store if necessary
        // FIXME: watch for overflow
        // FIXME: what if we're full?
        while (size >= queue.length) {
            Object[] newQueue = new Object[2 * queue.length];
            System.arraycopy(queue, 0, newQueue, 0, queue.length);
            queue = newQueue;
        }

        queue[size] = o;
        fixUp(size);
        return true;
    }

    public E poll() {
        if (size == 0)
            return null;
        return (E) remove(1);
    }

    public E peek() {
        return (E) queue[1];
    }

    // Collection Methods

    // these first two override just to get the throws docs

    /**
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     * @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);
    }

    /**
     * @throws ClassCastException if any element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     * @throws NullPointerException if <tt>c</tt> or any element in <tt>c</tt>
     * is <tt>null</tt>
     */
    public boolean addAll(Collection<? extends E> c) {
        return super.addAll(c);
    }

    public boolean remove(Object o) {
        if (o == null)
            return false;

        if (comparator == null) {
            for (int i = 1; i <= size; i++) {
                if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
                    remove(i);
                    return true;
                }
            }
        } else {
            for (int i = 1; i <= size; i++) {
                if (comparator.compare((E)queue[i], (E)o) == 0) {
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }

    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        /**
         * Index (into queue array) of element to be returned by
         * subsequent call to next.
         */
        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.
         */
        private int lastRet = 0;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        private int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor <= size;
        }

        public E next() {
            checkForComodification();
            if (cursor > size)
                throw new NoSuchElementException();
            E result = (E) queue[cursor];
            lastRet = cursor++;
            return result;
        }

        public void remove() {
            if (lastRet == 0)
                throw new IllegalStateException();
            checkForComodification();

            PriorityQueue.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = 0;
            expectedModCount = modCount;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * Returns the number of elements in this priority queue.
     *
     * @return the number of elements in this priority queue.
     */
    public int size() {
        return size;
    }

    /**
     * Remove all elements from the priority queue.
     */
    public void clear() {
        modCount++;

        // Null out element references to prevent memory leak
        for (int i=1; i<=size; i++)
            queue[i] = null;

        size = 0;
    }

    /**
     * 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?
     */
    private E remove(int i) {
        assert i <= size;
        modCount++;

        E result = (E) queue[i];
        queue[i] = queue[size];
        queue[size--] = null;  // Drop extra ref to prevent memory leak
        if (i <= size)
            fixDown(i);
        return result;
    }

    /**
     * Establishes the heap invariant (described above) assuming the heap
     * satisfies the invariant except possibly for the leaf-node indexed by k
     * (which may have a nextExecutionTime less than its parent's).
     *
     * This method functions by "promoting" queue[k] up the hierarchy
     * (by swapping it with its parent) repeatedly until queue[k]
     * is greater than or equal to its parent.
     */
    private void fixUp(int k) {
        if (comparator == null) {
            while (k > 1) {
                int j = k >> 1;
                if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        } else {
            while (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;
                k = j;
            }
        }
    }

    /**
     * Establishes the heap invariant (described above) in the subtree
     * rooted at k, which is assumed to satisfy the heap invariant except
     * possibly for node k itself (which may be greater than its children).
     *
     * This method functions by "demoting" queue[k] down the hierarchy
     * (by swapping it with its smaller child) repeatedly until queue[k]
     * is less than or equal to its children.
     */
    private void fixDown(int k) {
        int j;
        if (comparator == null) {
            while ((j = k << 1) <= size) {
                if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
                    j++; // j indexes smallest kid
                if (((Comparable<E>)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)
                    j++; // j indexes smallest kid
                if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
                    break;
                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        }
    }

    public Comparator<? super E> comparator() {
        return comparator;
    }

    /**
     * Save the state of the instance to a stream (that
     * is, serialize it).
     *
     * @serialData The length of the array backing the instance is
     * emitted (int), followed by all of its elements (each an
     * <tt>Object</tt>) in the proper order.
     * @param s the stream
     */
    private synchronized void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        s.defaultWriteObject();

        // Write out array length
        s.writeInt(queue.length);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++)
            s.writeObject(queue[i]);
    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     * @param s the stream
     */
    private synchronized void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in array length and allocate array
        int arrayLength = s.readInt();
        queue = new Object[arrayLength];

        // Read in all elements in the proper order.
        for (int i=0; i<size; i++)
            queue[i] = s.readObject();
    }

}

Revision:	1.19
Committed:	Mon Aug 4 16:14:48 2003 UTC (20 years, 9 months ago) by tim
Branch:	MAIN
Changes since 1.18:	+9 -9 lines
Log Message:	Make atomics emulation classes match the main atomics. Fix docs for atomics (both in main and emulation). Restored more specific iterator types in both blocking queue impls. Fix unchecked cast warning in PQ.
#	User	Rev	Content
1	tim	1.2	package java.util;
2	tim	1.1
3			/**
4	dholmes	1.18	* A priority queue based on a priority heap. This queue orders
5	brian	1.6	* elements according to an order specified at construction time, which is
6	tim	1.19	* specified in the same manner as {@link java.util.TreeSet} and
7	dholmes	1.18	* {@link java.util.TreeMap}: elements are ordered
8	tim	1.2	* either according to their <i>natural order</i> (see {@link Comparable}), or
9	tim	1.19	* according to a {@link java.util.Comparator}, depending on which
10	dholmes	1.18	* constructor is used.
11	tim	1.19	* <p>The <em>head</em> of this queue is the <em>least</em> element with
12			* respect to the specified ordering.
13	dholmes	1.18	* If multiple elements are tied for least value, the
14	tim	1.14	* head is one of those elements. A priority queue does not permit
15	dholmes	1.11	* <tt>null</tt> elements.
16	tim	1.14	*
17	dholmes	1.11	* <p>The {@link #remove()} and {@link #poll()} methods remove and
18			* return the head of the queue.
19			*
20			* <p>The {@link #element()} and {@link #peek()} methods return, but do
21			* not delete, the head of the queue.
22	tim	1.2	*
23	dl	1.7	* <p>A priority queue has a <i>capacity</i>. The capacity is the
24			* size of the array used internally to store the elements on the
25	tim	1.19	* queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.
26	dholmes	1.18	* It is always at least as large as the queue size. As
27	dl	1.7	* elements are added to a priority queue, its capacity grows
28			* automatically. The details of the growth policy are not specified.
29	tim	1.2	*
30	dholmes	1.11	* <p>Implementation note: this implementation provides O(log(n)) time
31			* for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
32			* <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
33			* <tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
34			* constant time for the retrieval methods (<tt>peek</tt>,
35			* <tt>element</tt>, and <tt>size</tt>).
36	tim	1.2	*
37			* <p>This class is a member of the
38			* <a href="{@docRoot}/../guide/collections/index.html">
39			* Java Collections Framework</a>.
40	dl	1.7	* @since 1.5
41			* @author Josh Bloch
42	tim	1.2	*/
43			public class PriorityQueue<E> extends AbstractQueue<E>
44	dholmes	1.18	implements Sorted, Queue<E>, java.io.Serializable {
45	dholmes	1.11
46	tim	1.2	private static final int DEFAULT_INITIAL_CAPACITY = 11;
47	tim	1.1
48	tim	1.2	/**
49			* Priority queue represented as a balanced binary heap: the two children
50			* of queue[n] are queue[2n] and queue[2n + 1]. The priority queue is
51			* ordered by comparator, or by the elements' natural ordering, if
52	brian	1.6	* comparator is null: For each node n in the heap and each descendant d
53			* of n, n <= d.
54	tim	1.2	*
55	brian	1.6	* The element with the lowest value is in queue[1], assuming the queue is
56			* nonempty. (A one-based array is used in preference to the traditional
57			* zero-based array to simplify parent and child calculations.)
58	tim	1.2	*
59			* queue.length must be >= 2, even if size == 0.
60			*/
61	tim	1.16	private transient Object[] queue;
62	tim	1.1
63	tim	1.2	/**
64			* The number of elements in the priority queue.
65			*/
66			private int size = 0;
67	tim	1.1
68	tim	1.2	/**
69			* The comparator, or null if priority queue uses elements'
70			* natural ordering.
71			*/
72	tim	1.16	private final Comparator<? super E> comparator;
73	tim	1.2
74			/**
75			* The number of times this priority queue has been
76			* <i>structurally modified</i>. See AbstractList for gory details.
77			*/
78	dl	1.5	private transient int modCount = 0;
79	tim	1.2
80			/**
81	dholmes	1.11	* Create a <tt>PriorityQueue</tt> with the default initial capacity
82	dl	1.7	* (11) that orders its elements according to their natural
83			* ordering (using <tt>Comparable</tt>.)
84	tim	1.2	*/
85			public PriorityQueue() {
86	dholmes	1.11	this(DEFAULT_INITIAL_CAPACITY, null);
87	tim	1.1	}
88	tim	1.2
89			/**
90	dholmes	1.11	* Create a <tt>PriorityQueue</tt> with the specified initial capacity
91	dl	1.7	* that orders its elements according to their natural ordering
92			* (using <tt>Comparable</tt>.)
93	tim	1.2	*
94			* @param initialCapacity the initial capacity for this priority queue.
95			*/
96			public PriorityQueue(int initialCapacity) {
97			this(initialCapacity, null);
98	tim	1.1	}
99	tim	1.2
100			/**
101	dholmes	1.11	* Create a <tt>PriorityQueue</tt> with the specified initial capacity
102	tim	1.2	* that orders its elements according to the specified comparator.
103			*
104			* @param initialCapacity the initial capacity for this priority queue.
105			* @param comparator the comparator used to order this priority queue.
106	dholmes	1.11	* If <tt>null</tt> then the order depends on the elements' natural
107			* ordering.
108	dholmes	1.15	* @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
109			* than 1
110	tim	1.2	*/
111	tim	1.16	public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
112	tim	1.2	if (initialCapacity < 1)
113	dholmes	1.15	throw new IllegalArgumentException();
114	tim	1.16	this.queue = new Object[initialCapacity + 1];
115	tim	1.2	this.comparator = comparator;
116	tim	1.1	}
117
118	tim	1.2	/**
119	dholmes	1.11	* Create a <tt>PriorityQueue</tt> containing the elements in the specified
120	tim	1.2	* collection. The priority queue has an initial capacity of 110% of the
121	tim	1.19	* size of the specified collection (bounded by
122			* <tt>Integer.MAX_VALUE-1</tt>); or 1 if the collection is empty.
123	dholmes	1.15	* If the specified collection
124	tim	1.2	* implements the {@link Sorted} interface, the priority queue will be
125			* sorted according to the same comparator, or according to its elements'
126			* natural order if the collection is sorted according to its elements'
127	brian	1.6	* natural order. If the specified collection does not implement
128			* <tt>Sorted</tt>, the priority queue is ordered according to
129	tim	1.2	* its elements' natural order.
130			*
131	dholmes	1.15	* @param c the collection whose elements are to be placed
132	tim	1.2	* into this priority queue.
133			* @throws ClassCastException if elements of the specified collection
134			* cannot be compared to one another according to the priority
135			* queue's ordering.
136	dholmes	1.15	* @throws NullPointerException if <tt>c</tt> or any element within it
137			* is <tt>null</tt>
138	tim	1.2	*/
139	tim	1.16	public PriorityQueue(Collection<? extends E> c) {
140	dholmes	1.15	int sz = c.size();
141	tim	1.2	int initialCapacity = (int)Math.min((sz * 110L) / 100,
142			Integer.MAX_VALUE - 1);
143			if (initialCapacity < 1)
144			initialCapacity = 1;
145	dholmes	1.15
146	tim	1.16	this.queue = new Object[initialCapacity + 1];
147	tim	1.2
148	tim	1.19	// FIXME: if c is larger than Integer.MAX_VALUE we'll
149	dholmes	1.18	// overflow the array
150
151	dholmes	1.15	if (c instanceof Sorted) {
152	tim	1.19	comparator = (Comparator<? super E>)((Sorted)c).comparator();
153	tim	1.2	} else {
154			comparator = null;
155			}
156	dholmes	1.18
157			for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
158			add(i.next());
159	tim	1.1	}
160
161	tim	1.2	// Queue Methods
162
163			/**
164	dholmes	1.11	* Add the specified element to this priority queue.
165	tim	1.2	*
166	dholmes	1.11	* @return <tt>true</tt>
167			* @throws ClassCastException if the specified element cannot be compared
168			* with elements currently in the priority queue according
169			* to the priority queue's ordering.
170	dholmes	1.18	* @throws NullPointerException if the specified element is <tt>null</tt>.
171	tim	1.2	*/
172	dholmes	1.18	public boolean offer(E o) {
173			if (o == null)
174	dholmes	1.11	throw new NullPointerException();
175			modCount++;
176			++size;
177
178			// Grow backing store if necessary
179	dholmes	1.18	// FIXME: watch for overflow
180			// FIXME: what if we're full?
181	dholmes	1.11	while (size >= queue.length) {
182	tim	1.16	Object[] newQueue = new Object[2 * queue.length];
183	dholmes	1.11	System.arraycopy(queue, 0, newQueue, 0, queue.length);
184			queue = newQueue;
185			}
186
187	dholmes	1.18	queue[size] = o;
188	dholmes	1.11	fixUp(size);
189			return true;
190			}
191
192	tim	1.1	public E poll() {
193	tim	1.2	if (size == 0)
194			return null;
195	tim	1.16	return (E) remove(1);
196	tim	1.1	}
197	tim	1.2
198	tim	1.1	public E peek() {
199	tim	1.16	return (E) queue[1];
200	tim	1.1	}
201
202	tim	1.2	// Collection Methods
203
204	dholmes	1.11	// these first two override just to get the throws docs
205
206			/**
207			* @throws NullPointerException if the specified element is <tt>null</tt>.
208	dholmes	1.15	* @throws ClassCastException if the specified element cannot be compared
209			* with elements currently in the priority queue according
210			* to the priority queue's ordering.
211	dholmes	1.11	*/
212	dholmes	1.18	public boolean add(E o) {
213			return super.add(o);
214	dholmes	1.11	}
215
216	tim	1.14	/**
217	dholmes	1.15	* @throws ClassCastException if any element cannot be compared
218			* with elements currently in the priority queue according
219			* to the priority queue's ordering.
220	dholmes	1.18	* @throws NullPointerException if <tt>c</tt> or any element in <tt>c</tt>
221			* is <tt>null</tt>
222	tim	1.14	*/
223			public boolean addAll(Collection<? extends E> c) {
224			return super.addAll(c);
225			}
226	dholmes	1.11
227	dl	1.12	public boolean remove(Object o) {
228	dholmes	1.11	if (o == null)
229	dholmes	1.15	return false;
230	tim	1.2
231			if (comparator == null) {
232			for (int i = 1; i <= size; i++) {
233	tim	1.16	if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
234	tim	1.2	remove(i);
235			return true;
236			}
237			}
238			} else {
239			for (int i = 1; i <= size; i++) {
240	tim	1.16	if (comparator.compare((E)queue[i], (E)o) == 0) {
241	tim	1.2	remove(i);
242			return true;
243			}
244			}
245			}
246	tim	1.1	return false;
247			}
248	tim	1.2
249			public Iterator<E> iterator() {
250	dl	1.7	return new Itr();
251	tim	1.2	}
252
253			private class Itr implements Iterator<E> {
254	dl	1.7	/**
255			* Index (into queue array) of element to be returned by
256	tim	1.2	* subsequent call to next.
257	dl	1.7	*/
258			private int cursor = 1;
259	tim	1.2
260	dl	1.7	/**
261			* Index of element returned by most recent call to next or
262			* previous. Reset to 0 if this element is deleted by a call
263			* to remove.
264			*/
265			private int lastRet = 0;
266
267			/**
268			* The modCount value that the iterator believes that the backing
269			* List should have. If this expectation is violated, the iterator
270			* has detected concurrent modification.
271			*/
272			private int expectedModCount = modCount;
273	tim	1.2
274	dl	1.7	public boolean hasNext() {
275			return cursor <= size;
276			}
277
278			public E next() {
279	tim	1.2	checkForComodification();
280			if (cursor > size)
281	dl	1.7	throw new NoSuchElementException();
282	tim	1.16	E result = (E) queue[cursor];
283	tim	1.2	lastRet = cursor++;
284			return result;
285	dl	1.7	}
286	tim	1.2
287	dl	1.7	public void remove() {
288			if (lastRet == 0)
289			throw new IllegalStateException();
290	tim	1.2	checkForComodification();
291
292			PriorityQueue.this.remove(lastRet);
293			if (lastRet < cursor)
294			cursor--;
295			lastRet = 0;
296			expectedModCount = modCount;
297	dl	1.7	}
298	tim	1.2
299	dl	1.7	final void checkForComodification() {
300			if (modCount != expectedModCount)
301			throw new ConcurrentModificationException();
302			}
303	tim	1.2	}
304
305			/**
306			* Returns the number of elements in this priority queue.
307	tim	1.10	*
308	tim	1.2	* @return the number of elements in this priority queue.
309			*/
310	tim	1.1	public int size() {
311	tim	1.2	return size;
312	tim	1.1	}
313	tim	1.2
314			/**
315			* Remove all elements from the priority queue.
316			*/
317			public void clear() {
318			modCount++;
319
320			// Null out element references to prevent memory leak
321			for (int i=1; i<=size; i++)
322			queue[i] = null;
323
324			size = 0;
325			}
326
327			/**
328			* Removes and returns the ith element from queue. Recall
329			* that queue is one-based, so 1 <= i <= size.
330			*
331			* XXX: Could further special-case i==size, but is it worth it?
332			* XXX: Could special-case i==0, but is it worth it?
333			*/
334			private E remove(int i) {
335			assert i <= size;
336			modCount++;
337
338	tim	1.16	E result = (E) queue[i];
339	tim	1.2	queue[i] = queue[size];
340			queue[size--] = null; // Drop extra ref to prevent memory leak
341			if (i <= size)
342			fixDown(i);
343			return result;
344	tim	1.1	}
345
346	tim	1.2	/**
347			* Establishes the heap invariant (described above) assuming the heap
348			* satisfies the invariant except possibly for the leaf-node indexed by k
349			* (which may have a nextExecutionTime less than its parent's).
350			*
351			* This method functions by "promoting" queue[k] up the hierarchy
352			* (by swapping it with its parent) repeatedly until queue[k]
353			* is greater than or equal to its parent.
354			*/
355			private void fixUp(int k) {
356			if (comparator == null) {
357			while (k > 1) {
358			int j = k >> 1;
359	tim	1.16	if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
360	tim	1.2	break;
361	tim	1.16	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
362	tim	1.2	k = j;
363			}
364			} else {
365			while (k > 1) {
366			int j = k >> 1;
367	tim	1.16	if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
368	tim	1.2	break;
369	tim	1.16	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
370	tim	1.2	k = j;
371			}
372			}
373			}
374
375			/**
376			* Establishes the heap invariant (described above) in the subtree
377			* rooted at k, which is assumed to satisfy the heap invariant except
378			* possibly for node k itself (which may be greater than its children).
379			*
380			* This method functions by "demoting" queue[k] down the hierarchy
381			* (by swapping it with its smaller child) repeatedly until queue[k]
382			* is less than or equal to its children.
383			*/
384			private void fixDown(int k) {
385			int j;
386			if (comparator == null) {
387			while ((j = k << 1) <= size) {
388	tim	1.16	if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
389	tim	1.2	j++; // j indexes smallest kid
390	tim	1.16	if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
391	tim	1.2	break;
392	tim	1.16	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
393	tim	1.2	k = j;
394			}
395			} else {
396			while ((j = k << 1) <= size) {
397	tim	1.16	if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
398	tim	1.2	j++; // j indexes smallest kid
399	tim	1.16	if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
400	tim	1.2	break;
401	tim	1.16	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
402	tim	1.2	k = j;
403			}
404			}
405			}
406
407	tim	1.16	public Comparator<? super E> comparator() {
408	tim	1.2	return comparator;
409			}
410	dl	1.5
411			/**
412			* Save the state of the instance to a stream (that
413			* is, serialize it).
414			*
415			* @serialData The length of the array backing the instance is
416			* emitted (int), followed by all of its elements (each an
417			* <tt>Object</tt>) in the proper order.
418	dl	1.7	* @param s the stream
419	dl	1.5	*/
420			private synchronized void writeObject(java.io.ObjectOutputStream s)
421			throws java.io.IOException{
422	dl	1.7	// Write out element count, and any hidden stuff
423			s.defaultWriteObject();
424	dl	1.5
425			// Write out array length
426			s.writeInt(queue.length);
427
428	dl	1.7	// Write out all elements in the proper order.
429			for (int i=0; i<size; i++)
430	dl	1.5	s.writeObject(queue[i]);
431			}
432
433			/**
434			* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
435			* deserialize it).
436	dl	1.7	* @param s the stream
437	dl	1.5	*/
438			private synchronized void readObject(java.io.ObjectInputStream s)
439			throws java.io.IOException, ClassNotFoundException {
440	dl	1.7	// Read in size, and any hidden stuff
441			s.defaultReadObject();
442	dl	1.5
443			// Read in array length and allocate array
444			int arrayLength = s.readInt();
445	tim	1.16	queue = new Object[arrayLength];
446	dl	1.5
447	dl	1.7	// Read in all elements in the proper order.
448			for (int i=0; i<size; i++)
449	tim	1.16	queue[i] = s.readObject();
450	dl	1.5	}
451
452	tim	1.1	}
453	dholmes	1.11