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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8