ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/PriorityQueue.java
(Generate patch)

Comparing jsr166/src/main/java/util/PriorityQueue.java (file contents):
Revision 1.2 by tim, Sun May 18 18:10:02 2003 UTC vs.
Revision 1.7 by dl, Tue Jun 24 14:34:30 2003 UTC

# Line 1 | Line 1
1   package java.util;
2  
3 – /*
4 – * Todo
5 – *
6 – *   1) Make it serializable.
7 – */
8 –
3   /**
4   * An unbounded priority queue based on a priority heap.  This queue orders
5 < * elements according to the order specified at creation time.  This order is
6 < * specified as for {@link TreeSet} and {@link TreeMap}: Elements are ordered
5 > * elements according to an order specified at construction time, which is
6 > * specified in the same manner as {@link TreeSet} and {@link TreeMap}: elements are ordered
7   * either according to their <i>natural order</i> (see {@link Comparable}), or
8   * according to a {@link Comparator}, depending on which constructor is used.
9   * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the
10   * minimal element with respect to the specified ordering.  If multiple
11 < * these elements are tied for least value, no guarantees are made as to
12 < * which of elements is returned.
11 > * elements are tied for least value, no guarantees are made as to
12 > * which of these elements is returned.
13   *
14 < * <p>Each priority queue has a <i>capacity</i>.  The capacity is the size of
15 < * the array used to store the elements on the queue.  It is always at least
16 < * as large as the queue size.  As elements are added to a priority list,
17 < * its capacity grows automatically.  The details of the growth policy are not
18 < * specified.
14 > * <p>A priority queue has a <i>capacity</i>.  The capacity is the
15 > * size of the array used internally to store the elements on the
16 > * queue.  It is always at least as large as the queue size.  As
17 > * elements are added to a priority queue, its capacity grows
18 > * automatically.  The details of the growth policy are not specified.
19   *
20 < *<p>Implementation note: this implementation provides O(log(n)) time for
21 < * the <tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt>
22 < * methods; linear time for the <tt>remove(Object)</tt> and
23 < * <tt>contains</tt> methods; and constant time for the <tt>peek</tt>,
24 < * <tt>element</tt>, and <tt>size</tt> methods.
20 > *<p>Implementation note: this implementation provides O(log(n)) time
21 > *for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
22 > *<tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
23 > *<tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
24 > *constant time for the retrieval methods (<tt>peek</tt>,
25 > *<tt>element</tt>, and <tt>size</tt>).
26   *
27   * <p>This class is a member of the
28   * <a href="{@docRoot}/../guide/collections/index.html">
29   * Java Collections Framework</a>.
30 + * @since 1.5
31 + * @author Josh Bloch
32   */
33   public class PriorityQueue<E> extends AbstractQueue<E>
34 <                              implements Queue<E>
38 < {
34 >                              implements Queue<E> {
35      private static final int DEFAULT_INITIAL_CAPACITY = 11;
36  
37      /**
38       * Priority queue represented as a balanced binary heap: the two children
39       * of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is
40       * ordered by comparator, or by the elements' natural ordering, if
41 <     * comparator is null:  For each node n in the heap, and each descendant
42 <     * of n, d, n <= d.
41 >     * comparator is null:  For each node n in the heap and each descendant d
42 >     * of n, n <= d.
43       *
44 <     * The element with the lowest value is in queue[1] (assuming the queue is
45 <     * nonempty). A one-based array is used in preference to the traditional
46 <     * zero-based array to simplify parent and child calculations.
44 >     * The element with the lowest value is in queue[1], assuming the queue is
45 >     * nonempty.  (A one-based array is used in preference to the traditional
46 >     * zero-based array to simplify parent and child calculations.)
47       *
48       * queue.length must be >= 2, even if size == 0.
49       */
50 <    private E[] queue;
50 >    private transient E[] queue;
51  
52      /**
53       * The number of elements in the priority queue.
# Line 68 | Line 64 | public class PriorityQueue<E> extends Ab
64       * The number of times this priority queue has been
65       * <i>structurally modified</i>.  See AbstractList for gory details.
66       */
67 <    private int modCount = 0;
67 >    private transient int modCount = 0;
68  
69      /**
70 <     * Create a new priority queue with the default initial capacity (11)
71 <     * that orders its elements according to their natural ordering.
70 >     * Create a new priority queue with the default initial capacity
71 >     * (11) that orders its elements according to their natural
72 >     * ordering (using <tt>Comparable</tt>.)
73       */
74      public PriorityQueue() {
75          this(DEFAULT_INITIAL_CAPACITY);
# Line 80 | Line 77 | public class PriorityQueue<E> extends Ab
77  
78      /**
79       * Create a new priority queue with the specified initial capacity
80 <     * that orders its elements according to their natural ordering.
80 >     * that orders its elements according to their natural ordering
81 >     * (using <tt>Comparable</tt>.)
82       *
83       * @param initialCapacity the initial capacity for this priority queue.
84       */
# Line 109 | Line 107 | public class PriorityQueue<E> extends Ab
107       * implements the {@link Sorted} interface, the priority queue will be
108       * sorted according to the same comparator, or according to its elements'
109       * natural order if the collection is sorted according to its elements'
110 <     * natural order.  If the specified collection does not implement the
111 <     * <tt>Sorted</tt> interface, the priority queue is ordered according to
110 >     * natural order.  If the specified collection does not implement
111 >     * <tt>Sorted</tt>, the priority queue is ordered according to
112       * its elements' natural order.
113       *
114       * @param initialElements the collection whose elements are to be placed
# Line 147 | Line 145 | public class PriorityQueue<E> extends Ab
145      // Queue Methods
146  
147      /**
148 <     * Remove and return the minimal element from this priority queue if
149 <     * it contains one or more elements, otherwise <tt>null</tt>.  The term
150 <     * <i>minimal</i> is defined according to this priority queue's order.
148 >     * Remove and return the minimal element from this priority queue
149 >     * if it contains one or more elements, otherwise return
150 >     * <tt>null</tt>.  The term <i>minimal</i> is defined according to
151 >     * this priority queue's order.
152       *
153       * @return the minimal element from this priority queue if it contains
154       *         one or more elements, otherwise <tt>null</tt>.
# Line 161 | Line 160 | public class PriorityQueue<E> extends Ab
160      }
161  
162      /**
163 <     * Return, but do not remove, the minimal element from the priority queue,
164 <     * or <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is
165 <     * defined according to this priority queue's order.  This method returns
166 <     * the same object reference that would be returned by by the
167 <     * <tt>poll</tt> method.  The two methods differ in that this method
168 <     * does not remove the element from the priority queue.
163 >     * Return, but do not remove, the minimal element from the
164 >     * priority queue, or return <tt>null</tt> if the queue is empty.
165 >     * The term <i>minimal</i> is defined according to this priority
166 >     * queue's order.  This method returns the same object reference
167 >     * that would be returned by by the <tt>poll</tt> method.  The two
168 >     * methods differ in that this method does not remove the element
169 >     * from the priority queue.
170       *
171       * @return the minimal element from this priority queue if it contains
172       *         one or more elements, otherwise <tt>null</tt>.
# Line 183 | Line 183 | public class PriorityQueue<E> extends Ab
183       * specified element (or equivalently, if this collection changed as a
184       * result of the call).
185       *
186 <     * @param o element to be removed from this collection, if present.
186 >     * @param element the element to be removed from this collection,
187 >     * if present.
188       * @return <tt>true</tt> if this collection changed as a result of the
189       *         call
190       * @throws ClassCastException if the specified element cannot be compared
# Line 215 | Line 216 | public class PriorityQueue<E> extends Ab
216  
217      /**
218       * Returns an iterator over the elements in this priority queue.  The
219 <     * first element returned by this iterator is the same element that
220 <     * would be returned by a call to <tt>peek</tt>.
221 <     *
219 >     * elements of the priority queue will be returned by this iterator in the
220 >     * order specified by the queue, which is to say the order they would be
221 >     * returned by repeated calls to <tt>poll</tt>.
222 >     *
223       * @return an <tt>Iterator</tt> over the elements in this priority queue.
224       */
225      public Iterator<E> iterator() {
# Line 229 | Line 231 | public class PriorityQueue<E> extends Ab
231           * Index (into queue array) of element to be returned by
232           * subsequent call to next.
233           */
234 <        int cursor = 1;
234 >        private int cursor = 1;
235  
236          /**
237           * Index of element returned by most recent call to next or
238           * previous.  Reset to 0 if this element is deleted by a call
239           * to remove.
240           */
241 <        int lastRet = 0;
241 >        private int lastRet = 0;
242  
243          /**
244           * The modCount value that the iterator believes that the backing
245           * List should have.  If this expectation is violated, the iterator
246           * has detected concurrent modification.
247           */
248 <        int expectedModCount = modCount;
248 >        private int expectedModCount = modCount;
249  
250          public boolean hasNext() {
251              return cursor <= size;
# Line 278 | Line 280 | public class PriorityQueue<E> extends Ab
280  
281      /**
282       * Returns the number of elements in this priority queue.
283 <     *
283 >     *
284       * @return the number of elements in this priority queue.
285       */
286      public int size() {
# Line 415 | Line 417 | public class PriorityQueue<E> extends Ab
417      Comparator comparator() {
418          return comparator;
419      }
420 +
421 +    /**
422 +     * Save the state of the instance to a stream (that
423 +     * is, serialize it).
424 +     *
425 +     * @serialData The length of the array backing the instance is
426 +     * emitted (int), followed by all of its elements (each an
427 +     * <tt>Object</tt>) in the proper order.
428 +     * @param s the stream
429 +     */
430 +    private synchronized void writeObject(java.io.ObjectOutputStream s)
431 +        throws java.io.IOException{
432 +        // Write out element count, and any hidden stuff
433 +        s.defaultWriteObject();
434 +
435 +        // Write out array length
436 +        s.writeInt(queue.length);
437 +
438 +        // Write out all elements in the proper order.
439 +        for (int i=0; i<size; i++)
440 +            s.writeObject(queue[i]);
441 +    }
442 +
443 +    /**
444 +     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
445 +     * deserialize it).
446 +     * @param s the stream
447 +     */
448 +    private synchronized void readObject(java.io.ObjectInputStream s)
449 +        throws java.io.IOException, ClassNotFoundException {
450 +        // Read in size, and any hidden stuff
451 +        s.defaultReadObject();
452 +
453 +        // Read in array length and allocate array
454 +        int arrayLength = s.readInt();
455 +        queue = new E[arrayLength];
456 +
457 +        // Read in all elements in the proper order.
458 +        for (int i=0; i<size; i++)
459 +            queue[i] = (E)s.readObject();
460 +    }
461 +
462   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines