1 /*
   2  * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package javany.util;
  27 
  28 import java.util.ConcurrentModificationException;
  29 import java.util.NoSuchElementException;
  30 import java.util.RandomAccess;
  31 
  32 import javany.util.function.*;
  33 
  34 /**
  35  * This class provides a skeletal implementation of the {@link List}
  36  * interface to minimize the effort required to implement this interface
  37  * backed by a "random access" data store (such as an array).  For sequential
  38  * access data (such as a linked list), {@link AbstractSequentialList} should
  39  * be used in preference to this class.
  40  *
  41  * <p>To implement an unmodifiable list, the programmer needs only to extend
  42  * this class and provide implementations for the {@link #get(int)} and
  43  * {@link List#size() size()} methods.
  44  *
  45  * <p>To implement a modifiable list, the programmer must additionally
  46  * override the {@link #set(int, Object) set(int, E)} method (which otherwise
  47  * throws an {@code UnsupportedOperationException}).  If the list is
  48  * variable-size the programmer must additionally override the
  49  * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods.
  50  *
  51  * <p>The programmer should generally provide a void (no argument) and collection
  52  * constructor, as per the recommendation in the {@link Collection} interface
  53  * specification.
  54  *
  55  * <p>Unlike the other abstract collection implementations, the programmer does
  56  * <i>not</i> have to provide an iterator implementation; the iterator and
  57  * list iterator are implemented by this class, on top of the "random access"
  58  * methods:
  59  * {@link #get(int)},
  60  * {@link #set(int, Object) set(int, E)},
  61  * {@link #add(int, Object) add(int, E)} and
  62  * {@link #remove(int)}.
  63  *
  64  * <p>The documentation for each non-abstract method in this class describes its
  65  * implementation in detail.  Each of these methods may be overridden if the
  66  * collection being implemented admits a more efficient implementation.
  67  *
  68  * <p>This class is a member of the
  69  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  70  * Java Collections Framework</a>.
  71  *
  72  * @author  Josh Bloch
  73  * @author  Neal Gafter
  74  * @since 1.2
  75  */
  76 
  77 public abstract class AbstractList<any E> extends AbstractCollection<E> implements List<E> {
  78     /**
  79      * Sole constructor.  (For invocation by subclass constructors, typically
  80      * implicit.)
  81      */
  82     protected AbstractList() {
  83     }
  84 
  85     /**
  86      * Appends the specified element to the end of this list (optional
  87      * operation).
  88      *
  89      * <p>Lists that support this operation may place limitations on what
  90      * elements may be added to this list.  In particular, some
  91      * lists will refuse to add null elements, and others will impose
  92      * restrictions on the type of elements that may be added.  List
  93      * classes should clearly specify in their documentation any restrictions
  94      * on what elements may be added.
  95      *
  96      * @implSpec
  97      * This implementation calls {@code add(size(), e)}.
  98      *
  99      * <p>Note that this implementation throws an
 100      * {@code UnsupportedOperationException} unless
 101      * {@link #add(int, Object) add(int, E)} is overridden.
 102      *
 103      * @param e element to be appended to this list
 104      * @return {@code true} (as specified by {@link Collection#add})
 105      * @throws UnsupportedOperationException if the {@code add} operation
 106      *         is not supported by this list
 107      * @throws ClassCastException if the class of the specified element
 108      *         prevents it from being added to this list
 109      * @throws NullPointerException if the specified element is null and this
 110      *         list does not permit null elements
 111      * @throws IllegalArgumentException if some property of this element
 112      *         prevents it from being added to this list
 113      */
 114     public boolean add(E e) {
 115         add(size(), e);
 116         return true;
 117     }
 118 
 119     /**
 120      * {@inheritDoc}
 121      *
 122      * @throws IndexOutOfBoundsException {@inheritDoc}
 123      */
 124     abstract public E get(int index);
 125 
 126     /**
 127      * {@inheritDoc}
 128      *
 129      * @implSpec
 130      * This implementation always throws an
 131      * {@code UnsupportedOperationException}.
 132      *
 133      * @throws UnsupportedOperationException {@inheritDoc}
 134      * @throws ClassCastException            {@inheritDoc}
 135      * @throws NullPointerException          {@inheritDoc}
 136      * @throws IllegalArgumentException      {@inheritDoc}
 137      * @throws IndexOutOfBoundsException     {@inheritDoc}
 138      */
 139     public E set(int index, E element) {
 140         throw new UnsupportedOperationException();
 141     }
 142 
 143     /**
 144      * {@inheritDoc}
 145      *
 146      * @implSpec
 147      * This implementation always throws an
 148      * {@code UnsupportedOperationException}.
 149      *
 150      * @throws UnsupportedOperationException {@inheritDoc}
 151      * @throws ClassCastException            {@inheritDoc}
 152      * @throws NullPointerException          {@inheritDoc}
 153      * @throws IllegalArgumentException      {@inheritDoc}
 154      * @throws IndexOutOfBoundsException     {@inheritDoc}
 155      */
 156     public void add(int index, E element) {
 157         throw new UnsupportedOperationException();
 158     }
 159 
 160     /**
 161      * {@inheritDoc}
 162      *
 163      * @implSpec
 164      * This implementation always throws an
 165      * {@code UnsupportedOperationException}.
 166      *
 167      * @throws UnsupportedOperationException {@inheritDoc}
 168      * @throws IndexOutOfBoundsException     {@inheritDoc}
 169      */
 170     public E remove(int index) {
 171         throw new UnsupportedOperationException();
 172     }
 173 
 174 
 175     // Search Operations
 176 
 177     /**
 178      * {@inheritDoc}
 179      *
 180      * @implSpec
 181      * This implementation first gets a list iterator (with
 182      * {@code listIterator()}).  Then, it iterates over the list until the
 183      * specified element is found or the end of the list is reached.
 184      *
 185      * @throws ClassCastException   {@inheritDoc}
 186      * @throws NullPointerException {@inheritDoc}
 187      */
 188     public int indexOf(Object o) {
 189         __WhereVal(E) {
 190             if (o == null) {
 191                 return -1;
 192             }
 193             ListIterator<E> it = listIterator();
 194             Function<E, Object> box = Any.converter();
 195             while (it.hasNext())
 196                 if (o.equals(box.apply(it.next()))) // boxing
 197                     return it.previousIndex();
 198             return -1;
 199         }
 200         __WhereRef(E) {
 201             ListIterator<E> it = listIterator();
 202             if (o == null) {
 203                 while (it.hasNext())
 204                     if (it.next() == null)
 205                         return it.previousIndex();
 206             } else {
 207                 while (it.hasNext())
 208                     if (o.equals(it.next()))
 209                         return it.previousIndex();
 210             }
 211             return -1;
 212         }
 213     }
 214 
 215     /**
 216      * {@inheritDoc}
 217      *
 218      * @implSpec
 219      * This implementation first gets a list iterator that points to the end
 220      * of the list (with {@code listIterator(size())}).  Then, it iterates
 221      * backwards over the list until the specified element is found, or the
 222      * beginning of the list is reached.
 223      *
 224      * @throws ClassCastException   {@inheritDoc}
 225      * @throws NullPointerException {@inheritDoc}
 226      */
 227     public int lastIndexOf(Object o) {
 228         __WhereVal(E) {
 229             if (o == null) {
 230                 return -1;
 231             }
 232             ListIterator<E> it = listIterator(size());
 233             Function<E, Object> box = Any.converter();
 234             while (it.hasPrevious())
 235                 if (o.equals(box.apply(it.previous()))) // boxing
 236                     return it.nextIndex();
 237             return -1;
 238         }
 239         __WhereRef(E) {
 240             ListIterator<E> it = listIterator(size());
 241             if (o == null) {
 242                 while (it.hasPrevious())
 243                     if (it.previous() == null)
 244                         return it.nextIndex();
 245             } else {
 246                 while (it.hasPrevious())
 247                     if (o.equals(it.previous()))
 248                         return it.nextIndex();
 249             }
 250             return -1;
 251         }
 252     }
 253 
 254 
 255     // Bulk Operations
 256 
 257     /**
 258      * Removes all of the elements from this list (optional operation).
 259      * The list will be empty after this call returns.
 260      *
 261      * @implSpec
 262      * This implementation calls {@code removeRange(0, size())}.
 263      *
 264      * <p>Note that this implementation throws an
 265      * {@code UnsupportedOperationException} unless {@code remove(int
 266      * index)} or {@code removeRange(int fromIndex, int toIndex)} is
 267      * overridden.
 268      *
 269      * @throws UnsupportedOperationException if the {@code clear} operation
 270      *         is not supported by this list
 271      */
 272     public void clear() {
 273         removeRange(0, size());
 274     }
 275 
 276     /**
 277      * {@inheritDoc}
 278      *
 279      * @implSpec
 280      * This implementation gets an iterator over the specified collection
 281      * and iterates over it, inserting the elements obtained from the
 282      * iterator into this list at the appropriate position, one at a time,
 283      * using {@code add(int, E)}.
 284      * Many implementations will override this method for efficiency.
 285      *
 286      * <p>Note that this implementation throws an
 287      * {@code UnsupportedOperationException} unless
 288      * {@link #add(int, Object) add(int, E)} is overridden.
 289      *
 290      * @throws UnsupportedOperationException {@inheritDoc}
 291      * @throws ClassCastException            {@inheritDoc}
 292      * @throws NullPointerException          {@inheritDoc}
 293      * @throws IllegalArgumentException      {@inheritDoc}
 294      * @throws IndexOutOfBoundsException     {@inheritDoc}
 295      */
 296     public boolean addAll(int index, Collection<? extends E> c) {
 297         rangeCheckForAdd(index);
 298         boolean modified = false;
 299         Iterator<? extends E> it = c.iterator();
 300         while (it.hasNext()) {
 301             E e = it.next();
 302             add(index++, e);
 303             modified = true;
 304         }
 305         return modified;
 306     }
 307 
 308 
 309     // Iterators
 310 
 311     /**
 312      * Returns an iterator over the elements in this list in proper sequence.
 313      *
 314      * @implSpec
 315      * This implementation returns a straightforward implementation of the
 316      * iterator interface, relying on the backing list's {@code size()},
 317      * {@code get(int)}, and {@code remove(int)} methods.
 318      *
 319      * <p>Note that the iterator returned by this method will throw an
 320      * {@link UnsupportedOperationException} in response to its
 321      * {@code remove} method unless the list's {@code remove(int)} method is
 322      * overridden.
 323      *
 324      * <p>This implementation can be made to throw runtime exceptions in the
 325      * face of concurrent modification, as described in the specification
 326      * for the (protected) {@link #modCount} field.
 327      *
 328      * @return an iterator over the elements in this list in proper sequence
 329      */
 330     public Iterator<E> iterator() {
 331         return new Itr();
 332     }
 333 
 334     /**
 335      * {@inheritDoc}
 336      *
 337      * @implSpec
 338      * This implementation returns {@code listIterator(0)}.
 339      *
 340      * @see #listIterator(int)
 341      */
 342     public ListIterator<E> listIterator() {
 343         return listIterator(0);
 344     }
 345 
 346     /**
 347      * {@inheritDoc}
 348      *
 349      * @implSpec
 350      * This implementation returns a straightforward implementation of the
 351      * {@code ListIterator} interface that extends the implementation of the
 352      * {@code Iterator} interface returned by the {@code iterator()} method.
 353      * The {@code ListIterator} implementation relies on the backing list's
 354      * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
 355      * and {@code remove(int)} methods.
 356      *
 357      * <p>Note that the list iterator returned by this implementation will
 358      * throw an {@link UnsupportedOperationException} in response to its
 359      * {@code remove}, {@code set} and {@code add} methods unless the
 360      * list's {@code remove(int)}, {@code set(int, E)}, and
 361      * {@code add(int, E)} methods are overridden.
 362      *
 363      * <p>This implementation can be made to throw runtime exceptions in the
 364      * face of concurrent modification, as described in the specification for
 365      * the (protected) {@link #modCount} field.
 366      *
 367      * @throws IndexOutOfBoundsException {@inheritDoc}
 368      */
 369     public ListIterator<E> listIterator(final int index) {
 370         rangeCheckForAdd(index);
 371 
 372         return new ListItr(index);
 373     }
 374 
 375     private class Itr implements Iterator<E> {
 376         /**
 377          * Index of element to be returned by subsequent call to next.
 378          */
 379         int cursor = 0;
 380 
 381         /**
 382          * Index of element returned by most recent call to next or
 383          * previous.  Reset to -1 if this element is deleted by a call
 384          * to remove.
 385          */
 386         int lastRet = -1;
 387 
 388         /**
 389          * The modCount value that the iterator believes that the backing
 390          * List should have.  If this expectation is violated, the iterator
 391          * has detected concurrent modification.
 392          */
 393         int expectedModCount = modCount;
 394 
 395         public boolean hasNext() {
 396             return cursor != size();
 397         }
 398 
 399         public E next() {
 400             checkForComodification();
 401             try {
 402                 int i = cursor;
 403                 E next = get(i);
 404                 lastRet = i;
 405                 cursor = i + 1;
 406                 return next;
 407             } catch (IndexOutOfBoundsException e) {
 408                 checkForComodification();
 409                 throw new NoSuchElementException();
 410             }
 411         }
 412 
 413         public void remove() {
 414             if (lastRet < 0)
 415                 throw new IllegalStateException();
 416             checkForComodification();
 417 
 418             try {
 419                 AbstractList.this.remove(lastRet);
 420                 if (lastRet < cursor)
 421                     cursor--;
 422                 lastRet = -1;
 423                 expectedModCount = modCount;
 424             } catch (IndexOutOfBoundsException e) {
 425                 throw new ConcurrentModificationException();
 426             }
 427         }
 428 
 429         final void checkForComodification() {
 430             if (modCount != expectedModCount)
 431                 throw new ConcurrentModificationException();
 432         }
 433     }
 434 
 435     private class ListItr extends Itr implements ListIterator<E> {
 436         ListItr(int index) {
 437             cursor = index;
 438         }
 439 
 440         public boolean hasPrevious() {
 441             return cursor != 0;
 442         }
 443 
 444         public E previous() {
 445             checkForComodification();
 446             try {
 447                 int i = cursor - 1;
 448                 E previous = get(i);
 449                 lastRet = cursor = i;
 450                 return previous;
 451             } catch (IndexOutOfBoundsException e) {
 452                 checkForComodification();
 453                 throw new NoSuchElementException();
 454             }
 455         }
 456 
 457         public int nextIndex() {
 458             return cursor;
 459         }
 460 
 461         public int previousIndex() {
 462             return cursor-1;
 463         }
 464 
 465         public void set(E e) {
 466             if (lastRet < 0)
 467                 throw new IllegalStateException();
 468             checkForComodification();
 469 
 470             try {
 471                 AbstractList.this.set(lastRet, e);
 472                 expectedModCount = modCount;
 473             } catch (IndexOutOfBoundsException ex) {
 474                 throw new ConcurrentModificationException();
 475             }
 476         }
 477 
 478         public void add(E e) {
 479             checkForComodification();
 480 
 481             try {
 482                 int i = cursor;
 483                 AbstractList.this.add(i, e);
 484                 lastRet = -1;
 485                 cursor = i + 1;
 486                 expectedModCount = modCount;
 487             } catch (IndexOutOfBoundsException ex) {
 488                 throw new ConcurrentModificationException();
 489             }
 490         }
 491     }
 492 
 493     /**
 494      * {@inheritDoc}
 495      *
 496      * @implSpec
 497      * This implementation returns a list that subclasses
 498      * {@code AbstractList}.  The subclass stores, in private fields, the
 499      * offset of the subList within the backing list, the size of the subList
 500      * (which can change over its lifetime), and the expected
 501      * {@code modCount} value of the backing list.  There are two variants
 502      * of the subclass, one of which implements {@code RandomAccess}.
 503      * If this list implements {@code RandomAccess} the returned list will
 504      * be an instance of the subclass that implements {@code RandomAccess}.
 505      *
 506      * <p>The subclass's {@code set(int, E)}, {@code get(int)},
 507      * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
 508      * Collection)} and {@code removeRange(int, int)} methods all
 509      * delegate to the corresponding methods on the backing abstract list,
 510      * after bounds-checking the index and adjusting for the offset.  The
 511      * {@code addAll(Collection c)} method merely returns {@code addAll(size,
 512      * c)}.
 513      *
 514      * <p>The {@code listIterator(int)} method returns a "wrapper object"
 515      * over a list iterator on the backing list, which is created with the
 516      * corresponding method on the backing list.  The {@code iterator} method
 517      * merely returns {@code listIterator()}, and the {@code size} method
 518      * merely returns the subclass's {@code size} field.
 519      *
 520      * <p>All methods first check to see if the actual {@code modCount} of
 521      * the backing list is equal to its expected value, and throw a
 522      * {@code ConcurrentModificationException} if it is not.
 523      *
 524      * @throws IndexOutOfBoundsException if an endpoint index value is out of range
 525      *         {@code (fromIndex < 0 || toIndex > size)}
 526      * @throws IllegalArgumentException if the endpoint indices are out of order
 527      *         {@code (fromIndex > toIndex)}
 528      */
 529     public List<E> subList(int fromIndex, int toIndex) {
 530         return (this instanceof RandomAccess ?
 531                 new RandomAccessSubList<>(this, fromIndex, toIndex) :
 532                 new SubList<>(this, fromIndex, toIndex));
 533     }
 534 
 535     // Comparison and hashing
 536 
 537     /**
 538      * Compares the specified object with this list for equality.  Returns
 539      * {@code true} if and only if the specified object is also a list, both
 540      * lists have the same size, and all corresponding pairs of elements in
 541      * the two lists are <i>equal</i>.  (Two elements {@code e1} and
 542      * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
 543      * e1.equals(e2))}.)  In other words, two lists are defined to be
 544      * equal if they contain the same elements in the same order.
 545      *
 546      * @implSpec
 547      * This implementation first checks if the specified object is this
 548      * list. If so, it returns {@code true}; if not, it checks if the
 549      * specified object is a list. If not, it returns {@code false}; if so,
 550      * it iterates over both lists, comparing corresponding pairs of elements.
 551      * If any comparison returns {@code false}, this method returns
 552      * {@code false}.  If either iterator runs out of elements before the
 553      * other it returns {@code false} (as the lists are of unequal length);
 554      * otherwise it returns {@code true} when the iterations complete.
 555      *
 556      * @param o the object to be compared for equality with this list
 557      * @return {@code true} if the specified object is equal to this list
 558      */
 559     @SuppressWarnings("unchecked")
 560     public boolean equals(Object o) {
 561         if (o == this)
 562             return true;
 563         if (!(o instanceof List<E>))
 564             return false;
 565 
 566         ListIterator<E> e1 = listIterator();
 567         ListIterator<? extends E> e2 = ((List<? extends E>) o).listIterator();
 568         while (e1.hasNext() && e2.hasNext()) {
 569             if (!Any.equals(e1.next(), e2.next()))
 570                 return false;
 571         }
 572         return !(e1.hasNext() || e2.hasNext());
 573     }
 574 
 575     /**
 576      * Returns the hash code value for this list.
 577      *
 578      * @implSpec
 579      * This implementation uses exactly the code that is used to define the
 580      * list hash function in the documentation for the {@link List#hashCode}
 581      * method.
 582      *
 583      * @return the hash code value for this list
 584      */
 585     public int hashCode() {
 586         int hashCode = 1;
 587         Iterator<E> it = iterator();
 588         while (it.hasNext()) {
 589             E e = it.next();
 590             hashCode = 31 * hashCode + Any.hashCode(e);
 591         }
 592         return hashCode;
 593     }
 594 
 595     /**
 596      * Removes from this list all of the elements whose index is between
 597      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 598      * Shifts any succeeding elements to the left (reduces their index).
 599      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 600      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 601      *
 602      * <p>This method is called by the {@code clear} operation on this list
 603      * and its subLists.  Overriding this method to take advantage of
 604      * the internals of the list implementation can <i>substantially</i>
 605      * improve the performance of the {@code clear} operation on this list
 606      * and its subLists.
 607      *
 608      * @implSpec
 609      * This implementation gets a list iterator positioned before
 610      * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
 611      * followed by {@code ListIterator.remove} until the entire range has
 612      * been removed.  <b>Note: if {@code ListIterator.remove} requires linear
 613      * time, this implementation requires quadratic time.</b>
 614      *
 615      * @param fromIndex index of first element to be removed
 616      * @param toIndex index after last element to be removed
 617      */
 618     protected void removeRange(int fromIndex, int toIndex) {
 619         ListIterator<E> it = listIterator(fromIndex);
 620         for (int i=0, n=toIndex-fromIndex; i<n; i++) {
 621             it.next();
 622             it.remove();
 623         }
 624     }
 625 
 626     /**
 627      * The number of times this list has been <i>structurally modified</i>.
 628      * Structural modifications are those that change the size of the
 629      * list, or otherwise perturb it in such a fashion that iterations in
 630      * progress may yield incorrect results.
 631      *
 632      * <p>This field is used by the iterator and list iterator implementation
 633      * returned by the {@code iterator} and {@code listIterator} methods.
 634      * If the value of this field changes unexpectedly, the iterator (or list
 635      * iterator) will throw a {@code ConcurrentModificationException} in
 636      * response to the {@code next}, {@code remove}, {@code previous},
 637      * {@code set} or {@code add} operations.  This provides
 638      * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
 639      * the face of concurrent modification during iteration.
 640      *
 641      * <p><b>Use of this field by subclasses is optional.</b> If a subclass
 642      * wishes to provide fail-fast iterators (and list iterators), then it
 643      * merely has to increment this field in its {@code add(int, E)} and
 644      * {@code remove(int)} methods (and any other methods that it overrides
 645      * that result in structural modifications to the list).  A single call to
 646      * {@code add(int, E)} or {@code remove(int)} must add no more than
 647      * one to this field, or the iterators (and list iterators) will throw
 648      * bogus {@code ConcurrentModificationExceptions}.  If an implementation
 649      * does not wish to provide fail-fast iterators, this field may be
 650      * ignored.
 651      */
 652     protected transient int modCount = 0;
 653 
 654     private void rangeCheckForAdd(int index) {
 655         if (index < 0 || index > size())
 656             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 657     }
 658 
 659     private String outOfBoundsMsg(int index) {
 660         return "Index: "+index+", Size: "+size();
 661     }
 662 }
 663 
 664 class SubList<any E> extends AbstractList<E> {
 665     private final AbstractList<E> l;
 666     private final int offset;
 667     private int size;
 668 
 669     SubList(AbstractList<E> list, int fromIndex, int toIndex) {
 670         if (fromIndex < 0)
 671             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 672         if (toIndex > list.size())
 673             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 674         if (fromIndex > toIndex)
 675             throw new IllegalArgumentException("fromIndex(" + fromIndex +
 676                                                ") > toIndex(" + toIndex + ")");
 677         l = list;
 678         offset = fromIndex;
 679         size = toIndex - fromIndex;
 680         this.modCount = l.modCount;
 681     }
 682 
 683     public E set(int index, E element) {
 684         rangeCheck(index);
 685         checkForComodification();
 686         return l.set(index+offset, element);
 687     }
 688 
 689     public E get(int index) {
 690         rangeCheck(index);
 691         checkForComodification();
 692         return l.get(index+offset);
 693     }
 694 
 695     public int size() {
 696         checkForComodification();
 697         return size;
 698     }
 699 
 700     public void add(int index, E element) {
 701         rangeCheckForAdd(index);
 702         checkForComodification();
 703         l.add(index+offset, element);
 704         this.modCount = l.modCount;
 705         size++;
 706     }
 707 
 708     public E remove(int index) {
 709         rangeCheck(index);
 710         checkForComodification();
 711         E result = l.remove(index+offset);
 712         this.modCount = l.modCount;
 713         size--;
 714         return result;
 715     }
 716 
 717     protected void removeRange(int fromIndex, int toIndex) {
 718         checkForComodification();
 719         l.removeRange(fromIndex+offset, toIndex+offset);
 720         this.modCount = l.modCount;
 721         size -= (toIndex-fromIndex);
 722     }
 723 
 724     public boolean addAll(Collection<? extends E> c) {
 725         return addAll(size, c);
 726     }
 727 
 728     public boolean addAll(int index, Collection<? extends E> c) {
 729         rangeCheckForAdd(index);
 730         int cSize = c.size();
 731         if (cSize==0)
 732             return false;
 733 
 734         checkForComodification();
 735         l.addAll(offset+index, c);
 736         this.modCount = l.modCount;
 737         size += cSize;
 738         return true;
 739     }
 740 
 741     public Iterator<E> iterator() {
 742         return listIterator();
 743     }
 744 
 745     public ListIterator<E> listIterator(final int index) {
 746         checkForComodification();
 747         rangeCheckForAdd(index);
 748 
 749         return new ListIterator<E>() {
 750             private final ListIterator<E> i = l.listIterator(index+offset);
 751 
 752             public boolean hasNext() {
 753                 return nextIndex() < size;
 754             }
 755 
 756             public E next() {
 757                 if (hasNext())
 758                     return i.next();
 759                 else
 760                     throw new NoSuchElementException();
 761             }
 762 
 763             public boolean hasPrevious() {
 764                 return previousIndex() >= 0;
 765             }
 766 
 767             public E previous() {
 768                 if (hasPrevious())
 769                     return i.previous();
 770                 else
 771                     throw new NoSuchElementException();
 772             }
 773 
 774             public int nextIndex() {
 775                 return i.nextIndex() - offset;
 776             }
 777 
 778             public int previousIndex() {
 779                 return i.previousIndex() - offset;
 780             }
 781 
 782             public void remove() {
 783                 i.remove();
 784                 SubList.this.modCount = l.modCount;
 785                 size--;
 786             }
 787 
 788             public void set(E e) {
 789                 i.set(e);
 790             }
 791 
 792             public void add(E e) {
 793                 i.add(e);
 794                 SubList.this.modCount = l.modCount;
 795                 size++;
 796             }
 797         };
 798     }
 799 
 800     public List<E> subList(int fromIndex, int toIndex) {
 801         return new SubList<>(this, fromIndex, toIndex);
 802     }
 803 
 804     private void rangeCheck(int index) {
 805         if (index < 0 || index >= size)
 806             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 807     }
 808 
 809     private void rangeCheckForAdd(int index) {
 810         if (index < 0 || index > size)
 811             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 812     }
 813 
 814     private String outOfBoundsMsg(int index) {
 815         return "Index: "+index+", Size: "+size;
 816     }
 817 
 818     private void checkForComodification() {
 819         if (this.modCount != l.modCount)
 820             throw new ConcurrentModificationException();
 821     }
 822 }
 823 
 824 class RandomAccessSubList<any E> extends SubList<E> implements RandomAccess {
 825     RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
 826         super(list, fromIndex, toIndex);
 827     }
 828 
 829     public List<E> subList(int fromIndex, int toIndex) {
 830         return new RandomAccessSubList<>(this, fromIndex, toIndex);
 831     }
 832 }