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.12 by dl, Mon Jul 28 09:40:07 2003 UTC vs.
Revision 1.15 by dholmes, Thu Jul 31 07:18:02 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}:
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 <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
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 < *
14 > *
15   * <p>The {@link #remove()} and {@link #poll()} methods remove and
16   * return the head of the queue.
17   *
# Line 38 | Line 38
38   * @author Josh Bloch
39   */
40   public class PriorityQueue<E> extends AbstractQueue<E>
41 <    implements Queue<E>, Sorted, java.io.Serializable {
41 >    implements Queue<E>, java.io.Serializable {
42  
43      private static final int DEFAULT_INITIAL_CAPACITY = 11;
44  
# Line 102 | Line 102 | public class PriorityQueue<E> extends Ab
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 +     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
106 +     * than 1
107       */
108      public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
109          if (initialCapacity < 1)
110 <            initialCapacity = 1;
110 >            throw new IllegalArgumentException();
111          queue = (E[]) new Object[initialCapacity + 1];
112          this.comparator = comparator;
113      }
# Line 113 | Line 115 | public class PriorityQueue<E> extends Ab
115      /**
116       * Create a <tt>PriorityQueue</tt> containing the elements in the specified
117       * collection.  The priority queue has an initial capacity of 110% of the
118 <     * size of the specified collection. If the specified collection
118 >     * size of the specified collection; or 1 if the collection is empty.
119 >     * If the specified collection
120       * implements the {@link Sorted} interface, the priority queue will be
121       * sorted according to the same comparator, or according to its elements'
122       * natural order if the collection is sorted according to its elements'
# Line 121 | Line 124 | public class PriorityQueue<E> extends Ab
124       * <tt>Sorted</tt>, the priority queue is ordered according to
125       * its elements' natural order.
126       *
127 <     * @param initialElements the collection whose elements are to be placed
127 >     * @param c the collection whose elements are to be placed
128       *        into this priority queue.
129       * @throws ClassCastException if elements of the specified collection
130       *         cannot be compared to one another according to the priority
131       *         queue's ordering.
132 <     * @throws NullPointerException if the specified collection or an
133 <     *         element of the specified collection is <tt>null</tt>.
132 >     * @throws NullPointerException if <tt>c</tt> or any element within it
133 >     * is <tt>null</tt>
134       */
135 <    public PriorityQueue(Collection<E> initialElements) {
136 <        int sz = initialElements.size();
135 >    public PriorityQueue(Collection<E> c) {
136 >        int sz = c.size();
137          int initialCapacity = (int)Math.min((sz * 110L) / 100,
138                                              Integer.MAX_VALUE - 1);
139          if (initialCapacity < 1)
140              initialCapacity = 1;
141 +
142          queue = (E[]) new Object[initialCapacity + 1];
143  
144 <        if (initialElements instanceof Sorted) {
145 <            comparator = ((Sorted)initialElements).comparator();
146 <            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
144 >        if (c instanceof Sorted) {
145 >            // FIXME: this code assumes too much
146 >            comparator = ((Sorted)c).comparator();
147 >            for (Iterator<E> i = c.iterator(); i.hasNext(); )
148                  queue[++size] = i.next();
149          } else {
150              comparator = null;
151 <            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
151 >            for (Iterator<E> i = c.iterator(); i.hasNext(); )
152                  add(i.next());
153          }
154      }
# Line 194 | Line 199 | public class PriorityQueue<E> extends Ab
199  
200      /**
201       * @throws NullPointerException if the specified element is <tt>null</tt>.
202 +     * @throws ClassCastException if the specified element cannot be compared
203 +     * with elements currently in the priority queue according
204 +     * to the priority queue's ordering.
205       */
206      public boolean add(E element) {
207          return super.add(element);
208      }
209  
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 –
210      /**
211 <     * @throws NullPointerException if the specified element is <tt>null</tt>.
211 >     * @throws NullPointerException if any element is <tt>null</tt>.
212 >     * @throws ClassCastException if any element cannot be compared
213 >     * with elements currently in the priority queue according
214 >     * to the priority queue's ordering.
215       */
216 +    public boolean addAll(Collection<? extends E> c) {
217 +        return super.addAll(c);
218 +    }
219 +
220      public boolean remove(Object o) {
221          if (o == null)
222 <            throw new NullPointerException();
222 >            return false;
223  
224          if (comparator == null) {
225              for (int i = 1; i <= size; i++) {
# Line 231 | Line 239 | public class PriorityQueue<E> extends Ab
239          return false;
240      }
241  
234 –    /**
235 –     * Returns an iterator over the elements in this priority queue.  The
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 –     *
240 –     * @return an <tt>Iterator</tt> over the elements in this priority queue.
241 –     */
242      public Iterator<E> iterator() {
243          return new Itr();
244      }

Diff Legend

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