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.7 by dl, Tue Jun 24 14:34:30 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>
32 < {
34 >                              implements Queue<E> {
35      private static final int DEFAULT_INITIAL_CAPACITY = 11;
36  
37      /**
# Line 65 | Line 67 | public class PriorityQueue<E> extends Ab
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 (using <tt>Comparable</tt>.)
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 74 | 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 (using <tt>Comparable</tt>.)
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 141 | 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 return <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 155 | 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 return <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 177 | 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 element the 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
191 <     *            with elements currently in the priority queue according
191 >     *            with elements currently in the priority queue according
192       *            to the priority queue's ordering.
193       * @throws NullPointerException if the specified element is null.
194       */
# Line 216 | Line 223 | public class PriorityQueue<E> extends Ab
223       * @return an <tt>Iterator</tt> over the elements in this priority queue.
224       */
225      public Iterator<E> iterator() {
226 <        return new Itr();
226 >        return new Itr();
227      }
228  
229      private class Itr implements Iterator<E> {
230 <        /**
231 <         * Index (into queue array) of element to be returned by
230 >        /**
231 >         * Index (into queue array) of element to be returned by
232           * subsequent call to next.
233 <         */
234 <        int cursor = 1;
233 >         */
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;
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;
242 <
243 <        public boolean hasNext() {
244 <            return cursor <= size;
245 <        }
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 >        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 >        private int expectedModCount = modCount;
249  
250 <        public E next() {
250 >        public boolean hasNext() {
251 >            return cursor <= size;
252 >        }
253 >
254 >        public E next() {
255              checkForComodification();
256              if (cursor > size)
257 <                throw new NoSuchElementException();
257 >                throw new NoSuchElementException();
258              E result = queue[cursor];
259              lastRet = cursor++;
260              return result;
261 <        }
261 >        }
262  
263 <        public void remove() {
264 <            if (lastRet == 0)
265 <                throw new IllegalStateException();
263 >        public void remove() {
264 >            if (lastRet == 0)
265 >                throw new IllegalStateException();
266              checkForComodification();
267  
268              PriorityQueue.this.remove(lastRet);
# Line 263 | Line 270 | public class PriorityQueue<E> extends Ab
270                  cursor--;
271              lastRet = 0;
272              expectedModCount = modCount;
273 <        }
273 >        }
274  
275 <        final void checkForComodification() {
276 <            if (modCount != expectedModCount)
277 <                throw new ConcurrentModificationException();
278 <        }
275 >        final void checkForComodification() {
276 >            if (modCount != expectedModCount)
277 >                throw new ConcurrentModificationException();
278 >        }
279      }
280  
281      /**
# Line 286 | Line 293 | public class PriorityQueue<E> extends Ab
293       * @param element the element to add.
294       * @return true
295       * @throws ClassCastException if the specified element cannot be compared
296 <     *            with elements currently in the priority queue according
296 >     *            with elements currently in the priority queue according
297       *            to the priority queue's ordering.
298       * @throws NullPointerException if the specified element is null.
299       */
# Line 405 | Line 412 | public class PriorityQueue<E> extends Ab
412       * <tt>null</tt> if it uses its elements' natural ordering.
413       *
414       * @return the comparator associated with this priority queue, or
415 <     *         <tt>null</tt> if it uses its elements' natural ordering.
415 >     *         <tt>null</tt> if it uses its elements' natural ordering.
416       */
417      Comparator comparator() {
418          return comparator;
# Line 418 | Line 425 | public class PriorityQueue<E> extends Ab
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();
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++)
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();
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++)
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  

Diff Legend

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