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

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8