--- jsr166/src/main/java/util/ArrayList.java 2005/11/25 13:34:29 1.2 +++ jsr166/src/main/java/util/ArrayList.java 2006/03/19 17:40:40 1.18 @@ -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 @@ -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,40 +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 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); - } - - private void initFromConcurrentlyMutating(Collection c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } - - private final static Object UNALLOCATED = new Object(); - + /** * Trims the capacity of this ArrayList instance to be the * list's current size. An application can use this operation to minimize @@ -175,14 +153,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,18 +162,23 @@ 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)); - if (newCapacity < minCapacity) - newCapacity = minCapacity; - elementData = Arrays.copyOf(elementData, newCapacity); + // 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); } /** @@ -348,15 +324,13 @@ public class ArrayList extends Abstra // Positional Access Operations - /** - * Create and return an appropriate exception for indexing errors + /** + * Returns error message string for IndexOutOfBoundsExceptions */ - private static IndexOutOfBoundsException rangeException(int i, int s) { - return new IndexOutOfBoundsException("Index: " + i + ", Size: " + s); + private String ioobe(int index) { + return "Index: " + index + ", Size: " + size; } - // Positional Access Operations - /** * Returns the element at the specified position in this list. * @@ -366,7 +340,7 @@ public class ArrayList extends Abstra */ public E get(int index) { if (index >= size) - throw rangeException(index, size); + throw new IndexOutOfBoundsException(ioobe(index)); return (E)elementData[index]; } @@ -381,7 +355,7 @@ public class ArrayList extends Abstra */ public E set(int index, E element) { if (index >= size) - throw rangeException(index, size); + throw new IndexOutOfBoundsException(ioobe(index)); E oldValue = (E) elementData[index]; elementData[index] = element; @@ -395,11 +369,12 @@ 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; + size = s + 1; return true; } @@ -415,14 +390,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; + throw new IndexOutOfBoundsException(ioobe(index)); + 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 +412,16 @@ public class ArrayList extends Abstra public E remove(int index) { int s = size - 1; if (index > s) - throw rangeException(index, size); - size = s; + throw new IndexOutOfBoundsException(ioobe(index)); 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 +520,7 @@ public class ArrayList extends Abstra */ public boolean addAll(int index, Collection c) { if (index > size || index < 0) - throw new IndexOutOfBoundsException( - "Index: " + index + ", Size: " + size); + throw new IndexOutOfBoundsException(ioobe(index)); Object[] a = c.toArray(); int numNew = a.length; @@ -608,7 +582,7 @@ public class ArrayList extends Abstra for (int i=0; i extends Abstra */ public ListIterator listIterator(int index) { if (index < 0 || index > size) - throw new IndexOutOfBoundsException("Index: "+index); + throw new IndexOutOfBoundsException(ioobe(index)); return new ArrayListIterator(index); } - + + /** + * {@inheritDoc} + */ + public ListIterator listIterator() { + return new ArrayListIterator(0); + } + /** * Returns an iterator over the elements in this list in proper sequence. * @@ -670,7 +651,7 @@ public class ArrayList extends Abstra } /** - * A streamlined version of AbstractList.Itr + * A streamlined version of AbstractList.ListItr */ final class ArrayListIterator implements ListIterator { int cursor; // index of next element to return; @@ -684,11 +665,11 @@ public class ArrayList extends Abstra } public boolean hasNext() { - return cursor < size; + return cursor != size; } public boolean hasPrevious() { - return cursor > 0; + return cursor != 0; } public int nextIndex() { @@ -700,46 +681,39 @@ public class ArrayList extends Abstra } public E next() { - if (expectedModCount == modCount) { + try { 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) + E next = get(i); + lastRet = i; + cursor = i + 1; + return next; + } catch (IndexOutOfBoundsException ex) { throw new NoSuchElementException(); - throw new ConcurrentModificationException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } } public E previous() { - if (expectedModCount == modCount) { + try { 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) + E prev = get(i); + lastRet = i; + cursor = i; + return prev; + } catch (IndexOutOfBoundsException ex) { throw new NoSuchElementException(); - throw new ConcurrentModificationException(); + } finally { + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } } public void remove() { if (lastRet < 0) throw new IllegalStateException(); - if (modCount != expectedModCount) + if (expectedModCount != modCount) throw new ConcurrentModificationException(); ArrayList.this.remove(lastRet); if (lastRet < cursor) @@ -751,19 +725,22 @@ public class ArrayList extends Abstra public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); - if (modCount != expectedModCount) + if (expectedModCount != modCount) throw new ConcurrentModificationException(); ArrayList.this.set(lastRet, e); expectedModCount = modCount; } public void add(E e) { - if (modCount != expectedModCount) + if (expectedModCount != modCount) throw new ConcurrentModificationException(); - ArrayList.this.add(cursor++, e); - lastRet = -1; - expectedModCount = modCount; + try { + ArrayList.this.add(cursor++, e); + lastRet = -1; + expectedModCount = modCount; + } catch (IndexOutOfBoundsException ex) { + throw new ConcurrentModificationException(); + } } } - }