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

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8