[cvs] / jsr166 / src / main / java / util / PriorityQueue.java Repository:
ViewVC logotype

Annotation of /jsr166/src/main/java/util/PriorityQueue.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.52 - (view) (download)

1 : dl 1.38 /*
2 : dl 1.52 * @(#)PriorityQueue.java 1.8 05/08/27
3 : dl 1.38 *
4 : dl 1.52 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5 : dl 1.38 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 :     */
7 :    
8 :     package java.util;
9 : dl 1.52 import java.util.*; // for javadoc (till 6280605 is fixed)
10 : tim 1.1
11 :     /**
12 : dl 1.41 * An unbounded priority {@linkplain Queue queue} based on a priority
13 : dl 1.52 * heap. The elements of the priority queue are ordered according to
14 :     * their {@linkplain Comparable natural ordering}, or by a {@link
15 :     * Comparator} provided at queue construction time, depending on which
16 :     * constructor is used. A priority queue does not permit
17 :     * <tt>null</tt> elements. A priority queue relying on natural
18 :     * ordering also does not permit insertion of non-comparable objects
19 :     * (doing so may result in <tt>ClassCastException</tt>).
20 : dl 1.40 *
21 : dl 1.41 * <p>The <em>head</em> of this queue is the <em>least</em> element
22 :     * with respect to the specified ordering. If multiple elements are
23 :     * tied for least value, the head is one of those elements -- ties are
24 : dl 1.42 * broken arbitrarily. The queue retrieval operations <tt>poll</tt>,
25 :     * <tt>remove</tt>, <tt>peek</tt>, and <tt>element</tt> access the
26 :     * element at the head of the queue.
27 : tim 1.14 *
28 : dl 1.41 * <p>A priority queue is unbounded, but has an internal
29 :     * <i>capacity</i> governing the size of an array used to store the
30 : dl 1.40 * elements on the queue. It is always at least as large as the queue
31 :     * size. As elements are added to a priority queue, its capacity
32 :     * grows automatically. The details of the growth policy are not
33 :     * specified.
34 : tim 1.2 *
35 : dl 1.50 * <p>This class and its iterator implement all of the
36 :     * <em>optional</em> methods of the {@link Collection} and {@link
37 : dl 1.52 * Iterator} interfaces. The Iterator provided in method {@link
38 :     * #iterator()} is <em>not</em> guaranteed to traverse the elements of
39 :     * the priority queue in any particular order. If you need ordered
40 :     * traversal, consider using <tt>Arrays.sort(pq.toArray())</tt>.
41 : dl 1.29 *
42 :     * <p> <strong>Note that this implementation is not synchronized.</strong>
43 :     * Multiple threads should not access a <tt>PriorityQueue</tt>
44 :     * instance concurrently if any of the threads modifies the list
45 :     * structurally. Instead, use the thread-safe {@link
46 : dholmes 1.34 * java.util.concurrent.PriorityBlockingQueue} class.
47 : dl 1.29 *
48 : dholmes 1.11 * <p>Implementation note: this implementation provides O(log(n)) time
49 :     * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
50 :     * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
51 :     * <tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
52 :     * constant time for the retrieval methods (<tt>peek</tt>,
53 :     * <tt>element</tt>, and <tt>size</tt>).
54 : tim 1.2 *
55 :     * <p>This class is a member of the
56 :     * <a href="{@docRoot}/../guide/collections/index.html">
57 :     * Java Collections Framework</a>.
58 : dl 1.7 * @since 1.5
59 : dl 1.52 * @version 1.8, 08/27/05
60 : dl 1.7 * @author Josh Bloch
61 : dl 1.45 * @param <E> the type of elements held in this collection
62 : tim 1.2 */
63 :     public class PriorityQueue<E> extends AbstractQueue<E>
64 : dl 1.47 implements java.io.Serializable {
65 : dholmes 1.11
66 : dl 1.31 private static final long serialVersionUID = -7720805057305804111L;
67 : dl 1.30
68 : tim 1.2 private static final int DEFAULT_INITIAL_CAPACITY = 11;
69 : tim 1.1
70 : tim 1.2 /**
71 :     * Priority queue represented as a balanced binary heap: the two children
72 :     * of queue[n] are queue[2*n] and queue[2*n + 1]. The priority queue is
73 :     * ordered by comparator, or by the elements' natural ordering, if
74 : brian 1.6 * comparator is null: For each node n in the heap and each descendant d
75 :     * of n, n <= d.
76 : tim 1.2 *
77 : brian 1.6 * The element with the lowest value is in queue[1], assuming the queue is
78 :     * nonempty. (A one-based array is used in preference to the traditional
79 :     * zero-based array to simplify parent and child calculations.)
80 : tim 1.2 *
81 :     * queue.length must be >= 2, even if size == 0.
82 :     */
83 : tim 1.16 private transient Object[] queue;
84 : tim 1.1
85 : tim 1.2 /**
86 :     * The number of elements in the priority queue.
87 :     */
88 :     private int size = 0;
89 : tim 1.1
90 : tim 1.2 /**
91 :     * The comparator, or null if priority queue uses elements'
92 :     * natural ordering.
93 :     */
94 : tim 1.16 private final Comparator<? super E> comparator;
95 : tim 1.2
96 :     /**
97 :     * The number of times this priority queue has been
98 :     * <i>structurally modified</i>. See AbstractList for gory details.
99 :     */
100 : dl 1.5 private transient int modCount = 0;
101 : tim 1.2
102 :     /**
103 : dl 1.52 * Creates a <tt>PriorityQueue</tt> with the default initial
104 :     * capacity (11) that orders its elements according to their
105 :     * {@linkplain Comparable natural ordering}.
106 : tim 1.2 */
107 :     public PriorityQueue() {
108 : dholmes 1.11 this(DEFAULT_INITIAL_CAPACITY, null);
109 : tim 1.1 }
110 : tim 1.2
111 :     /**
112 : dl 1.52 * Creates a <tt>PriorityQueue</tt> with the specified initial
113 :     * capacity that orders its elements according to their
114 :     * {@linkplain Comparable natural ordering}.
115 : tim 1.2 *
116 : dl 1.52 * @param initialCapacity the initial capacity for this priority queue
117 : dholmes 1.23 * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
118 :     * than 1
119 : tim 1.2 */
120 :     public PriorityQueue(int initialCapacity) {
121 :     this(initialCapacity, null);
122 : tim 1.1 }
123 : tim 1.2
124 :     /**
125 : dholmes 1.21 * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
126 : tim 1.2 * that orders its elements according to the specified comparator.
127 :     *
128 : dl 1.52 * @param initialCapacity the initial capacity for this priority queue
129 :     * @param comparator the comparator that will be used to order
130 :     * this priority queue. If <tt>null</tt>, the <i>natural
131 :     * ordering</i> of the elements will be used.
132 :     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is
133 :     * less than 1
134 : tim 1.2 */
135 : dl 1.52 public PriorityQueue(int initialCapacity,
136 : dholmes 1.23 Comparator<? super E> comparator) {
137 : tim 1.2 if (initialCapacity < 1)
138 : dholmes 1.15 throw new IllegalArgumentException();
139 : tim 1.16 this.queue = new Object[initialCapacity + 1];
140 : tim 1.2 this.comparator = comparator;
141 : tim 1.1 }
142 :    
143 : tim 1.2 /**
144 : dl 1.22 * Common code to initialize underlying queue array across
145 :     * constructors below.
146 :     */
147 :     private void initializeArray(Collection<? extends E> c) {
148 :     int sz = c.size();
149 :     int initialCapacity = (int)Math.min((sz * 110L) / 100,
150 :     Integer.MAX_VALUE - 1);
151 :     if (initialCapacity < 1)
152 :     initialCapacity = 1;
153 :    
154 :     this.queue = new Object[initialCapacity + 1];
155 :     }
156 :    
157 :     /**
158 : dl 1.52 * Initially fill elements of the queue array under the
159 : dl 1.22 * knowledge that it is sorted or is another PQ, in which
160 : dl 1.36 * case we can just place the elements in the order presented.
161 : dl 1.22 */
162 :     private void fillFromSorted(Collection<? extends E> c) {
163 : dl 1.52 for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) {
164 :     int k = ++size;
165 :     if (k >= queue.length)
166 :     grow(k);
167 :     queue[k] = i.next();
168 :     }
169 : dl 1.22 }
170 :    
171 :     /**
172 : dl 1.36 * Initially fill elements of the queue array that is not to our knowledge
173 :     * sorted, so we must rearrange the elements to guarantee the heap
174 :     * invariant.
175 : dl 1.22 */
176 :     private void fillFromUnsorted(Collection<? extends E> c) {
177 : dl 1.52 for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) {
178 :     int k = ++size;
179 :     if (k >= queue.length)
180 :     grow(k);
181 :     queue[k] = i.next();
182 :     }
183 : dl 1.36 heapify();
184 : dl 1.22 }
185 :    
186 :     /**
187 :     * Creates a <tt>PriorityQueue</tt> containing the elements in the
188 :     * specified collection. The priority queue has an initial
189 :     * capacity of 110% of the size of the specified collection or 1
190 :     * if the collection is empty. If the specified collection is an
191 : tim 1.25 * instance of a {@link java.util.SortedSet} or is another
192 : dl 1.52 * <tt>PriorityQueue</tt>, the priority queue will be ordered
193 :     * according to the same ordering. Otherwise, this priority queue
194 :     * will be ordered according to the natural ordering of its elements.
195 : tim 1.2 *
196 : dl 1.52 * @param c the collection whose elements are to be placed
197 :     * into this priority queue
198 : tim 1.2 * @throws ClassCastException if elements of the specified collection
199 :     * cannot be compared to one another according to the priority
200 : dl 1.52 * queue's ordering
201 :     * @throws NullPointerException if the specified collection or any
202 :     * of its elements are null
203 : tim 1.2 */
204 : tim 1.16 public PriorityQueue(Collection<? extends E> c) {
205 : dl 1.22 initializeArray(c);
206 : dl 1.27 if (c instanceof SortedSet) {
207 : dl 1.46 SortedSet<? extends E> s = (SortedSet<? extends E>)c;
208 : dl 1.22 comparator = (Comparator<? super E>)s.comparator();
209 :     fillFromSorted(s);
210 : dl 1.27 } else if (c instanceof PriorityQueue) {
211 : dl 1.22 PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c;
212 :     comparator = (Comparator<? super E>)s.comparator();
213 :     fillFromSorted(s);
214 : tim 1.26 } else {
215 : tim 1.2 comparator = null;
216 : dl 1.22 fillFromUnsorted(c);
217 : tim 1.2 }
218 : dl 1.22 }
219 :    
220 :     /**
221 :     * Creates a <tt>PriorityQueue</tt> containing the elements in the
222 : dl 1.52 * specified priority queue. The priority queue has an initial
223 :     * capacity of 110% of the size of the specified priority queue or
224 :     * 1 if the priority queue is empty. This priority queue will be
225 :     * ordered according to the same ordering as the given priority
226 :     * queue.
227 :     *
228 :     * @param c the priority queue whose elements are to be placed
229 :     * into this priority queue
230 :     * @throws ClassCastException if elements of <tt>c</tt> cannot be
231 :     * compared to one another according to <tt>c</tt>'s
232 :     * ordering
233 :     * @throws NullPointerException if the specified priority queue or any
234 :     * of its elements are null
235 : dl 1.22 */
236 :     public PriorityQueue(PriorityQueue<? extends E> c) {
237 :     initializeArray(c);
238 :     comparator = (Comparator<? super E>)c.comparator();
239 :     fillFromSorted(c);
240 :     }
241 : dholmes 1.18
242 : dl 1.22 /**
243 :     * Creates a <tt>PriorityQueue</tt> containing the elements in the
244 : dl 1.52 * specified sorted set. The priority queue has an initial
245 :     * capacity of 110% of the size of the specified sorted set or 1
246 :     * if the sorted set is empty. This priority queue will be ordered
247 :     * according to the same ordering as the given sorted set.
248 :     *
249 :     * @param c the sorted set whose elements are to be placed
250 :     * into this priority queue.
251 :     * @throws ClassCastException if elements of the specified sorted
252 :     * set cannot be compared to one another according to the
253 :     * sorted set's ordering
254 :     * @throws NullPointerException if the specified sorted set or any
255 :     * of its elements are null
256 : dl 1.22 */
257 :     public PriorityQueue(SortedSet<? extends E> c) {
258 :     initializeArray(c);
259 :     comparator = (Comparator<? super E>)c.comparator();
260 :     fillFromSorted(c);
261 : tim 1.1 }
262 :    
263 : dl 1.22 /**
264 : dl 1.52 * Resize array, if necessary, to be able to hold given index.
265 : dl 1.22 */
266 :     private void grow(int index) {
267 :     int newlen = queue.length;
268 :     if (index < newlen) // don't need to grow
269 :     return;
270 :     if (index == Integer.MAX_VALUE)
271 :     throw new OutOfMemoryError();
272 :     while (newlen <= index) {
273 :     if (newlen >= Integer.MAX_VALUE / 2) // avoid overflow
274 :     newlen = Integer.MAX_VALUE;
275 :     else
276 :     newlen <<= 2;
277 :     }
278 : dl 1.52 queue = Arrays.copyOf(queue, newlen);
279 : dl 1.22 }
280 : dl 1.36
281 : tim 1.2 /**
282 : dl 1.42 * Inserts the specified element into this priority queue.
283 : tim 1.2 *
284 : dl 1.52 * @return <tt>true</tt> (as specified by {@link Collection#add})
285 :     * @throws ClassCastException if the specified element cannot be
286 :     * compared with elements currently in this priority queue
287 :     * according to the priority queue's ordering
288 :     * @throws NullPointerException if the specified element is null
289 : tim 1.2 */
290 : dl 1.52 public boolean add(E e) {
291 :     return offer(e);
292 :     }
293 :    
294 :     /**
295 :     * Inserts the specified element into this priority queue.
296 :     *
297 :     * @return <tt>true</tt> (as specified by {@link Queue#offer})
298 :     * @throws ClassCastException if the specified element cannot be
299 :     * compared with elements currently in this priority queue
300 :     * according to the priority queue's ordering
301 :     * @throws NullPointerException if the specified element is null
302 :     */
303 :     public boolean offer(E e) {
304 :     if (e == null)
305 : dholmes 1.11 throw new NullPointerException();
306 :     modCount++;
307 :     ++size;
308 :    
309 :     // Grow backing store if necessary
310 : dl 1.52 if (size >= queue.length)
311 : dl 1.22 grow(size);
312 : dholmes 1.11
313 : dl 1.52 queue[size] = e;
314 : dholmes 1.11 fixUp(size);
315 :     return true;
316 :     }
317 :    
318 : dl 1.40 public E peek() {
319 : tim 1.2 if (size == 0)
320 :     return null;
321 : tim 1.16 return (E) queue[1];
322 : tim 1.1 }
323 :    
324 : dl 1.52 private int indexOf(Object o) {
325 :     if (o == null)
326 :     return -1;
327 :     for (int i = 1; i <= size; i++)
328 :     if (o.equals(queue[i]))
329 :     return i;
330 :     return -1;
331 :     }
332 :    
333 :     /**
334 :     * Removes a single instance of the specified element from this queue,
335 :     * if it is present. More formally, removes an element <tt>e</tt> such
336 :     * that <tt>o.equals(e)</tt>, if this queue contains one or more such
337 :     * elements. Returns true if this queue contained the specified element
338 :     * (or equivalently, if this queue changed as a result of the call).
339 :     *
340 :     * @param o element to be removed from this queue, if present
341 :     * @return <tt>true</tt> if this queue changed as a result of the call
342 :     */
343 :     public boolean remove(Object o) {
344 :     int i = indexOf(o);
345 :     if (i == -1)
346 :     return false;
347 :     else {
348 :     removeAt(i);
349 :     return true;
350 :     }
351 :     }
352 : dholmes 1.11
353 :     /**
354 : dl 1.52 * Returns <tt>true</tt> if this queue contains the specified element.
355 :     * More formally, returns <tt>true</tt> if and only if this queue contains
356 :     * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
357 : dholmes 1.23 *
358 : dl 1.52 * @param o object to be checked for containment in this queue
359 :     * @return <tt>true</tt> if this queue contains the specified element
360 : dholmes 1.11 */
361 : dl 1.52 public boolean contains(Object o) {
362 :     return indexOf(o) != -1;
363 : tim 1.14 }
364 : dholmes 1.11
365 : dl 1.49 /**
366 : dl 1.52 * Returns an array containing all of the elements in this queue,
367 :     * The elements are in no particular order.
368 :     *
369 :     * <p>The returned array will be "safe" in that no references to it are
370 :     * maintained by this list. (In other words, this method must allocate
371 :     * a new array). The caller is thus free to modify the returned array.
372 :     *
373 :     * @return an array containing all of the elements in this queue.
374 : dl 1.49 */
375 : dl 1.52 public Object[] toArray() {
376 :     return Arrays.copyOfRange(queue, 1, size+1);
377 :     }
378 : tim 1.2
379 : dl 1.52 /**
380 :     * Returns an array containing all of the elements in this queue.
381 :     * The elements are in no particular order. The runtime type of
382 :     * the returned array is that of the specified array. If the queue
383 :     * fits in the specified array, it is returned therein.
384 :     * Otherwise, a new array is allocated with the runtime type of
385 :     * the specified array and the size of this queue.
386 :     *
387 :     * <p>If the queue fits in the specified array with room to spare
388 :     * (i.e., the array has more elements than the queue), the element in
389 :     * the array immediately following the end of the collection is set to
390 :     * <tt>null</tt>. (This is useful in determining the length of the
391 :     * queue <i>only</i> if the caller knows that the queue does not contain
392 :     * any null elements.)
393 :     *
394 :     * @param a the array into which the elements of the queue are to
395 :     * be stored, if it is big enough; otherwise, a new array of the
396 :     * same runtime type is allocated for this purpose.
397 :     * @return an array containing the elements of the queue
398 :     * @throws ArrayStoreException if the runtime type of the specified array
399 :     * is not a supertype of the runtime type of every element in
400 :     * this queue
401 :     * @throws NullPointerException if the specified array is null
402 :     */
403 :     public <T> T[] toArray(T[] a) {
404 :     if (a.length < size)
405 :     // Make a new array of a's runtime type, but my contents:
406 :     return (T[]) Arrays.copyOfRange(queue, 1, size+1, a.getClass());
407 :     System.arraycopy(queue, 1, a, 0, size);
408 :     if (a.length > size)
409 :     a[size] = null;
410 :     return a;
411 : tim 1.1 }
412 : tim 1.2
413 : dholmes 1.23 /**
414 :     * Returns an iterator over the elements in this queue. The iterator
415 :     * does not return the elements in any particular order.
416 :     *
417 : dl 1.52 * @return an iterator over the elements in this queue
418 : dholmes 1.23 */
419 : tim 1.2 public Iterator<E> iterator() {
420 : dl 1.7 return new Itr();
421 : tim 1.2 }
422 :    
423 :     private class Itr implements Iterator<E> {
424 : dl 1.35
425 : dl 1.7 /**
426 :     * Index (into queue array) of element to be returned by
427 : tim 1.2 * subsequent call to next.
428 : dl 1.7 */
429 :     private int cursor = 1;
430 : tim 1.2
431 : dl 1.7 /**
432 : dl 1.36 * Index of element returned by most recent call to next,
433 :     * unless that element came from the forgetMeNot list.
434 :     * Reset to 0 if element is deleted by a call to remove.
435 : dl 1.7 */
436 :     private int lastRet = 0;
437 :    
438 :     /**
439 :     * The modCount value that the iterator believes that the backing
440 :     * List should have. If this expectation is violated, the iterator
441 :     * has detected concurrent modification.
442 :     */
443 :     private int expectedModCount = modCount;
444 : tim 1.2
445 : dl 1.36 /**
446 :     * A list of elements that were moved from the unvisited portion of
447 :     * the heap into the visited portion as a result of "unlucky" element
448 :     * removals during the iteration. (Unlucky element removals are those
449 :     * that require a fixup instead of a fixdown.) We must visit all of
450 :     * the elements in this list to complete the iteration. We do this
451 :     * after we've completed the "normal" iteration.
452 :     *
453 :     * We expect that most iterations, even those involving removals,
454 :     * will not use need to store elements in this field.
455 :     */
456 :     private ArrayList<E> forgetMeNot = null;
457 :    
458 :     /**
459 :     * Element returned by the most recent call to next iff that
460 :     * element was drawn from the forgetMeNot list.
461 :     */
462 :     private Object lastRetElt = null;
463 : dl 1.35
464 : dl 1.7 public boolean hasNext() {
465 : dl 1.36 return cursor <= size || forgetMeNot != null;
466 : dl 1.7 }
467 :    
468 :     public E next() {
469 : tim 1.2 checkForComodification();
470 : dl 1.36 E result;
471 :     if (cursor <= size) {
472 :     result = (E) queue[cursor];
473 :     lastRet = cursor++;
474 :     }
475 :     else if (forgetMeNot == null)
476 : dl 1.7 throw new NoSuchElementException();
477 : dl 1.36 else {
478 :     int remaining = forgetMeNot.size();
479 :     result = forgetMeNot.remove(remaining - 1);
480 : dl 1.52 if (remaining == 1)
481 : dl 1.36 forgetMeNot = null;
482 :     lastRet = 0;
483 :     lastRetElt = result;
484 :     }
485 : tim 1.2 return result;
486 : dl 1.7 }
487 : tim 1.2
488 : dl 1.7 public void remove() {
489 : tim 1.2 checkForComodification();
490 :    
491 : dl 1.36 if (lastRet != 0) {
492 :     E moved = PriorityQueue.this.removeAt(lastRet);
493 :     lastRet = 0;
494 :     if (moved == null) {
495 :     cursor--;
496 :     } else {
497 :     if (forgetMeNot == null)
498 : dl 1.37 forgetMeNot = new ArrayList<E>();
499 : dl 1.36 forgetMeNot.add(moved);
500 :     }
501 :     } else if (lastRetElt != null) {
502 :     PriorityQueue.this.remove(lastRetElt);
503 :     lastRetElt = null;
504 :     } else {
505 :     throw new IllegalStateException();
506 : dl 1.35 }
507 :    
508 : tim 1.2 expectedModCount = modCount;
509 : dl 1.7 }
510 : tim 1.2
511 : dl 1.7 final void checkForComodification() {
512 :     if (modCount != expectedModCount)
513 :     throw new ConcurrentModificationException();
514 :     }
515 : tim 1.2 }
516 :    
517 : tim 1.1 public int size() {
518 : tim 1.2 return size;
519 : tim 1.1 }
520 : tim 1.2
521 :     /**
522 : dl 1.52 * Removes all of the elements from this priority queue.
523 : dl 1.49 * The queue will be empty after this call returns.
524 : tim 1.2 */
525 :     public void clear() {
526 :     modCount++;
527 :    
528 :     // Null out element references to prevent memory leak
529 :     for (int i=1; i<=size; i++)
530 :     queue[i] = null;
531 :    
532 :     size = 0;
533 :     }
534 :    
535 : dl 1.40 public E poll() {
536 : dl 1.36 if (size == 0)
537 : dl 1.40 return null;
538 : dl 1.36 modCount++;
539 :    
540 :     E result = (E) queue[1];
541 :     queue[1] = queue[size];
542 :     queue[size--] = null; // Drop extra ref to prevent memory leak
543 :     if (size > 1)
544 :     fixDown(1);
545 :    
546 :     return result;
547 :     }
548 :    
549 :     /**
550 :     * Removes and returns the ith element from queue. (Recall that queue
551 :     * is one-based, so 1 <= i <= size.)
552 : tim 1.2 *
553 : dl 1.36 * Normally this method leaves the elements at positions from 1 up to i-1,
554 :     * inclusive, untouched. Under these circumstances, it returns null.
555 :     * Occasionally, in order to maintain the heap invariant, it must move
556 :     * the last element of the list to some index in the range [2, i-1],
557 :     * and move the element previously at position (i/2) to position i.
558 :     * Under these circumstances, this method returns the element that was
559 :     * previously at the end of the list and is now at some position between
560 :     * 2 and i-1 inclusive.
561 : tim 1.2 */
562 : dl 1.52 private E removeAt(int i) {
563 : dl 1.36 assert i > 0 && i <= size;
564 : tim 1.2 modCount++;
565 :    
566 : dl 1.36 E moved = (E) queue[size];
567 :     queue[i] = moved;
568 : tim 1.2 queue[size--] = null; // Drop extra ref to prevent memory leak
569 : dl 1.35 if (i <= size) {
570 : tim 1.2 fixDown(i);
571 : dl 1.36 if (queue[i] == moved) {
572 :     fixUp(i);
573 :     if (queue[i] != moved)
574 :     return moved;
575 :     }
576 : dl 1.35 }
577 : dl 1.36 return null;
578 : tim 1.1 }
579 :    
580 : tim 1.2 /**
581 :     * Establishes the heap invariant (described above) assuming the heap
582 :     * satisfies the invariant except possibly for the leaf-node indexed by k
583 :     * (which may have a nextExecutionTime less than its parent's).
584 :     *
585 :     * This method functions by "promoting" queue[k] up the hierarchy
586 :     * (by swapping it with its parent) repeatedly until queue[k]
587 :     * is greater than or equal to its parent.
588 :     */
589 :     private void fixUp(int k) {
590 :     if (comparator == null) {
591 :     while (k > 1) {
592 :     int j = k >> 1;
593 : dl 1.52 if (((Comparable<? super E>)queue[j]).compareTo((E)queue[k]) <= 0)
594 : tim 1.2 break;
595 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
596 : tim 1.2 k = j;
597 :     }
598 :     } else {
599 :     while (k > 1) {
600 : dl 1.35 int j = k >>> 1;
601 : tim 1.16 if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
602 : tim 1.2 break;
603 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
604 : tim 1.2 k = j;
605 :     }
606 :     }
607 :     }
608 :    
609 :     /**
610 :     * Establishes the heap invariant (described above) in the subtree
611 :     * rooted at k, which is assumed to satisfy the heap invariant except
612 :     * possibly for node k itself (which may be greater than its children).
613 :     *
614 :     * This method functions by "demoting" queue[k] down the hierarchy
615 :     * (by swapping it with its smaller child) repeatedly until queue[k]
616 :     * is less than or equal to its children.
617 :     */
618 :     private void fixDown(int k) {
619 :     int j;
620 :     if (comparator == null) {
621 : dl 1.33 while ((j = k << 1) <= size && (j > 0)) {
622 : dl 1.52 if (j<size &&
623 :     ((Comparable<? super E>)queue[j]).compareTo((E)queue[j+1]) > 0)
624 : tim 1.2 j++; // j indexes smallest kid
625 : dl 1.35
626 : dl 1.52 if (((Comparable<? super E>)queue[k]).compareTo((E)queue[j]) <= 0)
627 : tim 1.2 break;
628 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
629 : tim 1.2 k = j;
630 :     }
631 :     } else {
632 : dl 1.33 while ((j = k << 1) <= size && (j > 0)) {
633 : dl 1.52 if (j<size &&
634 : dl 1.35 comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
635 : tim 1.2 j++; // j indexes smallest kid
636 : tim 1.16 if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
637 : tim 1.2 break;
638 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
639 : tim 1.2 k = j;
640 :     }
641 :     }
642 : dl 1.36 }
643 : dl 1.35
644 : dl 1.36 /**
645 :     * Establishes the heap invariant (described above) in the entire tree,
646 :     * assuming nothing about the order of the elements prior to the call.
647 :     */
648 :     private void heapify() {
649 :     for (int i = size/2; i >= 1; i--)
650 :     fixDown(i);
651 : tim 1.2 }
652 :    
653 : dholmes 1.23 /**
654 : dl 1.52 * Returns the comparator used to order the elements in this
655 :     * queue, or <tt>null</tt> if this queue is sorted according to
656 :     * the {@linkplain Comparable natural ordering} of its elements.
657 :     *
658 :     * @return the comparator used to order this queue, or
659 :     * <tt>null</tt> if this queue is sorted according to the
660 :     * natural ordering of its elements.
661 : dholmes 1.23 */
662 : tim 1.16 public Comparator<? super E> comparator() {
663 : tim 1.2 return comparator;
664 :     }
665 : dl 1.5
666 :     /**
667 :     * Save the state of the instance to a stream (that
668 :     * is, serialize it).
669 :     *
670 :     * @serialData The length of the array backing the instance is
671 :     * emitted (int), followed by all of its elements (each an
672 :     * <tt>Object</tt>) in the proper order.
673 : dl 1.7 * @param s the stream
674 : dl 1.5 */
675 : dl 1.22 private void writeObject(java.io.ObjectOutputStream s)
676 : dl 1.5 throws java.io.IOException{
677 : dl 1.7 // Write out element count, and any hidden stuff
678 :     s.defaultWriteObject();
679 : dl 1.5
680 :     // Write out array length
681 :     s.writeInt(queue.length);
682 :    
683 : dl 1.7 // Write out all elements in the proper order.
684 : dl 1.39 for (int i=1; i<=size; i++)
685 : dl 1.5 s.writeObject(queue[i]);
686 :     }
687 :    
688 :     /**
689 : dl 1.52 * Reconstitute the <tt>PriorityQueue</tt> instance from a stream
690 :     * (that is, deserialize it).
691 : dl 1.7 * @param s the stream
692 : dl 1.5 */
693 : dl 1.22 private void readObject(java.io.ObjectInputStream s)
694 : dl 1.5 throws java.io.IOException, ClassNotFoundException {
695 : dl 1.7 // Read in size, and any hidden stuff
696 :     s.defaultReadObject();
697 : dl 1.5
698 :     // Read in array length and allocate array
699 :     int arrayLength = s.readInt();
700 : tim 1.16 queue = new Object[arrayLength];
701 : dl 1.5
702 : dl 1.7 // Read in all elements in the proper order.
703 : dl 1.39 for (int i=1; i<=size; i++)
704 : dl 1.37 queue[i] = (E) s.readObject();
705 : dl 1.5 }
706 :    
707 : tim 1.1 }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8