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

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8