/*

 * Copyright (c) 1997, 2010, 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.

     *

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

     */

    public boolean add(E e) {

        add(size(), e);

        return true;

    }

    /**

     * {@inheritDoc}

     *

     * @throws IndexOutOfBoundsException {@inheritDoc}

     */

    abstract public E get(int index);

    /**

     * {@inheritDoc}

     *

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

     *

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

     *

     * <p>This implementation always throws an

     * {@code UnsupportedOperationException}.

     *

     * @throws UnsupportedOperationException {@inheritDoc}

     * @throws IndexOutOfBoundsException     {@inheritDoc}

     */

    public E remove(int index) {

        throw new UnsupportedOperationException();

    }

    // Search Operations

    /**

     * {@inheritDoc}

     *

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

     *

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

     *

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

     *

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

     *

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

     */

    public void clear() {

        removeRange(0, size());

    }

    /**

     * {@inheritDoc}

     *

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

     *

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

     *

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

     */

    public Iterator<E> iterator() {

        return new Itr();

    }

    /**

     * {@inheritDoc}

     *

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

     *

     * @see #listIterator(int)

     */

    public ListIterator<E> listIterator() {

        return listIterator(0);

    }

    /**

     * {@inheritDoc}

     *

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

     *

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

     *

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

     *

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

     */

    public boolean equals(Object o) {

        if (o == this)

            return true;

        if (!(o instanceof List))

            return false;

        ListIterator<E> e1 = listIterator();

        ListIterator e2 = ((List) o).listIterator();

        while (e1.hasNext() && e2.hasNext()) {

            E o1 = e1.next();

            Object o2 = e2.next();

            if (!(o1==null ? o2==null : o1.equals(o2)))

                return false;

        }

        return !(e1.hasNext() || e2.hasNext());

    }

    /**

     * 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

     */

    public int hashCode() {

        int hashCode = 1;

        for (E e : this)

            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

        return hashCode;

    }

    /**

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

        ListIterator<E> it = listIterator(fromIndex);

        for (int i=0, n=toIndex-fromIndex; i<n; i++) {

            it.next();

            it.remove();

        }

    }

    /**

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

    private void rangeCheckForAdd(int index) {

        if (index < 0 || index > size())

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    private String outOfBoundsMsg(int index) {

        return "Index: "+index+", Size: "+size();

    }

}

class SubList<E> extends AbstractList<E> {

    private final AbstractList<E> l;

    private final int offset;

    private int size;

    SubList(AbstractList<E> list, int fromIndex, int toIndex) {

        if (fromIndex < 0)

            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);

        if (toIndex > list.size())

            throw new IndexOutOfBoundsException("toIndex = " + toIndex);

        if (fromIndex > toIndex)

            throw new IllegalArgumentException("fromIndex(" + fromIndex +

                                               ") > toIndex(" + toIndex + ")");

        l = list;

        offset = fromIndex;

        size = toIndex - fromIndex;

        this.modCount = l.modCount;

    }

    public E set(int index, E element) {

        rangeCheck(index);

        checkForComodification();

        return l.set(index+offset, element);

    }

    public E get(int index) {

        rangeCheck(index);

        checkForComodification();

        return l.get(index+offset);

    }

    public int size() {

        checkForComodification();

        return size;

    }

    public void add(int index, E element) {

        rangeCheckForAdd(index);

        checkForComodification();

        l.add(index+offset, element);

        this.modCount = l.modCount;

        size++;

    }

    public E remove(int index) {

        rangeCheck(index);

        checkForComodification();

        E result = l.remove(index+offset);

        this.modCount = l.modCount;

        size--;

        return result;

    }

    protected void removeRange(int fromIndex, int toIndex) {

        checkForComodification();

        l.removeRange(fromIndex+offset, toIndex+offset);

        this.modCount = l.modCount;

        size -= (toIndex-fromIndex);

    }

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

        return addAll(size, c);

    }

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

        rangeCheckForAdd(index);

        int cSize = c.size();

        if (cSize==0)

            return false;

        checkForComodification();

        l.addAll(offset+index, c);

        this.modCount = l.modCount;

        size += cSize;

        return true;

    }

    public Iterator<E> iterator() {

        return listIterator();

    }

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

        checkForComodification();

        rangeCheckForAdd(index);

        return new ListIterator<E>() {

            private final ListIterator<E> i = l.listIterator(index+offset);

            public boolean hasNext() {

                return nextIndex() < size;

            }

            public E next() {

                if (hasNext())

                    return i.next();

                else

                    throw new NoSuchElementException();

            }

            public boolean hasPrevious() {

                return previousIndex() >= 0;

            }

            public E previous() {

                if (hasPrevious())

                    return i.previous();

                else

                    throw new NoSuchElementException();

            }

            public int nextIndex() {

                return i.nextIndex() - offset;

            }

            public int previousIndex() {

                return i.previousIndex() - offset;

            }

            public void remove() {

                i.remove();

                SubList.this.modCount = l.modCount;

                size--;

            }

            public void set(E e) {

                i.set(e);

            }

            public void add(E e) {

                i.add(e);

                SubList.this.modCount = l.modCount;

                size++;

            }

        };

    }

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

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

    }

    private void rangeCheck(int index) {

        if (index < 0 || index >= size)

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    private void rangeCheckForAdd(int index) {

        if (index < 0 || index > size)

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    private String outOfBoundsMsg(int index) {

        return "Index: "+index+", Size: "+size;

    }

    private void checkForComodification() {

        if (this.modCount != l.modCount)

            throw new ConcurrentModificationException();

    }

}

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {

    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {

        super(list, fromIndex, toIndex);

    }

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

        return new RandomAccessSubList<>(this, fromIndex, toIndex);

    }

}