/[cvs]/jsr166/src/main/java/util/PriorityQueue.java
ViewVC logotype

Contents of /jsr166/src/main/java/util/PriorityQueue.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.25 - (show annotations)
Wed Aug 6 18:42:49 2003 UTC (16 years ago) by tim
Branch: MAIN
CVS Tags: JSR166_CR1
Changes since 1.24: +1 -1 lines
Fixes to minor errors found by DocCheck, includes stray Locks reference removal

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

dl@cs.oswego.edu
ViewVC Help
Powered by ViewVC 1.1.27