Replace existing ArrayList implementation with faster, simpler one.

2 files changed, 447 insertions, 462 deletions

diff --git a/luni/src/main/java/java/util/ArrayList.java b/luni/src/main/java/java/util/ArrayList.java
index b8c7056..7c46e89 100644
--- a/luni/src/main/java/java/util/ArrayList.java
+++ b/luni/src/main/java/java/util/ArrayList.java
@@ -15,12 +15,16 @@
  *  limitations under the License.
  */
 
+// BEGIN android-note
+// New implementation: simpler and faster than Harmony implementation.
+// BEGIN android-note
+
 package java.util;
 
 import java.io.IOException;
+import java.io.InvalidObjectException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
-import java.io.ObjectStreamField;
 import java.io.Serializable;
 import java.lang.reflect.Array;
 
@@ -29,37 +33,38 @@ import java.lang.reflect.Array;
  * optional operations adding, removing, and replacing are supported. The
  * elements can be any objects.
  *
+ * @param <E> The element type of this list.
  * @since 1.2
  */
-public class ArrayList<E> extends AbstractList<E> implements List<E>,
-        Cloneable, Serializable, RandomAccess {
-
-    private static final long serialVersionUID = 8683452581122892189L;
-
-    // BEGIN android-added
-    /** zero-element array */
-    private static final Object[] emptyArray = new Object[0];
-    // END android-added
-
-    private transient int firstIndex;
+public class ArrayList<E> extends AbstractList<E>
+        implements Cloneable, Serializable, RandomAccess {
+    /**
+     * An empty array of objects (to be shared among all empty lists).
+     */
+    private static final Object[] EMPTY_OBJECT_ARRAY = new Object[0];
 
-    private transient int lastIndex;
+    /**
+     * The minimum amount by which the capacity of an ArrayList will increase.
+     * This tuning parameter controls a time-space tradeoff. This value (12)
+     * gives empirically good results and is arguably consistent with the
+     * RI's specified default initial capacity of 10: instead of 10, we start
+     * with 0 (sans allocation) and jump to 12.
+     */
+    private static final int MIN_CAPACITY_INCREMENT = 12;
 
-    private transient E[] array;
+    /**
+     * The number of elements in this list.
+     */
+    int size;
 
     /**
-     * Constructs a new instance of {@code ArrayList} with zero capacity.
+     * The elements in this list, followed by nulls.
      */
-    public ArrayList() {
-        // BEGIN android-changed
-        // default capacity is zero, not ten
-        this(0);
-        // END android-changed
-    }
+    transient Object[] array;
 
     /**
      * Constructs a new instance of {@code ArrayList} with the specified
-     * capacity.
+     * initial capacity.
      *
      * @param capacity
      *            the initial capacity of this {@code ArrayList}.
@@ -68,37 +73,55 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
         if (capacity < 0) {
             throw new IllegalArgumentException();
         }
-        firstIndex = lastIndex = 0;
-        array = newElementArray(capacity);
+        array = (capacity == 0 ? EMPTY_OBJECT_ARRAY : new Object[capacity]);
+    }
+
+    /**
+     * Constructs a new {@code ArrayList} instance with zero initial capacity.
+     */
+    public ArrayList() {
+        array = EMPTY_OBJECT_ARRAY;
     }
 
     /**
      * Constructs a new instance of {@code ArrayList} containing the elements of
-     * the specified collection. The initial size of the {@code ArrayList} will
-     * be 10% higher than the size of the specified collection.
+     * the specified collection.
      *
      * @param collection
      *            the collection of elements to add.
      */
     public ArrayList(Collection<? extends E> collection) {
-        firstIndex = 0;
-        Object[] objects = collection.toArray();
-        int size = objects.length;
-        array = newElementArray(size + (size / 10));
-        System.arraycopy(objects, 0, array, 0, size);
-        lastIndex = size;
-        modCount = 1;
+        Object[] a = collection.toArray();
+        if (a.getClass() != Object[].class) {
+            Object[] newArray = new Object[a.length];
+            System.arraycopy(a, 0, newArray, 0, a.length);
+            a = newArray;
+        }
+        array = a;
+        size = a.length;
     }
 
-    @SuppressWarnings("unchecked")
-    private E[] newElementArray(int size) {
-        // BEGIN android-added
-        if (size == 0) {
-            return (E[])emptyArray;
+    /**
+     * Adds the specified object at the end of this {@code ArrayList}.
+     *
+     * @param object
+     *            the object to add.
+     * @return always true
+     */
+    @Override public boolean add(E object) {
+        Object[] a = array;
+        int s = size;
+        if (s == a.length) {
+            Object[] newArray = new Object[s +
+                    (s < (MIN_CAPACITY_INCREMENT / 2) ?
+                     MIN_CAPACITY_INCREMENT : s >> 1)];
+            System.arraycopy(a, 0, newArray, 0, s);
+            array = a = newArray;
         }
-        // END android-added
-
-        return (E[]) new Object[size];
+        a[s] = object;
+        size = s + 1;
+        modCount++;
+        return true;
     }
 
     /**
@@ -107,164 +130,136 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
      * specified location. If the location is equal to the size of this
      * {@code ArrayList}, the object is added at the end.
      *
-     * @param location
+     * @param index
      *            the index at which to insert the object.
      * @param object
      *            the object to add.
      * @throws IndexOutOfBoundsException
      *             when {@code location < 0 || > size()}
      */
-    @Override
-    public void add(int location, E object) {
-        int size = lastIndex - firstIndex;
-        if (0 < location && location < size) {
-            if (firstIndex == 0 && lastIndex == array.length) {
-                growForInsert(location, 1);
-            } else if ((location < size / 2 && firstIndex > 0)
-                    || lastIndex == array.length) {
-                System.arraycopy(array, firstIndex, array, --firstIndex,
-                        location);
-            } else {
-                int index = location + firstIndex;
-                System.arraycopy(array, index, array, index + 1, size
-                        - location);
-                lastIndex++;
-            }
-            array[location + firstIndex] = object;
-        } else if (location == 0) {
-            if (firstIndex == 0) {
-                growAtFront(1);
-            }
-            array[--firstIndex] = object;
-        } else if (location == size) {
-            if (lastIndex == array.length) {
-                growAtEnd(1);
-            }
-            array[lastIndex++] = object;
-        } else {
-            throw new IndexOutOfBoundsException();
+    @Override public void add(int index, E object) {
+        Object[] a = array;
+        int s = size;
+        if (index > s) {
+            throwIndexOutOfBoundsException(index, s);
         }
 
+        if (s < a.length) {
+            System.arraycopy(a, index, a, index + 1, s - index);
+        } else {
+            // assert s == a.length;
+            Object[] newArray = new Object[newCapacity(s)];
+            System.arraycopy(a, 0, newArray, 0, index);
+            System.arraycopy(a, index, newArray, index + 1, s - index);
+            array = a = newArray;
+        }
+        a[index] = object;
+        size = s + 1;
         modCount++;
     }
 
     /**
-     * Adds the specified object at the end of this {@code ArrayList}.
+     * This method controls the growth of ArrayList capacities.  It represents
+     * a time-space tradeoff: we don't want to grow lists too frequently
+     * (which wastes time and fragments storage), but we don't want to waste
+     * too much space in unused excess capacity.
      *
-     * @param object
-     *            the object to add.
-     * @return always true
+     * NOTE: This method is inlined into {@link #add(Object)} for performance.
+     * If you change the method, change it there too!
      */
-    @Override
-    public boolean add(E object) {
-        if (lastIndex == array.length) {
-            growAtEnd(1);
-        }
-        array[lastIndex++] = object;
-        modCount++;
-        return true;
+    private static int newCapacity(int currentCapacity) {
+        int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
+                MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
+        return currentCapacity + increment;
     }
 
     /**
-     * Inserts the objects in the specified collection at the specified location
-     * in this List. The objects are added in the order they are returned from
-     * the collection's iterator.
+     * Adds the objects in the specified collection to this {@code ArrayList}.
      *
-     * @param location
-     *            the index at which to insert.
      * @param collection
      *            the collection of objects.
      * @return {@code true} if this {@code ArrayList} is modified, {@code false}
      *         otherwise.
-     * @throws IndexOutOfBoundsException
-     *             when {@code location < 0 || > size()}
      */
-    @Override
-    public boolean addAll(int location, Collection<? extends E> collection) {
-        int size = lastIndex - firstIndex;
-        if (location < 0 || location > size) {
-            throw new IndexOutOfBoundsException();
-        }
-        if (this == collection) {
-            collection = (ArrayList)clone();
-        }
-        Object[] dumparray = collection.toArray();
-        int growSize = dumparray.length;
-        if (growSize == 0) {
+    @Override public boolean addAll(Collection<? extends E> collection) {
+        Object[] newPart = collection.toArray();
+        int newPartSize = newPart.length;
+        if (newPartSize == 0) {
             return false;
         }
-
-        if (0 < location && location < size) {
-            if (array.length - size < growSize) {
-                growForInsert(location, growSize);
-            } else if ((location < size / 2 && firstIndex > 0)
-                    || lastIndex > array.length - growSize) {
-                int newFirst = firstIndex - growSize;
-                if (newFirst < 0) {
-                    int index = location + firstIndex;
-                    System.arraycopy(array, index, array, index - newFirst,
-                            size - location);
-                    lastIndex -= newFirst;
-                    newFirst = 0;
-                }
-                System.arraycopy(array, firstIndex, array, newFirst, location);
-                firstIndex = newFirst;
-            } else {
-                int index = location + firstIndex;
-                System.arraycopy(array, index, array, index + growSize, size
-                        - location);
-                lastIndex += growSize;
-            }
-        } else if (location == 0) {
-            growAtFront(growSize);
-            firstIndex -= growSize;
-        } else if (location == size) {
-            if (lastIndex > array.length - growSize) {
-                growAtEnd(growSize);
-            }
-            lastIndex += growSize;
+        Object[] a = array;
+        int s = size;
+        int newSize = s + newPartSize; // If add overflows, arraycopy will fail
+        if (newSize > a.length) {
+            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
+            Object[] newArray = new Object[newCapacity];
+            System.arraycopy(a, 0, newArray, 0, s);
+            array = a = newArray;
         }
-
-        System.arraycopy(dumparray, 0, this.array, location + firstIndex,
-                growSize);
+        System.arraycopy(newPart, 0, a, s, newPartSize);
+        size = newSize;
         modCount++;
         return true;
     }
 
     /**
-     * Adds the objects in the specified collection to this {@code ArrayList}.
+     * Inserts the objects in the specified collection at the specified location
+     * in this List. The objects are added in the order they are returned from
+     * the collection's iterator.
      *
+     * @param index
+     *            the index at which to insert.
      * @param collection
      *            the collection of objects.
      * @return {@code true} if this {@code ArrayList} is modified, {@code false}
      *         otherwise.
+     * @throws IndexOutOfBoundsException
+     *             when {@code location < 0 || > size()}
      */
     @Override
-    public boolean addAll(Collection<? extends E> collection) {
-        Object[] dumpArray = collection.toArray();
-        if (dumpArray.length == 0) {
+    public boolean addAll(int index, Collection<? extends E> collection) {
+        Object[] newPart = collection.toArray();
+        int newPartSize = newPart.length;
+        if (newPartSize == 0) {
             return false;
         }
-        if (dumpArray.length > array.length - lastIndex) {
-            growAtEnd(dumpArray.length);
+        Object[] a = array;
+        int s = size;
+        if (index > s) {
+            throwIndexOutOfBoundsException(index, s);
         }
-        System.arraycopy(dumpArray, 0, this.array, lastIndex, dumpArray.length);
-        lastIndex += dumpArray.length;
+        int newSize = s + newPartSize; // If add overflows, arraycopy will fail
+        if (newSize <= a.length) {
+             System.arraycopy(a, index, a, index + newPartSize, s - index);
+        } else {
+            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
+            Object[] newArray = new Object[newCapacity];
+            System.arraycopy(a, 0, newArray, 0, index);
+            System.arraycopy(a, index, newArray, index + newPartSize, s-index);
+            array = a = newArray;
+        }
+        System.arraycopy(newPart, 0, a, index, newPartSize);
+        size = newSize;
         modCount++;
         return true;
     }
 
+    /** This method was extracted to encourage VM to inline callers. */
+    private static void throwIndexOutOfBoundsException(int index, int size) {
+        throw new IndexOutOfBoundsException("Invalid index " + index
+                + ", size is " + size);
+    }
+
     /**
      * Removes all elements from this {@code ArrayList}, leaving it empty.
      *
      * @see #isEmpty
      * @see #size
      */
-    @Override
-    public void clear() {
-        if (firstIndex != lastIndex) {
-            Arrays.fill(array, firstIndex, lastIndex, null);
-            firstIndex = lastIndex = 0;
+    @Override public void clear() {
+        if (size != 0) {
+            Arrays.fill(array, 0, size, null);
+            size = 0;
             modCount++;
         }
     }
@@ -276,45 +271,17 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
      * @return a shallow copy of this {@code ArrayList}
      * @see java.lang.Cloneable
      */
-    @Override
-    @SuppressWarnings("unchecked")
-    public Object clone() {
+    @Override public Object clone() {
         try {
-            ArrayList<E> newList = (ArrayList<E>) super.clone();
-            newList.array = array.clone();
-            return newList;
+            ArrayList<?> result = (ArrayList<?>) super.clone();
+            result.array = array.clone();
+            return result;
         } catch (CloneNotSupportedException e) {
-            return null;
+           throw new AssertionError();
         }
     }
 
     /**
-     * Searches this {@code ArrayList} for the specified object.
-     *
-     * @param object
-     *            the object to search for.
-     * @return {@code true} if {@code object} is an element of this
-     *         {@code ArrayList}, {@code false} otherwise
-     */
-    @Override
-    public boolean contains(Object object) {
-        if (object != null) {
-            for (int i = firstIndex; i < lastIndex; i++) {
-                if (object.equals(array[i])) {
-                    return true;
-                }
-            }
-        } else {
-            for (int i = firstIndex; i < lastIndex; i++) {
-                if (array[i] == null) {
-                    return true;
-                }
-            }
-        }
-        return false;
-    }
-
-    /**
      * Ensures that after this operation the {@code ArrayList} can hold the
      * specified number of elements without further growing.
      *
@@ -322,145 +289,93 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
      *            the minimum capacity asked for.
      */
     public void ensureCapacity(int minimumCapacity) {
-        if (array.length < minimumCapacity) {
-            if (firstIndex > 0) {
-                growAtFront(minimumCapacity - array.length);
-            } else {
-                growAtEnd(minimumCapacity - array.length);
-            }
+        Object[] a = array;
+        if (a.length < minimumCapacity) {
+            Object[] newArray = new Object[minimumCapacity];
+            System.arraycopy(a, 0, newArray, 0, size);
+            array = newArray;
+            modCount++;
         }
     }
 
-    @Override
-    public E get(int location) {
-        // BEGIN android-changed: slight performance improvement
-        int _firstIndex = firstIndex;
-        if (0 <= location && location < lastIndex - _firstIndex) {
-            return array[_firstIndex + location];
-        }
-        throw new IndexOutOfBoundsException("Invalid location " + location
-                + ", size is " + (lastIndex - _firstIndex));
-        // END android-changed
+    @SuppressWarnings("unchecked") @Override public E get(int index) {
+        if (index >= size) {
+            throwIndexOutOfBoundsException(index, size);
+        }
+        return (E) array[index];
     }
 
-    private void growAtEnd(int required) {
-        int size = lastIndex - firstIndex;
-        if (firstIndex >= required - (array.length - lastIndex)) {
-            int newLast = lastIndex - firstIndex;
-            if (size > 0) {
-                System.arraycopy(array, firstIndex, array, 0, size);
-                int start = newLast < firstIndex ? firstIndex : newLast;
-                Arrays.fill(array, start, array.length, null);
-            }
-            firstIndex = 0;
-            lastIndex = newLast;
-        } else {
-            int increment = size / 2;
-            if (required > increment) {
-                increment = required;
-            }
-            if (increment < 12) {
-                increment = 12;
-            }
-            E[] newArray = newElementArray(size + increment);
-            if (size > 0) {
-                System.arraycopy(array, firstIndex, newArray, 0, size);
-                firstIndex = 0;
-                lastIndex = size;
-            }
-            array = newArray;
-        }
+    /**
+     * Returns the number of elements in this {@code ArrayList}.
+     *
+     * @return the number of elements in this {@code ArrayList}.
+     */
+    @Override public int size() {
+        return size;
+    }
+
+    @Override public boolean isEmpty() {
+        return size == 0;
     }
 
-    private void growAtFront(int required) {
-        int size = lastIndex - firstIndex;
-        if (array.length - lastIndex + firstIndex >= required) {
-            int newFirst = array.length - size;
-            if (size > 0) {
-                System.arraycopy(array, firstIndex, array, newFirst, size);
-                int length = firstIndex + size > newFirst ? newFirst
-                        : firstIndex + size;
-                Arrays.fill(array, firstIndex, length, null);
+    /**
+     * Searches this {@code ArrayList} for the specified object.
+     *
+     * @param object
+     *            the object to search for.
+     * @return {@code true} if {@code object} is an element of this
+     *         {@code ArrayList}, {@code false} otherwise
+     */
+    @Override public boolean contains(Object object) {
+        Object[] a = array;
+        int s = size;
+        if (object != null) {
+            for (int i = 0; i < s; i++) {
+                if (object.equals(a[i])) {
+                    return true;
+                }
             }
-            firstIndex = newFirst;
-            lastIndex = array.length;
         } else {
-            int increment = size / 2;
-            if (required > increment) {
-                increment = required;
-            }
-            if (increment < 12) {
-                increment = 12;
-            }
-            E[] newArray = newElementArray(size + increment);
-            if (size > 0) {
-                System.arraycopy(array, firstIndex, newArray, newArray.length
-                        - size, size);
+            for (int i = 0; i < s; i++) {
+                if (a[i] == null) {
+                    return true;
+                }
             }
-            firstIndex = newArray.length - size;
-            lastIndex = newArray.length;
-            array = newArray;
         }
+        return false;
     }
 
-    private void growForInsert(int location, int required) {
-        int size = lastIndex - firstIndex;
-        int increment = size / 2;
-        if (required > increment) {
-            increment = required;
-        }
-        if (increment < 12) {
-            increment = 12;
-        }
-        E[] newArray = newElementArray(size + increment);
-        int newFirst = increment - required;
-        // Copy elements after location to the new array skipping inserted
-        // elements
-        System.arraycopy(array, location + firstIndex, newArray, newFirst
-                + location + required, size - location);
-        // Copy elements before location to the new array from firstIndex
-        System.arraycopy(array, firstIndex, newArray, newFirst, location);
-        firstIndex = newFirst;
-        lastIndex = size + increment;
-
-        array = newArray;
-    }
-
-    @Override
-    public int indexOf(Object object) {
+    @Override public int indexOf(Object object) {
+        Object[] a = array;
+        int s = size;
         if (object != null) {
-            for (int i = firstIndex; i < lastIndex; i++) {
-                if (object.equals(array[i])) {
-                    return i - firstIndex;
+            for (int i = 0; i < s; i++) {
+                if (object.equals(a[i])) {
+                    return i;
                 }
             }
         } else {
-            for (int i = firstIndex; i < lastIndex; i++) {
-                if (array[i] == null) {
-                    return i - firstIndex;
+            for (int i = 0; i < s; i++) {
+                if (a[i] == null) {
+                    return i;
                 }
             }
         }
         return -1;
     }
 
-    @Override
-    public boolean isEmpty() {
-        return lastIndex == firstIndex;
-    }
-
-    @Override
-    public int lastIndexOf(Object object) {
+    @Override public int lastIndexOf(Object object) {
+        Object[] a = array;
         if (object != null) {
-            for (int i = lastIndex - 1; i >= firstIndex; i--) {
-                if (object.equals(array[i])) {
-                    return i - firstIndex;
+            for (int i = size - 1; i >= 0; i--) {
+                if (object.equals(a[i])) {
+                    return i;
                 }
             }
         } else {
-            for (int i = lastIndex - 1; i >= firstIndex; i--) {
-                if (array[i] == null) {
-                    return i - firstIndex;
+            for (int i = size - 1; i >= 0; i--) {
+                if (a[i] == null) {
+                    return i;
                 }
             }
         }
@@ -470,99 +385,81 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
     /**
      * Removes the object at the specified location from this list.
      *
-     * @param location
+     * @param index
      *            the index of the object to remove.
      * @return the removed object.
      * @throws IndexOutOfBoundsException
      *             when {@code location < 0 || >= size()}
      */
-    @Override
-    public E remove(int location) {
-        E result;
-        int size = lastIndex - firstIndex;
-        if (0 <= location && location < size) {
-            if (location == size - 1) {
-                result = array[--lastIndex];
-                array[lastIndex] = null;
-            } else if (location == 0) {
-                result = array[firstIndex];
-                array[firstIndex++] = null;
-            } else {
-                int elementIndex = firstIndex + location;
-                result = array[elementIndex];
-                if (location < size / 2) {
-                    System.arraycopy(array, firstIndex, array, firstIndex + 1,
-                            location);
-                    array[firstIndex++] = null;
-                } else {
-                    System.arraycopy(array, elementIndex + 1, array,
-                            elementIndex, size - location - 1);
-                    array[--lastIndex] = null;
-                }
-            }
-            if (firstIndex == lastIndex) {
-                firstIndex = lastIndex = 0;
-            }
-        } else {
-            throw new IndexOutOfBoundsException();
+    @Override public E remove(int index) {
+        Object[] a = array;
+        int s = size;
+        if (index >= s) {
+            throwIndexOutOfBoundsException(index, s);
         }
-
+        @SuppressWarnings("unchecked") E result = (E) a[index];
+        System.arraycopy(a, index + 1, a, index, --s - index);
+        a[s] = null;  // Prevent memory leak
+        size = s;
         modCount++;
         return result;
     }
 
-    @Override
-    public boolean remove(Object object) {
-        int location = indexOf(object);
-        if (location >= 0) {
-            remove(location);
-            return true;
+    @Override public boolean remove(Object object) {
+        Object[] a = array;
+        int s = size;
+        if (object != null) {
+            for (int i = 0; i < s; i++) {
+                if (object.equals(a[i])) {
+                    System.arraycopy(a, i + 1, a, i, --s - i);
+                    a[s] = null;  // Prevent memory leak
+                    size = s;
+                    modCount++;
+                    return true;
+                }
+            }
+        } else {
+            for (int i = 0; i < s; i++) {
+                if (a[i] == null) {
+                    System.arraycopy(a, i + 1, a, i, --s - i);
+                    a[s] = null;  // Prevent memory leak
+                    size = s;
+                    modCount++;
+                    return true;
+                }
+            }
         }
         return false;
     }
 
-    /**
-     * Removes the objects in the specified range from the start to the end, but
-     * not including the end index.
-     *
-     * @param start
-     *            the index at which to start removing.
-     * @param end
-     *            the index one after the end of the range to remove.
-     * @throws IndexOutOfBoundsException
-     *             when {@code start < 0, start > end} or {@code end > size()}
-     */
-    @Override
-    protected void removeRange(int start, int end) {
-        if (start >= 0 && start <= end && end <= (lastIndex - firstIndex)) {
-            if (start == end) {
-                return;
-            }
-            int size = lastIndex - firstIndex;
-            if (end == size) {
-                Arrays.fill(array, firstIndex + start, lastIndex, null);
-                lastIndex = firstIndex + start;
-            } else if (start == 0) {
-                Arrays.fill(array, firstIndex, firstIndex + end, null);
-                firstIndex += end;
-            } else {
-                System.arraycopy(array, firstIndex + end, array, firstIndex
-                        + start, size - end);
-                int newLast = lastIndex + start - end;
-                Arrays.fill(array, newLast, lastIndex, null);
-                lastIndex = newLast;
-            }
-            modCount++;
-        } else {
-            throw new IndexOutOfBoundsException();
+    @Override protected void removeRange(int fromIndex, int toIndex) {
+        Object[] a = array;
+        int s = size;
+        if (fromIndex >= s) {
+            throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+                    + " >= size " + size);
         }
+        if (toIndex > s) {
+            throw new IndexOutOfBoundsException("toIndex " + toIndex
+                    + " > size " + size);
+        }
+        if (fromIndex > toIndex) {
+            throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+                    + " > toIndex " + toIndex);
+        }
+
+        System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
+        int rangeSize = toIndex - fromIndex;
+        Arrays.fill(a, s - rangeSize, s, null);
+        size = s - rangeSize;
+        modCount++;
     }
 
     /**
      * Replaces the element at the specified location in this {@code ArrayList}
      * with the specified object.
      *
-     * @param location
+     * @param index
      *            the index at which to put the specified object.
      * @param object
      *            the object to add.
@@ -570,24 +467,14 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
      * @throws IndexOutOfBoundsException
      *             when {@code location < 0 || >= size()}
      */
-    @Override
-    public E set(int location, E object) {
-        if (0 <= location && location < (lastIndex - firstIndex)) {
-            E result = array[firstIndex + location];
-            array[firstIndex + location] = object;
-            return result;
+    @Override public E set(int index, E object) {
+        Object[] a = array;
+        if (index >= size) {
+            throwIndexOutOfBoundsException(index, size);
         }
-        throw new IndexOutOfBoundsException();
-    }
-
-    /**
-     * Returns the number of elements in this {@code ArrayList}.
-     *
-     * @return the number of elements in this {@code ArrayList}.
-     */
-    @Override
-    public int size() {
-        return lastIndex - firstIndex;
+        @SuppressWarnings("unchecked") E result = (E) a[index];
+        a[index] = object;
+        return result;
     }
 
     /**
@@ -596,11 +483,10 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
      *
      * @return an array of the elements from this {@code ArrayList}
      */
-    @Override
-    public Object[] toArray() {
-        int size = lastIndex - firstIndex;
-        Object[] result = new Object[size];
-        System.arraycopy(array, firstIndex, result, 0, size);
+    @Override public Object[] toArray() {
+        int s = size;
+        Object[] result = new Object[s];
+        System.arraycopy(array, 0, result, 0, s);
         return result;
     }
 
@@ -619,17 +505,16 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
      *             when the type of an element in this {@code ArrayList} cannot
      *             be stored in the type of the specified array.
      */
-    @Override
-    @SuppressWarnings("unchecked")
-    public <T> T[] toArray(T[] contents) {
-        int size = lastIndex - firstIndex;
-        if (size > contents.length) {
-            Class<?> ct = contents.getClass().getComponentType();
-            contents = (T[]) Array.newInstance(ct, size);
+    @Override public <T> T[] toArray(T[] contents) {
+        int s = size;
+        if (contents.length < s) {
+            @SuppressWarnings("unchecked") T[] newArray
+                = (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
+            contents = newArray;
         }
-        System.arraycopy(array, firstIndex, contents, 0, size);
-        if (size < contents.length) {
-            contents[size] = null;
+        System.arraycopy(this.array, 0, contents, 0, s);
+        if (contents.length > s) {
+            contents[s] = null;
         }
         return contents;
     }
@@ -641,37 +526,132 @@ public class ArrayList<E> extends AbstractList<E> implements List<E>,
      * @see #size
      */
     public void trimToSize() {
-        int size = lastIndex - firstIndex;
-        E[] newArray = newElementArray(size);
-        System.arraycopy(array, firstIndex, newArray, 0, size);
-        array = newArray;
-        firstIndex = 0;
-        lastIndex = array.length;
-        modCount = 0;
+        int s = size;
+        if (s == array.length) {
+            return;
+        }
+        if (s == 0) {
+            array = EMPTY_OBJECT_ARRAY;
+        } else {
+            Object[] newArray = new Object[s];
+            System.arraycopy(array, 0, newArray, 0, s);
+            array = newArray;
+        }
+        modCount++;
+    }
+
+    @Override public Iterator<E> iterator() {
+        return new ArrayListIterator();
+    }
+
+    private class ArrayListIterator implements Iterator<E> {
+        /** Number of elements remaining in this iteration */
+        private int remaining = size;
+
+        /** Index of element that remove() would remove, or -1 if no such elt */
+        private int removalIndex = -1;
+
+        /** The expected modCount value */
+        private int expectedModCount = modCount;
+
+        public boolean hasNext() {
+            return remaining != 0;
+        }
+
+        @SuppressWarnings("unchecked") public E next() {
+            ArrayList<E> ourList = ArrayList.this;
+            int rem = remaining;
+            if (ourList.modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
+            if (rem == 0) {
+                throw new NoSuchElementException();
+            }
+            remaining = rem - 1;
+            return (E) ourList.array[removalIndex = ourList.size - rem];
+        }
+
+        public void remove() {
+            Object[] a = array;
+            int removalIdx = removalIndex;
+            if (modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
+            if (removalIdx < 0) {
+                throw new IllegalStateException();
+            }
+            System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
+            a[--size] = null;  // Prevent memory leak
+            removalIndex = -1;
+            expectedModCount = ++modCount;
+        }
     }
 
-    private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField(
-            "size", Integer.TYPE) }; //$NON-NLS-1$
+    @Override public int hashCode() {
+        Object[] a = array;
+        int hashCode = 1;
+        for (int i = 0, s = size; i < s; i++) {
+            Object e = a[i];
+            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
+        }
+        return hashCode;
+    }
+
+    @Override public boolean equals(Object o) {
+        if (o == this) {
+            return true;
+        }
+        if (!(o instanceof List)) {
+            return false;
+        }
+        List<?> that = (List<?>) o;
+        int s = size;
+        if (that.size() != s) {
+            return false;
+        }
+        Object[] a = array;
+        if (that instanceof RandomAccess) {
+            for (int i = 0; i < s; i++) {
+                Object eThis = a[i];
+                Object ethat = that.get(i);
+                if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
+                    return false;
+                }
+            }
+        } else {  // Argument list is not random access; use its iterator
+            Iterator<?> it = that.iterator();
+            for (int i = 0; i < s; i++) {
+                Object eThis = a[i];
+                Object eThat = it.next();
+                if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+
+    private static final long serialVersionUID = 8683452581122892189L;
 
     private void writeObject(ObjectOutputStream stream) throws IOException {
-        ObjectOutputStream.PutField fields = stream.putFields();
-        fields.put("size", lastIndex - firstIndex); //$NON-NLS-1$
-        stream.writeFields();
+        stream.defaultWriteObject();
         stream.writeInt(array.length);
-        Iterator<?> it = iterator();
-        while (it.hasNext()) {
-            stream.writeObject(it.next());
+        for (int i = 0; i < size; i++) {
+            stream.writeObject(array[i]);
         }
     }
 
-    @SuppressWarnings("unchecked")
     private void readObject(ObjectInputStream stream) throws IOException,
             ClassNotFoundException {
-        ObjectInputStream.GetField fields = stream.readFields();
-        lastIndex = fields.get("size", 0); //$NON-NLS-1$
-        array = newElementArray(stream.readInt());
-        for (int i = 0; i < lastIndex; i++) {
-            array[i] = (E) stream.readObject();
+        stream.defaultReadObject();
+        int cap = stream.readInt();
+        if (cap < size) {
+            throw new InvalidObjectException(
+                    "Capacity: " + cap + " < size: " + size);
+        }
+        array = (cap == 0 ? EMPTY_OBJECT_ARRAY : new Object[cap]);
+        for (int i = 0; i < size; i++) {
+            array[i] = stream.readObject();
         }
     }
-}
+ }
diff --git a/luni/src/test/java/tests/api/java/util/ArrayListTest.java b/luni/src/test/java/tests/api/java/util/ArrayListTest.java
index 8aa77cc..0356731 100644
--- a/luni/src/test/java/tests/api/java/util/ArrayListTest.java
+++ b/luni/src/test/java/tests/api/java/util/ArrayListTest.java
@@ -19,7 +19,7 @@ package tests.api.java.util;
 import dalvik.annotation.TestTargetNew;
 import dalvik.annotation.TestTargets;
 import dalvik.annotation.TestLevel;
-import dalvik.annotation.TestTargetClass; 
+import dalvik.annotation.TestTargetClass;
 
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -33,13 +33,13 @@ import java.util.Vector;
 
 import tests.support.Support_ListTest;
 
-@TestTargetClass(ArrayList.class) 
+@TestTargetClass(ArrayList.class)
 public class ArrayListTest extends junit.framework.TestCase {
 
     List alist;
 
     Object[] objArray;
-    
+
     /**
      * @tests java.util.ArrayList#ArrayList()
      */
@@ -72,7 +72,7 @@ public class ArrayListTest extends junit.framework.TestCase {
         // Test for method java.util.ArrayList(int)
         ArrayList al = new ArrayList(5);
         assertEquals("Incorrect arrayList created", 0, al.size());
-        
+
         try {
             new ArrayList(-10);
             fail("IllegalArgumentException expected");
@@ -130,14 +130,14 @@ public class ArrayListTest extends junit.framework.TestCase {
         assertNull("Should have returned null", alist.get(25));
         assertTrue("Should have returned the old item from slot 25", alist
                 .get(26) == oldItem);
-        
+
         try {
             alist.add(-1, null);
             fail("IndexOutOfBoundsException expected");
         } catch (IndexOutOfBoundsException e) {
             //expected
         }
-        
+
         try {
             alist.add(alist.size() + 1, null);
             fail("IndexOutOfBoundsException expected");
@@ -198,9 +198,9 @@ public class ArrayListTest extends junit.framework.TestCase {
         assertTrue("Incorrect size: " + alist.size(), alist.size() == 205);
         assertNull("Item at slot 100 should be null", alist.get(100));
         assertNull("Item at slot 101 should be null", alist.get(101));
-        assertEquals("Item at slot 102 should be 'yoink'", 
+        assertEquals("Item at slot 102 should be 'yoink'",
                 "yoink", alist.get(102));
-        assertEquals("Item at slot 103 should be 'kazoo'", 
+        assertEquals("Item at slot 103 should be 'kazoo'",
                 "kazoo", alist.get(103));
         assertNull("Item at slot 104 should be null", alist.get(104));
         alist.addAll(205, listWithNulls);
@@ -228,24 +228,29 @@ public class ArrayListTest extends junit.framework.TestCase {
         }
     }
 
-    /**
-     * @tests java.util.ArrayList#addAll(int, java.util.Collection)
-     */
-    @TestTargetNew(
-        level = TestLevel.PARTIAL_COMPLETE,
-        notes = "Verifies IndexOutOfBoundsException.",
-        method = "addAll",
-        args = {int.class, java.util.Collection.class}
-    )
-    public void test_addAllILjava_util_Collection_2() {
-        // Regression for HARMONY-467
-        ArrayList obj = new ArrayList();
-        try {
-            obj.addAll((int) -1, (Collection) null);
-            fail("IndexOutOfBoundsException expected");
-        } catch (IndexOutOfBoundsException e) {
-        }
-    }
+// BEGIN android-removed
+// The spec does not mandate that IndexOutOfBoundsException be thrown in
+// preference to NullPointerException when the caller desserves both.
+//
+//    /**
+//     * @tests java.util.ArrayList#addAll(int, java.util.Collection)
+//     */
+//    @TestTargetNew(
+//        level = TestLevel.PARTIAL_COMPLETE,
+//        notes = "Verifies IndexOutOfBoundsException.",
+//        method = "addAll",
+//        args = {int.class, java.util.Collection.class}
+//    )
+//    public void test_addAllILjava_util_Collection_2() {
+//        // Regression for HARMONY-467
+//        ArrayList obj = new ArrayList();
+//        try {
+//            obj.addAll((int) -1, (Collection) null);
+//            fail("IndexOutOfBoundsException expected");
+//        } catch (IndexOutOfBoundsException e) {
+//        }
+//    }
+// END android-removed
 
     /**
      * @tests java.util.ArrayList#addAll(java.util.Collection)
@@ -287,17 +292,17 @@ public class ArrayListTest extends junit.framework.TestCase {
                 .get(101) == i.next());
         assertTrue("Item at slot 103 is wrong: " + alist.get(102), alist
                 .get(102) == i.next());
-        
-        
+
+
         // Regression test for Harmony-3481
         ArrayList<Integer> originalList = new ArrayList<Integer>(12);
         for (int j = 0; j < 12; j++) {
             originalList.add(j);
         }
-        
+
         originalList.remove(0);
         originalList.remove(0);
-        
+
         ArrayList<Integer> additionalList = new ArrayList<Integer>(11);
         for (int j = 0; j < 11; j++) {
             additionalList.add(j);
@@ -672,7 +677,7 @@ public class ArrayListTest extends junit.framework.TestCase {
                 assertTrue("Returned incorrect array: " + i,
                         retArray[i] == objArray[i]);
         }
-        
+
         String[] strArray = new String[100];
         try {
             alist.toArray(strArray);
@@ -746,16 +751,16 @@ public class ArrayListTest extends junit.framework.TestCase {
 
         list.remove(0);
         assertEquals(1, list.size());
-        
+
         ArrayList collection = new ArrayList();
         collection.add("1");
         collection.add("2");
         collection.add("3");
         assertEquals(3, collection.size());
-        
+
         list.addAll(0, collection);
         assertEquals(4, list.size());
-        
+
         list.remove(0);
         list.remove(0);
         assertEquals(2, list.size());
@@ -769,13 +774,13 @@ public class ArrayListTest extends junit.framework.TestCase {
         collection.add("10");
         collection.add("11");
         collection.add("12");
-        
+
         assertEquals(12, collection.size());
-        
+
         list.addAll(0, collection);
         assertEquals(14, list.size());
     }
-    
+
     @TestTargetNew(
         level = TestLevel.COMPLETE,
         notes = "",
@@ -818,7 +823,7 @@ public class ArrayListTest extends junit.framework.TestCase {
         mal.add("f");
         mal.add("g");
         mal.add("h");
-        
+
         mal.removeRange(2, 4);
 
         String[] result = new String[6];
@@ -827,30 +832,30 @@ public class ArrayListTest extends junit.framework.TestCase {
                 new String[] { "a", "b", "e", "f", "g", "h"}));
     }
 
-    
+
     /**
      * Sets up the fixture, for example, open a network connection. This method
      * is called before a test is executed.
      */
     protected void setUp() throws Exception {
         super.setUp();
-        
+
         objArray = new Object[100];
         for (int i = 0; i < objArray.length; i++) {
             objArray[i] = new Integer(i);
         }
-        
+
         alist = new ArrayList();
         for (int i = 0; i < objArray.length; i++) {
             alist.add(objArray[i]);
         }
     }
-    
+
     @Override
     protected void tearDown() throws Exception {
         objArray = null;
         alist = null;
-        
+
         super.tearDown();
     }
 }