package resourceCode.util;

import java.util.Arrays;

import java.util.Collection;

import java.util.ConcurrentModificationException;

import java.util.RandomAccess;

/**

* ArrayList源码

*

* @author Administrator

*

* @param <E>

* 2016-9-9 下午03:55:12

*/

public class ArrayListMe<E> extends AbstractListMe<E> implements ListMe<E>,

RandomAccess, Cloneable, java.io.Serializable {

private static final long serialVersionUID = 8683452581122892189L;

/**

* The array buffer into which the elements of the ArrayList are stored. The

* capacity of the ArrayList is the length of this array buffer.

* 此数组缓冲到所存储的数组元素，这个数组的容量就是此缓冲区的长度

*/

private transient Object[] elementData;

/**

* The size of the ArrayList (the number of elements it contains).

*

* @serial

*/

private int size;

/**

* Constructs an empty list with an initial capacity of ten.

*/

public ArrayListMe() {

this(10);

}

/**

* 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

*/

public ArrayListMe(int initialCapacity) {

super();

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: "

+ initialCapacity);

this.elementData = new Object[initialCapacity];

}

/**

* Constructs a list containing the elements of the specified collection, in

* the order they are returned by the collection's iterator.

*

* @param c

* the collection whose elements are to be placed into this list

* @throws NullPointerException

* if the specified collection is null

*/

public ArrayListMe(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 = ArraysMe.copyOf(elementData, size, Object[].class);

}

/**

* Trims the capacity of this <tt>ArrayList</tt> instance to be the list's

* current size. An application can use this operation to minimize the

* storage of an <tt>ArrayList</tt> instance.

*/

public void trimToSize() {

modCount++;

int oldCapacity = elementData.length;

if (size < oldCapacity) {

elementData = ArraysMe.copyOf(elementData, size);

}

}

/**

* 数组长度很大的时候，显式调用ensureCapacity(size)方法可大大提高初始化list效率

*

* Increases the capacity of this <tt>ArrayList</tt> 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

*/

public void ensureCapacity(int minCapacity) {

modCount++;

int oldCapacity = elementData.length;

if (minCapacity > oldCapacity) {

Object oldData[] = elementData;

// 若当前容量不足以容纳当前的元素个数 设置 新的容量=(原始容量x3)/2 + 1

int newCapacity = (oldCapacity * 3) / 2 + 1;

if (newCapacity < minCapacity)

newCapacity = minCapacity;

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

elementData = ArraysMe.copyOf(elementData, newCapacity);

}

}

/**

* Returns the number of elements in this list.

*

* @return the number of elements in this list

*/

public int size() {

return size;

}

/**

* Returns <tt>true</tt> if this list contains no elements.

*

* @return <tt>true</tt> if this list contains no elements

*/

public boolean isEmpty() {

return size == 0;

}

/**

* Returns true if this list contains the specified element. More formally,

* returns true if and only if this list contains at least one element esuch

* that <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.

*

* @param o

* element whose presence in this list is to be tested

* @return <tt>trueif this list contains the specified element

*/

public boolean contains(Object o) {

return indexOf(o) >= 0;

}

/**

* Returns the index of the first occurrence of the specified element in

* this list, or -1 if this list does not contain the element. More

* formally, returns the lowest index <tt>isuch that

* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,

* or -1 if there is no such index.

*/

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;

}

/**

* Returns the index of the last occurrence of the specified element in this

* list, or -1 if this list does not contain the element. More formally,

* returns the highest index <tt>isuch that

* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,

* or -1 if there is no such index.

*/

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;

}

/**

* Returns a shallow copy of this <tt>ArrayListinstance. (The elements

* themselves are not copied.)

*

* @return a clone of this <tt>ArrayListinstance

*/

@SuppressWarnings("unchecked")

public Object clone() {

try {

ArrayListMe<E> v = (ArrayListMe<E>) 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();

}

}

/**

* Returns an array containing all of the elements in this list in proper

* sequence (from first to last element).

*

* <p>

* The returned array will be "safe" in that no references to it are

* maintained by this list. (In other words, this method must allocate a new

* array). The caller is thus free to modify the returned array.

*

* <p>

* This method acts as bridge between array-based and collection-based APIs.

*

* @return an array containing all of the elements in this list in proper

* sequence

*/

public Object[] toArray() {

return ArraysMe.copyOf(elementData, size);

}

/**

* Returns an array containing all of the elements in this list in proper

* sequence (from first to last element); the runtime type of the returned

* array is that of the specified array. If the list fits in the specified

* array, it is returned therein. Otherwise, a new array is allocated with

* the runtime type of the specified array and the size of this list.

*

* <p>

* If the list fits in the specified array with room to spare (i.e., the

* array has more elements than the list), the element in the array

* immediately following the end of the collection is set to <tt>null</tt>.

* (This is useful in determining the length of the list <i>only</i> if the

* caller knows that the list does not contain any null elements.)

*

* @param a

* the array into which the elements of the list are to be

* stored, if it is big enough; otherwise, a new array of the

* same runtime type is allocated for this purpose.

* @return an array containing the elements of the list

* @throws ArrayStoreException

* if the runtime type of the specified array is not a supertype

* of the runtime type of every element in this list

* @throws NullPointerException

* if the specified array is null

*/

@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[]) ArraysMe.copyOf(elementData, size, a.getClass());

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

if (a.length > size)

a[size] = null;

return a;

}

// Positional Access Operations

/**

* Returns the element at the specified position in this list.

*

* @param index

* index of the element to return

* @return the element at the specified position in this list

* @throws IndexOutOfBoundsException

* {@inheritDoc}

*/

