[cvs] / jsr166 / src / main / java / util / PriorityQueue.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/PriorityQueue.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.17, Thu Jul 31 19:49:42 2003 UTC revision 1.18, Mon Aug 4 01:48:39 2003 UTC
# Line 1  Line 1 
1   package java.util;   package java.util;
2    
3  /**  /**
4   * An unbounded priority queue based on a priority heap.  This queue orders   * A priority queue based on a priority heap.  This queue orders
5   * elements according to an order specified at construction time, which is   * elements according to an order specified at construction time, which is
6   * specified in the same manner as {@link java.util.TreeSet} and {@link java.util.TreeMap}:   * specified in the same manner as {@link java.util.TreeSet} and
7   * elements are ordered   * {@link java.util.TreeMap}: elements are ordered
8   * either according to their <i>natural order</i> (see {@link Comparable}), or   * either according to their <i>natural order</i> (see {@link Comparable}), or
9   * according to a {@link java.util.Comparator}, depending on which constructor is used.   * according to a {@link java.util.Comparator}, depending on which
10   * The <em>head</em> of this queue is the least element with respect to the   * constructor is used.
11   * specified ordering. If multiple elements are tied for least value, the   * <p>The <em>head</em> of this queue is the <em>least</em> element with
12     * respect to the specified ordering.
13     * If multiple elements are tied for least value, the
14   * head is one of those elements. A priority queue does not permit   * head is one of those elements. A priority queue does not permit
15   * <tt>null</tt> elements.   * <tt>null</tt> elements.
16   *   *
# Line 20  Line 22 
22   *   *
23   * <p>A priority queue has a <i>capacity</i>.  The capacity is the   * <p>A priority queue has a <i>capacity</i>.  The capacity is the
24   * size of the array used internally to store the elements on the   * size of the array used internally to store the elements on the
25   * queue.  It is always at least as large as the queue size.  As   * queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.
26     * It is always at least as large as the queue size.  As
27   * elements are added to a priority queue, its capacity grows   * elements are added to a priority queue, its capacity grows
28   * automatically.  The details of the growth policy are not specified.   * automatically.  The details of the growth policy are not specified.
29   *   *
# Line 38  Line 41 
41   * @author Josh Bloch   * @author Josh Bloch
42   */   */
43  public class PriorityQueue<E> extends AbstractQueue<E>  public class PriorityQueue<E> extends AbstractQueue<E>
44      implements Queue<E>, java.io.Serializable {      implements Sorted, Queue<E>, java.io.Serializable {
45    
46      private static final int DEFAULT_INITIAL_CAPACITY = 11;      private static final int DEFAULT_INITIAL_CAPACITY = 11;
47    
# Line 115  Line 118 
118      /**      /**
119       * Create a <tt>PriorityQueue</tt> containing the elements in the specified       * Create a <tt>PriorityQueue</tt> containing the elements in the specified
120       * collection.  The priority queue has an initial capacity of 110% of the       * collection.  The priority queue has an initial capacity of 110% of the
121       * size of the specified collection; or 1 if the collection is empty.       * 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       * If the specified collection
124       * implements the {@link Sorted} interface, the priority queue will be       * implements the {@link Sorted} interface, the priority queue will be
125       * sorted according to the same comparator, or according to its elements'       * sorted according to the same comparator, or according to its elements'
# Line 141  Line 145 
145    
146          this.queue = new Object[initialCapacity + 1];          this.queue = new Object[initialCapacity + 1];
147    
148            // FIXME: if c is larger than Integer.MAX_VALUE we'll
149            // overflow the array
150    
151          if (c instanceof Sorted) {          if (c instanceof Sorted) {
152              // FIXME: this code assumes too much              comparator = ((Sorted)c).comparator();
             this.comparator = (Comparator<? super E>) ((Sorted)c).comparator();  
             for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )  
                 queue[++size] = i.next();  
153          } else {          } else {
154              comparator = null;              comparator = null;
155            }
156    
157              for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )              for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
158                  add(i.next());                  add(i.next());
159          }          }
     }  
160    
161      // Queue Methods      // Queue Methods
162    
163      /**      /**
164       * Add the specified element to this priority queue.       * Add the specified element to this priority queue.
165       *       *
      * @param element the element to add.  
166       * @return <tt>true</tt>       * @return <tt>true</tt>
167       * @throws ClassCastException if the specified element cannot be compared       * @throws ClassCastException if the specified element cannot be compared
168       * with elements currently in the priority queue according       * with elements currently in the priority queue according
169       * to the priority queue's ordering.       * to the priority queue's ordering.
170       * @throws NullPointerException if the specified element is null.       * @throws NullPointerException if the specified element is <tt>null</tt>.
171       */       */
172      public boolean offer(E element) {      public boolean offer(E o) {
173          if (element == null)          if (o == null)
174              throw new NullPointerException();              throw new NullPointerException();
175          modCount++;          modCount++;
176          ++size;          ++size;
177    
178          // Grow backing store if necessary          // Grow backing store if necessary
179            // FIXME: watch for overflow
180            // FIXME: what if we're full?
181          while (size >= queue.length) {          while (size >= queue.length) {
182              Object[] newQueue = new Object[2 * queue.length];              Object[] newQueue = new Object[2 * queue.length];
183              System.arraycopy(queue, 0, newQueue, 0, queue.length);              System.arraycopy(queue, 0, newQueue, 0, queue.length);
184              queue = newQueue;              queue = newQueue;
185          }          }
186    
187          queue[size] = element;          queue[size] = o;
188          fixUp(size);          fixUp(size);
189          return true;          return true;
190      }      }
# Line 203  Line 209 
209       * with elements currently in the priority queue according       * with elements currently in the priority queue according
210       * to the priority queue's ordering.       * to the priority queue's ordering.
211       */       */
212      public boolean add(E element) {      public boolean add(E o) {
213          return super.add(element);          return super.add(o);
214      }      }
215    
216      /**      /**
      * @throws NullPointerException if any element is <tt>null</tt>.  
217       * @throws ClassCastException if any element cannot be compared       * @throws ClassCastException if any element cannot be compared
218       * with elements currently in the priority queue according       * with elements currently in the priority queue according
219       * to the priority queue's ordering.       * 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>
222       */       */
223      public boolean addAll(Collection<? extends E> c) {      public boolean addAll(Collection<? extends E> c) {
224          return super.addAll(c);          return super.addAll(c);

Legend:
Removed from v.1.17  
changed lines
  Added in v.1.18

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8