--- jsr166/src/main/java/util/ArrayList.java 2007/05/20 07:54:01 1.24 +++ jsr166/src/main/java/util/ArrayList.java 2007/09/11 15:38:02 1.25 @@ -31,23 +31,23 @@ package java.util; * null. In addition to implementing the List interface, * this class provides methods to manipulate the size of the array that is * used internally to store the list. (This class is roughly equivalent to - * Vector, except that it is unsynchronized.)

+ * Vector, except that it is unsynchronized.) * - * The size, isEmpty, get, set, + *

The size, isEmpty, get, set, * iterator, and listIterator operations run in constant * time. The add operation runs in amortized constant time, * that is, adding n elements requires O(n) time. All of the other operations * run in linear time (roughly speaking). The constant factor is low compared - * to that for the LinkedList implementation.

+ * to that for the LinkedList implementation. * - * Each ArrayList instance has a capacity. The capacity is + *

Each ArrayList instance has a capacity. The capacity is * the size of the array used to store the elements in the list. It is always * at least as large as the list size. As elements are added to an ArrayList, * its capacity grows automatically. The details of the growth policy are not * specified beyond the fact that adding an element has constant amortized - * time cost.

+ * time cost. * - * An application can increase the capacity of an ArrayList instance + *

An application can increase the capacity of an ArrayList instance * before adding a large number of elements using the ensureCapacity * operation. This may reduce the amount of incremental reallocation. * @@ -66,24 +66,27 @@ package java.util; * unsynchronized access to the list:

  *   List list = Collections.synchronizedList(new ArrayList(...));
* - *

