--- jsr166/src/main/java/util/ArrayList.java 2005/11/25 13:27:05 1.1 +++ jsr166/src/main/java/util/ArrayList.java 2005/11/28 02:35:46 1.10 @@ -101,9 +101,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,20 +123,40 @@ 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. + * iterator. The ArrayList instance has an initial capacity of + * 110% the size of the specified collection. * * @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) { - Object[] a = c.toArray(); - // If c.toArray incorrectly doesn't return Object[], copy it. - if (a.getClass() != Object[].class) - a = Arrays.copyOf(a, a.length, Object[].class); - elementData = a; - size = a.length; + 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 @@ -155,14 +175,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++; @@ -171,15 +184,18 @@ 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) + throw new OutOfMemoryError(); // int overflow 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 * 3) / 2)); if (newCapacity < minCapacity) newCapacity = minCapacity; elementData = Arrays.copyOf(elementData, newCapacity); @@ -328,15 +344,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. * @@ -346,7 +360,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]; } @@ -361,7 +375,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; @@ -375,11 +389,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; } @@ -395,14 +410,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; } /** @@ -417,16 +432,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; } /** @@ -525,8 +540,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; @@ -636,10 +650,17 @@ public class ArrayList 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. * @@ -650,7 +671,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; @@ -680,46 +701,38 @@ 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 next = get(i); + lastRet = i; + cursor = i; + return next; + } catch (IndexOutOfBoundsException ex) { throw new NoSuchElementException(); - throw new ConcurrentModificationException(); + } finally { + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + } } public void remove() { if (lastRet < 0) throw new IllegalStateException(); - if (modCount != expectedModCount) + if (modCount != expectedModCount) throw new ConcurrentModificationException(); ArrayList.this.remove(lastRet); if (lastRet < cursor) @@ -731,14 +744,14 @@ public class ArrayList extends Abstra public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); - if (modCount != expectedModCount) + if (modCount != expectedModCount) throw new ConcurrentModificationException(); ArrayList.this.set(lastRet, e); expectedModCount = modCount; } public void add(E e) { - if (modCount != expectedModCount) + if (modCount != expectedModCount) throw new ConcurrentModificationException(); ArrayList.this.add(cursor++, e); lastRet = -1;