--- jsr166/src/main/java/util/PriorityQueue.java	2003/07/28 10:08:24	1.13
+++ jsr166/src/main/java/util/PriorityQueue.java	2003/08/04 01:48:39	1.18
@@ -1,17 +1,19 @@
  package java.util;
 
 /**
- * An unbounded priority queue based on a priority heap.  This queue orders
+ * A priority queue based on a priority heap.  This queue orders
  * elements according to an order specified at construction time, which is
- * specified in the same manner as {@link TreeSet} and {@link TreeMap}: 
- * elements are ordered
+ * specified in the same manner as {@link java.util.TreeSet} and 
+ * {@link java.util.TreeMap}: elements are ordered
  * either according to their <i>natural order</i> (see {@link Comparable}), or
- * according to a {@link Comparator}, depending on which constructor is used.
- * The <em>head</em> of this queue is the least element with respect to the
- * specified ordering. If multiple elements are tied for least value, the 
- * head is one of those elements. A priority queue does not permit 
+ * according to a {@link java.util.Comparator}, depending on which 
+ * constructor is used.
+ * <p>The <em>head</em> of this queue is the <em>least</em> element with 
+ * respect to the specified ordering. 
+ * If multiple elements are tied for least value, the
+ * head is one of those elements. A priority queue does not permit
  * <tt>null</tt> elements.
- * 
+ *
  * <p>The {@link #remove()} and {@link #poll()} methods remove and
  * return the head of the queue.
  *
@@ -20,7 +22,8 @@
  *
  * <p>A priority queue has a <i>capacity</i>.  The capacity is the
  * size of the array used internally to store the elements on the
- * queue.  It is always at least as large as the queue size.  As
+ * queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.  
+ * It is always at least as large as the queue size.  As
  * elements are added to a priority queue, its capacity grows
  * automatically.  The details of the growth policy are not specified.
  *
@@ -38,7 +41,7 @@
  * @author Josh Bloch
  */
 public class PriorityQueue<E> extends AbstractQueue<E>
