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.14 by tim, Mon Jul 28 16:00:19 2003 UTC vs.
Revision 1.28 by dl, Wed Aug 13 14:11:59 2003 UTC

# Line 1 | Line 1
1   package java.util;
2  
3   /**
4 < * An unbounded 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 TreeSet} and {@link TreeMap}:
8 < * elements are ordered
7 > * specified in the same manner as {@link java.util.TreeSet} and
8 > * {@link java.util.TreeMap}: elements are ordered
9   * either according to their <i>natural order</i> (see {@link Comparable}), or
10 < * according to a {@link Comparator}, depending on which constructor is used.
11 < * The <em>head</em> of this queue is the least element with respect to the
12 < * specified ordering. If multiple elements are tied for least value, the
10 > * according to a {@link java.util.Comparator}, depending on which
11 > * constructor is used.
12 > * <p>The <em>head</em> of this queue is the <em>least</em> element with
13 > * respect to the specified ordering.
14 > * If multiple elements are tied for least value, the
15   * head is one of those elements. A priority queue does not permit
16   * <tt>null</tt> elements.
17   *
# Line 20 | 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.  It is always at least as large as the queue size.  As
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.
30   *
# Line 55 | Line 59 | public class PriorityQueue<E> extends Ab
59       *
60       * queue.length must be >= 2, even if size == 0.
61       */
62 <    private transient E[] queue;
62 >    private transient Object[] queue;
63  
64      /**
65       * The number of elements in the priority queue.
# Line 66 | Line 70 | public class PriorityQueue<E> extends Ab
70       * The comparator, or null if priority queue uses elements'
71       * natural ordering.
72       */
73 <    private final Comparator<E> comparator;
73 >    private final Comparator<? super E> comparator;
74  
75      /**
76       * The number of times this priority queue has been
# Line 75 | 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>.)
84 >     * ordering (using <tt>Comparable</tt>).
85       */
86      public PriorityQueue() {
87          this(DEFAULT_INITIAL_CAPACITY, null);
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>.)
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.
108       * @param comparator the comparator used to order this priority queue.
109       * If <tt>null</tt> then the order depends on the elements' natural
110       * ordering.
111 +     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
112 +     * than 1
113       */
114 <    public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
114 >    public PriorityQueue(int initialCapacity,
115 >                         Comparator<? super E> comparator) {
116          if (initialCapacity < 1)
117 <            initialCapacity = 1;
118 <        queue = (E[]) new Object[initialCapacity + 1];
117 >            throw new IllegalArgumentException();
118 >        this.queue = new Object[initialCapacity + 1];
119          this.comparator = comparator;
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
116 <     * size of the specified collection. If the specified collection
117 <     * implements the {@link Sorted} interface, the priority queue will be
118 <     * sorted according to the same comparator, or according to its elements'
119 <     * natural order if the collection is sorted according to its elements'
120 <     * natural order.  If the specified collection does not implement
121 <     * <tt>Sorted</tt>, the priority queue is ordered according to
122 <     * its elements' natural order.
123 <     *
124 <     * @param initialElements the collection whose elements are to be placed
125 <     *        into this priority queue.
126 <     * @throws ClassCastException if elements of the specified collection
127 <     *         cannot be compared to one another according to the priority
128 <     *         queue's ordering.
129 <     * @throws NullPointerException if the specified collection or an
130 <     *         element of the specified collection is <tt>null</tt>.
123 >     * Common code to initialize underlying queue array across
124 >     * constructors below.
125       */
126 <    public PriorityQueue(Collection<E> initialElements) {
127 <        int sz = initialElements.size();
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);
130          if (initialCapacity < 1)
131              initialCapacity = 1;
138 –        queue = (E[]) new Object[initialCapacity + 1];
132  
133 <        if (initialElements instanceof Sorted) {
134 <            comparator = ((Sorted)initialElements).comparator();
135 <            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
136 <                queue[++size] = i.next();
133 >        this.queue = new Object[initialCapacity + 1];
134 >    }
135 >
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 >
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 java.util.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) {
180 >            // @fixme double-cast workaround for compiler
181 >            SortedSet<? extends E> s = (SortedSet<? extends E>) (SortedSet)c;
182 >            comparator = (Comparator<? super E>)s.comparator();
183 >            fillFromSorted(s);
184 >        } else if (c instanceof PriorityQueue) {
185 >            PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c;
186 >            comparator = (Comparator<? super E>)s.comparator();
187 >            fillFromSorted(s);
188          } else {
189              comparator = null;
190 <            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
147 <                add(i.next());
190 >            fillFromUnsorted(c);
191          }
192      }
193  
194 +    /**
195 +     * Creates a <tt>PriorityQueue</tt> containing the elements in the
196 +     * specified collection.  The priority queue has an initial
197 +     * capacity of 110% of the size of the specified collection or 1
198 +     * if the collection is empty.  This priority queue will be sorted
199 +     * according to the same comparator as the given collection, or
200 +     * according to its elements' natural order if the collection is
201 +     * sorted according to its elements' natural order.
202 +     *
203 +     * @param c the collection whose elements are to be placed
204 +     *        into this priority queue.
205 +     * @throws ClassCastException if elements of the specified collection
206 +     *         cannot be compared to one another according to the priority
207 +     *         queue's ordering.
208 +     * @throws NullPointerException if <tt>c</tt> or any element within it
209 +     * is <tt>null</tt>
210 +     */
211 +    public PriorityQueue(PriorityQueue<? extends E> c) {
212 +        initializeArray(c);
213 +        comparator = (Comparator<? super E>)c.comparator();
214 +        fillFromSorted(c);
215 +    }
216 +
217 +    /**
218 +     * Creates a <tt>PriorityQueue</tt> containing the elements in the
219 +     * specified collection.  The priority queue has an initial
220 +     * capacity of 110% of the size of the specified collection or 1
221 +     * if the collection is empty.  This priority queue will be sorted
222 +     * according to the same comparator as the given collection, or
223 +     * according to its elements' natural order if the collection is
224 +     * sorted according to its elements' natural order.
225 +     *
226 +     * @param c the collection whose elements are to be placed
227 +     *        into this priority queue.
228 +     * @throws ClassCastException if elements of the specified collection
229 +     *         cannot be compared to one another according to the priority
230 +     *         queue's ordering.
231 +     * @throws NullPointerException if <tt>c</tt> or any element within it
232 +     * is <tt>null</tt>
233 +     */
234 +    public PriorityQueue(SortedSet<? extends E> c) {
235 +        initializeArray(c);
236 +        comparator = (Comparator<? super E>)c.comparator();
237 +        fillFromSorted(c);
238 +    }
239 +
240 +    /**
241 +     * Resize array, if necessary, to be able to hold given index
242 +     */
243 +    private void grow(int index) {
244 +        int newlen = queue.length;
245 +        if (index < newlen) // don't need to grow
246 +            return;
247 +        if (index == Integer.MAX_VALUE)
248 +            throw new OutOfMemoryError();
249 +        while (newlen <= index) {
250 +            if (newlen >= Integer.MAX_VALUE / 2)  // avoid overflow
251 +                newlen = Integer.MAX_VALUE;
252 +            else
253 +                newlen <<= 2;
254 +        }
255 +        Object[] newQueue = new Object[newlen];
256 +        System.arraycopy(queue, 0, newQueue, 0, queue.length);
257 +        queue = newQueue;
258 +    }
259 +            
260      // Queue Methods
261  
262 +
263 +
264      /**
265       * Add the specified element to this priority queue.
266       *
156 –     * @param element the element to add.
267       * @return <tt>true</tt>
268       * @throws ClassCastException if the specified element cannot be compared
269       * with elements currently in the priority queue according
270       * to the priority queue's ordering.
271 <     * @throws NullPointerException if the specified element is null.
271 >     * @throws NullPointerException if the specified element is <tt>null</tt>.
272       */
273 <    public boolean offer(E element) {
274 <        if (element == null)
273 >    public boolean offer(E o) {
274 >        if (o == null)
275              throw new NullPointerException();
276          modCount++;
277          ++size;
278  
279          // Grow backing store if necessary
280 <        while (size >= queue.length) {
281 <            E[] newQueue = (E[]) new Object[2 * queue.length];
172 <            System.arraycopy(queue, 0, newQueue, 0, queue.length);
173 <            queue = newQueue;
174 <        }
280 >        if (size >= queue.length)
281 >            grow(size);
282  
283 <        queue[size] = element;
283 >        queue[size] = o;
284          fixUp(size);
285          return true;
286      }
# Line 181 | Line 288 | public class PriorityQueue<E> extends Ab
288      public E poll() {
289          if (size == 0)
290              return null;
291 <        return remove(1);
291 >        return (E) remove(1);
292      }
293  
294      public E peek() {
295 <        return queue[1];
295 >        return (E) queue[1];
296      }
297  
298 <    // Collection Methods
192 <
193 <    // these first two override just to get the throws docs
298 >    // Collection Methods - the first two override to update docs
299  
300      /**
301 <     * @throws NullPointerException if the specified element is <tt>null</tt>.
301 >     * Adds the specified element to this queue.
302 >     * @return <tt>true</tt> (as per the general contract of
303 >     * <tt>Collection.add</tt>).
304 >     *
305 >     * @throws NullPointerException {@inheritDoc}
306 >     * @throws ClassCastException if the specified element cannot be compared
307 >     * with elements currently in the priority queue according
308 >     * to the priority queue's ordering.
309       */
310 <    public boolean add(E element) {
311 <        return super.add(element);
310 >    public boolean add(E o) {
311 >        return super.add(o);
312      }
313  
314 +  
315      /**
316 <     * @throws NullPointerException if any element is <tt>null</tt>.
316 >     * Adds all of the elements in the specified collection to this queue.
317 >     * The behavior of this operation is undefined if
318 >     * the specified collection is modified while the operation is in
319 >     * progress.  (This implies that the behavior of this call is undefined if
320 >     * the specified collection is this queue, and this queue is nonempty.)
321 >     * <p>
322 >     * This implementation iterates over the specified collection, and adds
323 >     * each object returned by the iterator to this collection, in turn.
324 >     * @throws NullPointerException {@inheritDoc}
325 >     * @throws ClassCastException if any element cannot be compared
326 >     * with elements currently in the priority queue according
327 >     * to the priority queue's ordering.
328       */
329      public boolean addAll(Collection<? extends E> c) {
330          return super.addAll(c);
331      }
332  
333 <    /**
334 <     * @throws NullPointerException if the specified element is <tt>null</tt>.
333 >
334 > /**
335 >     * Removes a single instance of the specified element from this
336 >     * queue, if it is present.  More formally,
337 >     * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
338 >     * o.equals(e))</tt>, if the queue contains one or more such
339 >     * elements.  Returns <tt>true</tt> if the queue contained the
340 >     * specified element (or equivalently, if the queue changed as a
341 >     * result of the call).
342 >     *
343 >     * <p>This implementation iterates over the queue looking for the
344 >     * specified element.  If it finds the element, it removes the element
345 >     * from the queue using the iterator's remove method.<p>
346 >     *
347       */
348      public boolean remove(Object o) {
349          if (o == null)
350 <            throw new NullPointerException();
350 >            return false;
351  
352          if (comparator == null) {
353              for (int i = 1; i <= size; i++) {
354 <                if (((Comparable)queue[i]).compareTo(o) == 0) {
354 >                if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
355                      remove(i);
356                      return true;
357                  }
358              }
359          } else {
360              for (int i = 1; i <= size; i++) {
361 <                if (comparator.compare(queue[i], (E)o) == 0) {
361 >                if (comparator.compare((E)queue[i], (E)o) == 0) {
362                      remove(i);
363                      return true;
364                  }
# Line 232 | Line 368 | public class PriorityQueue<E> extends Ab
368      }
369  
370      /**
371 <     * Returns an iterator over the elements in this priority queue.  The
372 <     * 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>.
371 >     * Returns an iterator over the elements in this queue. The iterator
372 >     * does not return the elements in any particular order.
373       *
374 <     * @return an <tt>Iterator</tt> over the elements in this priority queue.
374 >     * @return an iterator over the elements in this queue.
375       */
376      public Iterator<E> iterator() {
377          return new Itr();
# Line 272 | Line 406 | public class PriorityQueue<E> extends Ab
406              checkForComodification();
407              if (cursor > size)
408                  throw new NoSuchElementException();
409 <            E result = queue[cursor];
409 >            E result = (E) queue[cursor];
410              lastRet = cursor++;
411              return result;
412          }
# Line 295 | Line 429 | public class PriorityQueue<E> extends Ab
429          }
430      }
431  
298 –    /**
299 –     * Returns the number of elements in this priority queue.
300 –     *
301 –     * @return the number of elements in this priority queue.
302 –     */
432      public int size() {
433          return size;
434      }
# Line 328 | Line 457 | public class PriorityQueue<E> extends Ab
457          assert i <= size;
458          modCount++;
459  
460 <        E result = queue[i];
460 >        E result = (E) queue[i];
461          queue[i] = queue[size];
462          queue[size--] = null;  // Drop extra ref to prevent memory leak
463          if (i <= size)
# Line 349 | Line 478 | public class PriorityQueue<E> extends Ab
478          if (comparator == null) {
479              while (k > 1) {
480                  int j = k >> 1;
481 <                if (((Comparable)queue[j]).compareTo(queue[k]) <= 0)
481 >                if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
482                      break;
483 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
483 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
484                  k = j;
485              }
486          } else {
487              while (k > 1) {
488                  int j = k >> 1;
489 <                if (comparator.compare(queue[j], queue[k]) <= 0)
489 >                if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
490                      break;
491 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
491 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
492                  k = j;
493              }
494          }
# Line 378 | Line 507 | public class PriorityQueue<E> extends Ab
507          int j;
508          if (comparator == null) {
509              while ((j = k << 1) <= size) {
510 <                if (j<size && ((Comparable)queue[j]).compareTo(queue[j+1]) > 0)
510 >                if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
511                      j++; // j indexes smallest kid
512 <                if (((Comparable)queue[k]).compareTo(queue[j]) <= 0)
512 >                if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
513                      break;
514 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
514 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
515                  k = j;
516              }
517          } else {
518              while ((j = k << 1) <= size) {
519 <                if (j < size && comparator.compare(queue[j], queue[j+1]) > 0)
519 >                if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
520                      j++; // j indexes smallest kid
521 <                if (comparator.compare(queue[k], queue[j]) <= 0)
521 >                if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
522                      break;
523 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
523 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
524                  k = j;
525              }
526          }
527      }
528  
529 <    public Comparator comparator() {
529 >
530 >    /**
531 >     * Returns the comparator used to order this collection, or <tt>null</tt>
532 >     * if this collection is sorted according to its elements natural ordering
533 >     * (using <tt>Comparable</tt>).
534 >     *
535 >     * @return the comparator used to order this collection, or <tt>null</tt>
536 >     * if this collection is sorted according to its elements natural ordering.
537 >     */
538 >    public Comparator<? super E> comparator() {
539          return comparator;
540      }
541  
# Line 410 | Line 548 | public class PriorityQueue<E> extends Ab
548       * <tt>Object</tt>) in the proper order.
549       * @param s the stream
550       */
551 <    private synchronized void writeObject(java.io.ObjectOutputStream s)
551 >    private void writeObject(java.io.ObjectOutputStream s)
552          throws java.io.IOException{
553          // Write out element count, and any hidden stuff
554          s.defaultWriteObject();
# Line 428 | Line 566 | public class PriorityQueue<E> extends Ab
566       * deserialize it).
567       * @param s the stream
568       */
569 <    private synchronized void readObject(java.io.ObjectInputStream s)
569 >    private void readObject(java.io.ObjectInputStream s)
570          throws java.io.IOException, ClassNotFoundException {
571          // Read in size, and any hidden stuff
572          s.defaultReadObject();
573  
574          // Read in array length and allocate array
575          int arrayLength = s.readInt();
576 <        queue = (E[]) new Object[arrayLength];
576 >        queue = new Object[arrayLength];
577  
578          // Read in all elements in the proper order.
579          for (int i=0; i<size; i++)
580 <            queue[i] = (E)s.readObject();
580 >            queue[i] = s.readObject();
581      }
582  
583   }

Diff Legend

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