Replace existing ArrayList implementation with faster, simpler one.
diff --git a/libcore/luni/src/main/java/java/util/ArrayList.java b/libcore/luni/src/main/java/java/util/ArrayList.java
index b8c7056..7c46e89 100644
--- a/libcore/luni/src/main/java/java/util/ArrayList.java
+++ b/libcore/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 @@
* 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;
-
- private transient int lastIndex;
-
- private transient E[] array;
+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];
/**
- * Constructs a new instance of {@code ArrayList} with zero capacity.
+ * 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.
*/
- public ArrayList() {
- // BEGIN android-changed
- // default capacity is zero, not ten
- this(0);
- // END android-changed
- }
+ private static final int MIN_CAPACITY_INCREMENT = 12;
+
+ /**
+ * The number of elements in this list.
+ */
+ int size;
+
+ /**
+ * The elements in this list, followed by nulls.
+ */
+ 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,84 +73,32 @@
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;
- }
-
- @SuppressWarnings("unchecked")
- private E[] newElementArray(int size) {
- // BEGIN android-added
- if (size == 0) {
- return (E[])emptyArray;
+ 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;
}
- // END android-added
-
- return (E[]) new Object[size];
- }
-
- /**
- * Inserts the specified object into this {@code ArrayList} at the specified
- * location. The object is inserted before any previous element at the
- * specified location. If the location is equal to the size of this
- * {@code ArrayList}, the object is added at the end.
- *
- * @param location
- * 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();
- }
-
- modCount++;
+ array = a;
+ size = a.length;
}
/**
@@ -155,80 +108,69 @@
* the object to add.
* @return always true
*/
- @Override
- public boolean add(E object) {
- if (lastIndex == array.length) {
- growAtEnd(1);
+ @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;
}
- array[lastIndex++] = object;
+ a[s] = object;
+ size = s + 1;
modCount++;
return true;
}
/**
- * 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.
+ * Inserts the specified object into this {@code ArrayList} at the specified
+ * location. The object is inserted before any previous element at the
+ * specified location. If the location is equal to the size of this
+ * {@code ArrayList}, the object is added at the end.
*
- * @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.
+ * @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 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) {
- return false;
+ @Override public void add(int index, E object) {
+ Object[] a = array;
+ int s = size;
+ if (index > s) {
+ throwIndexOutOfBoundsException(index, s);
}
- 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;
+ 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;
}
-
- System.arraycopy(dumparray, 0, this.array, location + firstIndex,
- growSize);
+ a[index] = object;
+ size = s + 1;
modCount++;
- return true;
+ }
+
+ /**
+ * 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.
+ *
+ * NOTE: This method is inlined into {@link #add(Object)} for performance.
+ * If you change the method, change it there too!
+ */
+ private static int newCapacity(int currentCapacity) {
+ int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
+ MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
+ return currentCapacity + increment;
}
/**
@@ -239,32 +181,85 @@
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
*/
- @Override
- public boolean addAll(Collection<? extends E> collection) {
- Object[] dumpArray = collection.toArray();
- if (dumpArray.length == 0) {
+ @Override public boolean addAll(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;
+ 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, lastIndex, dumpArray.length);
- lastIndex += dumpArray.length;
+ System.arraycopy(newPart, 0, a, s, newPartSize);
+ size = newSize;
modCount++;
return true;
}
/**
+ * 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(int index, Collection<? extends E> collection) {
+ Object[] newPart = collection.toArray();
+ int newPartSize = newPart.length;
+ if (newPartSize == 0) {
+ return false;
+ }
+ Object[] a = array;
+ int s = size;
+ if (index > s) {
+ throwIndexOutOfBoundsException(index, s);
+ }
+ 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 @@
* @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 @@
* 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);
- }
- }
- }
-
- @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
- }
-
- 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;
- }
+ Object[] a = array;
+ if (a.length < minimumCapacity) {
+ Object[] newArray = new Object[minimumCapacity];
+ System.arraycopy(a, 0, newArray, 0, size);
array = newArray;
+ modCount++;
}
}
- 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);
- }
- 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);
- }
- firstIndex = newArray.length - size;
- lastIndex = newArray.length;
- array = newArray;
+ @SuppressWarnings("unchecked") @Override public E get(int index) {
+ if (index >= size) {
+ throwIndexOutOfBoundsException(index, size);
}
+ return (E) array[index];
}
- 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;
+ /**
+ * 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 int indexOf(Object object) {
+ @Override public boolean isEmpty() {
+ return size == 0;
+ }
+
+ /**
+ * 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 = 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 true;
}
}
} 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 true;
+ }
+ }
+ }
+ return false;
+ }
+
+ @Override public int indexOf(Object object) {
+ Object[] a = array;
+ int s = size;
+ if (object != null) {
+ for (int i = 0; i < s; i++) {
+ if (object.equals(a[i])) {
+ return i;
+ }
+ }
+ } else {
+ 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 @@
/**
* 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 @@
* @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 @@
*
* @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 @@
* 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 @@
* @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++;
}
- private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField(
- "size", Integer.TYPE) }; //$NON-NLS-1$
+ @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;
+ }
+ }
+
+ @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/libcore/luni/src/test/java/tests/api/java/util/ArrayListTest.java b/libcore/luni/src/test/java/tests/api/java/util/ArrayListTest.java
index 8aa77cc..0356731 100644
--- a/libcore/luni/src/test/java/tests/api/java/util/ArrayListTest.java
+++ b/libcore/luni/src/test/java/tests/api/java/util/ArrayListTest.java
@@ -19,7 +19,7 @@
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 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 @@
// 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 @@
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 @@
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 @@
}
}
- /**
- * @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 @@
.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 @@
assertTrue("Returned incorrect array: " + i,
retArray[i] == objArray[i]);
}
-
+
String[] strArray = new String[100];
try {
alist.toArray(strArray);
@@ -746,16 +751,16 @@
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 @@
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 @@
mal.add("f");
mal.add("g");
mal.add("h");
-
+
mal.removeRange(2, 4);
String[] result = new String[6];
@@ -827,30 +832,30 @@
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();
}
}
