package java.util;

import ej.annotation.Nullable;

/**
 * An ordered collection (also known as a <i>sequence</i>). The user of this interface has precise
 * control over where in the list each element is inserted. The user can access elements by their
 * integer index (position in the list), and search for elements in the list.
 * <p>
 *
 * Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs
 * of elements <code>e1</code> and <code>e2</code> such that <code>e1.equals(e2)</code>, and they typically
 * allow multiple null elements if they allow null elements at all. It is not inconceivable that
 * someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions
 * when the user attempts to insert them, but we expect this usage to be rare.
 * <p>
 *
 * The <code>List</code> interface places additional stipulations, beyond those specified in the
 * <code>Collection</code> interface, on the contracts of the <code>iterator</code>, <code>add</code>,
 * <code>remove</code>, <code>equals</code>, and <code>hashCode</code> methods. Declarations for other inherited
 * methods are also included here for convenience.
 * <p>
 *
 * The <code>List</code> interface provides four methods for positional (indexed) access to list
 * elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time
 * proportional to the index value for some implementations (the <code>LinkedList</code> class, for
 * example). Thus, iterating over the elements in a list is typically preferable to indexing through
 * it if the caller does not know the implementation.
 * <p>
 *
 * The <code>List</code> interface provides a special iterator, called a <code>ListIterator</code>, that
 * allows element insertion and replacement, and bidirectional access in addition to the normal
 * operations that the <code>Iterator</code> interface provides. A method is provided to obtain a list
 * iterator that starts at a specified position in the list.
 * <p>
 *
 * The <code>List</code> interface provides two methods to search for a specified object. From a
 * performance standpoint, these methods should be used with caution. In many implementations they
 * will perform costly linear searches.
 * <p>
 *
 * The <code>List</code> interface provides two methods to efficiently insert and remove multiple
 * elements at an arbitrary point in the list.
 * <p>
 *
 * Note: While it is permissible for lists to contain themselves as elements, extreme caution is
 * advised: the <code>equals</code> and <code>hashCode</code> methods are no longer well defined on such a
 * list.
 *
 * <p>
 * Some list implementations have restrictions on the elements that they may contain. For example,
 * some implementations prohibit null elements, and some have restrictions on the types of their
 * elements. Attempting to add an ineligible element throws an unchecked exception, typically
 * <code>NullPointerException</code> or <code>ClassCastException</code>. Attempting to query the presence of
 * an ineligible element may throw an exception, or it may simply return false; some implementations
 * will exhibit the former behavior and some will exhibit the latter. More generally, attempting an
 * operation on an ineligible element whose completion would not result in the insertion of an
 * ineligible element into the list may throw an exception or it may succeed, at the option of the
 * implementation. Such exceptions are marked as "optional" in the specification for this interface.
 *
 * <p>
 * This interface is a member of the Java Collections Framework
 *
 * @param <E>
 *        the type of elements in this list
 *
 * @see Collection
 * @see Set
 * @see ArrayList
 * @see Vector
 * @see AbstractList
 */
public interface List<E> extends Collection<E> {

	/**
	 * 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.
	 *
	 * @param e
	 *        element to be appended to this list
	 * @return <code>true</code> (as specified by {@link Collection#add})
	 * @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 this element prevents it from being added to this list
	 */
	@Override
	boolean add(E e);

	/**
	 * 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).
	 *
	 * @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>)
	 */
	void add(int index, E element);

	/**
	 * 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 (optional operation). 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.)
	 *
	 * @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
	 * @see #add(Object)
	 */
	@Override
	boolean addAll(Collection<? extends E> c);

	/**
	 * 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.)
	 *
	 * @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>)
	 */
	boolean addAll(int index, Collection<? extends E> c);

	/**
	 * Removes all of the elements from this list (optional operation). The list will be empty after
	 * this call returns.
	 *
	 * @throws UnsupportedOperationException
	 *         if the <code>clear</code> operation is not supported by this list
	 */
	@Override
	void clear();

	/**
	 * 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
	 * @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
	boolean contains(Object o);

	/**
	 * Returns <code>true</code> if this list contains all of the elements of the specified collection.
	 *
	 * @param c
	 *        collection to be checked for containment in this list
	 * @return <code>true</code> if this list contains all of the elements of the specified collection
	 * @throws ClassCastException
	 *         if the types of one or more elements in the specified collection are incompatible with
	 *         this list (<a href="Collection.html#optional-restrictions">optional</a>)
	 * @throws NullPointerException
	 *         if the specified collection contains one or more null elements and this list does not
	 *         permit null elements (<a href="Collection.html#optional-restrictions">optional</a>), or
	 *         if the specified collection is null
	 * @see #contains(Object)
	 */
	@Override
	boolean containsAll(Collection<?> c);

