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.38 by dl, Mon Sep 1 12:23:28 2003 UTC vs.
Revision 1.50 by dl, Wed Jun 2 23:45:46 2004 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
8   package java.util;
9  
10   /**
11 < * An unbounded priority {@linkplain Queue queue} based on a priority heap.
12 < * This queue orders elements according to an order specified at construction
13 < * time, which is specified in the same manner as {@link java.util.TreeSet}
14 < * and {@link java.util.TreeMap}: elements are ordered either according to
15 < * their <i>natural order</i> (see {@link Comparable}), or according to a
16 < * {@link java.util.Comparator}, depending on which constructor is used.
17 < * <p>The <em>head</em> of this queue is the <em>least</em> element with
18 < * respect to the specified ordering.  If multiple elements are tied for least
19 < * value, the head is one of those elements. A priority queue does not permit
20 < * <tt>null</tt> elements.
11 > * An unbounded priority {@linkplain Queue queue} based on a priority
12 > * heap.  This queue orders elements according to an order specified
13 > * at construction time, which is specified either according to their
14 > * <i>natural order</i> (see {@link Comparable}), or according to a
15 > * {@link java.util.Comparator}, depending on which constructor is
16 > * used. A priority queue does not permit <tt>null</tt> elements.
17 > * A priority queue relying on natural ordering also does not
18 > * permit insertion of non-comparable objects (doing so may result
19 > * in <tt>ClassCastException</tt>).
20   *
21 < * <p>The {@link #remove()} and {@link #poll()} methods remove and
22 < * return the head of the queue.
21 > * <p>The <em>head</em> of this queue is the <em>least</em> element
22 > * with respect to the specified ordering.  If multiple elements are
23 > * tied for least value, the head is one of those elements -- ties are
24 > * broken arbitrarily.  The queue retrieval operations <tt>poll</tt>,
25 > * <tt>remove</tt>, <tt>peek</tt>, and <tt>element</tt> access the
26 > * element at the head of the queue.
27   *
28 < * <p>The {@link #element()} and {@link #peek()} methods return, but do
29 < * not delete, the head of the queue.
28 > * <p>A priority queue is unbounded, but has an internal
29 > * <i>capacity</i> governing the size of an array used to store the
30 > * elements on the queue.  It is always at least as large as the queue
31 > * size.  As elements are added to a priority queue, its capacity
32 > * grows automatically.  The details of the growth policy are not
33 > * specified.
34   *
35 < * <p>A priority queue has a <i>capacity</i>.  The capacity is the
36 < * size of the array used internally to store the elements on the
37 < * queue.
38 < * It is always at least as large as the queue size.  As
39 < * elements are added to a priority queue, its capacity grows
33 < * automatically.  The details of the growth policy are not specified.
34 < *
35 < * <p>The Iterator provided in method {@link #iterator()} is <em>not</em>
35 > * <p>This class and its iterator implement all of the
36 > * <em>optional</em> methods of the {@link Collection} and {@link
37 > * Iterator} interfaces.
38 > * The
39 > * Iterator provided in method {@link #iterator()} is <em>not</em>
40   * guaranteed to traverse the elements of the PriorityQueue in any
41   * particular order. If you need ordered traversal, consider using
42   * <tt>Arrays.sort(pq.toArray())</tt>.
# Line 57 | Line 61 | package java.util;
61   * @since 1.5
62   * @version %I%, %G%
63   * @author Josh Bloch
64 + * @param <E> the type of elements held in this collection
65   */
66   public class PriorityQueue<E> extends AbstractQueue<E>
67 <    implements Queue<E>, java.io.Serializable {
67 >    implements java.io.Serializable {
68  
69      private static final long serialVersionUID = -7720805057305804111L;
70  
# Line 196 | Line 201 | public class PriorityQueue<E> extends Ab
201      public PriorityQueue(Collection<? extends E> c) {
202          initializeArray(c);
203          if (c instanceof SortedSet) {
204 <            // @fixme double-cast workaround for compiler
200 <            SortedSet<? extends E> s = (SortedSet<? extends E>) (SortedSet)c;
204 >            SortedSet<? extends E> s = (SortedSet<? extends E>)c;
205              comparator = (Comparator<? super E>)s.comparator();
206              fillFromSorted(s);
207          } else if (c instanceof PriorityQueue) {
# Line 277 | Line 281 | public class PriorityQueue<E> extends Ab
281      }
282              
283  
280 –    // Queue Methods
281 –
284      /**
285 <     * Add the specified element to this priority queue.
285 >     * Inserts the specified element into this priority queue.
286       *
287       * @return <tt>true</tt>
288       * @throws ClassCastException if the specified element cannot be compared
# Line 303 | Line 305 | public class PriorityQueue<E> extends Ab
305          return true;
306      }
307  
308 <    public E poll() {
308 >    public E peek() {
309          if (size == 0)
310              return null;
309 –        return remove();
310 –    }
311 –
312 –    public E peek() {
311          return (E) queue[1];
312      }
313  
# Line 320 | Line 318 | public class PriorityQueue<E> extends Ab
318       * @return <tt>true</tt> (as per the general contract of
319       * <tt>Collection.add</tt>).
320       *
321 <     * @throws NullPointerException {@inheritDoc}
321 >     * @throws NullPointerException if the specified element is <tt>null</tt>.
322       * @throws ClassCastException if the specified element cannot be compared
323       * with elements currently in the priority queue according
324       * to the priority queue's ordering.
325       */
326      public boolean add(E o) {
327 <        return super.add(o);
330 <    }
331 <
332 <  
333 <    /**
334 <     * Adds all of the elements in the specified collection to this queue.
335 <     * The behavior of this operation is undefined if
336 <     * the specified collection is modified while the operation is in
337 <     * progress.  (This implies that the behavior of this call is undefined if
338 <     * the specified collection is this queue, and this queue is nonempty.)
339 <     * <p>
340 <     * This implementation iterates over the specified collection, and adds
341 <     * each object returned by the iterator to this collection, in turn.
342 <     * @throws NullPointerException {@inheritDoc}
343 <     * @throws ClassCastException if any element cannot be compared
344 <     * with elements currently in the priority queue according
345 <     * to the priority queue's ordering.
346 <     */
347 <    public boolean addAll(Collection<? extends E> c) {
348 <        return super.addAll(c);
327 >        return offer(o);
328      }
329  
351 –
330      /**
331       * Removes a single instance of the specified element from this
332 <     * queue, if it is present.  More formally,
355 <     * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
356 <     * o.equals(e))</tt>, if the queue contains one or more such
357 <     * elements.  Returns <tt>true</tt> if the queue contained the
358 <     * specified element (or equivalently, if the queue changed as a
359 <     * result of the call).
360 <     *
361 <     * <p>This implementation iterates over the queue looking for the
362 <     * specified element.  If it finds the element, it removes the element
363 <     * from the queue using the iterator's remove method.<p>
364 <     *
332 >     * queue, if it is present.
333       */
334      public boolean remove(Object o) {
335          if (o == null)
# Line 494 | Line 462 | public class PriorityQueue<E> extends Ab
462      }
463  
464      /**
465 <     * Remove all elements from the priority queue.
465 >     * Removes all elements from the priority queue.
466 >     * The queue will be empty after this call returns.
467       */
468      public void clear() {
469          modCount++;
# Line 506 | Line 475 | public class PriorityQueue<E> extends Ab
475          size = 0;
476      }
477  
478 <    /**
510 <     * Removes and returns the first element from queue.
511 <     */
512 <    public E remove() {
478 >    public E poll() {
479          if (size == 0)
480 <            throw new NoSuchElementException();
480 >            return null;
481          modCount++;
482  
483          E result = (E) queue[1];
# Line 657 | Line 623 | public class PriorityQueue<E> extends Ab
623          s.writeInt(queue.length);
624  
625          // Write out all elements in the proper order.
626 <        for (int i=0; i<size; i++)
626 >        for (int i=1; i<=size; i++)
627              s.writeObject(queue[i]);
628      }
629  
# Line 676 | Line 642 | public class PriorityQueue<E> extends Ab
642          queue = new Object[arrayLength];
643  
644          // Read in all elements in the proper order.
645 <        for (int i=0; i<size; i++)
645 >        for (int i=1; i<=size; i++)
646              queue[i] = (E) s.readObject();
647      }
648  

Diff Legend

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