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

1 : tim 1.2 package java.util;
2 : tim 1.1
3 :     /**
4 : dholmes 1.20 * An unbounded priority queue based on a priority heap. This queue orders
5 : brian 1.6 * elements according to an order specified at construction time, which is
6 : tim 1.19 * specified in the same manner as {@link java.util.TreeSet} and
7 : dholmes 1.18 * {@link java.util.TreeMap}: elements are ordered
8 : tim 1.2 * either according to their <i>natural order</i> (see {@link Comparable}), or
9 : tim 1.19 * according to a {@link java.util.Comparator}, depending on which
10 : dholmes 1.18 * constructor is used.
11 : tim 1.19 * <p>The <em>head</em> of this queue is the <em>least</em> element with
12 :     * respect to the specified ordering.
13 : dholmes 1.18 * If multiple elements are tied for least value, the
14 : tim 1.14 * head is one of those elements. A priority queue does not permit
15 : dholmes 1.11 * <tt>null</tt> elements.
16 : tim 1.14 *
17 : dholmes 1.11 * <p>The {@link #remove()} and {@link #poll()} methods remove and
18 :     * return the head of the queue.
19 :     *
20 :     * <p>The {@link #element()} and {@link #peek()} methods return, but do
21 :     * not delete, the head of the queue.
22 : tim 1.2 *
23 : dl 1.7 * <p>A priority queue has a <i>capacity</i>. The capacity is the
24 :     * size of the array used internally to store the elements on the
25 : dholmes 1.20 * queue.
26 : dholmes 1.18 * It is always at least as large as the queue size. As
27 : dl 1.7 * elements are added to a priority queue, its capacity grows
28 :     * automatically. The details of the growth policy are not specified.
29 : tim 1.2 *
30 : dholmes 1.11 * <p>Implementation note: this implementation provides O(log(n)) time
31 :     * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
32 :     * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
33 :     * <tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
34 :     * constant time for the retrieval methods (<tt>peek</tt>,
35 :     * <tt>element</tt>, and <tt>size</tt>).
36 : tim 1.2 *
37 :     * <p>This class is a member of the
38 :     * <a href="{@docRoot}/../guide/collections/index.html">
39 :     * Java Collections Framework</a>.
40 : dl 1.7 * @since 1.5
41 :     * @author Josh Bloch
42 : tim 1.2 */
43 :     public class PriorityQueue<E> extends AbstractQueue<E>
44 : dl 1.22 implements Queue<E>, java.io.Serializable {
45 : dholmes 1.11
46 : tim 1.2 private static final int DEFAULT_INITIAL_CAPACITY = 11;
47 : tim 1.1
48 : tim 1.2 /**
49 :     * Priority queue represented as a balanced binary heap: the two children
50 :     * of queue[n] are queue[2*n] and queue[2*n + 1]. The priority queue is
51 :     * ordered by comparator, or by the elements' natural ordering, if
52 : brian 1.6 * comparator is null: For each node n in the heap and each descendant d
53 :     * of n, n <= d.
54 : tim 1.2 *
55 : brian 1.6 * The element with the lowest value is in queue[1], assuming the queue is
56 :     * nonempty. (A one-based array is used in preference to the traditional
57 :     * zero-based array to simplify parent and child calculations.)
58 : tim 1.2 *
59 :     * queue.length must be >= 2, even if size == 0.
60 :     */
61 : tim 1.16 private transient Object[] queue;
62 : tim 1.1
63 : tim 1.2 /**
64 :     * The number of elements in the priority queue.
65 :     */
66 :     private int size = 0;
67 : tim 1.1
68 : tim 1.2 /**
69 :     * The comparator, or null if priority queue uses elements'
70 :     * natural ordering.
71 :     */
72 : tim 1.16 private final Comparator<? super E> comparator;
73 : tim 1.2
74 :     /**
75 :     * The number of times this priority queue has been
76 :     * <i>structurally modified</i>. See AbstractList for gory details.
77 :     */
78 : dl 1.5 private transient int modCount = 0;
79 : tim 1.2
80 :     /**
81 : dholmes 1.21 * Creates a <tt>PriorityQueue</tt> with the default initial capacity
82 : dl 1.7 * (11) that orders its elements according to their natural
83 :     * ordering (using <tt>Comparable</tt>.)
84 : tim 1.2 */
85 :     public PriorityQueue() {
86 : dholmes 1.11 this(DEFAULT_INITIAL_CAPACITY, null);
87 : tim 1.1 }
88 : tim 1.2
89 :     /**
90 : dholmes 1.21 * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
91 : dl 1.7 * that orders its elements according to their natural ordering
92 :     * (using <tt>Comparable</tt>.)
93 : tim 1.2 *
94 :     * @param initialCapacity the initial capacity for this priority queue.
95 :     */
96 :     public PriorityQueue(int initialCapacity) {
97 :     this(initialCapacity, null);
98 : tim 1.1 }
99 : tim 1.2
100 :     /**
101 : dholmes 1.21 * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
102 : tim 1.2 * that orders its elements according to the specified comparator.
103 :     *
104 :     * @param initialCapacity the initial capacity for this priority queue.
105 :     * @param comparator the comparator used to order this priority queue.
106 : dholmes 1.11 * If <tt>null</tt> then the order depends on the elements' natural
107 :     * ordering.
108 : dholmes 1.15 * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
109 :     * than 1
110 : tim 1.2 */
111 : tim 1.16 public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
112 : tim 1.2 if (initialCapacity < 1)
113 : dholmes 1.15 throw new IllegalArgumentException();
114 : tim 1.16 this.queue = new Object[initialCapacity + 1];
115 : tim 1.2 this.comparator = comparator;
116 : tim 1.1 }
117 :    
118 : tim 1.2 /**
119 : dl 1.22 * Common code to initialize underlying queue array across
120 :     * constructors below.
121 :     */
122 :     private void initializeArray(Collection<? extends E> c) {
123 :     int sz = c.size();
124 :     int initialCapacity = (int)Math.min((sz * 110L) / 100,
125 :     Integer.MAX_VALUE - 1);
126 :     if (initialCapacity < 1)
127 :     initialCapacity = 1;
128 :    
129 :     this.queue = new Object[initialCapacity + 1];
130 :     }
131 :    
132 :     /**
133 :     * Initially fill elements of the queue array under the
134 :     * knowledge that it is sorted or is another PQ, in which
135 :     * case we can just place the elements without fixups.
136 :     */
137 :     private void fillFromSorted(Collection<? extends E> c) {
138 :     for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
139 :     queue[++size] = i.next();
140 :     }
141 :    
142 :    
143 :     /**
144 :     * Initially fill elements of the queue array that is
145 :     * not to our knowledge sorted, so we must add them
146 :     * one by one.
147 :     */
148 :     private void fillFromUnsorted(Collection<? extends E> c) {
149 :     for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
150 :     add(i.next());
151 :     }
152 :    
153 :     /**
154 :     * Creates a <tt>PriorityQueue</tt> containing the elements in the
155 :     * specified collection. The priority queue has an initial
156 :     * capacity of 110% of the size of the specified collection or 1
157 :     * if the collection is empty. If the specified collection is an
158 :     * instance of a {@link SortedSet} or is another
159 :     * <tt>PriorityQueue</tt>, the priority queue will be sorted
160 :     * according to the same comparator, or according to its elements'
161 :     * natural order if the collection is sorted according to its
162 :     * elements' natural order. Otherwise, the priority queue is
163 :     * ordered according to its elements' natural order.
164 : tim 1.2 *
165 : dholmes 1.15 * @param c the collection whose elements are to be placed
166 : tim 1.2 * into this priority queue.
167 :     * @throws ClassCastException if elements of the specified collection
168 :     * cannot be compared to one another according to the priority
169 :     * queue's ordering.
170 : dholmes 1.15 * @throws NullPointerException if <tt>c</tt> or any element within it
171 :     * is <tt>null</tt>
172 : tim 1.2 */
173 : tim 1.16 public PriorityQueue(Collection<? extends E> c) {
174 : dl 1.22 initializeArray(c);
175 :     if (c instanceof SortedSet<? extends E>) {
176 :     SortedSet<? extends E> s = (SortedSet<? extends E>) c;
177 :     comparator = (Comparator<? super E>)s.comparator();
178 :     fillFromSorted(s);
179 :     }
180 :     else if (c instanceof PriorityQueue<? extends E>) {
181 :     PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c;
182 :     comparator = (Comparator<? super E>)s.comparator();
183 :     fillFromSorted(s);
184 :     }
185 :     else {
186 : tim 1.2 comparator = null;
187 : dl 1.22 fillFromUnsorted(c);
188 : tim 1.2 }
189 : dl 1.22 }
190 :    
191 :     /**
192 :     * Creates a <tt>PriorityQueue</tt> containing the elements in the
193 :     * specified collection. The priority queue has an initial
194 :     * capacity of 110% of the size of the specified collection or 1
195 :     * if the collection is empty. This priority queue will be sorted
196 :     * according to the same comparator as the given collection, or
197 :     * according to its elements' natural order if the collection is
198 :     * sorted according to its elements' natural order.
199 :     *
200 :     * @param c the collection whose elements are to be placed
201 :     * into this priority queue.
202 :     * @throws ClassCastException if elements of the specified collection
203 :     * cannot be compared to one another according to the priority
204 :     * queue's ordering.
205 :     * @throws NullPointerException if <tt>c</tt> or any element within it
206 :     * is <tt>null</tt>
207 :     */
208 :     public PriorityQueue(PriorityQueue<? extends E> c) {
209 :     initializeArray(c);
210 :     comparator = (Comparator<? super E>)c.comparator();
211 :     fillFromSorted(c);
212 :     }
213 : dholmes 1.18
214 : dl 1.22 /**
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(SortedSet<? extends E> c) {
232 :     initializeArray(c);
233 :     comparator = (Comparator<? super E>)c.comparator();
234 :     fillFromSorted(c);
235 : tim 1.1 }
236 :    
237 : dl 1.22 /**
238 :     * Resize array, if necessary, to be able to hold given index
239 :     */
240 :     private void grow(int index) {
241 :     int newlen = queue.length;
242 :     if (index < newlen) // don't need to grow
243 :     return;
244 :     if (index == Integer.MAX_VALUE)
245 :     throw new OutOfMemoryError();
246 :     while (newlen <= index) {
247 :     if (newlen >= Integer.MAX_VALUE / 2) // avoid overflow
248 :     newlen = Integer.MAX_VALUE;
249 :     else
250 :     newlen <<= 2;
251 :     }
252 :     Object[] newQueue = new Object[newlen];
253 :     System.arraycopy(queue, 0, newQueue, 0, queue.length);
254 :     queue = newQueue;
255 :     }
256 :    
257 : tim 1.2 // Queue Methods
258 :    
259 :     /**
260 : dholmes 1.11 * Add the specified element to this priority queue.
261 : tim 1.2 *
262 : dholmes 1.11 * @return <tt>true</tt>
263 :     * @throws ClassCastException if the specified element cannot be compared
264 :     * with elements currently in the priority queue according
265 :     * to the priority queue's ordering.
266 : dholmes 1.18 * @throws NullPointerException if the specified element is <tt>null</tt>.
267 : tim 1.2 */
268 : dholmes 1.18 public boolean offer(E o) {
269 :     if (o == null)
270 : dholmes 1.11 throw new NullPointerException();
271 :     modCount++;
272 :     ++size;
273 :    
274 :     // Grow backing store if necessary
275 : dl 1.22 if (size >= queue.length)
276 :     grow(size);
277 : dholmes 1.11
278 : dholmes 1.18 queue[size] = o;
279 : dholmes 1.11 fixUp(size);
280 :     return true;
281 :     }
282 :    
283 : tim 1.1 public E poll() {
284 : tim 1.2 if (size == 0)
285 :     return null;
286 : tim 1.16 return (E) remove(1);
287 : tim 1.1 }
288 : tim 1.2
289 : tim 1.1 public E peek() {
290 : tim 1.16 return (E) queue[1];
291 : tim 1.1 }
292 :    
293 : tim 1.2 // Collection Methods
294 :    
295 : dholmes 1.11 // these first two override just to get the throws docs
296 :    
297 :     /**
298 :     * @throws NullPointerException if the specified element is <tt>null</tt>.
299 : dholmes 1.15 * @throws ClassCastException if the specified element cannot be compared
300 :     * with elements currently in the priority queue according
301 :     * to the priority queue's ordering.
302 : dholmes 1.11 */
303 : dholmes 1.18 public boolean add(E o) {
304 :     return super.add(o);
305 : dholmes 1.11 }
306 :    
307 : tim 1.14 /**
308 : dholmes 1.15 * @throws ClassCastException if any element cannot be compared
309 :     * with elements currently in the priority queue according
310 :     * to the priority queue's ordering.
311 : dholmes 1.18 * @throws NullPointerException if <tt>c</tt> or any element in <tt>c</tt>
312 :     * is <tt>null</tt>
313 : tim 1.14 */
314 :     public boolean addAll(Collection<? extends E> c) {
315 :     return super.addAll(c);
316 :     }
317 : dholmes 1.11
318 : dl 1.12 public boolean remove(Object o) {
319 : dholmes 1.11 if (o == null)
320 : dholmes 1.15 return false;
321 : tim 1.2
322 :     if (comparator == null) {
323 :     for (int i = 1; i <= size; i++) {
324 : tim 1.16 if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
325 : tim 1.2 remove(i);
326 :     return true;
327 :     }
328 :     }
329 :     } else {
330 :     for (int i = 1; i <= size; i++) {
331 : tim 1.16 if (comparator.compare((E)queue[i], (E)o) == 0) {
332 : tim 1.2 remove(i);
333 :     return true;
334 :     }
335 :     }
336 :     }
337 : tim 1.1 return false;
338 :     }
339 : tim 1.2
340 :     public Iterator<E> iterator() {
341 : dl 1.7 return new Itr();
342 : tim 1.2 }
343 :    
344 :     private class Itr implements Iterator<E> {
345 : dl 1.7 /**
346 :     * Index (into queue array) of element to be returned by
347 : tim 1.2 * subsequent call to next.
348 : dl 1.7 */
349 :     private int cursor = 1;
350 : tim 1.2
351 : dl 1.7 /**
352 :     * Index of element returned by most recent call to next or
353 :     * previous. Reset to 0 if this element is deleted by a call
354 :     * to remove.
355 :     */
356 :     private int lastRet = 0;
357 :    
358 :     /**
359 :     * The modCount value that the iterator believes that the backing
360 :     * List should have. If this expectation is violated, the iterator
361 :     * has detected concurrent modification.
362 :     */
363 :     private int expectedModCount = modCount;
364 : tim 1.2
365 : dl 1.7 public boolean hasNext() {
366 :     return cursor <= size;
367 :     }
368 :    
369 :     public E next() {
370 : tim 1.2 checkForComodification();
371 :     if (cursor > size)
372 : dl 1.7 throw new NoSuchElementException();
373 : tim 1.16 E result = (E) queue[cursor];
374 : tim 1.2 lastRet = cursor++;
375 :     return result;
376 : dl 1.7 }
377 : tim 1.2
378 : dl 1.7 public void remove() {
379 :     if (lastRet == 0)
380 :     throw new IllegalStateException();
381 : tim 1.2 checkForComodification();
382 :    
383 :     PriorityQueue.this.remove(lastRet);
384 :     if (lastRet < cursor)
385 :     cursor--;
386 :     lastRet = 0;
387 :     expectedModCount = modCount;
388 : dl 1.7 }
389 : tim 1.2
390 : dl 1.7 final void checkForComodification() {
391 :     if (modCount != expectedModCount)
392 :     throw new ConcurrentModificationException();
393 :     }
394 : tim 1.2 }
395 :    
396 :     /**
397 :     * Returns the number of elements in this priority queue.
398 : tim 1.10 *
399 : tim 1.2 * @return the number of elements in this priority queue.
400 :     */
401 : tim 1.1 public int size() {
402 : tim 1.2 return size;
403 : tim 1.1 }
404 : tim 1.2
405 :     /**
406 :     * Remove all elements from the priority queue.
407 :     */
408 :     public void clear() {
409 :     modCount++;
410 :    
411 :     // Null out element references to prevent memory leak
412 :     for (int i=1; i<=size; i++)
413 :     queue[i] = null;
414 :    
415 :     size = 0;
416 :     }
417 :    
418 :     /**
419 :     * Removes and returns the ith element from queue. Recall
420 :     * that queue is one-based, so 1 <= i <= size.
421 :     *
422 :     * XXX: Could further special-case i==size, but is it worth it?
423 :     * XXX: Could special-case i==0, but is it worth it?
424 :     */
425 :     private E remove(int i) {
426 :     assert i <= size;
427 :     modCount++;
428 :    
429 : tim 1.16 E result = (E) queue[i];
430 : tim 1.2 queue[i] = queue[size];
431 :     queue[size--] = null; // Drop extra ref to prevent memory leak
432 :     if (i <= size)
433 :     fixDown(i);
434 :     return result;
435 : tim 1.1 }
436 :    
437 : tim 1.2 /**
438 :     * Establishes the heap invariant (described above) assuming the heap
439 :     * satisfies the invariant except possibly for the leaf-node indexed by k
440 :     * (which may have a nextExecutionTime less than its parent's).
441 :     *
442 :     * This method functions by "promoting" queue[k] up the hierarchy
443 :     * (by swapping it with its parent) repeatedly until queue[k]
444 :     * is greater than or equal to its parent.
445 :     */
446 :     private void fixUp(int k) {
447 :     if (comparator == null) {
448 :     while (k > 1) {
449 :     int j = k >> 1;
450 : tim 1.16 if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
451 : tim 1.2 break;
452 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
453 : tim 1.2 k = j;
454 :     }
455 :     } else {
456 :     while (k > 1) {
457 :     int j = k >> 1;
458 : tim 1.16 if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
459 : tim 1.2 break;
460 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
461 : tim 1.2 k = j;
462 :     }
463 :     }
464 :     }
465 :    
466 :     /**
467 :     * Establishes the heap invariant (described above) in the subtree
468 :     * rooted at k, which is assumed to satisfy the heap invariant except
469 :     * possibly for node k itself (which may be greater than its children).
470 :     *
471 :     * This method functions by "demoting" queue[k] down the hierarchy
472 :     * (by swapping it with its smaller child) repeatedly until queue[k]
473 :     * is less than or equal to its children.
474 :     */
475 :     private void fixDown(int k) {
476 :     int j;
477 :     if (comparator == null) {
478 :     while ((j = k << 1) <= size) {
479 : tim 1.16 if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
480 : tim 1.2 j++; // j indexes smallest kid
481 : tim 1.16 if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
482 : tim 1.2 break;
483 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
484 : tim 1.2 k = j;
485 :     }
486 :     } else {
487 :     while ((j = k << 1) <= size) {
488 : tim 1.16 if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
489 : tim 1.2 j++; // j indexes smallest kid
490 : tim 1.16 if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
491 : tim 1.2 break;
492 : tim 1.16 Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
493 : tim 1.2 k = j;
494 :     }
495 :     }
496 :     }
497 :    
498 : tim 1.16 public Comparator<? super E> comparator() {
499 : tim 1.2 return comparator;
500 :     }
501 : dl 1.5
502 :     /**
503 :     * Save the state of the instance to a stream (that
504 :     * is, serialize it).
505 :     *
506 :     * @serialData The length of the array backing the instance is
507 :     * emitted (int), followed by all of its elements (each an
508 :     * <tt>Object</tt>) in the proper order.
509 : dl 1.7 * @param s the stream
510 : dl 1.5 */
511 : dl 1.22 private void writeObject(java.io.ObjectOutputStream s)
512 : dl 1.5 throws java.io.IOException{
513 : dl 1.7 // Write out element count, and any hidden stuff
514 :     s.defaultWriteObject();
515 : dl 1.5
516 :     // Write out array length
517 :     s.writeInt(queue.length);
518 :    
519 : dl 1.7 // Write out all elements in the proper order.
520 :     for (int i=0; i<size; i++)
521 : dl 1.5 s.writeObject(queue[i]);
522 :     }
523 :    
524 :     /**
525 :     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
526 :     * deserialize it).
527 : dl 1.7 * @param s the stream
528 : dl 1.5 */
529 : dl 1.22 private void readObject(java.io.ObjectInputStream s)
530 : dl 1.5 throws java.io.IOException, ClassNotFoundException {
531 : dl 1.7 // Read in size, and any hidden stuff
532 :     s.defaultReadObject();
533 : dl 1.5
534 :     // Read in array length and allocate array
535 :     int arrayLength = s.readInt();
536 : tim 1.16 queue = new Object[arrayLength];
537 : dl 1.5
538 : dl 1.7 // Read in all elements in the proper order.
539 :     for (int i=0; i<size; i++)
540 : tim 1.16 queue[i] = s.readObject();
541 : dl 1.5 }
542 :    
543 : tim 1.1 }
544 : dholmes 1.11

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8