--- jsr166/src/main/java/util/ArrayList.java 2005/11/25 13:34:29 1.2
+++ jsr166/src/main/java/util/ArrayList.java 2006/05/28 23:36:29 1.21
@@ -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 List interface. Implements
@@ -67,7 +66,7 @@ import java.util.*; // for javadoc (till
* should be used only to detect bugs.
*
* This class is a member of the
- *
+ *
* Java Collections Framework.
*
* @author Josh Bloch
@@ -101,9 +100,9 @@ public class ArrayList 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,30 +122,19 @@ public class ArrayList extends Abstra
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
- * iterator. The ArrayList instance has an initial capacity of
- * 110% the size of the specified collection.
+ * 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) {
- int size = c.size();
- // 10% for growth
- int cap = ((size/10)+1)*11;
- if (cap > 0) {
- Object[] a = new Object[cap];
- a[size] = a[size+1] = UNALLOCATED;
- Object[] b = c.toArray(a);
- if (b[size] == null && b[size+1] == UNALLOCATED) {
- b[size+1] = null;
- elementData = b;
- this.size = size;
- return;
- }
- }
- initFromConcurrentlyMutating(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 void initFromConcurrentlyMutating(Collection extends E> c) {
elementData = c.toArray();
size = elementData.length;
@@ -154,9 +142,9 @@ public class ArrayList extends Abstra
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
-
+
private final static Object UNALLOCATED = new Object();
-
+
/**
* Trims the capacity of this ArrayList instance to be the
* list's current size. An application can use this operation to minimize
@@ -175,14 +163,7 @@ public class ArrayList 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 ArrayList 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++;
@@ -191,15 +172,20 @@ public class ArrayList 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);
@@ -348,15 +334,13 @@ public class ArrayList 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.
*
@@ -366,8 +350,8 @@ public class ArrayList 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];
}
/**
@@ -381,8 +365,7 @@ public class ArrayList 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;
@@ -395,12 +378,13 @@ public class ArrayList extends Abstra
* @return true (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;
}
/**
@@ -415,14 +399,14 @@ public class ArrayList 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;
}
/**
@@ -437,16 +421,16 @@ public class ArrayList 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;
}
/**
@@ -545,8 +529,7 @@ public class ArrayList 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;
@@ -608,7 +591,7 @@ public class ArrayList extends Abstra
for (int i=0; i extends Abstra
for (int i=0; iList.listIterator(int).
- *
- * The list-iterator is fail-fast: if the list is structurally
- * modified at any time after the Iterator is created, in any way except
- * through the list-iterator's own remove or add
- * methods, the list-iterator will throw a
- * ConcurrentModificationException. 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 next)
- * @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 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 iterator() {
- return new ArrayListIterator(0);
- }
-
- /**
- * A streamlined version of AbstractList.Itr
- */
- final class ArrayListIterator implements ListIterator {
- 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;
- }
- }
-
}