The iterators returned by this class's iterator and - * listIterator methods are fail-fast: if the list is - * structurally modified at any time after the iterator is created, in any way - * except through the iterator's own remove or add methods, - * the iterator will throw a {@link 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.

+ *

+ * The iterators returned by this class's {@link #iterator() iterator} and + * {@link #listIterator(int) listIterator} methods are fail-fast: + * if the list is structurally modified at any time after the iterator is + * created, in any way except through the iterator's own + * {@link ListIterator#remove() remove} or + * {@link ListIterator#add(Object) add} methods, the iterator will throw a + * {@link 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. * - * Note that the fail-fast behavior of an iterator cannot be guaranteed + *

Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators - * throw ConcurrentModificationException on a best-effort basis. + * throw {@code ConcurrentModificationException} on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this - * exception for its correctness: the fail-fast behavior of iterators - * should be used only to detect bugs.

+ * exception for its correctness: the fail-fast behavior of iterators + * should be used only to detect bugs. * - * This class is a member of the + *

This class is a member of the * * Java Collections Framework. * @@ -118,9 +121,9 @@ public class ArrayList extends Abstra /** * Constructs an empty list with the specified initial capacity. * - * @param initialCapacity the initial capacity of the list - * @throws IllegalArgumentException if the specified initial capacity - * is negative + * @param initialCapacity the initial capacity of the list + * @exception IllegalArgumentException if the specified initial capacity + * is negative */ public ArrayList(int initialCapacity) { super(); @@ -171,32 +174,19 @@ 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 + * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { modCount++; - if (minCapacity > elementData.length) - growArray(minCapacity); - } - - /** - * 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 + 1) * 2) : - ((oldCapacity / 2) * 3)); - if (newCapacity < 0) // overflow - newCapacity = Integer.MAX_VALUE; - if (newCapacity < minCapacity) - newCapacity = minCapacity; - elementData = Arrays.copyOf(elementData, newCapacity); + if (minCapacity > oldCapacity) { + Object oldData[] = elementData; + int newCapacity = (oldCapacity * 3)/2 + 1; + if (newCapacity < minCapacity) + newCapacity = minCapacity; + // minCapacity is usually close to size, so this is a win: + elementData = Arrays.copyOf(elementData, newCapacity); + } } /** @@ -278,7 +268,8 @@ public class ArrayList extends Abstra */ public Object clone() { try { - ArrayList v = (ArrayList) super.clone(); + @SuppressWarnings("unchecked") + ArrayList v = (ArrayList) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; @@ -330,6 +321,7 @@ public class ArrayList extends Abstra * this list * @throws NullPointerException if the specified array is null */ + @SuppressWarnings("unchecked") public T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: @@ -342,11 +334,9 @@ public class ArrayList extends Abstra // Positional Access Operations - /** - * Throws an appropriate exception for indexing errors. - */ - private static void indexOutOfBounds(int i, int s) { - throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + s); + @SuppressWarnings("unchecked") + E elementData(int index) { + return (E) elementData[index]; } /** @@ -357,9 +347,9 @@ public class ArrayList extends Abstra * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { - if (index >= size) - indexOutOfBounds(index, size); - return (E) elementData[index]; + rangeCheck(index); + + return elementData(index); } /** @@ -372,9 +362,9 @@ public class ArrayList extends Abstra * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { - if (index >= size) - indexOutOfBounds(index, size); - E oldValue = (E) elementData[index]; + rangeCheck(index); + + E oldValue = elementData(index); elementData[index] = element; return oldValue; } @@ -386,12 +376,8 @@ public class ArrayList extends Abstra * @return true (as specified by {@link Collection#add}) */ public boolean add(E e) { - modCount++; - int s = size; - if (s >= elementData.length) - growArray(s + 1); - elementData[s] = e; - size = s + 1; + ensureCapacity(size + 1); // Increments modCount!! + elementData[size++] = e; return true; } @@ -405,16 +391,13 @@ public class ArrayList extends Abstra * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { - int s = size; - if (index > s || index < 0) - indexOutOfBounds(index, s); - modCount++; - if (s >= elementData.length) - growArray(s + 1); - System.arraycopy(elementData, index, - elementData, index + 1, s - index); + rangeCheckForAdd(index); + + ensureCapacity(size+1); // Increments modCount!! + System.arraycopy(elementData, index, elementData, index + 1, + size - index); elementData[index] = element; - size = s + 1; + size++; } /** @@ -427,17 +410,17 @@ public class ArrayList extends Abstra * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { - int s = size - 1; - if (index > s) - indexOutOfBounds(index, size); + rangeCheck(index); + modCount++; - E oldValue = (E) elementData[index]; - int numMoved = s - index; + E oldValue = elementData(index); + + int numMoved = size - index - 1; if (numMoved > 0) - System.arraycopy(elementData, index + 1, - elementData, index, numMoved); - elementData[s] = null; - size = s; + System.arraycopy(elementData, index+1, elementData, index, + numMoved); + elementData[--size] = null; // Let gc do its work + return oldValue; } @@ -536,8 +519,7 @@ public class ArrayList extends Abstra * @throws NullPointerException if the specified collection is null */ public boolean addAll(int index, Collection c) { - if (index > size || index < 0) - indexOutOfBounds(index, size); + rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; @@ -555,16 +537,17 @@ public class ArrayList extends Abstra /** * Removes from this list all of the elements whose index is between - * fromIndex, inclusive, and toIndex, exclusive. + * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. * Shifts any succeeding elements to the left (reduces their index). - * This call shortens the list by (toIndex - fromIndex) elements. - * (If toIndex==fromIndex, this operation has no effect.) + * This call shortens the list by {@code (toIndex - fromIndex)} elements. + * (If {@code toIndex==fromIndex}, this operation has no effect.) * - * @param fromIndex index of first element to be removed - * @param toIndex index after last element to be removed - * @throws IndexOutOfBoundsException if fromIndex or toIndex out of - * range (fromIndex < 0 || fromIndex >= size() || toIndex - * > size() || toIndex < fromIndex) + * @throws IndexOutOfBoundsException if {@code fromIndex} or + * {@code toIndex} is out of range + * ({@code fromIndex < 0 || + * fromIndex >= size() || + * toIndex > size() || + * toIndex < fromIndex}) */ protected void removeRange(int fromIndex, int toIndex) { modCount++; @@ -579,6 +562,97 @@ public class ArrayList extends Abstra } /** + * Checks if the given index is in range. If not, throws an appropriate + * runtime exception. This method does *not* check if the index is + * negative: It is always used immediately prior to an array access, + * which throws an ArrayIndexOutOfBoundsException if index is negative. + */ + private void rangeCheck(int index) { + if (index >= size) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); + } + + /** + * A version of rangeCheck used by add and addAll. + */ + private void rangeCheckForAdd(int index) { + if (index > size || index < 0) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); + } + + /** + * Constructs an IndexOutOfBoundsException detail message. + * Of the many possible refactorings of the error handling code, + * this "outlining" performs best with both server and client VMs. + */ + private String outOfBoundsMsg(int index) { + return "Index: "+index+", Size: "+size; + } + + /** + * Removes from this list all of its elements that are contained in the + * specified collection. + * + * @param c collection containing elements to be removed from this list + * @return {@code true} if this list changed as a result of the call + * @throws ClassCastException if the class of an element of this list + * is incompatible with the specified collection (optional) + * @throws NullPointerException if this list contains a null element and the + * specified collection does not permit null elements (optional), + * or if the specified collection is null + * @see Collection#contains(Object) + */ + public boolean removeAll(Collection c) { + return batchRemove(c, false); + } + + /** + * Retains only the elements in this list that are contained in the + * specified collection. In other words, removes from this list all + * of its elements that are not contained in the specified collection. + * + * @param c collection containing elements to be retained in this list + * @return {@code true} if this list changed as a result of the call + * @throws ClassCastException if the class of an element of this list + * is incompatible with the specified collection (optional) + * @throws NullPointerException if this list contains a null element and the + * specified collection does not permit null elements (optional), + * or if the specified collection is null + * @see Collection#contains(Object) + */ + public boolean retainAll(Collection c) { + return batchRemove(c, true); + } + + private boolean batchRemove(Collection c, boolean complement) { + final Object[] elementData = this.elementData; + int r = 0, w = 0; + boolean modified = false; + try { + for (; r < size; r++) + if (c.contains(elementData[r]) == complement) + elementData[w++] = elementData[r]; + } finally { + // Preserve behavioral compatibility with AbstractCollection, + // even if c.contains() throws. + if (r != size) { + System.arraycopy(elementData, r, + elementData, w, + size - r); + w += size - r; + } + if (w != size) { + for (int i = w; i < size; i++) + elementData[i] = null; + modCount += size - w; + size = w; + modified = true; + } + } + return modified; + } + + /** * Save the state of the ArrayList instance to a stream (that * is, serialize it). * @@ -599,7 +673,7 @@ public class ArrayList extends Abstra for (int i=0; i extends Abstra for (int i=0; iThe returned list iterator is fail-fast. + * + * @throws IndexOutOfBoundsException {@inheritDoc} + */ + public ListIterator listIterator(int index) { + if (index < 0 || index > size) + throw new IndexOutOfBoundsException("Index: "+index); + return new ListItr(index); + } + + /** + * Returns a list iterator over the elements in this list (in proper + * sequence). + * + *

The returned list iterator is fail-fast. + * + * @see #listIterator(int) + */ + public ListIterator listIterator() { + return new ListItr(0); + } + + /** + * Returns an iterator over the elements in this list in proper sequence. + * + *

The returned iterator is fail-fast. + * + * @return an iterator over the elements in this list in proper sequence + */ + public Iterator iterator() { + return new Itr(); + } + + /** + * An optimized version of AbstractList.Itr + */ + private class Itr implements Iterator { + int cursor; // index of next element to return + int lastRet = -1; // index of last element returned; -1 if no such + int expectedModCount = modCount; + + public boolean hasNext() { + return cursor != size; + } + + @SuppressWarnings("unchecked") + public E next() { + checkForComodification(); + int i = cursor; + if (i >= size) + throw new NoSuchElementException(); + Object[] elementData = ArrayList.this.elementData; + if (i >= elementData.length) + throw new ConcurrentModificationException(); + cursor = i + 1; + return (E) elementData[lastRet = i]; + } + + public void remove() { + if (lastRet < 0) + throw new IllegalStateException(); + checkForComodification(); + + try { + ArrayList.this.remove(lastRet); + cursor = lastRet; + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + final void checkForComodification() { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + } + } + + /** + * An optimized version of AbstractList.ListItr + */ + private class ListItr extends Itr implements ListIterator { + ListItr(int index) { + super(); + cursor = index; + } + + public boolean hasPrevious() { + return cursor != 0; + } + + public int nextIndex() { + return cursor; + } + + public int previousIndex() { + return cursor - 1; + } + + @SuppressWarnings("unchecked") + public E previous() { + checkForComodification(); + int i = cursor - 1; + if (i < 0) + throw new NoSuchElementException(); + Object[] elementData = ArrayList.this.elementData; + if (i >= elementData.length) + throw new ConcurrentModificationException(); + cursor = i; + return (E) elementData[lastRet = i]; + } + + public void set(E e) { + if (lastRet < 0) + throw new IllegalStateException(); + checkForComodification(); + + try { + ArrayList.this.set(lastRet, e); + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void add(E e) { + checkForComodification(); + + try { + int i = cursor; + ArrayList.this.add(i, e); + cursor = i + 1; + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + } + + /** + * Returns a view of the portion of this list between the specified + * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If + * {@code fromIndex} and {@code toIndex} are equal, the returned list is + * empty.) The returned list is backed by this list, so non-structural + * changes in the returned list are reflected in this list, and vice-versa. + * The returned list supports all of the optional list operations. + * + *

This method eliminates the need for explicit range operations (of + * the sort that commonly exist for arrays). Any operation that expects + * a list can be used as a range operation by passing a subList view + * instead of a whole list. For example, the following idiom + * removes a range of elements from a list: + * 

+     *      list.subList(from, to).clear();
+     *
+ * Similar idioms may be constructed for {@link #indexOf(Object)} and + * {@link #lastIndexOf(Object)}, and all of the algorithms in the + * {@link Collections} class can be applied to a subList. + * + *

The semantics of the list returned by this method become undefined if + * the backing list (i.e., this list) is structurally modified in + * any way other than via the returned list. (Structural modifications are + * those that change the size of this list, or otherwise perturb it in such + * a fashion that iterations in progress may yield incorrect results.) + * + * @throws IndexOutOfBoundsException {@inheritDoc} + * @throws IllegalArgumentException {@inheritDoc} + */ + public List subList(int fromIndex, int toIndex) { + subListRangeCheck(fromIndex, toIndex, size); + return new SubList(this, 0, fromIndex, toIndex); + } + + static void subListRangeCheck(int fromIndex, int toIndex, int size) { + if (fromIndex < 0) + throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); + if (toIndex > size) + throw new IndexOutOfBoundsException("toIndex = " + toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException("fromIndex(" + fromIndex + + ") > toIndex(" + toIndex + ")"); + } + + private class SubList extends AbstractList implements RandomAccess { + private final AbstractList parent; + private final int parentOffset; + private final int offset; + private int size; + + SubList(AbstractList parent, + int offset, int fromIndex, int toIndex) { + this.parent = parent; + this.parentOffset = fromIndex; + this.offset = offset + fromIndex; + this.size = toIndex - fromIndex; + this.modCount = ArrayList.this.modCount; + } + + public E set(int index, E e) { + rangeCheck(index); + checkForComodification(); + E oldValue = ArrayList.this.elementData(offset + index); + ArrayList.this.elementData[offset + index] = e; + return oldValue; + } + + public E get(int index) { + rangeCheck(index); + checkForComodification(); + return ArrayList.this.elementData(offset + index); + } + + public int size() { + checkForComodification(); + return this.size; + } + + public void add(int index, E e) { + rangeCheckForAdd(index); + checkForComodification(); + parent.add(parentOffset + index, e); + this.modCount = parent.modCount; + this.size++; + } + + public E remove(int index) { + rangeCheck(index); + checkForComodification(); + E result = parent.remove(parentOffset + index); + this.modCount = parent.modCount; + this.size--; + return result; + } + + protected void removeRange(int fromIndex, int toIndex) { + checkForComodification(); + parent.removeRange(parentOffset + fromIndex, + parentOffset + toIndex); + this.modCount = parent.modCount; + this.size -= toIndex - fromIndex; + } + + public boolean addAll(Collection c) { + return addAll(this.size, c); + } + + public boolean addAll(int index, Collection c) { + rangeCheckForAdd(index); + int cSize = c.size(); + if (cSize==0) + return false; + + checkForComodification(); + parent.addAll(parentOffset + index, c); + this.modCount = parent.modCount; + this.size += cSize; + return true; + } + + public Iterator iterator() { + return listIterator(); + } + + public ListIterator listIterator(final int index) { + checkForComodification(); + rangeCheckForAdd(index); + + return new ListIterator() { + int cursor = index; + int lastRet = -1; + int expectedModCount = ArrayList.this.modCount; + + public boolean hasNext() { + return cursor != SubList.this.size; + } + + @SuppressWarnings("unchecked") + public E next() { + checkForComodification(); + int i = cursor; + if (i >= SubList.this.size) + throw new NoSuchElementException(); + Object[] elementData = ArrayList.this.elementData; + if (offset + i >= elementData.length) + throw new ConcurrentModificationException(); + cursor = i + 1; + return (E) elementData[offset + (lastRet = i)]; + } + + public boolean hasPrevious() { + return cursor != 0; + } + + @SuppressWarnings("unchecked") + public E previous() { + checkForComodification(); + int i = cursor - 1; + if (i < 0) + throw new NoSuchElementException(); + Object[] elementData = ArrayList.this.elementData; + if (offset + i >= elementData.length) + throw new ConcurrentModificationException(); + cursor = i; + return (E) elementData[offset + (lastRet = i)]; + } + + public int nextIndex() { + return cursor; + } + + public int previousIndex() { + return cursor - 1; + } + + public void remove() { + if (lastRet < 0) + throw new IllegalStateException(); + checkForComodification(); + + try { + SubList.this.remove(lastRet); + cursor = lastRet; + lastRet = -1; + expectedModCount = ArrayList.this.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void set(E e) { + if (lastRet < 0) + throw new IllegalStateException(); + checkForComodification(); + + try { + ArrayList.this.set(offset + lastRet, e); + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + public void add(E e) { + checkForComodification(); + + try { + int i = cursor; + SubList.this.add(i, e); + cursor = i + 1; + lastRet = -1; + expectedModCount = ArrayList.this.modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } + } + + final void checkForComodification() { + if (expectedModCount != ArrayList.this.modCount) + throw new ConcurrentModificationException(); + } + }; + } + + public List subList(int fromIndex, int toIndex) { + subListRangeCheck(fromIndex, toIndex, size); + return new SubList(this, offset, fromIndex, toIndex); + } + + private void rangeCheck(int index) { + if (index < 0 || index >= this.size) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); + } + + private void rangeCheckForAdd(int index) { + if (index < 0 || index > this.size) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); + } + + private String outOfBoundsMsg(int index) { + return "Index: "+index+", Size: "+this.size; + } + + private void checkForComodification() { + if (ArrayList.this.modCount != this.modCount) + throw new ConcurrentModificationException(); + } + } }