/*

 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.util;

/**

 * 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).  For sequential

 * access data (such as a linked list), {@link AbstractSequentialList} should

 * be used in preference to this class.

 *

 * <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

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @author  Josh Bloch

 * @author  Neal Gafter

 * @since 1.2

 */

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

    /**

     * 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.

     *

     * @implSpec

     * 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

     */

    public boolean add(E e) {

        add(size(), e);

        return true;

    }

    /**

     * {@inheritDoc}

     *

     * @throws IndexOutOfBoundsException {@inheritDoc}

     */

    abstract public E get(int index);

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * This implementation always throws an

     * {@code UnsupportedOperationException}.

     *

     * @throws UnsupportedOperationException {@inheritDoc}

     * @throws ClassCastException            {@inheritDoc}

     * @throws NullPointerException          {@inheritDoc}

     * @throws IllegalArgumentException      {@inheritDoc}

     * @throws IndexOutOfBoundsException     {@inheritDoc}

     */

    public E set(int index, E element) {

        throw new UnsupportedOperationException();

    }

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * This implementation always throws an

     * {@code UnsupportedOperationException}.

     *

     * @throws UnsupportedOperationException {@inheritDoc}

     * @throws ClassCastException            {@inheritDoc}

     * @throws NullPointerException          {@inheritDoc}

     * @throws IllegalArgumentException      {@inheritDoc}

     * @throws IndexOutOfBoundsException     {@inheritDoc}

     */

    public void add(int index, E element) {

        throw new UnsupportedOperationException();

    }

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * This implementation always throws an

     * {@code UnsupportedOperationException}.

     *

     * @throws UnsupportedOperationException {@inheritDoc}

     * @throws IndexOutOfBoundsException     {@inheritDoc}

     */

    public E remove(int index) {

        throw new UnsupportedOperationException();

    }

    // Search Operations

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * 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.

     *

     * @throws ClassCastException   {@inheritDoc}

     * @throws NullPointerException {@inheritDoc}

     */

    public int indexOf(Object o) {

        ListIterator<E> it = listIterator();

        if (o==null) {

            while (it.hasNext())

                if (it.next()==null)

                    return it.previousIndex();

        } else {

            while (it.hasNext())

                if (o.equals(it.next()))

                    return it.previousIndex();

        }

        return -1;

    }

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * 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.

     *

     * @throws ClassCastException   {@inheritDoc}

     * @throws NullPointerException {@inheritDoc}

     */

    public int lastIndexOf(Object o) {

        ListIterator<E> it = listIterator(size());

        if (o==null) {

            while (it.hasPrevious())

                if (it.previous()==null)

                    return it.nextIndex();

        } else {

            while (it.hasPrevious())

                if (o.equals(it.previous()))

                    return it.nextIndex();

        }

        return -1;

    }

    // Bulk Operations

    /**

     * Removes all of the elements from this list (optional operation).

     * The list will be empty after this call returns.

     *

     * @implSpec

     * 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

     */

    public void clear() {

        removeRange(0, size());

    }

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * 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.

     *

     * @throws UnsupportedOperationException {@inheritDoc}

     * @throws ClassCastException            {@inheritDoc}

     * @throws NullPointerException          {@inheritDoc}

     * @throws IllegalArgumentException      {@inheritDoc}

     * @throws IndexOutOfBoundsException     {@inheritDoc}

     */

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

        rangeCheckForAdd(index);

        boolean modified = false;

        for (E e : c) {

            add(index++, e);

            modified = true;

        }

        return modified;

    }

    // Iterators

    /**

     * Returns an iterator over the elements in this list in proper sequence.

     *

     * @implSpec

     * 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

     */

    public Iterator<E> iterator() {

        return new Itr();

    }

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * This implementation returns {@code listIterator(0)}.

     *

     * @see #listIterator(int)

     */

    public ListIterator<E> listIterator() {

        return listIterator(0);

    }

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * 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.

     *

     * @throws IndexOutOfBoundsException {@inheritDoc}

     */

    public ListIterator<E> listIterator(final int index) {

        rangeCheckForAdd(index);

        return new ListItr(index);

    }

    private class Itr implements Iterator<E> {

        /**

         * Index of element to be returned by subsequent call to next.

         */

        int cursor = 0;

        /**

         * Index of element returned by most recent call to next or

         * previous.  Reset to -1 if this element is deleted by a call

         * to remove.

         */

        int lastRet = -1;

        /**

         * The modCount value that the iterator believes that the backing

         * List should have.  If this expectation is violated, the iterator

         * has detected concurrent modification.

         */

        int expectedModCount = modCount;

        public boolean hasNext() {

            return cursor != size();

        }

        public E next() {

            checkForComodification();

            try {

                int i = cursor;

                E next = get(i);

                lastRet = i;

                cursor = i + 1;

                return next;

            } catch (IndexOutOfBoundsException e) {

                checkForComodification();

                throw new NoSuchElementException();

            }

        }

        public void remove() {

            if (lastRet < 0)

                throw new IllegalStateException();

            checkForComodification();

            try {

                AbstractList.this.remove(lastRet);

                if (lastRet < cursor)

                    cursor--;

                lastRet = -1;

                expectedModCount = modCount;

            } catch (IndexOutOfBoundsException e) {

                throw new ConcurrentModificationException();

            }

        }

        final void checkForComodification() {

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

        }

    }

    private class ListItr extends Itr implements ListIterator<E> {

        ListItr(int index) {

            cursor = index;

        }

        public boolean hasPrevious() {

            return cursor != 0;

        }

        public E previous() {

            checkForComodification();

            try {

                int i = cursor - 1;

                E previous = get(i);

                lastRet = cursor = i;

                return previous;

            } catch (IndexOutOfBoundsException e) {

                checkForComodification();

                throw new NoSuchElementException();

            }

        }

        public int nextIndex() {

            return cursor;

        }

        public int previousIndex() {

            return cursor-1;

        }

        public void set(E e) {

            if (lastRet < 0)

                throw new IllegalStateException();

            checkForComodification();

            try {

                AbstractList.this.set(lastRet, e);

                expectedModCount = modCount;

            } catch (IndexOutOfBoundsException ex) {

                throw new ConcurrentModificationException();

            }

        }

        public void add(E e) {

            checkForComodification();

            try {

                int i = cursor;

                AbstractList.this.add(i, e);

                lastRet = -1;

                cursor = i + 1;

                expectedModCount = modCount;

            } catch (IndexOutOfBoundsException ex) {

                throw new ConcurrentModificationException();

            }

        }

    }

    /**

     * {@inheritDoc}

     *

     * @implSpec

     * 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.

     *

     * @throws IndexOutOfBoundsException if an endpoint index value is out of range

     *         {@code (fromIndex < 0 || toIndex > size)}

     * @throws IllegalArgumentException if the endpoint indices are out of order

     *         {@code (fromIndex > toIndex)}

     */

    public List<E> subList(int fromIndex, int toIndex) {

        return (this instanceof RandomAccess ?

                new RandomAccessSubList<>(this, fromIndex, toIndex) :

                new SubList<>(this, fromIndex, toIndex));

    }

    // Comparison and hashing

    /**

     * 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.

     *

     * @implSpec

     * 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