package java.util;

import ej.annotation.Nullable;

/**
 * This class provides a skeletal implementation of the {@link List} interface to minimize the
 * effort required to implement this interface backed by a "random access" data store (such as an
 * array).
 *
 * <p>
 * To implement an unmodifiable list, the programmer needs only to extend this class and provide
 * implementations for the {@link #get(int)} and {@link List#size() size()} methods.
 *
 * <p>
 * To implement a modifiable list, the programmer must additionally override the
 * {@link #set(int, Object) set(int, E)} method (which otherwise throws an
 * {@code UnsupportedOperationException}). If the list is variable-size the programmer must
 * additionally override the {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods.
 *
 * <p>
 * The programmer should generally provide a void (no argument) and collection constructor, as per
 * the recommendation in the {@link Collection} interface specification.
 *
 * <p>
 * Unlike the other abstract collection implementations, the programmer does <i>not</i> have to
 * provide an iterator implementation; the iterator and list iterator are implemented by this class,
 * on top of the "random access" methods: {@link #get(int)}, {@link #set(int, Object) set(int, E)},
 * {@link #add(int, Object) add(int, E)} and {@link #remove(int)}.
 *
 * <p>
 * The documentation for each non-abstract method in this class describes its implementation in
 * detail. Each of these methods may be overridden if the collection being implemented admits a more
 * efficient implementation.
 *
 * <p>
 * This class is a member of the Java Collections Framework.
 * 
 * @param <E> the type of the elements in this list
 */

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {

	/**
	 * The number of times this list has been <i>structurally modified</i>. Structural modifications are
	 * those that change the size of the list, or otherwise perturb it in such a fashion that iterations
	 * in progress may yield incorrect results.
	 *
	 * <p>
	 * This field is used by the iterator and list iterator implementation returned by the
	 * {@code iterator} and {@code listIterator} methods. If the value of this field changes
	 * unexpectedly, the iterator (or list iterator) will throw a
	 * {@code ConcurrentModificationException} in response to the {@code next}, {@code remove},
	 * {@code previous}, {@code set} or {@code add} operations. This provides <i>fail-fast</i> behavior,
	 * rather than non-deterministic behavior in the face of concurrent modification during iteration.
	 *
	 * <p>
	 * <b>Use of this field by subclasses is optional.</b> If a subclass wishes to provide fail-fast
	 * iterators (and list iterators), then it merely has to increment this field in its
	 * {@code add(int, E)} and {@code remove(int)} methods (and any other methods that it overrides that
	 * result in structural modifications to the list). A single call to {@code add(int, E)} or
	 * {@code remove(int)} must add no more than one to this field, or the iterators (and list
	 * iterators) will throw bogus {@code ConcurrentModificationExceptions}. If an implementation does
	 * not wish to provide fail-fast iterators, this field may be ignored.
	 */
	protected transient int modCount = 0;

	/**
	 * Sole constructor. (For invocation by subclass constructors, typically implicit.)
	 */
	protected AbstractList() {
	}

	/**
	 * Appends the specified element to the end of this list (optional operation).
	 *
	 * <p>
	 * Lists that support this operation may place limitations on what elements may be added to this
	 * list. In particular, some lists will refuse to add null elements, and others will impose
	 * restrictions on the type of elements that may be added. List classes should clearly specify in
	 * their documentation any restrictions on what elements may be added.
	 *
	 * <p>
	 * This implementation calls {@code add(size(), e)}.
	 *
	 * <p>
	 * Note that this implementation throws an {@code UnsupportedOperationException} unless
	 * {@link #add(int, Object) add(int, E)} is overridden.
	 *
	 * @param e
	 *        element to be appended to this list
	 * @return {@code true} (as specified by {@link Collection#add})
	 * @throws UnsupportedOperationException
	 *         if the {@code add} operation is not supported by this list
	 * @throws ClassCastException
	 *         if the class of the specified element prevents it from being added to this list
	 * @throws NullPointerException
	 *         if the specified element is null and this list does not permit null elements
	 * @throws IllegalArgumentException
	 *         if some property of this element prevents it from being added to this list
	 */
	@Override
	public boolean add(E e) {
		throw new RuntimeException();
	}

	/**
	 * Inserts the specified element at the specified position in this list (optional operation). Shifts
	 * the element currently at that position (if any) and any subsequent elements to the right (adds
	 * one to their indices).
	 *
	 * <p>
	 * This implementation always throws an {@code UnsupportedOperationException}.
	 *
	 * @param index
	 *        index at which the specified element is to be inserted
	 * @param element
	 *        element to be inserted
	 * @throws UnsupportedOperationException
	 *         if the <code>add</code> operation is not supported by this list
	 * @throws ClassCastException
	 *         if the class of the specified element prevents it from being added to this list
	 * @throws NullPointerException
	 *         if the specified element is null and this list does not permit null elements
	 * @throws IllegalArgumentException
	 *         if some property of the specified element prevents it from being added to this list
	 * @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();
	}

	/**
	 * Inserts all of the elements in the specified collection into this list at the specified position
	 * (optional operation). 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 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. (Note that this will occur if the specified collection is this list, and it's
	 * nonempty.)
	 *
	 * <p>
	 * This implementation gets an iterator over the specified collection and iterates over it,
	 * inserting the elements obtained from the iterator into this list at the appropriate position, one
	 * at a time, using {@code add(int, E)}. Many implementations will override this method for
	 * efficiency.
	 *
	 * <p>
	 * Note that this implementation throws an {@code UnsupportedOperationException} unless
	 * {@link #add(int, Object) add(int, E)} is overridden.
	 *
	 * @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 UnsupportedOperationException
	 *         if the <code>addAll</code> operation is not supported by this list
	 * @throws ClassCastException
	 *         if the class of an element of the specified collection prevents it from being added to
	 *         this list
	 * @throws NullPointerException
	 *         if the specified collection contains one or more null elements and this list does not
	 *         permit null elements, or if the specified collection is null
	 * @throws IllegalArgumentException
	 *         if some property of an element of the specified collection prevents it from being added
	 *         to this list
	 * @throws IndexOutOfBoundsException
	 *         if the index is out of range (<code>index &lt; 0 || index &gt; size()</code>)
	 */
	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		throw new RuntimeException();
	}

	/**
	 * Removes all of the elements from this list (optional operation). The list will be empty after
	 * this call returns.
	 *
	 * <p>
	 * This implementation calls {@code removeRange(0, size())}.
	 *
	 * <p>
	 * Note that this implementation throws an {@code UnsupportedOperationException} unless
	 * {@code remove(int
	 * index)} or {@code removeRange(int fromIndex, int toIndex)} is overridden.
	 *
	 * @throws UnsupportedOperationException
	 *         if the {@code clear} operation is not supported by this list
	 */
	@Override
	public void clear() {
		throw new RuntimeException();
	}

	/**
	 * Compares the specified object with this list for equality. Returns {@code true} if and only if
	 * the specified object is also a list, both lists have the same size, and all corresponding pairs
	 * of elements in the two lists are <i>equal</i>. (Two elements {@code e1} and {@code e2} are
	 * <i>equal</i> if {@code (e1==null ? e2==null :
	 * e1.equals(e2))}.) In other words, two lists are defined to be equal if they contain the same
	 * elements in the same order.
	 * <p>
	 *
	 * This implementation first checks if the specified object is this list. If so, it returns
	 * {@code true}; if not, it checks if the specified object is a list. If not, it returns
	 * {@code false}; if so, it iterates over both lists, comparing corresponding pairs of elements. If
	 * any comparison returns {@code false}, this method returns {@code false}. If either iterator runs
	 * out of elements before the other it returns {@code false} (as the lists are of unequal length);
	 * otherwise it returns {@code true} when the iterations complete.
	 *
	 * @param o
	 *        the object to be compared for equality with this list
	 * @return {@code true} if the specified object is equal to this list
	 */
	@Override
	public boolean equals(@Nullable Object o) {
		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 abstract E get(int index);

	/**
	 * Returns the hash code value for this list.
	 *
	 * <p>
	 * This implementation uses exactly the code that is used to define the list hash function in the
	 * documentation for the {@link List#hashCode} method.
	 *
	 * @return the hash code value for this list
	 */
	@Override
	public int hashCode() {
		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.
	 *
	 * <p>
	 * This implementation first gets a list iterator (with {@code listIterator()}). Then, it iterates
	 * over the list until the specified element is found or the end of the list is reached.
	 *
	 * @param o
	 *        element to search for
	 * @return the index of the first occurrence of the specified element in this list, or -1 if this
	 *         list does not contain the element
	 * @throws ClassCastException
	 *         if the type of the specified element is incompatible with this list
	 *         (<a href="Collection.html#optional-restrictions">optional</a>)
	 * @throws NullPointerException
	 *         if the specified element is null and this list does not permit null elements
	 *         (<a href="Collection.html#optional-restrictions">optional</a>)
	 */
	@Override
	public int indexOf(Object o) {
		throw new RuntimeException();
	}

	/**
	 * Returns an iterator over the elements in this list in proper sequence.
	 *
	 * <p>
	 * This implementation returns a straightforward implementation of the iterator interface, relying
	 * on the backing list's {@code size()}, {@code get(int)}, and {@code remove(int)} methods.
	 *
	 * <p>
	 * Note that the iterator returned by this method will throw an
	 * {@link UnsupportedOperationException} in response to its {@code remove} method unless the list's
	 * {@code remove(int)} method is overridden.
	 *
	 * <p>
	 * This implementation can be made to throw runtime exceptions in the face of concurrent
	 * modification, as described in the specification for the (protected) {@link #modCount} field.
	 *
	 * @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.
	 *
	 * <p>
	 * This implementation first gets a list iterator that points to the end of the list (with
	 * {@code listIterator(size())}). Then, it iterates backwards over the list until the specified
	 * element is found, or the beginning of the list is reached.
	 *
	 * @param o
	 *        element to search for
	 * @return the index of the last occurrence of the specified element in this list, or -1 if this
	 *         list does not contain the element
	 * @throws ClassCastException
	 *         if the type of the specified element is incompatible with this list
	 *         (<a href="Collection.html#optional-restrictions">optional</a>)
	 * @throws NullPointerException
	 *         if the specified element is null and this list does not permit null elements
	 *         (<a href="Collection.html#optional-restrictions">optional</a>)
	 */
	@Override
	public int lastIndexOf(Object o) {
		throw new RuntimeException();
	}

	/**
	 * Returns a list iterator over the elements in this list (in proper sequence).
	 *
	 * <p>
	 * This implementation returns {@code listIterator(0)}.
	 *
	 * @return a list iterator over the elements in this list (in proper sequence)
	 *
	 * @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>
	 * This implementation returns a straightforward implementation of the {@code ListIterator}
	 * interface that extends the implementation of the {@code Iterator} interface returned by the
	 * {@code iterator()} method. The {@code ListIterator} implementation relies on the backing list's
	 * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)} and {@code remove(int)} methods.
	 *
	 * <p>
	 * Note that the list iterator returned by this implementation will throw an
	 * {@link UnsupportedOperationException} in response to its {@code remove}, {@code set} and
	 * {@code add} methods unless the list's {@code remove(int)}, {@code set(int, E)}, and
	 * {@code add(int, E)} methods are overridden.
	 *
	 * <p>
	 * This implementation can be made to throw runtime exceptions in the face of concurrent
	 * modification, as described in the specification for the (protected) {@link #modCount} field.
	 *
	 * @param index
	 *        index of the first element to be returned from the list iterator (by a call to
	 *        {@link ListIterator#next next})
	 * @return a list iterator over the elements in this list (in proper sequence), starting at the
	 *         specified position in the list
	 * @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 (optional operation). Shifts any
	 * subsequent elements to the left (subtracts one from their indices). Returns the element that was
	 * removed from the list.
	 *
	 * <p>
	 * This implementation always throws an {@code UnsupportedOperationException}.
	 *
	 * @param index
	 *        the index of the element to be removed
	 * @return the element previously at the specified position
	 * @throws UnsupportedOperationException
	 *         if the <code>remove</code> operation is not supported by this 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 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.)
	 *
	 * <p>
	 * This method is called by the {@code clear} operation on this list and its subLists. Overriding
	 * this method to take advantage of the internals of the list implementation can
	 * <i>substantially</i> improve the performance of the {@code clear} operation on this list and its
	 * subLists.
	 *
	 * <p>
	 * This implementation gets a list iterator positioned before {@code fromIndex}, and repeatedly
	 * calls {@code ListIterator.next} followed by {@code ListIterator.remove} until the entire range
	 * has been removed. <b>Note: if {@code ListIterator.remove} requires linear time, this
	 * implementation requires quadratic time.</b>
	 *
	 * @param fromIndex
	 *        index of first element to be removed
	 * @param toIndex
	 *        index after last element to be removed
	 */
	protected void removeRange(int fromIndex, int toIndex) {
		throw new RuntimeException();
	}

	/**
	 * Replaces the element at the specified position in this list with the specified element (optional
	 * operation).
	 *
	 * <p>
	 * This implementation always throws an {@code UnsupportedOperationException}.
	 *
	 * @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 UnsupportedOperationException
	 *         if the <code>set</code> operation is not supported by this list
	 * @throws ClassCastException
	 *         if the class of the specified element prevents it from being added to this list
	 * @throws NullPointerException
	 *         if the specified element is null and this list does not permit null elements
	 * @throws IllegalArgumentException
	 *         if some property of the specified element prevents it from being added to this list
	 * @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 a view of the portion of this list between the specified <code>fromIndex</code>, inclusive,
	 * and <code>toIndex</code>, exclusive. (If <code>fromIndex</code> and <code>toIndex</code> 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 supported by this list.
	 * <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 <code>indexOf</code> and <code>lastIndexOf</code>, and all of the
	 * algorithms in the <code>Collections</code> class can be applied to a subList.
	 * <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.)
	 *
	 * <p>
	 * This implementation returns a list that subclasses {@code AbstractList}. The subclass stores, in
	 * private fields, the offset of the subList within the backing list, the size of the subList (which
	 * can change over its lifetime), and the expected {@code modCount} value of the backing list. There
	 * are two variants of the subclass, one of which implements {@code RandomAccess}. If this list
	 * implements {@code RandomAccess} the returned list will be an instance of the subclass that
	 * implements {@code RandomAccess}.
	 *
	 * <p>
	 * The subclass's {@code set(int, E)}, {@code get(int)}, {@code add(int, E)}, {@code remove(int)},
	 * {@code addAll(int,
	 * Collection)} and {@code removeRange(int, int)} methods all delegate to the corresponding methods
	 * on the backing abstract list, after bounds-checking the index and adjusting for the offset. The
	 * {@code addAll(Collection c)} method merely returns {@code addAll(size,
	 * c)}.
	 *
	 * <p>
	 * The {@code listIterator(int)} method returns a "wrapper object" over a list iterator on the
	 * backing list, which is created with the corresponding method on the backing list. The
	 * {@code iterator} method merely returns {@code listIterator()}, and the {@code size} method merely
	 * returns the subclass's {@code size} field.
	 *
	 * <p>
	 * All methods first check to see if the actual {@code modCount} of the backing list is equal to its
	 * expected value, and throw a {@code ConcurrentModificationException} if it is not.
	 *
	 * @param fromIndex
	 *        low endpoint (inclusive) of the subList
	 * @param toIndex
	 *        high endpoint (exclusive) of the subList
	 * @return a view of the specified range within this list
	 * @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();
	}

}