--- jsr166/src/main/java/util/PriorityQueue.java	2005/11/27 20:41:02	1.55
+++ jsr166/src/main/java/util/PriorityQueue.java	2005/11/29 08:52:26	1.59
@@ -1,5 +1,5 @@
 /*
- * @(#)PriorityQueue.java	1.8 05/08/27
+ * %W% %E%
  *
  * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
@@ -136,7 +136,7 @@ public class PriorityQueue<E> extends Ab
         this.queue = new Object[initialCapacity];
         this.comparator = comparator;
     }
-    
+
     /**
      * Creates a <tt>PriorityQueue</tt> containing the elements in the
      * specified collection.   If the specified collection is an
@@ -155,10 +155,10 @@ public class PriorityQueue<E> extends Ab
      */
     public PriorityQueue(Collection<? extends E> c) {
         initFromCollection(c);
-        if (c instanceof SortedSet) 
+        if (c instanceof SortedSet)
             comparator = (Comparator<? super E>)
                 ((SortedSet<? extends E>)c).comparator();
-        else if (c instanceof PriorityQueue) 
+        else if (c instanceof PriorityQueue)
             comparator = (Comparator<? super E>)
                 ((PriorityQueue<? extends E>)c).comparator();
         else {
@@ -215,7 +215,7 @@ public class PriorityQueue<E> extends Ab
             a = Arrays.copyOf(a, a.length, Object[].class);
         queue = a;
         size = a.length;
-    }        
+    }
 
     /**
      * Increases the capacity of the array.
@@ -229,7 +229,9 @@ public class PriorityQueue<E> extends Ab
         // Double size if small; else grow by 50%
         int newCapacity = ((oldCapacity < 64)?
                            ((oldCapacity + 1) * 2):
-                           ((oldCapacity * 3) / 2));
+                           ((oldCapacity / 2) * 3));
+        if (newCapacity < 0) // overflow
+            newCapacity = Integer.MAX_VALUE;
         if (newCapacity < minCapacity)
             newCapacity = minCapacity;
         queue = Arrays.copyOf(queue, newCapacity);
@@ -307,12 +309,12 @@ public class PriorityQueue<E> extends Ab
 	}
     }
 
-    /** 
+    /**
      * Version of remove using reference equality, not equals.
-     * Needed by iterator.remove
-     * 
+     * Needed by iterator.remove.
+     *
      * @param o element to be removed from this queue, if present
-     * @return <tt>true</tt> if removed.
+     * @return <tt>true</tt> if removed
      */
     boolean removeEq(Object o) {
 	for (int i = 0; i < size; i++) {
@@ -344,7 +346,7 @@ public class PriorityQueue<E> extends Ab
      * maintained by this list.  (In other words, this method must allocate
      * a new array).  The caller is thus free to modify the returned array.
      *
-     * @return an array containing all of the elements in this queue.
+     * @return an array containing all of the elements in this queue
      */
     public Object[] toArray() {
         return Arrays.copyOf(queue, size);
@@ -435,19 +437,19 @@ public class PriorityQueue<E> extends Ab
         private int expectedModCount = modCount;
 
         public boolean hasNext() {
-            return cursor < size || 
+            return cursor < size ||
                 (forgetMeNot != null && !forgetMeNot.isEmpty());
         }
 
         public E next() {
             if (expectedModCount != modCount)
                 throw new ConcurrentModificationException();
-            if (cursor < size) 
+            if (cursor < size)
                 return (E) queue[lastRet = cursor++];
             if (forgetMeNot != null) {
                 lastRet = -1;
                 lastRetElt = forgetMeNot.poll();
-                if (lastRetElt != null) 
+                if (lastRetElt != null)
                     return lastRetElt;
             }
             throw new NoSuchElementException();
@@ -461,17 +463,17 @@ public class PriorityQueue<E> extends Ab
             if (lastRet != -1) {
                 E moved = PriorityQueue.this.removeAt(lastRet);
                 lastRet = -1;
-                if (moved == null) 
+                if (moved == null)
                     cursor--;
                 else {
                     if (forgetMeNot == null)
                         forgetMeNot = new ArrayDeque<E>();
                     forgetMeNot.add(moved);
-                }            
+                }
             } else {
                 PriorityQueue.this.removeEq(lastRetElt);
                 lastRetElt = null;
-            } 
+            }
             expectedModCount = modCount;
         }
 
@@ -525,7 +527,7 @@ public class PriorityQueue<E> extends Ab
             queue[i] = null;
         else {
             E moved = (E) queue[s];
-            queue[s] = null;  
+            queue[s] = null;
             siftDown(i, moved);
             if (queue[i] == moved) {
                 siftUp(i, moved);
@@ -544,12 +546,12 @@ public class PriorityQueue<E> extends Ab
      * To simplify and speed up coercions and comparisons. the
      * Comparable and Comparator versions are separated into different
      * methods that are otherwise identical. (Similarly for siftDown.)
-     * 
+     *
      * @param k the position to fill
      * @param x the item to insert
      */
     private void siftUp(int k, E x) {
-        if (comparator != null) 
+        if (comparator != null)
             siftUpUsingComparator(k, x);
         else
             siftUpComparable(k, x);
@@ -560,7 +562,7 @@ public class PriorityQueue<E> extends Ab
         while (k > 0) {
             int parent = (k - 1) >>> 1;
             Object e = queue[parent];
-            if (key.compareTo((E)e) >= 0) 
+            if (key.compareTo((E)e) >= 0)
                 break;
             queue[k] = e;
             k = parent;
@@ -572,7 +574,7 @@ public class PriorityQueue<E> extends Ab
         while (k > 0) {
             int parent = (k - 1) >>> 1;
             Object e = queue[parent];
-            if (comparator.compare(x, (E)e) >= 0) 
+            if (comparator.compare(x, (E)e) >= 0)
                 break;
             queue[k] = e;
             k = parent;
@@ -589,7 +591,7 @@ public class PriorityQueue<E> extends Ab
      * @param x the item to insert
      */
     private void siftDown(int k, E x) {
-        if (comparator != null) 
+        if (comparator != null)
             siftDownUsingComparator(k, x);
         else
             siftDownComparable(k, x);
@@ -621,8 +623,8 @@ public class PriorityQueue<E> extends Ab
             int right = child + 1;
             if (right < size &&
                 comparator.compare((E)c, (E)queue[right]) > 0)
-                c = queue[child = right]; 
-            if (comparator.compare(x, (E)c) <= 0) 
+                c = queue[child = right];
+            if (comparator.compare(x, (E)c) <= 0)
                 break;
             queue[k] = c;
             k = child;
@@ -635,7 +637,7 @@ public class PriorityQueue<E> extends Ab
      * assuming nothing about the order of the elements prior to the call.
      */
     private void heapify() {
-        for (int i = (size >>> 1) - 1; i >= 0; i--) 
+        for (int i = (size >>> 1) - 1; i >= 0; i--)
             siftDown(i, (E)queue[i]);
     }