--- jsr166/src/main/java/util/ArrayList.java	2005/11/25 13:27:05	1.1
+++ jsr166/src/main/java/util/ArrayList.java	2006/04/21 20:49:03	1.20
@@ -1,12 +1,11 @@
 /*
  * %W% %E%
  *
- * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  */
 
 package java.util;
-import java.util.*; // for javadoc (till 6280605 is fixed)
 
 /**
  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
@@ -101,9 +100,9 @@ public class ArrayList<E> extends Abstra
     /**
      * Constructs an empty list with the specified initial capacity.
      *
-     * @param   initialCapacity   the initial capacity of the list
-     * @exception IllegalArgumentException if the specified initial capacity
-     *            is negative
+     * @param initialCapacity the initial capacity of the list
+     * @throws IllegalArgumentException if the specified initial capacity
+     *         is negative
      */
     public ArrayList(int initialCapacity) {
 	super();
@@ -123,20 +122,29 @@ public class ArrayList<E> extends Abstra
     /**
      * Constructs a list containing the elements of the specified
      * collection, in the order they are returned by the collection's
-     * iterator.  
+     * iterator.
      *
      * @param c the collection whose elements are to be placed into this list
      * @throws NullPointerException if the specified collection is null
      */
     public ArrayList(Collection<? extends E> c) {
-        Object[] a = c.toArray();
-        // If c.toArray incorrectly doesn't return Object[], copy it.
-        if (a.getClass() != Object[].class)
-            a = Arrays.copyOf(a, a.length, Object[].class);
-        elementData = a;
-        size = a.length;
+	elementData = c.toArray();
+	size = elementData.length;
+	// c.toArray might (incorrectly) not return Object[] (see 6260652)
+	if (elementData.getClass() != Object[].class)
+	    elementData = Arrays.copyOf(elementData, size, Object[].class);
+    }
+
+    private void initFromConcurrentlyMutating(Collection<? extends E> c) {
+	elementData = c.toArray();
+	size = elementData.length;
+	// c.toArray might (incorrectly) not return Object[] (see 6260652)
+	if (elementData.getClass() != Object[].class)
+	    elementData = Arrays.copyOf(elementData, size, Object[].class);
     }
 
+    private final static Object UNALLOCATED = new Object();
+
     /**
      * Trims the capacity of this <tt>ArrayList</tt> instance to be the
      * list's current size.  An application can use this operation to minimize
@@ -155,14 +163,7 @@ public class ArrayList<E> extends Abstra
      * necessary, to ensure that it can hold at least the number of elements
      * specified by the minimum capacity argument.
      *
-     * @param   minCapacity   the desired minimum capacity
-     */
-    /**
-     * Increases the capacity of this <tt>ArrayList</tt> instance, if
-     * necessary, to ensure that it can hold at least the number of elements
-     * specified by the minimum capacity argument.
-     *
-     * @param   minCapacity   the desired minimum capacity
+     * @param minCapacity the desired minimum capacity
      */
     public void ensureCapacity(int minCapacity) {
 	modCount++;
@@ -171,15 +172,20 @@ public class ArrayList<E> extends Abstra
     }
 
     /**
-     * Increase the capacity of the array.
-     * @param   minCapacity   the desired minimum capacity
+     * Increases the capacity of the array.
+     *
+     * @param minCapacity the desired minimum capacity
      */
     private void growArray(int minCapacity) {
+	if (minCapacity < 0) // overflow
+	    throw new OutOfMemoryError();
 	int oldCapacity = elementData.length;
         // Double size if small; else grow by 50%
-        int newCapacity = ((oldCapacity < 64)? 
-                           (oldCapacity * 2):
-                           ((oldCapacity * 3)/2 + 1));
+        int newCapacity = ((oldCapacity < 64) ?
+                           ((oldCapacity + 1) * 2) :
+                           ((oldCapacity / 2) * 3));
+        if (newCapacity < 0) // overflow
+            newCapacity = Integer.MAX_VALUE;
         if (newCapacity < minCapacity)
             newCapacity = minCapacity;
         elementData = Arrays.copyOf(elementData, newCapacity);
@@ -328,15 +334,13 @@ public class ArrayList<E> extends Abstra
 
     // Positional Access Operations
 
-    /** 
-     * Create and return an appropriate exception for indexing errors 
+    /**
+     * Throws an appropriate exception for indexing errors.
      */
-    private static IndexOutOfBoundsException rangeException(int i, int s) {
-        return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
+    private static void indexOutOfBounds(int i, int s) {
+        throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + s);
     }
 
-    // Positional Access Operations
-
     /**
      * Returns the element at the specified position in this list.
      *
@@ -346,8 +350,8 @@ public class ArrayList<E> extends Abstra
      */
     public E get(int index) {
 	if (index >= size)
-            throw rangeException(index, size);
-        return (E)elementData[index];
+	    indexOutOfBounds(index, size);
+	return (E) elementData[index];
     }
 
     /**
@@ -361,8 +365,7 @@ public class ArrayList<E> extends Abstra
      */
     public E set(int index, E element) {
  	if (index >= size)
-             throw rangeException(index, size);
-
+            indexOutOfBounds(index, size);
 	E oldValue = (E) elementData[index];
 	elementData[index] = element;
 	return oldValue;
@@ -375,12 +378,13 @@ public class ArrayList<E> extends Abstra
      * @return <tt>true</tt> (as specified by {@link Collection#add})
      */
     public boolean add(E e) {
-        ++modCount;
-        int s = size++;
+        modCount++;
+        int s = size;
         if (s >= elementData.length)
             growArray(s + 1);
  	elementData[s] = e;
- 	return true;
+	size = s + 1;
+	return true;
     }
 
     /**
@@ -395,14 +399,14 @@ public class ArrayList<E> extends Abstra
     public void add(int index, E element) {
         int s = size;
 	if (index > s || index < 0)
-	    throw rangeException(index, s);
-        ++modCount;
-        size = s + 1;
+	    indexOutOfBounds(index, s);
+        modCount++;
         if (s >= elementData.length)
             growArray(s + 1);
-	System.arraycopy(elementData, index, elementData, index + 1,
-			 s - index);
+	System.arraycopy(elementData, index,
+			 elementData, index + 1, s - index);
 	elementData[index] = element;
+        size = s + 1;
     }
 
     /**
@@ -417,16 +421,16 @@ public class ArrayList<E> extends Abstra
     public E remove(int index) {
         int s = size - 1;
 	if (index > s)
-	    throw rangeException(index, size);
-        size = s;
+	    indexOutOfBounds(index, size);
 	modCount++;
-	Object oldValue = elementData[index];
+	E oldValue = (E) elementData[index];
 	int numMoved = s - index;
 	if (numMoved > 0)
-	    System.arraycopy(elementData, index+1, elementData, index, 
-                             numMoved);
-	elementData[s] = null; // forget removed element
-	return (E)oldValue;
+	    System.arraycopy(elementData, index + 1,
+			     elementData, index, numMoved);
+	elementData[s] = null;
+	size = s;
+	return oldValue;
     }
 
     /**
@@ -525,8 +529,7 @@ public class ArrayList<E> extends Abstra
      */
     public boolean addAll(int index, Collection<? extends E> c) {
 	if (index > size || index < 0)
-	    throw new IndexOutOfBoundsException(
-		"Index: " + index + ", Size: " + size);
+	    indexOutOfBounds(index, size);
 
 	Object[] a = c.toArray();
 	int numNew = a.length;
@@ -588,7 +591,7 @@ public class ArrayList<E> extends Abstra
 	for (int i=0; i<size; i++)
             s.writeObject(elementData[i]);
 
-	if (modCount != expectedModCount) {
+	if (expectedModCount != modCount) {
             throw new ConcurrentModificationException();
         }
 
@@ -611,139 +614,4 @@ public class ArrayList<E> extends Abstra
 	for (int i=0; i<size; i++)
             a[i] = s.readObject();
     }
-
-
-    /**
-     * Returns a list-iterator of the elements in this list (in proper
-     * sequence), starting at the specified position in the list.
-     * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
-     *
-     * The list-iterator is <i>fail-fast</i>: if the list is structurally
-     * modified at any time after the Iterator is created, in any way except
-     * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
-     * methods, the list-iterator will throw a
-     * <tt>ConcurrentModificationException</tt>.  Thus, in the face of
-     * concurrent modification, the iterator fails quickly and cleanly, rather
-     * than risking arbitrary, non-deterministic behavior at an undetermined
-     * time in the future.
-     *
-     * @param index index of the first element to be returned from the
-     *              list-iterator (by a call to <tt>next</tt>)
-     * @return a ListIterator of the elements in this list (in proper
-     *         sequence), starting at the specified position in the list
-     * @throws IndexOutOfBoundsException {@inheritDoc}
-     * @see List#listIterator(int)
-     */
-    public ListIterator<E> listIterator(int index) {
-	if (index < 0 || index > size)
-            throw new IndexOutOfBoundsException("Index: "+index);
-	return new ArrayListIterator(index);
-    }
- 
-    /**
-     * Returns an iterator over the elements in this list in proper sequence.
-     *
-     * @return an iterator over the elements in this list in proper sequence
-     */
-    public Iterator<E> iterator() {
-    	return new ArrayListIterator(0);
-    }
-
-    /**
-     * A streamlined version of AbstractList.Itr 
-     */
-    final class ArrayListIterator implements ListIterator<E> {
-	int cursor;           // index of next element to return;
-	int lastRet;          // index of last element, or -1 if no such
-	int expectedModCount; // to check for CME
-
-	ArrayListIterator(int index) {
-	    cursor = index;
-            lastRet = -1;
-            expectedModCount = modCount;
-	}
-
-	public boolean hasNext() {
-            return cursor < size;
-	}
-
-	public boolean hasPrevious() {
-	    return cursor > 0;
-	}
-
-	public int nextIndex() {
-	    return cursor;
-	}
-
-	public int previousIndex() {
-	    return cursor - 1;
-	}
-
-	public E next() {
-            if (expectedModCount == modCount) {
-                int i = cursor;
-                if (i < size) {
-                    try {
-                        E e = (E)elementData[i];
-                        lastRet = i;
-                        cursor = i + 1;
-                        return e;
-                    } catch (IndexOutOfBoundsException fallthrough) { 
-                    }
-                }
-            }
-            // Prefer reporting CME if applicable on failures
-            if (expectedModCount == modCount)
-                throw new NoSuchElementException();
-            throw new ConcurrentModificationException();
-	}
-
-        public E previous() {
-            if (expectedModCount == modCount) {
-                int i = cursor - 1;
-                if (i < size) {
-                    try {
-                        E e = (E)elementData[i];
-                        lastRet = i;
-                        cursor = i;
-                        return e;
-                    } catch (IndexOutOfBoundsException fallthrough) { 
-                    }
-                }
-            }
-            if (expectedModCount == modCount)
-                throw new NoSuchElementException();
-            throw new ConcurrentModificationException();
-        }
-
-	public void remove() {
-	    if (lastRet < 0)
-		throw new IllegalStateException();
-            if (modCount != expectedModCount) 
-                throw new ConcurrentModificationException();
-            ArrayList.this.remove(lastRet);
-            if (lastRet < cursor)
-                cursor--;
-            lastRet = -1;
-            expectedModCount = modCount;
-	}
-
-	public void set(E e) {
-	    if (lastRet < 0)
-		throw new IllegalStateException();
-            if (modCount != expectedModCount) 
-                throw new ConcurrentModificationException();
-            ArrayList.this.set(lastRet, e);
-            expectedModCount = modCount;
-	}
-
-	public void add(E e) {
-            if (modCount != expectedModCount) 
-                throw new ConcurrentModificationException();
-            ArrayList.this.add(cursor++, e);
-            lastRet = -1;
-            expectedModCount = modCount;
-	}
-    }
-
 }