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.7 by dl, Tue Jun 24 14:34:30 2003 UTC vs.
Revision 1.11 by dholmes, Mon Jul 28 04:11:54 2003 UTC

# Line 3 | Line 3
3   /**
4   * An unbounded priority queue based on a priority heap.  This queue orders
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
6 > * specified in the same manner as {@link TreeSet} and {@link TreeMap}:
7 > * elements are ordered
8   * either according to their <i>natural order</i> (see {@link Comparable}), or
9   * according to a {@link Comparator}, depending on which constructor is used.
10 < * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the
11 < * minimal element with respect to the specified ordering.  If multiple
12 < * elements are tied for least value, no guarantees are made as to
13 < * which of these elements is returned.
10 > * The <em>head</em> of this queue is the least element with respect to the
11 > * specified ordering. If multiple elements are tied for least value, the
12 > * head is one of those elements. A priority queue does not permit
13 > * <tt>null</tt> elements.
14 > *
15 > * <p>The {@link #remove()} and {@link #poll()} methods remove and
16 > * return the head of the queue.
17 > *
18 > * <p>The {@link #element()} and {@link #peek()} methods return, but do
19 > * not delete, the head of the queue.
20   *
21   * <p>A priority queue has a <i>capacity</i>.  The capacity is the
22   * size of the array used internally to store the elements on the
# Line 17 | Line 24
24   * elements are added to a priority queue, its capacity grows
25   * automatically.  The details of the growth policy are not specified.
26   *
27 < *<p>Implementation note: this implementation provides O(log(n)) time
28 < *for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
29 < *<tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
30 < *<tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
31 < *constant time for the retrieval methods (<tt>peek</tt>,
32 < *<tt>element</tt>, and <tt>size</tt>).
27 > * <p>Implementation note: this implementation provides O(log(n)) time
28 > * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
29 > * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
30 > * <tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
31 > * constant time for the retrieval methods (<tt>peek</tt>,
32 > * <tt>element</tt>, and <tt>size</tt>).
33   *
34   * <p>This class is a member of the
35   * <a href="{@docRoot}/../guide/collections/index.html">
# Line 31 | Line 38
38   * @author Josh Bloch
39   */
40   public class PriorityQueue<E> extends AbstractQueue<E>
41 <                              implements Queue<E> {
41 >    implements Queue<E>, Sorted, java.io.Serializable {
42 >
43      private static final int DEFAULT_INITIAL_CAPACITY = 11;
44  
45      /**
# Line 67 | Line 75 | public class PriorityQueue<E> extends Ab
75      private transient int modCount = 0;
76  
77      /**
78 <     * Create a new priority queue with the default initial capacity
78 >     * Create a <tt>PriorityQueue</tt> with the default initial capacity
79       * (11) that orders its elements according to their natural
80       * ordering (using <tt>Comparable</tt>.)
81       */
82      public PriorityQueue() {
83 <        this(DEFAULT_INITIAL_CAPACITY);
83 >        this(DEFAULT_INITIAL_CAPACITY, null);
84      }
85  
86      /**
87 <     * Create a new priority queue with the specified initial capacity
87 >     * Create a <tt>PriorityQueue</tt> with the specified initial capacity
88       * that orders its elements according to their natural ordering
89       * (using <tt>Comparable</tt>.)
90       *
# Line 87 | Line 95 | public class PriorityQueue<E> extends Ab
95      }
96  
97      /**
98 <     * Create a new priority queue with the specified initial capacity (11)
98 >     * Create a <tt>PriorityQueue</tt> with the specified initial capacity
99       * that orders its elements according to the specified comparator.
100       *
101       * @param initialCapacity the initial capacity for this priority queue.
102       * @param comparator the comparator used to order this priority queue.
103 +     * If <tt>null</tt> then the order depends on the elements' natural
104 +     * ordering.
105       */
106      public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
107          if (initialCapacity < 1)
108              initialCapacity = 1;
109 <        queue = new E[initialCapacity + 1];
109 >        queue = (E[]) new Object[initialCapacity + 1];
110          this.comparator = comparator;
111      }
112  
113      /**
114 <     * Create a new priority queue containing the elements in the specified
114 >     * Create a <tt>PriorityQueue</tt> containing the elements in the specified
115       * collection.  The priority queue has an initial capacity of 110% of the
116       * size of the specified collection. If the specified collection
117       * implements the {@link Sorted} interface, the priority queue will be
# Line 125 | Line 135 | public class PriorityQueue<E> extends Ab
135                                              Integer.MAX_VALUE - 1);
136          if (initialCapacity < 1)
137              initialCapacity = 1;
138 <        queue = new E[initialCapacity + 1];
129 <
130 <        /* Commented out to compile with generics compiler
138 >        queue = (E[]) new Object[initialCapacity + 1];
139  
140          if (initialElements instanceof Sorted) {
141              comparator = ((Sorted)initialElements).comparator();
142              for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
143                  queue[++size] = i.next();
144          } else {
137 –        */
138 –        {
145              comparator = null;
146              for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
147                  add(i.next());
# Line 145 | Line 151 | public class PriorityQueue<E> extends Ab
151      // Queue Methods
152  
153      /**
154 <     * 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.
154 >     * Add the specified element to this priority queue.
155       *
156 <     * @return the minimal element from this priority queue if it contains
157 <     *         one or more elements, otherwise <tt>null</tt>.
156 >     * @param element the element to add.
157 >     * @return <tt>true</tt>
158 >     * @throws ClassCastException if the specified element cannot be compared
159 >     * with elements currently in the priority queue according
160 >     * to the priority queue's ordering.
161 >     * @throws NullPointerException if the specified element is null.
162       */
163 +    public boolean offer(E element) {
164 +        if (element == null)
165 +            throw new NullPointerException();
166 +        modCount++;
167 +        ++size;
168 +
169 +        // Grow backing store if necessary
170 +        while (size >= queue.length) {
171 +            E[] newQueue = (E[]) new Object[2 * queue.length];
172 +            System.arraycopy(queue, 0, newQueue, 0, queue.length);
173 +            queue = newQueue;
174 +        }
175 +
176 +        queue[size] = element;
177 +        fixUp(size);
178 +        return true;
179 +    }
180 +
181      public E poll() {
182          if (size == 0)
183              return null;
184          return remove(1);
185      }
186  
162 –    /**
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>.
173 –     */
187      public E peek() {
188          return queue[1];
189      }
190  
191      // Collection Methods
192  
193 +    // these first two override just to get the throws docs
194 +
195      /**
196 <     * Removes a single instance of the specified element from this priority
182 <     * queue, if it is present.  Returns true if this collection contained the
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,
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
192 <     *            to the priority queue's ordering.
193 <     * @throws NullPointerException if the specified element is null.
196 >     * @throws NullPointerException if the specified element is <tt>null</tt>.
197       */
198 <    public boolean remove(Object element) {
199 <        if (element == null)
198 >    public boolean add(E element) {
199 >        return super.add(element);
200 >    }
201 >
202 >    /**
203 >     * @throws NullPointerException if any element is <tt>null</tt>.
204 >     */
205 >    public boolean addAll(Collection c) {
206 >        return super.addAll(c);
207 >    }
208 >
209 >    /**
210 >     * @throws NullPointerException if the specified element is <tt>null</tt>.
211 >     */
212 >    public boolean remove(E o) {
213 >        if (o == null)
214              throw new NullPointerException();
215  
216          if (comparator == null) {
217              for (int i = 1; i <= size; i++) {
218 <                if (((Comparable)queue[i]).compareTo(element) == 0) {
218 >                if (((Comparable)queue[i]).compareTo(o) == 0) {
219                      remove(i);
220                      return true;
221                  }
222              }
223          } else {
224              for (int i = 1; i <= size; i++) {
225 <                if (comparator.compare(queue[i], (E) element) == 0) {
225 >                if (comparator.compare(queue[i], o) == 0) {
226                      remove(i);
227                      return true;
228                  }
# Line 219 | Line 236 | public class PriorityQueue<E> extends Ab
236       * elements of the priority queue will be returned by this iterator in the
237       * order specified by the queue, which is to say the order they would be
238       * returned by repeated calls to <tt>poll</tt>.
239 <     *
239 >     *
240       * @return an <tt>Iterator</tt> over the elements in this priority queue.
241       */
242      public Iterator<E> iterator() {
# Line 280 | Line 297 | public class PriorityQueue<E> extends Ab
297  
298      /**
299       * Returns the number of elements in this priority queue.
300 <     *
300 >     *
301       * @return the number of elements in this priority queue.
302       */
303      public int size() {
# Line 288 | Line 305 | public class PriorityQueue<E> extends Ab
305      }
306  
307      /**
291 –     * Add the specified element to this priority queue.
292 –     *
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
297 –     *            to the priority queue's ordering.
298 –     * @throws NullPointerException if the specified element is null.
299 –     */
300 –    public boolean offer(E element) {
301 –        if (element == null)
302 –            throw new NullPointerException();
303 –        modCount++;
304 –
305 –        // Grow backing store if necessary
306 –        if (++size == queue.length) {
307 –            E[] newQueue = new E[2 * queue.length];
308 –            System.arraycopy(queue, 0, newQueue, 0, size);
309 –            queue = newQueue;
310 –        }
311 –
312 –        queue[size] = element;
313 –        fixUp(size);
314 –        return true;
315 –    }
316 –
317 –    /**
308       * Remove all elements from the priority queue.
309       */
310      public void clear() {
# Line 407 | Line 397 | public class PriorityQueue<E> extends Ab
397          }
398      }
399  
400 <    /**
411 <     * Returns the comparator associated with this priority queue, or
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.
416 <     */
417 <    Comparator comparator() {
400 >    public Comparator comparator() {
401          return comparator;
402      }
403  
# Line 452 | Line 435 | public class PriorityQueue<E> extends Ab
435  
436          // Read in array length and allocate array
437          int arrayLength = s.readInt();
438 <        queue = new E[arrayLength];
438 >        queue = (E[]) new Object[arrayLength];
439  
440          // Read in all elements in the proper order.
441          for (int i=0; i<size; i++)
# Line 460 | Line 443 | public class PriorityQueue<E> extends Ab
443      }
444  
445   }
446 +

Diff Legend

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