[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.37 - (view) (download)

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8