implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

private static final long serialVersionUID = 8683452581122892189L;

/**

private static final int DEFAULT_CAPACITY = 10;

/**

private static final Object[] EMPTY_ELEMENTDATA = {};

/**

transient Object[] elementData; // non-private to simplify nested class access

/**

private int size;

/**

public ArrayList(int initialCapacity) {

super();

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: "+

initialCapacity);

this.elementData = new Object[initialCapacity];

}

/**

public ArrayList() {

super();

this.elementData = EMPTY_ELEMENTDATA;

}

/**

public ArrayList(Collection<? extends E> 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);

}

/**

public void trimToSize() {

modCount++;

if (size < elementData.length) {

elementData = Arrays.copyOf(elementData, size);

}

}

/**

public void ensureCapacity(int minCapacity) {

int minExpand = (elementData != EMPTY_ELEMENTDATA)

// any size if real element table

? 0

// larger than default for empty table. It's already supposed to be

// at default size.

: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {

ensureExplicitCapacity(minCapacity);

}

}

private void ensureCapacityInternal(int minCapacity) {

if (elementData == EMPTY_ELEMENTDATA) {

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

}

ensureExplicitCapacity(minCapacity);

}

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

// overflow-conscious code

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

/**

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity);

}

private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow

throw new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ?

Integer.MAX_VALUE :

MAX_ARRAY_SIZE;

}

/**

public int size() {

return size;

}

/**

public boolean isEmpty() {

return size == 0;

}

/**

public boolean contains(Object o) {

return indexOf(o) >= 0;

}

/**

public int indexOf(Object o) {

if (o == null) {

for (int i = 0; i < size; i++)

if (elementData[i]==null)

return i;

} else {

for (int i = 0; i < size; i++)

if (o.equals(elementData[i]))

return i;

}

return -1;

}

/**

public int lastIndexOf(Object o) {

if (o == null) {

for (int i = size-1; i >= 0; i--)

if (elementData[i]==null)

return i;

} else {

for (int i = size-1; i >= 0; i--)

if (o.equals(elementData[i]))

return i;

}

return -1;

}

/**

public Object clone() {

try {

ArrayList<?> v = (ArrayList<?>) super.clone();

v.elementData = Arrays.copyOf(elementData, size);

v.modCount = 0;

return v;

} catch (CloneNotSupportedException e) {

// this shouldn't happen, since we are Cloneable

throw new InternalError(e);

}

}

/**

public Object[] toArray() {

return Arrays.copyOf(elementData, size);

}

/**

@SuppressWarnings("unchecked")

public <T> T[] toArray(T[] a) {

if (a.length < size)

// Make a new array of a's runtime type, but my contents:

return (T[]) Arrays.copyOf(elementData, size, a.getClass());

System.arraycopy(elementData, 0, a, 0, size);

if (a.length > size)

a[size] = null;

return a;

}

// Positional Access Operations

@SuppressWarnings("unchecked")

E elementData(int index) {

return (E) elementData[index];

}

/**

public E get(int index) {

rangeCheck(index);

return elementData(index);

}

/**

public E set(int index, E element) {

rangeCheck(index);

E oldValue = elementData(index);

elementData[index] = element;

return oldValue;

}

/**

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

/**

public void add(int index, E element) {

rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!

System.arraycopy(elementData, index, elementData, index + 1,

size - index);

elementData[index] = element;

size++;

}

/**

public E remove(int index) {

rangeCheck(index);

modCount++;

E oldValue = elementData(index);

int numMoved = size - index - 1;

if (numMoved > 0)

System.arraycopy(elementData, index+1, elementData, index,

numMoved);

elementData[--size] = null; // clear to let GC do its work

return oldValue;

}

/**

public boolean remove(Object o) {

if (o == null) {

for (int index = 0; index < size; index++)

if (elementData[index] == null) {

fastRemove(index);

return true;

}

} else {

for (int index = 0; index < size; index++)

if (o.equals(elementData[index])) {

fastRemove(index);

return true;

}

}

return false;

}

/*

private void fastRemove(int index) {

modCount++;

int numMoved = size - index - 1;

if (numMoved > 0)

System.arraycopy(elementData, index+1, elementData, index,

numMoved);

elementData[--size] = null; // clear to let GC do its work

}

/**

public void clear() {

modCount++;

// clear to let GC do its work

for (int i = 0; i < size; i++)

elementData[i] = null;

size = 0;

}

/**

public boolean addAll(Collection<? extends E> c) {

Object[] a = c.toArray();

int numNew = a.length;

ensureCapacityInternal(size + numNew); // Increments modCount

System.arraycopy(a, 0, elementData, size, numNew);

size += numNew;

return numNew != 0;

}

/**

public boolean addAll(int index, Collection<? extends E> c) {

rangeCheckForAdd(index);

Object[] a = c.toArray();

int numNew = a.length;

ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;

if (numMoved > 0)

System.arraycopy(elementData, index, elementData, index + numNew,

numMoved);

System.arraycopy(a, 0, elementData, index, numNew);

size += numNew;

return numNew != 0;

}

/**

protected void removeRange(int fromIndex, int toIndex) {

modCount++;

int numMoved = size - toIndex;

System.arraycopy(elementData, toIndex, elementData, fromIndex,

numMoved);

// clear to let GC do its work

int newSize = size - (toIndex-fromIndex);

for (int i = newSize; i < size; i++) {

elementData[i] = null;

}

size = newSize;

}

/**

private void rangeCheck(int index) {

if (index >= size)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**

private void rangeCheckForAdd(int index) {

if (index > size || index < 0)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**

private String outOfBoundsMsg(int index) {

return "Index: "+index+", Size: "+size;

}

/**

public boolean removeAll(Collection<?> c) {

Objects.requireNonNull(c);

return batchRemove(c, false);

}

/**

public boolean retainAll(Collection<?> c) {

Objects.requireNonNull(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) {

// clear to let GC do its work

for (int i = w; i < size; i++)

elementData[i] = null;

modCount += size - w;

size = w;

modified = true;

}

}

return modified;

}

/**

private void writeObject(java.io.ObjectOutputStream s)

throws java.io.IOException{

// Write out element count, and any hidden stuff

int expectedModCount = modCount;

s.defaultWriteObject();

// Write out size as capacity for behavioural compatibility with clone()

s.writeInt(size);

// Write out all elements in the proper order.

for (int i=0; i<size; i++) {

s.writeObject(elementData[i]);

}

if (modCount != expectedModCount) {

throw new ConcurrentModificationException();

}

}

/**

private void readObject(java.io.ObjectInputStream s)

throws java.io.IOException, ClassNotFoundException {

elementData = EMPTY_ELEMENTDATA;

// Read in size, and any hidden stuff

s.defaultReadObject();

// Read in capacity

s.readInt(); // ignored

if (size > 0) {

// be like clone(), allocate array based upon size not capacity

ensureCapacityInternal(size);

Object[] a = elementData;

// Read in all elements in the proper order.

for (int i=0; i<size; i++) {

a[i] = s.readObject();

}

}

}

/**

public ListIterator<E> listIterator(int index) {

if (index < 0 || index > size)

throw new IndexOutOfBoundsException("Index: "+index);

return new ListItr(index);

}

/**

public ListIterator<E> listIterator() {

return new ListItr(0);

}

/**

public Iterator<E> iterator() {

return new Itr();

}

/**

private class Itr implements Iterator<E> {

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();

}

}

@Override

@SuppressWarnings("unchecked")

public void forEachRemaining(Consumer<? super E> consumer) {

Objects.requireNonNull(consumer);

final int size = ArrayList.this.size;

int i = cursor;

if (i >= size) {

return;

}

final Object[] elementData = ArrayList.this.elementData;

if (i >= elementData.length) {

throw new ConcurrentModificationException();

}

while (i != size && modCount == expectedModCount) {

consumer.accept((E) elementData[i++]);

}

// update once at end of iteration to reduce heap write traffic

cursor = i;

lastRet = i - 1;

checkForComodification();

}

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

}

/**

private class ListItr extends Itr implements ListIterator<E> {

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();

}

}

}

/**

public List<E> 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<E> implements RandomAccess {

private final AbstractList<E> parent;

private final int parentOffset;

private final int offset;

int size;