java/util/PriorityQueue.java

 package java.util;

/**
 * An unbounded 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 TreeSet} and {@link TreeMap}: elements are ordered
 * either according to their <i>natural order</i> (see {@link Comparable}), or
 * according to a {@link Comparator}, depending on which constructor is used.
 * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the
 * minimal element with respect to the specified ordering.  If multiple
 * elements are tied for least value, no guarantees are made as to
 * which of these elements is returned.
 *
 * <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.  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 Queue<E> {
    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 E[] 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<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 new priority queue 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);
    }

    /**
     * Create a new priority queue 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 new priority queue with the specified initial capacity (11)
     * 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.
     */
    public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
        if (initialCapacity < 1)
            initialCapacity = 1;
        queue = new E[initialCapacity + 1];
        this.comparator = comparator;
    }

    /**
     * Create a new priority queue containing the elements in the specified
     * collection.  The priority queue has an initial capacity of 110% of the
     * size of the specified collection. 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 initialElements 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 the specified collection or an
     *         element of the specified collection is <tt>null</tt>.
     */
    public PriorityQueue(Collection<E> initialElements) {
        int sz = initialElements.size();
        int initialCapacity = (int)Math.min((sz * 110L) / 100,
                                            Integer.MAX_VALUE - 1);
        if (initialCapacity < 1)
            initialCapacity = 1;
        queue = new E[initialCapacity + 1];

        /* Commented out to compile with generics compiler

        if (initialElements instanceof Sorted) {
            comparator = ((Sorted)initialElements).comparator();
            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
                queue[++size] = i.next();
        } else {
        */
        {
            comparator = null;
            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
                add(i.next());
        }
    }

    // Queue Methods

    /**
     * Remove and return the minimal element from this priority queue
     * if it contains one or more elements, otherwise return
     * <tt>null</tt>.  The term <i>minimal</i> is defined according to
     * this priority queue's order.
     *
     * @return the minimal element from this priority queue if it contains
     *         one or more elements, otherwise <tt>null</tt>.
     */
    public E poll() {
        if (size == 0)
            return null;
        return remove(1);
    }

    /**
     * Return, but do not remove, the minimal element from the
     * priority queue, or return <tt>null</tt> if the queue is empty.
     * The term <i>minimal</i> is defined according to this priority
     * queue's order.  This method returns the same object reference
     * that would be returned by by the <tt>poll</tt> method.  The two
     * methods differ in that this method does not remove the element
     * from the priority queue.
     *
     * @return the minimal element from this priority queue if it contains
     *         one or more elements, otherwise <tt>null</tt>.
     */
    public E peek() {
        return queue[1];
    }

    // Collection Methods

    /**
     * Removes a single instance of the specified element from this priority
     * queue, if it is present.  Returns true if this collection contained the
     * specified element (or equivalently, if this collection changed as a
     * result of the call).
     *
     * @param element the element to be removed from this collection,
     * if present.
     * @return <tt>true</tt> if this collection changed as a result of the
     *         call
     * @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.
     */
    public boolean remove(Object element) {
        if (element == null)
            throw new NullPointerException();

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

    /**
     * Returns an iterator over the elements in this priority queue.  The
     * elements of the priority queue will be returned by this iterator in the
     * order specified by the queue, which is to say the order they would be
     * returned by repeated calls to <tt>poll</tt>.
     * 
     * @return an <tt>Iterator</tt> over the elements in this priority queue.
     */
    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 = 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;
    }

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

        // Grow backing store if necessary
        if (++size == queue.length) {
            E[] newQueue = new E[2 * queue.length];
            System.arraycopy(queue, 0, newQueue, 0, size);
            queue = newQueue;
        }

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

    /**
     * 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 = 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)queue[j]).compareTo(queue[k]) <= 0)
                    break;
                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        } else {
            while (k > 1) {
                int j = k >> 1;
                if (comparator.compare(queue[j], queue[k]) <= 0)
                    break;
                E 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)queue[j]).compareTo(queue[j+1]) > 0)
                    j++; // j indexes smallest kid
                if (((Comparable)queue[k]).compareTo(queue[j]) <= 0)
                    break;
                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        } else {
            while ((j = k << 1) <= size) {
                if (j < size && comparator.compare(queue[j], queue[j+1]) > 0)
                    j++; // j indexes smallest kid
                if (comparator.compare(queue[k], queue[j]) <= 0)
                    break;
                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                k = j;
            }
        }
    }

    /**
     * Returns the comparator associated with this priority queue, or
     * <tt>null</tt> if it uses its elements' natural ordering.
     *
     * @return the comparator associated with this priority queue, or
     *         <tt>null</tt> if it uses its elements' natural ordering.
     */
    Comparator 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 E[arrayLength];

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

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