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.19 by tim, Mon Aug 4 16:14:48 2003 UTC vs.
Revision 1.23 by dholmes, Wed Aug 6 01:57:53 2003 UTC

# Line 1 | Line 1
1   package java.util;
2  
3   /**
4 < * A priority queue based on a priority heap.  This queue orders
4 > * An unbounded priority {@linkplain Queue queue} based on a priority heap.  
5 > * This queue orders
6   * elements according to an order specified at construction time, which is
7   * specified in the same manner as {@link java.util.TreeSet} and
8   * {@link java.util.TreeMap}: elements are ordered
# Line 22 | Line 23
23   *
24   * <p>A priority queue has a <i>capacity</i>.  The capacity is the
25   * size of the array used internally to store the elements on the
26 < * queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.
26 > * queue.
27   * It is always at least as large as the queue size.  As
28   * elements are added to a priority queue, its capacity grows
29   * automatically.  The details of the growth policy are not specified.
# Line 41 | Line 42
42   * @author Josh Bloch
43   */
44   public class PriorityQueue<E> extends AbstractQueue<E>
45 <    implements Sorted, Queue<E>, java.io.Serializable {
45 >    implements Queue<E>, java.io.Serializable {
46  
47      private static final int DEFAULT_INITIAL_CAPACITY = 11;
48  
# Line 78 | Line 79 | public class PriorityQueue<E> extends Ab
79      private transient int modCount = 0;
80  
81      /**
82 <     * Create a <tt>PriorityQueue</tt> with the default initial capacity
82 >     * Creates a <tt>PriorityQueue</tt> with the default initial capacity
83       * (11) that orders its elements according to their natural
84       * ordering (using <tt>Comparable</tt>.)
85       */
# Line 87 | Line 88 | public class PriorityQueue<E> extends Ab
88      }
89  
90      /**
91 <     * Create a <tt>PriorityQueue</tt> with the specified initial capacity
91 >     * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
92       * that orders its elements according to their natural ordering
93       * (using <tt>Comparable</tt>.)
94       *
95       * @param initialCapacity the initial capacity for this priority queue.
96 +     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
97 +     * than 1
98       */
99      public PriorityQueue(int initialCapacity) {
100          this(initialCapacity, null);
101      }
102  
103      /**
104 <     * Create a <tt>PriorityQueue</tt> with the specified initial capacity
104 >     * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
105       * that orders its elements according to the specified comparator.
106       *
107       * @param initialCapacity the initial capacity for this priority queue.
# Line 108 | Line 111 | public class PriorityQueue<E> extends Ab
111       * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
112       * than 1
113       */
114 <    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
114 >    public PriorityQueue(int initialCapacity,
115 >                         Comparator<? super E> comparator) {
116          if (initialCapacity < 1)
117              throw new IllegalArgumentException();
118          this.queue = new Object[initialCapacity + 1];
# Line 116 | Line 120 | public class PriorityQueue<E> extends Ab
120      }
121  
122      /**
123 <     * Create a <tt>PriorityQueue</tt> containing the elements in the specified
124 <     * collection.  The priority queue has an initial capacity of 110% of the
121 <     * size of the specified collection (bounded by
122 <     * <tt>Integer.MAX_VALUE-1</tt>); or 1 if the collection is empty.
123 <     * If the specified collection
124 <     * implements the {@link Sorted} interface, the priority queue will be
125 <     * sorted according to the same comparator, or according to its elements'
126 <     * natural order if the collection is sorted according to its elements'
127 <     * natural order.  If the specified collection does not implement
128 <     * <tt>Sorted</tt>, the priority queue is ordered according to
129 <     * its elements' natural order.
130 <     *
131 <     * @param c the collection whose elements are to be placed
132 <     *        into this priority queue.
133 <     * @throws ClassCastException if elements of the specified collection
134 <     *         cannot be compared to one another according to the priority
135 <     *         queue's ordering.
136 <     * @throws NullPointerException if <tt>c</tt> or any element within it
137 <     * is <tt>null</tt>
123 >     * Common code to initialize underlying queue array across
124 >     * constructors below.
125       */
126 <    public PriorityQueue(Collection<? extends E> c) {
126 >    private void initializeArray(Collection<? extends E> c) {
127          int sz = c.size();
128          int initialCapacity = (int)Math.min((sz * 110L) / 100,
129                                              Integer.MAX_VALUE - 1);
# Line 144 | Line 131 | public class PriorityQueue<E> extends Ab
131              initialCapacity = 1;
132  
133          this.queue = new Object[initialCapacity + 1];
134 +    }
135  
136 <        // FIXME: if c is larger than Integer.MAX_VALUE we'll
137 <        // overflow the array
136 >    /**
137 >     * Initially fill elements of the queue array under the
138 >     * knowledge that it is sorted or is another PQ, in which
139 >     * case we can just place the elements without fixups.
140 >     */
141 >    private void fillFromSorted(Collection<? extends E> c) {
142 >        for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
143 >            queue[++size] = i.next();
144 >    }
145  
151 –        if (c instanceof Sorted) {
152 –            comparator = (Comparator<? super E>)((Sorted)c).comparator();
153 –        } else {
154 –            comparator = null;
155 –        }
146  
147 +    /**
148 +     * Initially fill elements of the queue array that is
149 +     * not to our knowledge sorted, so we must add them
150 +     * one by one.
151 +     */
152 +    private void fillFromUnsorted(Collection<? extends E> c) {
153          for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
154              add(i.next());
155      }
156  
157 +    /**
158 +     * Creates a <tt>PriorityQueue</tt> containing the elements in the
159 +     * specified collection.  The priority queue has an initial
160 +     * capacity of 110% of the size of the specified collection or 1
161 +     * if the collection is empty.  If the specified collection is an
162 +     * instance of a {@link SortedSet} or is another
163 +     * <tt>PriorityQueue</tt>, the priority queue will be sorted
164 +     * according to the same comparator, or according to its elements'
165 +     * natural order if the collection is sorted according to its
166 +     * elements' natural order.  Otherwise, the priority queue is
167 +     * ordered according to its elements' natural order.
168 +     *
169 +     * @param c the collection whose elements are to be placed
170 +     *        into this priority queue.
171 +     * @throws ClassCastException if elements of the specified collection
172 +     *         cannot be compared to one another according to the priority
173 +     *         queue's ordering.
174 +     * @throws NullPointerException if <tt>c</tt> or any element within it
175 +     * is <tt>null</tt>
176 +     */
177 +    public PriorityQueue(Collection<? extends E> c) {
178 +        initializeArray(c);
179 +        if (c instanceof SortedSet<? extends E>) {
180 +            SortedSet<? extends E> s = (SortedSet<? extends E>) c;
181 +            comparator = (Comparator<? super E>)s.comparator();
182 +            fillFromSorted(s);
183 +        }
184 +        else if (c instanceof PriorityQueue<? extends E>) {
185 +            PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c;
186 +            comparator = (Comparator<? super E>)s.comparator();
187 +            fillFromSorted(s);
188 +        }
189 +        else {
190 +            comparator = null;
191 +            fillFromUnsorted(c);
192 +        }
193 +    }
194 +
195 +    /**
196 +     * Creates a <tt>PriorityQueue</tt> containing the elements in the
197 +     * specified collection.  The priority queue has an initial
198 +     * capacity of 110% of the size of the specified collection or 1
199 +     * if the collection is empty.  This priority queue will be sorted
200 +     * according to the same comparator as the given collection, or
201 +     * according to its elements' natural order if the collection is
202 +     * sorted according to its elements' natural order.
203 +     *
204 +     * @param c the collection whose elements are to be placed
205 +     *        into this priority queue.
206 +     * @throws ClassCastException if elements of the specified collection
207 +     *         cannot be compared to one another according to the priority
208 +     *         queue's ordering.
209 +     * @throws NullPointerException if <tt>c</tt> or any element within it
210 +     * is <tt>null</tt>
211 +     */
212 +    public PriorityQueue(PriorityQueue<? extends E> c) {
213 +        initializeArray(c);
214 +        comparator = (Comparator<? super E>)c.comparator();
215 +        fillFromSorted(c);
216 +    }
217 +
218 +    /**
219 +     * Creates a <tt>PriorityQueue</tt> containing the elements in the
220 +     * specified collection.  The priority queue has an initial
221 +     * capacity of 110% of the size of the specified collection or 1
222 +     * if the collection is empty.  This priority queue will be sorted
223 +     * according to the same comparator as the given collection, or
224 +     * according to its elements' natural order if the collection is
225 +     * sorted according to its elements' natural order.
226 +     *
227 +     * @param c the collection whose elements are to be placed
228 +     *        into this priority queue.
229 +     * @throws ClassCastException if elements of the specified collection
230 +     *         cannot be compared to one another according to the priority
231 +     *         queue's ordering.
232 +     * @throws NullPointerException if <tt>c</tt> or any element within it
233 +     * is <tt>null</tt>
234 +     */
235 +    public PriorityQueue(SortedSet<? extends E> c) {
236 +        initializeArray(c);
237 +        comparator = (Comparator<? super E>)c.comparator();
238 +        fillFromSorted(c);
239 +    }
240 +
241 +    /**
242 +     * Resize array, if necessary, to be able to hold given index
243 +     */
244 +    private void grow(int index) {
245 +        int newlen = queue.length;
246 +        if (index < newlen) // don't need to grow
247 +            return;
248 +        if (index == Integer.MAX_VALUE)
249 +            throw new OutOfMemoryError();
250 +        while (newlen <= index) {
251 +            if (newlen >= Integer.MAX_VALUE / 2)  // avoid overflow
252 +                newlen = Integer.MAX_VALUE;
253 +            else
254 +                newlen <<= 2;
255 +        }
256 +        Object[] newQueue = new Object[newlen];
257 +        System.arraycopy(queue, 0, newQueue, 0, queue.length);
258 +        queue = newQueue;
259 +    }
260 +            
261      // Queue Methods
262  
263 +
264 +
265      /**
266       * Add the specified element to this priority queue.
267       *
# Line 176 | Line 278 | public class PriorityQueue<E> extends Ab
278          ++size;
279  
280          // Grow backing store if necessary
281 <        // FIXME: watch for overflow
282 <        // FIXME: what if we're full?
181 <        while (size >= queue.length) {
182 <            Object[] newQueue = new Object[2 * queue.length];
183 <            System.arraycopy(queue, 0, newQueue, 0, queue.length);
184 <            queue = newQueue;
185 <        }
281 >        if (size >= queue.length)
282 >            grow(size);
283  
284          queue[size] = o;
285          fixUp(size);
# Line 199 | Line 296 | public class PriorityQueue<E> extends Ab
296          return (E) queue[1];
297      }
298  
299 <    // Collection Methods
203 <
204 <    // these first two override just to get the throws docs
299 >    // Collection Methods - the first two override to update docs
300  
301      /**
302 <     * @throws NullPointerException if the specified element is <tt>null</tt>.
302 >     * Adds the specified element to this queue.
303 >     * @return <tt>true</tt> (as per the general contract of
304 >     * <tt>Collection.add</tt>).
305 >     *
306 >     * @throws NullPointerException {@inheritDoc}
307       * @throws ClassCastException if the specified element cannot be compared
308       * with elements currently in the priority queue according
309       * to the priority queue's ordering.
# Line 213 | Line 312 | public class PriorityQueue<E> extends Ab
312          return super.add(o);
313      }
314  
315 +  
316      /**
317 +     * Adds all of the elements in the specified collection to this queue.
318 +     * The behavior of this operation is undefined if
319 +     * the specified collection is modified while the operation is in
320 +     * progress.  (This implies that the behavior of this call is undefined if
321 +     * the specified collection is this queue, and this queue is nonempty.)
322 +     * <p>
323 +     * This implementation iterates over the specified collection, and adds
324 +     * each object returned by the iterator to this collection, in turn.
325 +     * @throws NullPointerException {@inheritDoc}
326       * @throws ClassCastException if any element cannot be compared
327       * with elements currently in the priority queue according
328       * to the priority queue's ordering.
220 –     * @throws NullPointerException if <tt>c</tt> or any element in <tt>c</tt>
221 –     * is <tt>null</tt>
329       */
330      public boolean addAll(Collection<? extends E> c) {
331          return super.addAll(c);
332      }
333  
334 +
335 + /**
336 +     * Removes a single instance of the specified element from this
337 +     * queue, if it is present.  More formally,
338 +     * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
339 +     * o.equals(e))</tt>, if the queue contains one or more such
340 +     * elements.  Returns <tt>true</tt> if the queue contained the
341 +     * specified element (or equivalently, if the queue changed as a
342 +     * result of the call).
343 +     *
344 +     * <p>This implementation iterates over the queue looking for the
345 +     * specified element.  If it finds the element, it removes the element
346 +     * from the queue using the iterator's remove method.<p>
347 +     *
348 +     */
349      public boolean remove(Object o) {
350          if (o == null)
351              return false;
# Line 246 | Line 368 | public class PriorityQueue<E> extends Ab
368          return false;
369      }
370  
371 +    /**
372 +     * Returns an iterator over the elements in this queue. The iterator
373 +     * does not return the elements in any particular order.
374 +     *
375 +     * @return an iterator over the elements in this queue.
376 +     */
377      public Iterator<E> iterator() {
378          return new Itr();
379      }
# Line 302 | Line 430 | public class PriorityQueue<E> extends Ab
430          }
431      }
432  
305 –    /**
306 –     * Returns the number of elements in this priority queue.
307 –     *
308 –     * @return the number of elements in this priority queue.
309 –     */
433      public int size() {
434          return size;
435      }
# Line 404 | Line 527 | public class PriorityQueue<E> extends Ab
527          }
528      }
529  
530 +
531 +    /**
532 +     * Returns the comparator used to order this collection, or <tt>null</tt>
533 +     * if this collection is sorted according to its elements natural ordering
534 +     * (using <tt>Comparable</tt>.)
535 +     *
536 +     * @return the comparator used to order this collection, or <tt>null</tt>
537 +     * if this collection is sorted according to its elements natural ordering.
538 +     */
539      public Comparator<? super E> comparator() {
540          return comparator;
541      }
# Line 417 | Line 549 | public class PriorityQueue<E> extends Ab
549       * <tt>Object</tt>) in the proper order.
550       * @param s the stream
551       */
552 <    private synchronized void writeObject(java.io.ObjectOutputStream s)
552 >    private void writeObject(java.io.ObjectOutputStream s)
553          throws java.io.IOException{
554          // Write out element count, and any hidden stuff
555          s.defaultWriteObject();
# Line 435 | Line 567 | public class PriorityQueue<E> extends Ab
567       * deserialize it).
568       * @param s the stream
569       */
570 <    private synchronized void readObject(java.io.ObjectInputStream s)
570 >    private void readObject(java.io.ObjectInputStream s)
571          throws java.io.IOException, ClassNotFoundException {
572          // Read in size, and any hidden stuff
573          s.defaultReadObject();

Diff Legend

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