-    implements Queue<E>, java.io.Serializable {
+    implements Sorted, Queue<E>, java.io.Serializable {
 
     private static final int DEFAULT_INITIAL_CAPACITY = 11;
 
@@ -55,7 +58,7 @@ public class PriorityQueue<E> extends Ab
      *
      * queue.length must be >= 2, even if size == 0.
      */
-    private transient E[] queue;
+    private transient Object[] queue;
 
     /**
      * The number of elements in the priority queue.
@@ -66,7 +69,7 @@ public class PriorityQueue<E> extends Ab
      * The comparator, or null if priority queue uses elements'
      * natural ordering.
      */
-    private final Comparator<E> comparator;
+    private final Comparator<? super E> comparator;
 
     /**
      * The number of times this priority queue has been
@@ -102,18 +105,22 @@ public class PriorityQueue<E> extends Ab
      * @param comparator the comparator used to order this priority queue.
      * If <tt>null</tt> then the order depends on the elements' natural
      * ordering.
+     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
+     * than 1
      */
-    public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
+    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
         if (initialCapacity < 1)
-            initialCapacity = 1;
-        queue = (E[]) new Object[initialCapacity + 1];
+            throw new IllegalArgumentException();
+        this.queue = new Object[initialCapacity + 1];
         this.comparator = comparator;
     }
 
     /**
      * Create a <tt>PriorityQueue</tt> containing the elements in the specified
      * collection.  The priority queue has an initial capacity of 110% of the
-     * size of the specified collection. If the specified collection
+     * size of the specified collection (bounded by 
+     * <tt>Integer.MAX_VALUE-1</tt>); or 1 if the collection is empty. 
+     * If the specified collection
      * implements the {@link Sorted} interface, the priority queue will be
      * sorted according to the same comparator, or according to its elements'
      * natural order if the collection is sorted according to its elements'
@@ -121,31 +128,34 @@ public class PriorityQueue<E> extends Ab
      * <tt>Sorted</tt>, the priority queue is ordered according to
      * its elements' natural order.
      *
-     * @param initialElements the collection whose elements are to be placed
+     * @param c the collection whose elements are to be placed
      *        into this priority queue.
      * @throws ClassCastException if elements of the specified collection
      *         cannot be compared to one another according to the priority
      *         queue's ordering.
-     * @throws NullPointerException if the specified collection or an
-     *         element of the specified collection is <tt>null</tt>.
+     * @throws NullPointerException if <tt>c</tt> or any element within it
+     * is <tt>null</tt>
      */
-    public PriorityQueue(Collection<E> initialElements) {
-        int sz = initialElements.size();
+    public PriorityQueue(Collection<? extends E> c) {
+        int sz = c.size();
         int initialCapacity = (int)Math.min((sz * 110L) / 100,
                                             Integer.MAX_VALUE - 1);
         if (initialCapacity < 1)
             initialCapacity = 1;
-        queue = (E[]) new Object[initialCapacity + 1];
 
-        if (initialElements instanceof Sorted) {
-            comparator = ((Sorted)initialElements).comparator();
-            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
-                queue[++size] = i.next();
+        this.queue = new Object[initialCapacity + 1];
+
+        // FIXME: if c is larger than Integer.MAX_VALUE we'll 
+        // overflow the array
+
+        if (c instanceof Sorted) {
+            comparator = ((Sorted)c).comparator();
         } else {
             comparator = null;
-            for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
-                add(i.next());
         }
+
+        for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
+            add(i.next());
     }
 
     // Queue Methods
@@ -153,27 +163,28 @@ public class PriorityQueue<E> extends Ab
     /**
      * Add the specified element to this priority queue.
      *
-     * @param element the element to add.
      * @return <tt>true</tt>
      * @throws ClassCastException if the specified element cannot be compared
      * with elements currently in the priority queue according
      * to the priority queue's ordering.
-     * @throws NullPointerException if the specified element is null.
+     * @throws NullPointerException if the specified element is <tt>null</tt>.
      */
-    public boolean offer(E element) {
-        if (element == null)
+    public boolean offer(E o) {
+        if (o == null)
             throw new NullPointerException();
         modCount++;
         ++size;
 
         // Grow backing store if necessary
+        // FIXME: watch for overflow
+        // FIXME: what if we're full?
         while (size >= queue.length) {
-            E[] newQueue = (E[]) new Object[2 * queue.length];
+            Object[] newQueue = new Object[2 * queue.length];
             System.arraycopy(queue, 0, newQueue, 0, queue.length);
             queue = newQueue;
         }
 
-        queue[size] = element;
+        queue[size] = o;
         fixUp(size);
         return true;
     }
@@ -181,11 +192,11 @@ public class PriorityQueue<E> extends Ab
     public E poll() {
         if (size == 0)
             return null;
-        return remove(1);
+        return (E) remove(1);
     }
 
     public E peek() {
-        return queue[1];
+        return (E) queue[1];
     }
 
     // Collection Methods
@@ -194,35 +205,39 @@ public class PriorityQueue<E> extends Ab
 
     /**
      * @throws NullPointerException if the specified element is <tt>null</tt>.
+     * @throws ClassCastException if the specified element cannot be compared
+     * with elements currently in the priority queue according
+     * to the priority queue's ordering.
      */
-    public boolean add(E element) {
-        return super.add(element);
+    public boolean add(E o) {
+        return super.add(o);
     }
 
-    //    /**
-    //     * @throws NullPointerException if any element is <tt>null</tt>.
-    //     */
-    //    public boolean addAll(Collection c) {
-    //        return super.addAll(c);
-    //    }
-
     /**
-     * @throws NullPointerException if the specified element is <tt>null</tt>.
+     * @throws ClassCastException if any element cannot be compared
+     * with elements currently in the priority queue according
+     * to the priority queue's ordering.
+     * @throws NullPointerException if <tt>c</tt> or any element in <tt>c</tt>
+     * is <tt>null</tt>
      */
+    public boolean addAll(Collection<? extends E> c) {
+        return super.addAll(c);
+    }
+
     public boolean remove(Object o) {
         if (o == null)
-            throw new NullPointerException();
+            return false;
 
         if (comparator == null) {
             for (int i = 1; i <= size; i++) {
-                if (((Comparable)queue[i]).compareTo(o) == 0) {
+                if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
                     remove(i);
                     return true;
                 }
             }
         } else {
             for (int i = 1; i <= size; i++) {
-                if (comparator.compare(queue[i], (E)o) == 0) {
+                if (comparator.compare((E)queue[i], (E)o) == 0) {
                     remove(i);
                     return true;
                 }
@@ -231,14 +246,6 @@ public class PriorityQueue<E> extends Ab
         return false;
     }
 
-    /**
-     * Returns an iterator over the elements in this priority queue.  The
-     * elements of the priority queue will be returned by this iterator in the
-     * order specified by the queue, which is to say the order they would be
-     * returned by repeated calls to <tt>poll</tt>.
-     *
-     * @return an <tt>Iterator</tt> over the elements in this priority queue.
-     */
     public Iterator<E> iterator() {
         return new Itr();
     }
@@ -272,7 +279,7 @@ public class PriorityQueue<E> extends Ab
             checkForComodification();
             if (cursor > size)
                 throw new NoSuchElementException();
-            E result = queue[cursor];
+            E result = (E) queue[cursor];
             lastRet = cursor++;
             return result;
         }
@@ -328,7 +335,7 @@ public class PriorityQueue<E> extends Ab
         assert i <= size;
         modCount++;
 
-        E result = queue[i];
+        E result = (E) queue[i];
         queue[i] = queue[size];
         queue[size--] = null;  // Drop extra ref to prevent memory leak
         if (i <= size)
@@ -349,17 +356,17 @@ public class PriorityQueue<E> extends Ab
         if (comparator == null) {
             while (k > 1) {
                 int j = k >> 1;
-                if (((Comparable)queue[j]).compareTo(queue[k]) <= 0)
+                if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
                     break;
-                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
+                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                 k = j;
             }
         } else {
             while (k > 1) {
                 int j = k >> 1;
-                if (comparator.compare(queue[j], queue[k]) <= 0)
+                if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
                     break;
-                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
+                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                 k = j;
             }
         }
@@ -378,26 +385,26 @@ public class PriorityQueue<E> extends Ab
         int j;
         if (comparator == null) {
             while ((j = k << 1) <= size) {
-                if (j<size && ((Comparable)queue[j]).compareTo(queue[j+1]) > 0)
+                if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
                     j++; // j indexes smallest kid
-                if (((Comparable)queue[k]).compareTo(queue[j]) <= 0)
+                if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
                     break;
-                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
+                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                 k = j;
             }
         } else {
             while ((j = k << 1) <= size) {
-                if (j < size && comparator.compare(queue[j], queue[j+1]) > 0)
+                if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
                     j++; // j indexes smallest kid
-                if (comparator.compare(queue[k], queue[j]) <= 0)
+                if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
                     break;
-                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
+                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
                 k = j;
             }
         }
     }
 
-    public Comparator comparator() {
+    public Comparator<? super E> comparator() {
         return comparator;
     }
 
@@ -435,11 +442,11 @@ public class PriorityQueue<E> extends Ab
 
         // Read in array length and allocate array
         int arrayLength = s.readInt();
-        queue = (E[]) new Object[arrayLength];
+        queue = new Object[arrayLength];
 
         // Read in all elements in the proper order.
         for (int i=0; i<size; i++)
-            queue[i] = (E)s.readObject();
+            queue[i] = s.readObject();
     }
 
 }