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.4 by tim, Mon May 19 02:45:07 2003 UTC vs.
Revision 1.8 by dl, Tue Jul 1 16:29:45 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>
35 < {
34 >                              implements Queue<E>,
35 >                                         java.io.Serializable {
36      private static final int DEFAULT_INITIAL_CAPACITY = 11;
37  
38      /**
39       * Priority queue represented as a balanced binary heap: the two children
40       * of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is
41       * ordered by comparator, or by the elements' natural ordering, if
42 <     * comparator is null:  For each node n in the heap, and each descendant
43 <     * of n, d, n <= d.
42 >     * comparator is null:  For each node n in the heap and each descendant d
43 >     * of n, n <= d.
44       *
45 <     * The element with the lowest value is in queue[1] (assuming the queue is
46 <     * nonempty). A one-based array is used in preference to the traditional
47 <     * zero-based array to simplify parent and child calculations.
45 >     * The element with the lowest value is in queue[1], assuming the queue is
46 >     * nonempty.  (A one-based array is used in preference to the traditional
47 >     * zero-based array to simplify parent and child calculations.)
48       *
49       * queue.length must be >= 2, even if size == 0.
50       */
51 <    private E[] queue;
51 >    private transient E[] queue;
52  
53      /**
54       * The number of elements in the priority queue.
# Line 68 | Line 65 | public class PriorityQueue<E> extends Ab
65       * The number of times this priority queue has been
66       * <i>structurally modified</i>.  See AbstractList for gory details.
67       */
68 <    private int modCount = 0;
68 >    private transient int modCount = 0;
69  
70      /**
71 <     * Create a new priority queue with the default initial capacity (11)
72 <     * that orders its elements according to their natural ordering.
71 >     * Create a new priority queue with the default initial capacity
72 >     * (11) that orders its elements according to their natural
73 >     * ordering (using <tt>Comparable</tt>.)
74       */
75      public PriorityQueue() {
76          this(DEFAULT_INITIAL_CAPACITY);
# Line 80 | Line 78 | public class PriorityQueue<E> extends Ab
78  
79      /**
80       * Create a new priority queue with the specified initial capacity
81 <     * that orders its elements according to their natural ordering.
81 >     * that orders its elements according to their natural ordering
82 >     * (using <tt>Comparable</tt>.)
83       *
84       * @param initialCapacity the initial capacity for this priority queue.
85       */
# Line 109 | Line 108 | public class PriorityQueue<E> extends Ab
108       * implements the {@link Sorted} interface, the priority queue will be
109       * sorted according to the same comparator, or according to its elements'
110       * natural order if the collection is sorted according to its elements'
111 <     * natural order.  If the specified collection does not implement the
112 <     * <tt>Sorted</tt> interface, the priority queue is ordered according to
111 >     * natural order.  If the specified collection does not implement
112 >     * <tt>Sorted</tt>, the priority queue is ordered according to
113       * its elements' natural order.
114       *
115       * @param initialElements the collection whose elements are to be placed
# Line 129 | Line 128 | public class PriorityQueue<E> extends Ab
128              initialCapacity = 1;
129          queue = new E[initialCapacity + 1];
130  
131 +
132          if (initialElements instanceof Sorted) {
133              comparator = ((Sorted)initialElements).comparator();
134              for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
# Line 143 | Line 143 | public class PriorityQueue<E> extends Ab
143      // Queue Methods
144  
145      /**
146 <     * Remove and return the minimal element from this priority queue if
147 <     * it contains one or more elements, otherwise <tt>null</tt>.  The term
148 <     * <i>minimal</i> is defined according to this priority queue's order.
146 >     * Remove and return the minimal element from this priority queue
147 >     * if it contains one or more elements, otherwise return
148 >     * <tt>null</tt>.  The term <i>minimal</i> is defined according to
149 >     * this priority queue's order.
150       *
151       * @return the minimal element from this priority queue if it contains
152       *         one or more elements, otherwise <tt>null</tt>.
# Line 157 | Line 158 | public class PriorityQueue<E> extends Ab
158      }
159  
160      /**
161 <     * Return, but do not remove, the minimal element from the priority queue,
162 <     * or <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is
163 <     * defined according to this priority queue's order.  This method returns
164 <     * the same object reference that would be returned by by the
165 <     * <tt>poll</tt> method.  The two methods differ in that this method
166 <     * does not remove the element from the priority queue.
161 >     * Return, but do not remove, the minimal element from the
162 >     * priority queue, or return <tt>null</tt> if the queue is empty.
163 >     * The term <i>minimal</i> is defined according to this priority
164 >     * queue's order.  This method returns the same object reference
165 >     * that would be returned by by the <tt>poll</tt> method.  The two
166 >     * methods differ in that this method does not remove the element
167 >     * from the priority queue.
168       *
169       * @return the minimal element from this priority queue if it contains
170       *         one or more elements, otherwise <tt>null</tt>.
# Line 179 | Line 181 | public class PriorityQueue<E> extends Ab
181       * specified element (or equivalently, if this collection changed as a
182       * result of the call).
183       *
184 <     * @param o element to be removed from this collection, if present.
184 >     * @param element the element to be removed from this collection,
185 >     * if present.
186       * @return <tt>true</tt> if this collection changed as a result of the
187       *         call
188       * @throws ClassCastException if the specified element cannot be compared
# Line 211 | Line 214 | public class PriorityQueue<E> extends Ab
214  
215      /**
216       * Returns an iterator over the elements in this priority queue.  The
217 <     * first element returned by this iterator is the same element that
218 <     * would be returned by a call to <tt>peek</tt>.
219 <     *
217 >     * elements of the priority queue will be returned by this iterator in the
218 >     * order specified by the queue, which is to say the order they would be
219 >     * returned by repeated calls to <tt>poll</tt>.
220 >     *
221       * @return an <tt>Iterator</tt> over the elements in this priority queue.
222       */
223      public Iterator<E> iterator() {
# Line 225 | Line 229 | public class PriorityQueue<E> extends Ab
229           * Index (into queue array) of element to be returned by
230           * subsequent call to next.
231           */
232 <        int cursor = 1;
232 >        private int cursor = 1;
233  
234          /**
235           * Index of element returned by most recent call to next or
236           * previous.  Reset to 0 if this element is deleted by a call
237           * to remove.
238           */
239 <        int lastRet = 0;
239 >        private int lastRet = 0;
240  
241          /**
242           * The modCount value that the iterator believes that the backing
243           * List should have.  If this expectation is violated, the iterator
244           * has detected concurrent modification.
245           */
246 <        int expectedModCount = modCount;
246 >        private int expectedModCount = modCount;
247  
248          public boolean hasNext() {
249              return cursor <= size;
# Line 274 | Line 278 | public class PriorityQueue<E> extends Ab
278  
279      /**
280       * Returns the number of elements in this priority queue.
281 <     *
281 >     *
282       * @return the number of elements in this priority queue.
283       */
284      public int size() {
# Line 408 | Line 412 | public class PriorityQueue<E> extends Ab
412       * @return the comparator associated with this priority queue, or
413       *         <tt>null</tt> if it uses its elements' natural ordering.
414       */
415 <    Comparator<E> comparator() {
415 >    public Comparator comparator() {
416          return comparator;
417      }
418 +
419 +    /**
420 +     * Save the state of the instance to a stream (that
421 +     * is, serialize it).
422 +     *
423 +     * @serialData The length of the array backing the instance is
424 +     * emitted (int), followed by all of its elements (each an
425 +     * <tt>Object</tt>) in the proper order.
426 +     * @param s the stream
427 +     */
428 +    private synchronized void writeObject(java.io.ObjectOutputStream s)
429 +        throws java.io.IOException{
430 +        // Write out element count, and any hidden stuff
431 +        s.defaultWriteObject();
432 +
433 +        // Write out array length
434 +        s.writeInt(queue.length);
435 +
436 +        // Write out all elements in the proper order.
437 +        for (int i=0; i<size; i++)
438 +            s.writeObject(queue[i]);
439 +    }
440 +
441 +    /**
442 +     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
443 +     * deserialize it).
444 +     * @param s the stream
445 +     */
446 +    private synchronized void readObject(java.io.ObjectInputStream s)
447 +        throws java.io.IOException, ClassNotFoundException {
448 +        // Read in size, and any hidden stuff
449 +        s.defaultReadObject();
450 +
451 +        // Read in array length and allocate array
452 +        int arrayLength = s.readInt();
453 +        queue = new E[arrayLength];
454 +
455 +        // Read in all elements in the proper order.
456 +        for (int i=0; i<size; i++)
457 +            queue[i] = (E)s.readObject();
458 +    }
459 +
460   }

Diff Legend

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