/[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.14 - (show annotations)
Mon Jul 28 16:00:19 2003 UTC (16 years ago) by tim
Branch: MAIN
Changes since 1.13: +10 -10 lines
Added addAll() back in.

1 package java.util;
2
3 /**
4 * An unbounded priority queue based on a priority heap. This queue orders
5 * elements according to an order specified at construction time, which is
6 * specified in the same manner as {@link TreeSet} and {@link TreeMap}:
7 * elements are ordered
8 * 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 * 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 *
21 * <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 *
27 * <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 *
34 * <p>This class is a member of the
35 * <a href="{@docRoot}/../guide/collections/index.html">
36 * Java Collections Framework</a>.
37 * @since 1.5
38 * @author Josh Bloch
39 */
40 public class PriorityQueue<E> extends AbstractQueue<E>
41 implements Queue<E>, java.io.Serializable {
42
43 private static final int DEFAULT_INITIAL_CAPACITY = 11;
44
45 /**
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 * comparator is null: For each node n in the heap and each descendant d
50 * of n, n <= d.
51 *
52 * 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 *
56 * queue.length must be >= 2, even if size == 0.
57 */
58 private transient E[] queue;
59
60 /**
61 * The number of elements in the priority queue.
62 */
63 private int size = 0;
64
65 /**
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 private transient int modCount = 0;
76
77 /**
78 * Create a <tt>PriorityQueue</tt> with the default initial capacity
79 * (11) that orders its elements according to their natural
80 * ordering (using <tt>Comparable</tt>.)
81 */
82 public PriorityQueue() {
83 this(DEFAULT_INITIAL_CAPACITY, null);
84 }
85
86 /**
87 * Create a <tt>PriorityQueue</tt> with the specified initial capacity
88 * that orders its elements according to their natural ordering
89 * (using <tt>Comparable</tt>.)
90 *
91 * @param initialCapacity the initial capacity for this priority queue.
92 */
93 public PriorityQueue(int initialCapacity) {
94 this(initialCapacity, null);
95 }
96
97 /**
98 * Create a <tt>PriorityQueue</tt> with the specified initial capacity
99 * 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 * If <tt>null</tt> then the order depends on the elements' natural
104 * ordering.
105 */
106 public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
107 if (initialCapacity < 1)
108 initialCapacity = 1;
109 queue = (E[]) new Object[initialCapacity + 1];
110 this.comparator = comparator;
111 }
112
113 /**
114 * Create a <tt>PriorityQueue</tt> containing the elements in the specified
115 * 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 * natural order. If the specified collection does not implement
121 * <tt>Sorted</tt>, the priority queue is ordered according to
122 * 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 queue = (E[]) new Object[initialCapacity + 1];
139
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 }
150
151 // Queue Methods
152
153 /**
154 * Add the specified element to this priority queue.
155 *
156 * @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 */
163 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 public E poll() {
182 if (size == 0)
183 return null;
184 return remove(1);
185 }
186
187 public E peek() {
188 return queue[1];
189 }
190
191 // Collection Methods
192
193 // 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 /**
203 * @throws NullPointerException if any element is <tt>null</tt>.
204 */
205 public boolean addAll(Collection<? extends E> c) {
206 return super.addAll(c);
207 }
208
209 /**
210 * @throws NullPointerException if the specified element is <tt>null</tt>.
211 */
212 public boolean remove(Object o) {
213 if (o == null)
214 throw new NullPointerException();
215
216 if (comparator == null) {
217 for (int i = 1; i <= size; i++) {
218 if (((Comparable)queue[i]).compareTo(o) == 0) {
219 remove(i);
220 return true;
221 }
222 }
223 } else {
224 for (int i = 1; i <= size; i++) {
225 if (comparator.compare(queue[i], (E)o) == 0) {
226 remove(i);
227 return true;
228 }
229 }
230 }
231 return false;
232 }
233
234 /**
235 * Returns an iterator over the elements in this priority queue. The
236 * 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 *
240 * @return an <tt>Iterator</tt> over the elements in this priority queue.
241 */
242 public Iterator<E> iterator() {
243 return new Itr();
244 }
245
246 private class Itr implements Iterator<E> {
247 /**
248 * Index (into queue array) of element to be returned by
249 * subsequent call to next.
250 */
251 private int cursor = 1;
252
253 /**
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
267 public boolean hasNext() {
268 return cursor <= size;
269 }
270
271 public E next() {
272 checkForComodification();
273 if (cursor > size)
274 throw new NoSuchElementException();
275 E result = queue[cursor];
276 lastRet = cursor++;
277 return result;
278 }
279
280 public void remove() {
281 if (lastRet == 0)
282 throw new IllegalStateException();
283 checkForComodification();
284
285 PriorityQueue.this.remove(lastRet);
286 if (lastRet < cursor)
287 cursor--;
288 lastRet = 0;
289 expectedModCount = modCount;
290 }
291
292 final void checkForComodification() {
293 if (modCount != expectedModCount)
294 throw new ConcurrentModificationException();
295 }
296 }
297
298 /**
299 * Returns the number of elements in this priority queue.
300 *
301 * @return the number of elements in this priority queue.
302 */
303 public int size() {
304 return size;
305 }
306
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 }
338
339 /**
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 public Comparator comparator() {
401 return comparator;
402 }
403
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 * @param s the stream
412 */
413 private synchronized void writeObject(java.io.ObjectOutputStream s)
414 throws java.io.IOException{
415 // Write out element count, and any hidden stuff
416 s.defaultWriteObject();
417
418 // Write out array length
419 s.writeInt(queue.length);
420
421 // Write out all elements in the proper order.
422 for (int i=0; i<size; i++)
423 s.writeObject(queue[i]);
424 }
425
426 /**
427 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
428 * deserialize it).
429 * @param s the stream
430 */
431 private synchronized void readObject(java.io.ObjectInputStream s)
432 throws java.io.IOException, ClassNotFoundException {
433 // Read in size, and any hidden stuff
434 s.defaultReadObject();
435
436 // Read in array length and allocate array
437 int arrayLength = s.readInt();
438 queue = (E[]) new Object[arrayLength];
439
440 // Read in all elements in the proper order.
441 for (int i=0; i<size; i++)
442 queue[i] = (E)s.readObject();
443 }
444
445 }
446

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