package java.util;

/**
 * Resizable-array implementation of the <code>List</code> interface. Implements all optional list
 * operations, and permits all elements, including <code>null</code>. In addition to implementing the
 * <code>List</code> 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 <code>Vector</code>, except
 * that it is unsynchronized.)
 *
 * <p>
 * The <code>size</code>, <code>isEmpty</code>, <code>get</code>, <code>set</code>, <code>iterator</code>, and
 * <code>listIterator</code> operations run in constant time. The <code>add</code> operation runs in
 * <i>amortized constant time</i>, 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 <code>LinkedList</code> implementation.
 *
 * <p>
 * Each <code>ArrayList</code> instance has a <i>capacity</i>. 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.
 *
 * <p>
 * An application can increase the capacity of an <code>ArrayList</code> instance before adding a large
 * number of elements using the <code>ensureCapacity</code> operation. This may reduce the amount of
 * incremental reallocation.
 *
 * <p>
 * <strong>Note that this implementation is not synchronized.</strong> If multiple threads access an
 * <code>ArrayList</code> instance concurrently, and at least one of the threads modifies the list
 * structurally, it <i>must</i> be synchronized externally. (A structural modification is any
 * operation that adds or deletes one or more elements, or explicitly resizes the backing array;
 * merely setting the value of an element is not a structural modification.) This is typically
 * accomplished by synchronizing on some object that naturally encapsulates the list.
 *
 * 
 * <p><a id="fail-fast"></a>
 * The iterators returned by this class's {@link #iterator()} and
 * {@link #listIterator(int)} methods are <em>fail-fast</em>: 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.
 *
 * <p>
 * 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 {@code ConcurrentModificationException} on a best-effort
 * basis. Therefore, it would be wrong to write a program that depended on this exception for its
 * correctness: <i>the fail-fast behavior of iterators should be used only to detect bugs.</i>
 *
 * <p>
 * This class is a member of the Java Collections Framework
 * 
 * @param <E> the type of the elements in this list
 *
 * @see Collection
 * @see List
 * @see Vector
 */

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
	/**
	 * Constructs an empty list with an initial capacity of ten.
	 */
	public ArrayList() {
		throw new RuntimeException();
	}

	/**
	 * 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 ArrayList(Collection<? extends E> c) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 */
	public ArrayList(int initialCapacity) {
		throw new RuntimeException();
	}

	/**
	 * Appends the specified element to the end of this list.
	 *
	 * @param e
	 *        element to be appended to this list
	 * @return <code>true</code> (as specified by {@link Collection#add})
	 */
	@Override
	public boolean add(E e) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 *         if the index is out of range (<code>index &lt; 0 || index &gt; size()</code>)
	 */
	@Override
	public void add(int index, E element) {
		throw new RuntimeException();
	}

	/**
	 * 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 <code>true</code> if this list changed as a result of the call
	 * @throws NullPointerException
	 *         if the specified collection is null
	 */
	@Override
	public boolean addAll(Collection<? extends E> c) {
		throw new RuntimeException();
	}

	/**
	 * 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 <code>true</code> if this list changed as a result of the call
	 * @throws IndexOutOfBoundsException
	 *         if the index is out of range (<code>index &lt; 0 || index &gt; size()</code>)
	 * @throws NullPointerException
	 *         if the specified collection is null
	 */
	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		throw new RuntimeException();
	}

	/**
	 * Removes all of the elements from this list. The list will be empty after this call returns.
	 */
	@Override
	public void clear() {
		throw new RuntimeException();
	}

	/**
	 * Returns a shallow copy of this <code>ArrayList</code> instance. (The elements themselves are not
	 * copied.)
	 *
	 * @return a clone of this <code>ArrayList</code> instance
	 */
	@Override
	public Object clone() {
		throw new RuntimeException();
	}

	/**
	 * Returns <code>true</code> if this list contains the specified element. More formally, returns
	 * <code>true</code> if and only if this list contains at least one element <code>e</code> such that
	 * <code>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</code>.
	 *
	 * @param o
	 *        element whose presence in this list is to be tested
	 * @return <code>true</code> if this list contains the specified element
	 */
	@Override
	public boolean contains(Object o) {
		throw new RuntimeException();
	}

	/**
	 * Increases the capacity of this <code>ArrayList</code> 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) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 *         if the index is out of range (<code>index &lt; 0 || index &gt;= size()</code>)
	 */
	@Override
	public E get(int index) {
		throw new RuntimeException();
	}

	/**
	 * 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 <code>i</code> such that
	 * <code>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</code>, or -1 if there is no
	 * such index.
	 */
	@Override
	public int indexOf(Object o) {
		throw new RuntimeException();
	}

	/**
	 * Returns <code>true</code> if this list contains no elements.
	 *
	 * @return <code>true</code> if this list contains no elements
	 */
	@Override
	public boolean isEmpty() {
		throw new RuntimeException();
	}

	/**
	 * Returns an iterator over the elements in this list in proper sequence.
	 *
	 * <p>
	 * The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
	 *
	 * @return an iterator over the elements in this list in proper sequence
	 */
	@Override
	public Iterator<E> iterator() {
		throw new RuntimeException();
	}

	/**
	 * 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 <code>i</code> such that
	 * <code>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</code>, or -1 if there is no
	 * such index.
	 */
	@Override
	public int lastIndexOf(Object o) {
		throw new RuntimeException();
	}

	/**
	 * Returns a list iterator over the elements in this list (in proper sequence).
	 *
	 * <p>
	 * The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
	 *
	 * @see #listIterator(int)
	 */
	@Override
	public ListIterator<E> listIterator() {
		throw new RuntimeException();
	}

	/**
	 * Returns a list iterator over the elements in this list (in proper sequence), starting at the
	 * specified position in the list. The specified index indicates the first element that would be
	 * returned by an initial call to {@link ListIterator#next next}. An initial call to
	 * {@link ListIterator#previous previous} would return the element with the specified index minus
	 * one.
	 *
	 * <p>
	 * The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
	 *
	 * @throws IndexOutOfBoundsException
	 *         if the index is out of range ({@code index < 0 || index > size()})
	 */
	@Override
	public ListIterator<E> listIterator(int index) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 *         if the index is out of range (<code>index &lt; 0 || index &gt;= size()</code>)
	 */
	@Override
	public E remove(int index) {
		throw new RuntimeException();
	}

	/**
	 * 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 <code>i</code> such that
	 * <code>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</code> (if such an element
	 * exists). Returns <code>true</code> if 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 <code>true</code> if this list contained the specified element
	 */
	@Override
	public boolean remove(Object o) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 *         (<a href="Collection.html#optional-restrictions">optional</a>)
	 * @throws NullPointerException
	 *         if this list contains a null element and the specified collection does not permit null
	 *         elements (<a href="Collection.html#optional-restrictions">optional</a>), or if the
	 *         specified collection is null
	 * @see Collection#contains(Object)
	 */
	@Override
	public boolean removeAll(Collection<?> c) {
		throw new RuntimeException();
	}

	/**
	 * Removes from this list all of the elements whose index is between {@code fromIndex}, inclusive,
	 * and {@code toIndex}, exclusive. Shifts any succeeding elements to the left (reduces their index).
	 * This call shortens the list by {@code (toIndex - fromIndex)} elements. (If
	 * {@code toIndex==fromIndex}, this operation has no effect.)
	 *
	 * @throws IndexOutOfBoundsException
	 *         if {@code fromIndex} or {@code toIndex} is out of range ({@code fromIndex < 0 ||
	 *          fromIndex >= size() ||
	 *          toIndex > size() ||
	 *          toIndex < fromIndex})
	 */
	@Override
	protected void removeRange(int fromIndex, int toIndex) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 *         (<a href="Collection.html#optional-restrictions">optional</a>)
	 * @throws NullPointerException
	 *         if this list contains a null element and the specified collection does not permit null
	 *         elements (<a href="Collection.html#optional-restrictions">optional</a>), or if the
	 *         specified collection is null
	 * @see Collection#contains(Object)
	 */
	@Override
	public boolean retainAll(Collection<?> c) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 *         if the index is out of range (<code>index &lt; 0 || index &gt;= size()</code>)
	 */
	@Override
	public E set(int index, E element) {
		throw new RuntimeException();
	}

	/**
	 * Returns the number of elements in this list.
	 *
	 * @return the number of elements in this list
	 */
	@Override
	public int size() {
		throw new RuntimeException();
	}

	/**
	 * 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.
	 *
	 * <p>
	 * 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:
	 *
	 * <pre>
	 * list.subList(from, to).clear();
	 * </pre>
	 *
	 * Similar idioms may be constructed for {@link #indexOf(Object)} and {@link #lastIndexOf(Object)}.
	 *
	 * <p>
	 * The semantics of the list returned by this method become undefined if the backing list (i.e.,
	 * this list) is <i>structurally modified</i> 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
	 *         {for an illegal endpoint index value (<code>fromIndex &lt; 0 || toIndex &gt; size ||
	 *         fromIndex &gt; toIndex</code>)
	 */
	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		throw new RuntimeException();
	}

	/**
	 * 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
	 */
	@Override
	public Object[] toArray() {
		throw new RuntimeException();
	}

	/**
	 * 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 <code>null</code>. (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
	 */
	@Override
	public <T> T[] toArray(T[] a) {
		throw new RuntimeException();
	}

	/**
	 * Trims the capacity of this <code>ArrayList</code> instance to be the list's current size. An
	 * application can use this operation to minimize the storage of an <code>ArrayList</code> instance.
	 */
	public void trimToSize() {
		throw new RuntimeException();
	}
}