	/**
	 * Compares the specified object with this list for equality. Returns <code>true</code> 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</code> and <code>e2</code> are
	 * <i>equal</i> if <code>(e1==null ? e2==null :
	 * e1.equals(e2))</code>.) In other words, two lists are defined to be equal if they contain the same
	 * elements in the same order. This definition ensures that the equals method works properly across
	 * different implementations of the <code>List</code> interface.
	 *
	 * @param o
	 *        the object to be compared for equality with this list
	 * @return <code>true</code> if the specified object is equal to this list
	 */
	@Override
	boolean equals(@Nullable Object o);

	/**
	 * 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>)
	 */
	E get(int index);

	/**
	 * Returns the hash code value for this list. The hash code of a list is defined to be the result of
	 * the following calculation:
	 *
	 * <pre>
	 * int hashCode = 1;
	 * for (E e : list)
	 * 	hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
	 * </pre>
	 *
	 * This ensures that <code>list1.equals(list2)</code> implies that
	 * <code>list1.hashCode()==list2.hashCode()</code> for any two lists, <code>list1</code> and <code>list2</code>,
	 * as required by the general contract of {@link Object#hashCode}.
	 *
	 * @return the hash code value for this list
	 * @see Object#equals(Object)
	 * @see #equals(Object)
	 */
	@Override
	int hashCode();

	/**
	 * 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.
	 *
	 * @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>)
	 */
	int indexOf(Object o);

	/**
	 * Returns <code>true</code> if this list contains no elements.
	 *
	 * @return <code>true</code> if this list contains no elements
	 */
	@Override
	boolean isEmpty();

	/**
	 * Returns an iterator over the elements in this list in proper sequence.
	 *
	 * @return an iterator over the elements in this list in proper sequence
	 */
	@Override
	Iterator<E> iterator();

	/**
	 * 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.
	 *
	 * @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>)
	 */
	int lastIndexOf(Object o);

	/**
	 * Returns a list iterator over the elements in this list (in proper sequence).
	 *
	 * @return a list iterator over the elements in this list (in proper sequence)
	 */
	ListIterator<E> listIterator();

	/**
	 * 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.
	 *
	 * @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()})
	 */
	ListIterator<E> listIterator(int index);

	/**
	 * 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.
	 *
	 * @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>)
	 */
	E remove(int index);

	/**
	 * Removes the first occurrence of the specified element from this list, if it is present (optional
	 * operation). If this 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
	 * @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>)
	 * @throws UnsupportedOperationException
	 *         if the <code>remove</code> operation is not supported by this list
	 */
	@Override
	boolean remove(Object o);

	/**
	 * Removes from this list all of its elements that are contained in the specified collection
	 * (optional operation).
	 *
	 * @param c
	 *        collection containing elements to be removed from this list
	 * @return <code>true</code> if this list changed as a result of the call
	 * @throws UnsupportedOperationException
	 *         if the <code>removeAll</code> operation is not supported by this list
	 * @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 #remove(Object)
	 * @see #contains(Object)
	 */
	@Override
	boolean removeAll(Collection<?> c);

	/**
	 * Retains only the elements in this list that are contained in the specified collection (optional
	 * operation). 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</code> if this list changed as a result of the call
	 * @throws UnsupportedOperationException
	 *         if the <code>retainAll</code> operation is not supported by this list
	 * @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 #remove(Object)
	 * @see #contains(Object)
	 */
	@Override
	boolean retainAll(Collection<?> c);

	/**
	 * Replaces the element at the specified position in this list with the specified element (optional
	 * operation).
	 *
	 * @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>)
	 */
	E set(int index, E element);

	/**
	 * Returns the number of elements in this list. If this list contains more than
	 * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>.
	 *
	 * @return the number of elements in this list
	 */
	@Override
	int size();

	/**
	 * 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.)
	 *
	 * @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>)
	 */
	List<E> subList(int fromIndex, int toIndex);

	/**
	 * 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 even if this list is backed by an 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
	Object[] toArray();

	/**
	 * 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 list 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.)
	 *
	 * <p>
	 * Like the {@link #toArray()} method, this method acts as bridge between array-based and
	 * collection-based APIs. Further, this method allows precise control over the runtime type of the
	 * output array, and may, under certain circumstances, be used to save allocation costs.
	 *
	 * <p>
	 * Suppose <code>x</code> is a list known to contain only strings. The following code can be used to
	 * dump the list into a newly allocated array of <code>String</code>:
	 *
	 * <pre>
	 * String[] y = x.toArray(new String[0]);
	 * </pre>
	 *
	 * Note that <code>toArray(new Object[0])</code> is identical in function to <code>toArray()</code>.
	 *
	 * @param a
	 *        the array into which the elements of this 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 this 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
	<T> T[] toArray(T[] a);
}