PriorityQueue


1   /*
2    * @(#)PriorityQueue.java   1.6 04/06/11
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util;
9   
10  /**
11   * 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   * A priority queue relying on natural ordering also does not
18   * permit insertion of non-comparable objects (doing so may result
19   * in <tt>ClassCastException</tt>). 
20   *
21   * <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   * 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   *
28   * <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   * 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   *
35   * <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   * Iterator provided in method {@link #iterator()} is <em>not</em>
40   * 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   * java.util.concurrent.PriorityBlockingQueue} class.
49   *
50   * 
51   * <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   *
58   * <p>This class is a member of the
59   * <a HREF="{@docRoot}/../guide/collections/index.html">
60   * Java Collections Framework</a>.
61   * @since 1.5
62   * @version 1.6, 06/11/04
63   * @author Josh Bloch
64   * @param <E> the type of elements held in this collection
65   */
66  public class PriorityQueue<E> extends AbstractQueue  <E>
67      implements java.io.Serializable   {
68  
69      private static final long serialVersionUID = -7720805057305804111L;
70  
71      private static final int DEFAULT_INITIAL_CAPACITY = 11;
72  
73      /**
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       * comparator is null:  For each node n in the heap and each descendant d
78       * of n, n <= d.
79       *
80       * 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       *
84       * queue.length must be >= 2, even if size == 0.
85       */
86      private transient Object  [] queue;
87  
88      /**
89       * The number of elements in the priority queue.
90       */
91      private int size = 0;
92  
93      /**
94       * The comparator, or null if priority queue uses elements'
95       * natural ordering.
96       */
97      private final Comparator  <? super E> comparator;
98  
99      /**
100      * The number of times this priority queue has been
101      * <i>structurally modified</i>.  See AbstractList for gory details.
102      */
103     private transient int modCount = 0;
104 
105     /**
106      * Creates a <tt>PriorityQueue</tt> with the default initial capacity
107      * (11) that orders its elements according to their natural
108      * ordering (using <tt>Comparable</tt>).
109      */
110     public PriorityQueue() {
111         this(DEFAULT_INITIAL_CAPACITY, null);
112     }
113 
114     /**
115      * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
116      * that orders its elements according to their natural ordering
117      * (using <tt>Comparable</tt>).
118      *
119      * @param initialCapacity the initial capacity for this priority queue.
120      * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
121      * than 1
122      */
123     public PriorityQueue(int initialCapacity) {
124         this(initialCapacity, null);
125     }
126 
127     /**
128      * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
129      * 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      * If <tt>null</tt> then the order depends on the elements' natural
134      * ordering.
135      * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
136      * than 1
137      */
138     public PriorityQueue(int initialCapacity, 
139                          Comparator  <? super E> comparator) {
140         if (initialCapacity < 1)
141             throw new IllegalArgumentException  ();
142         this.queue = new Object  [initialCapacity + 1];
143         this.comparator = comparator;
144     }
145 
146     /**
147      * 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      * case we can just place the elements in the order presented.
164      */
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      * 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      */
175     private void fillFromUnsorted(Collection  <? extends E> c) {
176         for (Iterator  <? extends E> i = c.iterator(); i.hasNext(); )
177             queue[++size] = i.next();
178         heapify();
179     }
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      * instance of a {@link java.util.SortedSet} or is another
187      * <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      *
193      * @param c the collection whose elements are to be placed
194      *        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      * @throws NullPointerException if <tt>c</tt> or any element within it
199      * is <tt>null</tt>
200      */
201     public PriorityQueue(Collection  <? extends E> c) {
202         initializeArray(c);
203         if (c instanceof SortedSet  ) {
204             SortedSet  <? extends E> s = (SortedSet  <? extends E>)c;
205             comparator = (Comparator  <? super E>)s.comparator();
206             fillFromSorted(s);
207         } else if (c instanceof PriorityQueue  ) {
208             PriorityQueue  <? extends E> s = (PriorityQueue  <? extends E>) c;
209             comparator = (Comparator  <? super E>)s.comparator();
210             fillFromSorted(s);
211         } else {
212             comparator = null;
213             fillFromUnsorted(c);
214         }
215     }
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 
240     /**
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     }
262 
263     /**
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 
284     /**
285      * Inserts the specified element into this priority queue.
286      *
287      * @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      * @throws NullPointerException if the specified element is <tt>null</tt>.
292      */
293     public boolean offer(E o) {
294         if (o == null)
295             throw new NullPointerException  ();
296         modCount++;
297         ++size;
298 
299         // Grow backing store if necessary
300         if (size >= queue.length) 
301             grow(size);
302 
303         queue[size] = o;
304         fixUp(size);
305         return true;
306     }
307 
308     public E peek() {
309         if (size == 0)
310             return null;
311         return (E) queue[1];
312     }
313 
314     // Collection Methods - the first two override to update docs
315 
316     /**
317      * 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      * @throws NullPointerException if the specified element is <tt>null</tt>.
322      * @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      */
326     public boolean add(E o) {
327         return offer(o);
328     }
329 
330     /**
331      * Removes a single instance of the specified element from this
332      * queue, if it is present.
333      */
334     public boolean remove(Object   o) {
335         if (o == null)
336             return false;
337 
338         if (comparator == null) {
339             for (int i = 1; i <= size; i++) {
340                 if (((Comparable  <E>)queue[i]).compareTo((E)o) == 0) {
341                     removeAt(i);
342                     return true;
343                 }
344             }
345         } else {
346             for (int i = 1; i <= size; i++) {
347                 if (comparator.compare((E)queue[i], (E)o) == 0) {
348                     removeAt(i);
349                     return true;
350                 }
351             }
352         }
353         return false;
354     }
355 
356     /**
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     public Iterator  <E> iterator() {
363         return new Itr();
364     }
365 
366     private class Itr implements Iterator  <E> {
367 
368         /**
369          * Index (into queue array) of element to be returned by
370          * subsequent call to next.
371          */
372         private int cursor = 1;
373 
374         /**
375          * 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          */
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 
388         /**
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 
407         public boolean hasNext() {
408             return cursor <= size || forgetMeNot != null;
409         }
410 
411         public E next() {
412             checkForComodification();
413             E result;
414             if (cursor <= size) {
415                 result = (E) queue[cursor];
416                 lastRet = cursor++;
417             }
418             else if (forgetMeNot == null)
419                 throw new NoSuchElementException  ();
420             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             return result;
429         }
430 
431         public void remove() {
432             checkForComodification();
433 
434             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                         forgetMeNot = new ArrayList  <E>();
442                     forgetMeNot.add(moved);
443                 }
444             } else if (lastRetElt != null) {
445                 PriorityQueue.this.remove(lastRetElt);
446                 lastRetElt = null;
447             } else {
448                 throw new IllegalStateException  ();
449             }
450 
451             expectedModCount = modCount;
452         }
453 
454         final void checkForComodification() {
455             if (modCount != expectedModCount)
456                 throw new ConcurrentModificationException  ();
457         }
458     }
459 
460     public int size() {
461         return size;
462     }
463 
464     /**
465      * Removes all elements from the priority queue.
466      * The queue will be empty after this call returns.
467      */
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     public E poll() {
479         if (size == 0)
480             return null;
481         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      *
496      * 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      */
505     private E removeAt(int i) { 
506         assert i > 0 && i <= size;
507         modCount++;
508 
509         E moved = (E) queue[size];
510         queue[i] = moved;
511         queue[size--] = null;  // Drop extra ref to prevent memory leak
512         if (i <= size) {
513             fixDown(i);
514             if (queue[i] == moved) {
515                 fixUp(i);
516                 if (queue[i] != moved)
517                     return moved;
518             }
519         }
520         return null;
521     }
522 
523     /**
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                 if (((Comparable  <E>)queue[j]).compareTo((E)queue[k]) <= 0)
537                     break;
538                 Object   tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
539                 k = j;
540             }
541         } else {
542             while (k > 1) {
543                 int j = k >>> 1;
544                 if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
545                     break;
546                 Object   tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
547                 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             while ((j = k << 1) <= size && (j > 0)) {
565                 if (j<size && 
566                     ((Comparable  <E>)queue[j]).compareTo((E)queue[j+1]) > 0)
567                     j++; // j indexes smallest kid
568 
569                 if (((Comparable  <E>)queue[k]).compareTo((E)queue[j]) <= 0)
570                     break;
571                 Object   tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
572                 k = j;
573             }
574         } else {
575             while ((j = k << 1) <= size && (j > 0)) {
576                 if (j<size && 
577                     comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
578                     j++; // j indexes smallest kid
579                 if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
580                     break;
581                 Object   tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
582                 k = j;
583             }
584         }
585     }
586 
587     /**
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     }
595 
596     /**
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      * (using <tt>Comparable</tt>).
600      *
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     public Comparator  <? super E> comparator() {
605         return comparator;
606     }
607 
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      * @param s the stream
616      */
617     private void writeObject(java.io.ObjectOutputStream   s)
618         throws java.io.IOException  {
619         // Write out element count, and any hidden stuff
620         s.defaultWriteObject();
621 
622         // Write out array length
623         s.writeInt(queue.length);
624 
625         // Write out all elements in the proper order.
626         for (int i=1; i<=size; i++)
627             s.writeObject(queue[i]);
628     }
629 
630     /**
631      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
632      * deserialize it).
633      * @param s the stream
634      */
635     private void readObject(java.io.ObjectInputStream   s)
636         throws java.io.IOException  , ClassNotFoundException   {
637         // Read in size, and any hidden stuff
638         s.defaultReadObject();
639 
640         // Read in array length and allocate array
641         int arrayLength = s.readInt();
642         queue = new Object  [arrayLength];
643 
644         // Read in all elements in the proper order.
645         for (int i=1; i<=size; i++)
646             queue[i] = (E) s.readObject();
647     }
648 
649 }
650
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags