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

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8