/*
 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

import java.util.function.Consumer;

/**
 * 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}/java.base/java/util/package-summary.html#CollectionsFramework">
 * 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}
 */
 public abstract 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
 * 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) {
 subListRangeCheck(fromIndex, toIndex, size());
 return (this instanceof RandomAccess ?
 new RandomAccessSubList<>(this, fromIndex, toIndex) :
 new SubList<>(this, fromIndex, toIndex));
 }

 static void subListRangeCheck(int fromIndex, int toIndex, int size) {
 if (fromIndex < 0)
 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 if (toIndex > size)
 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 if (fromIndex > toIndex)
 throw new IllegalArgumentException("fromIndex(" + fromIndex +
 ") > toIndex(" + 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
 * @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.
 *
 * @implSpec
 * 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.
 *
 * @implSpec
 * 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();
 }

 /**
 * An index-based split-by-two, lazily initialized Spliterator covering
 * a List that access elements via {@link List#get}.
 *
 * If access results in an IndexOutOfBoundsException then a
 * ConcurrentModificationException is thrown instead (since the list has
 * been structurally modified while traversing).
 *
 * If the List is an instance of AbstractList then concurrent modification
 * checking is performed using the AbstractList's modCount field.
 */
 static final class RandomAccessSpliterator<E> implements Spliterator<E> {

 private final List<E> list;
 private int index; // current index, modified on advance/split
 private int fence; // -1 until used; then one past last index

 // The following fields are valid if covering an AbstractList
 private final AbstractList<E> alist;
 private int expectedModCount; // initialized when fence set

 RandomAccessSpliterator(List<E> list) {
 assert list instanceof RandomAccess;

 this.list = list;
 this.index = 0;
 this.fence = -1;

 this.alist = list instanceof AbstractList ? (AbstractList<E>) list : null;
 this.expectedModCount = alist != null ? alist.modCount : 0;
 }

 /** Create new spliterator covering the given range */
 private RandomAccessSpliterator(RandomAccessSpliterator<E> parent,
 int origin, int fence) {
 this.list = parent.list;
 this.index = origin;
 this.fence = fence;

 this.alist = parent.alist;
 this.expectedModCount = parent.expectedModCount;
 }

 private int getFence() { // initialize fence to size on first use
 int hi;
 List<E> lst = list;
 if ((hi = fence) < 0) {
 if (alist != null) {
 expectedModCount = alist.modCount;
 }
 hi = fence = lst.size();
 }
 return hi;
 }

 public Spliterator<E> trySplit() {
 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
 return (lo >= mid) ? null : // divide range in half unless too small
 new RandomAccessSpliterator<>(this, lo, index = mid);
 }

 public boolean tryAdvance(Consumer<? super E> action) {
 if (action == null)
 throw new NullPointerException();
 int hi = getFence(), i = index;
 if (i < hi) {
 index = i + 1;
 action.accept(get(list, i));
 checkAbstractListModCount(alist, expectedModCount);
 return true;
 }
 return false;
 }

 public void forEachRemaining(Consumer<? super E> action) {
 Objects.requireNonNull(action);
 List<E> lst = list;
 int hi = getFence();
 int i = index;
 index = hi;
 for (; i < hi; i++) {
 action.accept(get(lst, i));
 }
 checkAbstractListModCount(alist, expectedModCount);
 }

 public long estimateSize() {
 return (long) (getFence() - index);
 }

 public int characteristics() {
 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
 }

 private static <E> E get(List<E> list, int i) {
 try {
 return list.get(i);
 } catch (IndexOutOfBoundsException ex) {
 throw new ConcurrentModificationException();
 }
 }

 static void checkAbstractListModCount(AbstractList<?> alist, int expectedModCount) {
 if (alist != null && alist.modCount != expectedModCount) {
 throw new ConcurrentModificationException();
 }
 }
 }

 private static class SubList<E> extends AbstractList<E> {
 private final AbstractList<E> root;
 private final SubList<E> parent;
 private final int offset;
 protected int size;

 /**
 * Constructs a sublist of an arbitrary AbstractList, which is
 * not a SubList itself.
 */
 public SubList(AbstractList<E> root, int fromIndex, int toIndex) {
 this.root = root;
 this.parent = null;
 this.offset = fromIndex;
 this.size = toIndex - fromIndex;
 this.modCount = root.modCount;
 }

 /**
 * Constructs a sublist of another SubList.
 */
 protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
 this.root = parent.root;
 this.parent = parent;
 this.offset = parent.offset + fromIndex;
 this.size = toIndex - fromIndex;
 this.modCount = root.modCount;
 }

 public E set(int index, E element) {
 Objects.checkIndex(index, size);
 checkForComodification();
 return root.set(offset + index, element);
 }

 public E get(int index) {
 Objects.checkIndex(index, size);
 checkForComodification();
 return root.get(offset + index);
 }

 public int size() {
 checkForComodification();
 return size;
 }

 public void add(int index, E element) {
 rangeCheckForAdd(index);
 checkForComodification();
 root.add(offset + index, element);
 updateSizeAndModCount(1);
 }

 public E remove(int index) {
 Objects.checkIndex(index, size);
 checkForComodification();
 E result = root.remove(offset + index);
 updateSizeAndModCount(-1);
 return result;
 }

 protected void removeRange(int fromIndex, int toIndex) {
 checkForComodification();
 root.removeRange(offset + fromIndex, offset + toIndex);
 updateSizeAndModCount(fromIndex - toIndex);
 }

 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();
 root.addAll(offset + index, c);
 updateSizeAndModCount(cSize);
 return true;
 }

 public Iterator<E> iterator() {
 return listIterator();
 }

 public ListIterator<E> listIterator(int index) {
 checkForComodification();
 rangeCheckForAdd(index);

 return new ListIterator<E>() {
 private final ListIterator<E> i =
 root.listIterator(offset + index);

 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();
 updateSizeAndModCount(-1);
 }

 public void set(E e) {
 i.set(e);
 }

 public void add(E e) {
 i.add(e);
 updateSizeAndModCount(1);
 }
 };
 }

 public List<E> subList(int fromIndex, int toIndex) {
 subListRangeCheck(fromIndex, toIndex, size);
 return new SubList<>(this, fromIndex, toIndex);
 }

 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 (root.modCount != this.modCount)
 throw new ConcurrentModificationException();
 }

 private void updateSizeAndModCount(int sizeChange) {
 SubList<E> slist = this;
 do {
 slist.size += sizeChange;
 slist.modCount = root.modCount;
 slist = slist.parent;
 } while (slist != null);
 }
 }

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

 /**
 * Constructs a sublist of an arbitrary AbstractList, which is
 * not a RandomAccessSubList itself.
 */
 RandomAccessSubList(AbstractList<E> root,
 int fromIndex, int toIndex) {
 super(root, fromIndex, toIndex);
 }

 /**
 * Constructs a sublist of another RandomAccessSubList.
 */
 RandomAccessSubList(RandomAccessSubList<E> parent,
 int fromIndex, int toIndex) {
 super(parent, fromIndex, toIndex);
 }

 public List<E> subList(int fromIndex, int toIndex) {
 subListRangeCheck(fromIndex, toIndex, size);
 return new RandomAccessSubList<>(this, fromIndex, toIndex);
 }
 }
}