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.6 by brian, Mon Jun 23 02:26:15 2003 UTC vs.
Revision 1.9 by dl, Sun Jul 13 22:51:22 2003 UTC

# Line 11 | Line 11
11   * elements are tied for least value, no guarantees are made as to
12   * which of these elements is returned.
13   *
14 < * <p>A priority queue has a <i>capacity</i>.  The capacity is the size of
15 < * the array used internally 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 queue,
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 insertion methods (<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(Object)</tt> methods; and constant time for the retrieval methods (<tt>peek</tt>,
24 < * <tt>element</tt>, and <tt>size</tt>).
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      /**
# Line 65 | Line 68 | public class PriorityQueue<E> extends Ab
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 (using <tt>Comparable</tt>.)
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 74 | 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 (using <tt>Comparable</tt>.)
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 123 | Line 128 | public class PriorityQueue<E> extends Ab
128              initialCapacity = 1;
129          queue = new E[initialCapacity + 1];
130  
126 –        /* Commented out to compile with generics compiler
131  
132          if (initialElements instanceof Sorted) {
133              comparator = ((Sorted)initialElements).comparator();
134              for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
135                  queue[++size] = i.next();
136          } else {
133 –        */
134 –        {
137              comparator = null;
138              for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
139                  add(i.next());
# Line 141 | 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 return <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 155 | 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 return <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 177 | 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 element the 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
189 <     *            with elements currently in the priority queue according
189 >     *            with elements currently in the priority queue according
190       *            to the priority queue's ordering.
191       * @throws NullPointerException if the specified element is null.
192       */
# Line 216 | Line 221 | public class PriorityQueue<E> extends Ab
221       * @return an <tt>Iterator</tt> over the elements in this priority queue.
222       */
223      public Iterator<E> iterator() {
224 <        return new Itr();
224 >        return new Itr();
225      }
226  
227      private class Itr implements Iterator<E> {
228 <        /**
229 <         * Index (into queue array) of element to be returned by
228 >        /**
229 >         * Index (into queue array) of element to be returned by
230           * subsequent call to next.
231 <         */
232 <        int cursor = 1;
231 >         */
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;
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;
242 <
243 <        public boolean hasNext() {
244 <            return cursor <= size;
245 <        }
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 >        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 >        private int expectedModCount = modCount;
247  
248 <        public E next() {
248 >        public boolean hasNext() {
249 >            return cursor <= size;
250 >        }
251 >
252 >        public E next() {
253              checkForComodification();
254              if (cursor > size)
255 <                throw new NoSuchElementException();
255 >                throw new NoSuchElementException();
256              E result = queue[cursor];
257              lastRet = cursor++;
258              return result;
259 <        }
259 >        }
260  
261 <        public void remove() {
262 <            if (lastRet == 0)
263 <                throw new IllegalStateException();
261 >        public void remove() {
262 >            if (lastRet == 0)
263 >                throw new IllegalStateException();
264              checkForComodification();
265  
266              PriorityQueue.this.remove(lastRet);
# Line 263 | Line 268 | public class PriorityQueue<E> extends Ab
268                  cursor--;
269              lastRet = 0;
270              expectedModCount = modCount;
271 <        }
271 >        }
272  
273 <        final void checkForComodification() {
274 <            if (modCount != expectedModCount)
275 <                throw new ConcurrentModificationException();
276 <        }
273 >        final void checkForComodification() {
274 >            if (modCount != expectedModCount)
275 >                throw new ConcurrentModificationException();
276 >        }
277      }
278  
279      /**
# Line 286 | Line 291 | public class PriorityQueue<E> extends Ab
291       * @param element the element to add.
292       * @return true
293       * @throws ClassCastException if the specified element cannot be compared
294 <     *            with elements currently in the priority queue according
294 >     *            with elements currently in the priority queue according
295       *            to the priority queue's ordering.
296       * @throws NullPointerException if the specified element is null.
297       */
# Line 294 | Line 299 | public class PriorityQueue<E> extends Ab
299          if (element == null)
300              throw new NullPointerException();
301          modCount++;
302 +        ++size;
303  
304          // Grow backing store if necessary
305 <        if (++size == queue.length) {
305 >        while (size >= queue.length) {
306              E[] newQueue = new E[2 * queue.length];
307 <            System.arraycopy(queue, 0, newQueue, 0, size);
307 >            System.arraycopy(queue, 0, newQueue, 0, queue.length);
308              queue = newQueue;
309          }
310  
# Line 405 | Line 411 | public class PriorityQueue<E> extends Ab
411       * <tt>null</tt> if it uses its elements' natural ordering.
412       *
413       * @return the comparator associated with this priority queue, or
414 <     *         <tt>null</tt> if it uses its elements' natural ordering.
414 >     *         <tt>null</tt> if it uses its elements' natural ordering.
415       */
416 <    Comparator comparator() {
416 >    public Comparator comparator() {
417          return comparator;
418      }
419  
# Line 418 | Line 424 | public class PriorityQueue<E> extends Ab
424       * @serialData The length of the array backing the instance is
425       * emitted (int), followed by all of its elements (each an
426       * <tt>Object</tt>) in the proper order.
427 +     * @param s the stream
428       */
429      private synchronized void writeObject(java.io.ObjectOutputStream s)
430          throws java.io.IOException{
431 <        // Write out element count, and any hidden stuff
432 <        s.defaultWriteObject();
431 >        // Write out element count, and any hidden stuff
432 >        s.defaultWriteObject();
433  
434          // Write out array length
435          s.writeInt(queue.length);
436  
437 <        // Write out all elements in the proper order.
438 <        for (int i=0; i<size; i++)
437 >        // Write out all elements in the proper order.
438 >        for (int i=0; i<size; i++)
439              s.writeObject(queue[i]);
440      }
441  
442      /**
443       * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
444       * deserialize it).
445 +     * @param s the stream
446       */
447      private synchronized void readObject(java.io.ObjectInputStream s)
448          throws java.io.IOException, ClassNotFoundException {
449 <        // Read in size, and any hidden stuff
450 <        s.defaultReadObject();
449 >        // Read in size, and any hidden stuff
450 >        s.defaultReadObject();
451  
452          // Read in array length and allocate array
453          int arrayLength = s.readInt();
454          queue = new E[arrayLength];
455  
456 <        // Read in all elements in the proper order.
457 <        for (int i=0; i<size; i++)
456 >        // Read in all elements in the proper order.
457 >        for (int i=0; i<size; i++)
458              queue[i] = (E)s.readObject();
459      }
460  

Diff Legend

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