/*

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

     }

 }