public E get(int index) {

RangeCheck(index);

return (E) elementData[index];

}

/**

* Replaces the element at the specified position in this list with the

* specified element.

*

* @param index

* index of the element to replace

* @param element

* element to be stored at the specified position

* @return the element previously at the specified position

* @throws IndexOutOfBoundsException

* {@inheritDoc}

*/

public E set(int index, E element) {

RangeCheck(index);

E oldValue = (E) elementData[index];

elementData[index] = element;

return oldValue;

}

/**

* Appends the specified element to the end of this list.

*

* @param e

* element to be appended to this list

* @return <tt>true(as specified by {@link Collection#add})

*/

public boolean add(E e) {

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

elementData[size++] = e;

return true;

}

/**

* Inserts the specified element at the specified position in this list.

* Shifts the element currently at that position (if any) and any subsequent

* elements to the right (adds one to their indices).

*

* @param index

* index at which the specified element is to be inserted

* @param element

* element to be inserted

* @throws IndexOutOfBoundsException

* {@inheritDoc}

*/

public void add(int index, E element) {

if (index > size || index < 0)

throw new IndexOutOfBoundsException("Index: " + index + ", Size: "

+ size);

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

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

- index);

elementData[index] = element;

size++;

}

/**

* Removes the element at the specified position in this list. Shifts any

* subsequent elements to the left (subtracts one from their indices).

*

* @param index

* the index of the element to be removed

* @return the element that was removed from the list

* @throws IndexOutOfBoundsException

* {@inheritDoc}

*/

@SuppressWarnings("unchecked")

public E remove(int index) {

RangeCheck(index);

modCount++;

E oldValue = (E) elementData[index];

int numMoved = size - index - 1;

if (numMoved > 0)

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

numMoved);

elementData[--size] = null; // Let gc do its work

return oldValue;

}

/**

* Removes the first occurrence of the specified element from this list, if

* it is present. If the list does not contain the element, it is unchanged.

* More formally, removes the element with the lowest index <tt>isuch

* that

* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>

* (if such an element exists). Returns <tt>trueif this list contained

* the specified element (or equivalently, if this list changed as a result

* of the call).

*

* @param o

* element to be removed from this list, if present

* @return <tt>trueif this list contained the specified element

*/

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 remove method that skips bounds checking and does not return the

* value removed.

*/

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; // Let gc do its work

}

/**

* Removes all of the elements from this list. The list will be empty after

* this call returns.

*/

public void clear() {

modCount++;

// Let gc do its work

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

elementData[i] = null;

size = 0;

}

/**

* Appends all of the elements in the specified collection to the end of

* this list, in the order that they are returned by the specified

* collection's Iterator. The behavior of this operation is undefined if the

* specified collection is modified while the operation is in progress.

* (This implies that the behavior of this call is undefined if the

* specified collection is this list, and this list is nonempty.)

*

* @param c

* collection containing elements to be added to this list

* @return <tt>trueif this list changed as a result of the call

* @throws NullPointerException

* if the specified collection is null

*/

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

Object[] a = c.toArray();

int numNew = a.length;

ensureCapacity(size + numNew); // Increments modCount

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

size += numNew;

return numNew != 0;

}

/**

* Inserts all of the elements in the specified collection into this list,

* starting at the specified position. Shifts the element currently at that

* position (if any) and any subsequent elements to the right (increases

* their indices). The new elements will appear in the list in the order

* that they are returned by the specified collection's iterator.

*

* @param index

* index at which to insert the first element from the specified

* collection

* @param c

* collection containing elements to be added to this list

* @return <tt>trueif this list changed as a result of the call

* @throws IndexOutOfBoundsException

* {@inheritDoc}

* @throws NullPointerException

* if the specified collection is null

*/

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

if (index > size || index < 0)

throw new IndexOutOfBoundsException("Index: " + index + ", Size: "

+ size);

Object[] a = c.toArray();

int numNew = a.length;

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

}

/**

* Removes from this list all of the elements whose index is between

* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive. Shifts

* any succeeding elements to the left (reduces their index). This call

* shortens the list by <tt>(toIndex - fromIndex)elements. (If

* <tt>toIndex==fromIndex</tt>, 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 &lt; 0 ||

* fromIndex &gt;= size() || toIndex &gt; size() || toIndex &lt;

* fromIndex)

*/

protected void removeRange(int fromIndex, int toIndex) {

modCount++;

int numMoved = size - toIndex;

System

.arraycopy(elementData, toIndex, elementData, fromIndex,

numMoved);

// Let gc do its work

int newSize = size - (toIndex - fromIndex);

while (size != newSize)

elementData[--size] = null;

}

/**

* 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("Index: " + index + ", Size: "

+ size);

}

/**

* Save the state of the <tt>ArrayListinstance to a stream (that is,

* serialize it).

*

* @serialData The length of the array backing the <tt>ArrayList</tt>

* instance is emitted (int), followed by all of its elements

* (each an <tt>Object</tt>) in the proper order.

*/

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 array length

s.writeInt(elementData.length);

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

}

}

/**

* Reconstitute the <tt>ArrayListinstance from a stream (that is,

* deserialize it).

*/

private void readObject(java.io.ObjectInputStream s)

throws java.io.IOException, ClassNotFoundException {

// Read in size, and any hidden stuff

s.defaultReadObject();

// Read in array length and allocate array

int arrayLength = s.readInt();

Object[] a = elementData = new Object[arrayLength];

// Read in all elements in the proper order.

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

a[i] = s.readObject();

}

}