001/* AbstractList.java -- Abstract implementation of most of List
002   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005
003   Free Software Foundation, Inc.
004
005This file is part of GNU Classpath.
006
007GNU Classpath is free software; you can redistribute it and/or modify
008it under the terms of the GNU General Public License as published by
009the Free Software Foundation; either version 2, or (at your option)
010any later version.
011
012GNU Classpath is distributed in the hope that it will be useful, but
013WITHOUT ANY WARRANTY; without even the implied warranty of
014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015General Public License for more details.
016
017You should have received a copy of the GNU General Public License
018along with GNU Classpath; see the file COPYING.  If not, write to the
019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02002110-1301 USA.
021
022Linking this library statically or dynamically with other modules is
023making a combined work based on this library.  Thus, the terms and
024conditions of the GNU General Public License cover the whole
025combination.
026
027As a special exception, the copyright holders of this library give you
028permission to link this library with independent modules to produce an
029executable, regardless of the license terms of these independent
030modules, and to copy and distribute the resulting executable under
031terms of your choice, provided that you also meet, for each linked
032independent module, the terms and conditions of the license of that
033module.  An independent module is a module which is not derived from
034or based on this library.  If you modify this library, you may extend
035this exception to your version of the library, but you are not
036obligated to do so.  If you do not wish to do so, delete this
037exception statement from your version. */
038
039
040package java.util;
041
042/**
043 * A basic implementation of most of the methods in the List interface to make
044 * it easier to create a List based on a random-access data structure. If
045 * the list is sequential (such as a linked list), use AbstractSequentialList.
046 * To create an unmodifiable list, it is only necessary to override the
047 * size() and get(int) methods (this contrasts with all other abstract
048 * collection classes which require an iterator to be provided). To make the
049 * list modifiable, the set(int, Object) method should also be overridden, and
050 * to make the list resizable, the add(int, Object) and remove(int) methods
051 * should be overridden too. Other methods should be overridden if the
052 * backing data structure allows for a more efficient implementation.
053 * The precise implementation used by AbstractList is documented, so that
054 * subclasses can tell which methods could be implemented more efficiently.
055 * <p>
056 *
057 * As recommended by Collection and List, the subclass should provide at
058 * least a no-argument and a Collection constructor. This class is not
059 * synchronized.
060 *
061 * @author Original author unknown
062 * @author Bryce McKinlay
063 * @author Eric Blake (ebb9@email.byu.edu)
064 * @see Collection
065 * @see List
066 * @see AbstractSequentialList
067 * @see AbstractCollection
068 * @see ListIterator
069 * @since 1.2
070 * @status updated to 1.4
071 */
072public abstract class AbstractList<E>
073  extends AbstractCollection<E>
074  implements List<E>
075{
076  /**
077   * A count of the number of structural modifications that have been made to
078   * the list (that is, insertions and removals). Structural modifications
079   * are ones which change the list size or affect how iterations would
080   * behave. This field is available for use by Iterator and ListIterator,
081   * in order to throw a {@link ConcurrentModificationException} in response
082   * to the next operation on the iterator. This <i>fail-fast</i> behavior
083   * saves the user from many subtle bugs otherwise possible from concurrent
084   * modification during iteration.
085   * <p>
086   *
087   * To make lists fail-fast, increment this field by just 1 in the
088   * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
089   * Otherwise, this field may be ignored.
090   */
091  protected transient int modCount;
092
093  /**
094   * The main constructor, for use by subclasses.
095   */
096  protected AbstractList()
097  {
098  }
099
100  /**
101   * Returns the elements at the specified position in the list.
102   *
103   * @param index the element to return
104   * @return the element at that position
105   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
106   */
107  public abstract E get(int index);
108
109  /**
110   * Insert an element into the list at a given position (optional operation).
111   * This shifts all existing elements from that position to the end one
112   * index to the right.  This version of add has no return, since it is
113   * assumed to always succeed if there is no exception. This implementation
114   * always throws UnsupportedOperationException, and must be overridden to
115   * make a modifiable List.  If you want fail-fast iterators, be sure to
116   * increment modCount when overriding this.
117   *
118   * @param index the location to insert the item
119   * @param o the object to insert
120   * @throws UnsupportedOperationException if this list does not support the
121   *         add operation
122   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
123   * @throws ClassCastException if o cannot be added to this list due to its
124   *         type
125   * @throws IllegalArgumentException if o cannot be added to this list for
126   *         some other reason
127   * @see #modCount
128   */
129  public void add(int index, E o)
130  {
131    throw new UnsupportedOperationException();
132  }
133
134  /**
135   * Add an element to the end of the list (optional operation). If the list
136   * imposes restraints on what can be inserted, such as no null elements,
137   * this should be documented. This implementation calls
138   * <code>add(size(), o);</code>, and will fail if that version does.
139   *
140   * @param o the object to add
141   * @return true, as defined by Collection for a modified list
142   * @throws UnsupportedOperationException if this list does not support the
143   *         add operation
144   * @throws ClassCastException if o cannot be added to this list due to its
145   *         type
146   * @throws IllegalArgumentException if o cannot be added to this list for
147   *         some other reason
148   * @see #add(int, Object)
149   */
150  public boolean add(E o)
151  {
152    add(size(), o);
153    return true;
154  }
155
156  /**
157   * Insert the contents of a collection into the list at a given position
158   * (optional operation). Shift all elements at that position to the right
159   * by the number of elements inserted. This operation is undefined if
160   * this list is modified during the operation (for example, if you try
161   * to insert a list into itself). This implementation uses the iterator of
162   * the collection, repeatedly calling add(int, Object); this will fail
163   * if add does. This can often be made more efficient.
164   *
165   * @param index the location to insert the collection
166   * @param c the collection to insert
167   * @return true if the list was modified by this action, that is, if c is
168   *         non-empty
169   * @throws UnsupportedOperationException if this list does not support the
170   *         addAll operation
171   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
172   * @throws ClassCastException if some element of c cannot be added to this
173   *         list due to its type
174   * @throws IllegalArgumentException if some element of c cannot be added
175   *         to this list for some other reason
176   * @throws NullPointerException if the specified collection is null
177   * @see #add(int, Object)
178   */
179  public boolean addAll(int index, Collection<? extends E> c)
180  {
181    Iterator<? extends E> itr = c.iterator();
182    int size = c.size();
183    for (int pos = size; pos > 0; pos--)
184      add(index++, itr.next());
185    return size > 0;
186  }
187
188  /**
189   * Clear the list, such that a subsequent call to isEmpty() would return
190   * true (optional operation). This implementation calls
191   * <code>removeRange(0, size())</code>, so it will fail unless remove
192   * or removeRange is overridden.
193   *
194   * @throws UnsupportedOperationException if this list does not support the
195   *         clear operation
196   * @see #remove(int)
197   * @see #removeRange(int, int)
198   */
199  public void clear()
200  {
201    removeRange(0, size());
202  }
203
204  /**
205   * Test whether this list is equal to another object. A List is defined to be
206   * equal to an object if and only if that object is also a List, and the two
207   * lists have the same sequence. Two lists l1 and l2 are equal if and only
208   * if <code>l1.size() == l2.size()</code>, and for every integer n between 0
209   * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ?
210   * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
211   * <p>
212   *
213   * This implementation returns true if the object is this, or false if the
214   * object is not a List.  Otherwise, it iterates over both lists (with
215   * iterator()), returning false if two elements compare false or one list
216   * is shorter, and true if the iteration completes successfully.
217   *
218   * @param o the object to test for equality with this list
219   * @return true if o is equal to this list
220   * @see Object#equals(Object)
221   * @see #hashCode()
222   */
223  public boolean equals(Object o)
224  {
225    if (o == this)
226      return true;
227    if (! (o instanceof List))
228      return false;
229    int size = size();
230    if (size != ((List) o).size())
231      return false;
232
233    Iterator<E> itr1 = iterator();
234    Iterator itr2 = ((List) o).iterator();
235
236    while (--size >= 0)
237      if (! equals(itr1.next(), itr2.next()))
238        return false;
239    return true;
240  }
241
242  /**
243   * Obtains a hash code for this list. In order to obey the general
244   * contract of the hashCode method of class Object, this value is
245   * calculated as follows:
246   * 
247<pre>hashCode = 1;
248Iterator i = list.iterator();
249while (i.hasNext())
250{
251  Object obj = i.next();
252  hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
253}</pre>
254   *
255   * This ensures that the general contract of Object.hashCode() is adhered to.
256   *
257   * @return the hash code of this list
258   *
259   * @see Object#hashCode()
260   * @see #equals(Object)
261   */
262  public int hashCode()
263  {
264    int hashCode = 1;
265    Iterator<E> itr = iterator();
266    int pos = size();
267    while (--pos >= 0)
268      hashCode = 31 * hashCode + hashCode(itr.next());
269    return hashCode;
270  }
271
272  /**
273   * Obtain the first index at which a given object is to be found in this
274   * list. This implementation follows a listIterator() until a match is found,
275   * or returns -1 if the list end is reached.
276   *
277   * @param o the object to search for
278   * @return the least integer n such that <code>o == null ? get(n) == null :
279   *         o.equals(get(n))</code>, or -1 if there is no such index
280   */
281  public int indexOf(Object o)
282  {
283    ListIterator<E> itr = listIterator();
284    int size = size();
285    for (int pos = 0; pos < size; pos++)
286      if (equals(o, itr.next()))
287        return pos;
288    return -1;
289  }
290
291  /**
292   * Obtain an Iterator over this list, whose sequence is the list order.
293   * This implementation uses size(), get(int), and remove(int) of the
294   * backing list, and does not support remove unless the list does. This
295   * implementation is fail-fast if you correctly maintain modCount.
296   * Also, this implementation is specified by Sun to be distinct from
297   * listIterator, although you could easily implement it as
298   * <code>return listIterator(0)</code>.
299   *
300   * @return an Iterator over the elements of this list, in order
301   * @see #modCount
302   */
303  public Iterator<E> iterator()
304  {
305    // Bah, Sun's implementation forbids using listIterator(0).
306    return new Iterator<E>()
307    {
308      private int pos = 0;
309      private int size = size();
310      private int last = -1;
311      private int knownMod = modCount;
312
313      // This will get inlined, since it is private.
314      /**
315       * Checks for modifications made to the list from
316       * elsewhere while iteration is in progress.
317       *
318       * @throws ConcurrentModificationException if the
319       *         list has been modified elsewhere.
320       */
321      private void checkMod()
322      {
323        if (knownMod != modCount)
324          throw new ConcurrentModificationException();
325      }
326
327      /**
328       * Tests to see if there are any more objects to
329       * return.
330       *
331       * @return True if the end of the list has not yet been
332       *         reached.
333       */
334      public boolean hasNext()
335      {
336        return pos < size;
337      }
338
339      /**
340       * Retrieves the next object from the list.
341       *
342       * @return The next object.
343       * @throws NoSuchElementException if there are
344       *         no more objects to retrieve.
345       * @throws ConcurrentModificationException if the
346       *         list has been modified elsewhere.
347       */
348      public E next()
349      {
350        checkMod();
351        if (pos == size)
352          throw new NoSuchElementException();
353        last = pos;
354        return get(pos++);
355      }
356
357      /**
358       * Removes the last object retrieved by <code>next()</code>
359       * from the list, if the list supports object removal.
360       *
361       * @throws ConcurrentModificationException if the list
362       *         has been modified elsewhere.
363       * @throws IllegalStateException if the iterator is positioned
364       *         before the start of the list or the last object has already
365       *         been removed.
366       * @throws UnsupportedOperationException if the list does
367       *         not support removing elements.
368       */
369      public void remove()
370      {
371        checkMod();
372        if (last < 0)
373          throw new IllegalStateException();
374        AbstractList.this.remove(last);
375        pos--;
376        size--;
377        last = -1;
378        knownMod = modCount;
379      }
380    };
381  }
382
383  /**
384   * Obtain the last index at which a given object is to be found in this
385   * list. This implementation grabs listIterator(size()), then searches
386   * backwards for a match or returns -1.
387   *
388   * @return the greatest integer n such that <code>o == null ? get(n) == null
389   *         : o.equals(get(n))</code>, or -1 if there is no such index
390   */
391  public int lastIndexOf(Object o)
392  {
393    int pos = size();
394    ListIterator<E> itr = listIterator(pos);
395    while (--pos >= 0)
396      if (equals(o, itr.previous()))
397        return pos;
398    return -1;
399  }
400
401  /**
402   * Obtain a ListIterator over this list, starting at the beginning. This
403   * implementation returns listIterator(0).
404   *
405   * @return a ListIterator over the elements of this list, in order, starting
406   *         at the beginning
407   */
408  public ListIterator<E> listIterator()
409  {
410    return listIterator(0);
411  }
412
413  /**
414   * Obtain a ListIterator over this list, starting at a given position.
415   * A first call to next() would return the same as get(index), and a
416   * first call to previous() would return the same as get(index - 1).
417   * <p>
418   *
419   * This implementation uses size(), get(int), set(int, Object),
420   * add(int, Object), and remove(int) of the backing list, and does not
421   * support remove, set, or add unless the list does. This implementation
422   * is fail-fast if you correctly maintain modCount.
423   *
424   * @param index the position, between 0 and size() inclusive, to begin the
425   *        iteration from
426   * @return a ListIterator over the elements of this list, in order, starting
427   *         at index
428   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
429   * @see #modCount
430   */
431  public ListIterator<E> listIterator(final int index)
432  {
433    if (index < 0 || index > size())
434      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
435                                          + size());
436
437    return new ListIterator<E>()
438    {
439      private int knownMod = modCount;
440      private int position = index;
441      private int lastReturned = -1;
442      private int size = size();
443
444      // This will get inlined, since it is private.
445      /**
446       * Checks for modifications made to the list from
447       * elsewhere while iteration is in progress.
448       *
449       * @throws ConcurrentModificationException if the
450       *         list has been modified elsewhere.
451       */
452      private void checkMod()
453      {
454        if (knownMod != modCount)
455          throw new ConcurrentModificationException();
456      }
457
458      /**
459       * Tests to see if there are any more objects to
460       * return.
461       *
462       * @return True if the end of the list has not yet been
463       *         reached.
464       */
465      public boolean hasNext()
466      {
467        return position < size;
468      }
469
470      /**
471       * Tests to see if there are objects prior to the
472       * current position in the list.
473       *
474       * @return True if objects exist prior to the current
475       *         position of the iterator.
476       */
477      public boolean hasPrevious()
478      {
479        return position > 0;
480      }
481
482      /**
483       * Retrieves the next object from the list.
484       *
485       * @return The next object.
486       * @throws NoSuchElementException if there are no
487       *         more objects to retrieve.
488       * @throws ConcurrentModificationException if the
489       *         list has been modified elsewhere.
490       */
491      public E next()
492      {
493        checkMod();
494        if (position == size)
495          throw new NoSuchElementException();
496        lastReturned = position;
497        return get(position++);
498      }
499
500      /**
501       * Retrieves the previous object from the list.
502       *
503       * @return The next object.
504       * @throws NoSuchElementException if there are no
505       *         previous objects to retrieve.
506       * @throws ConcurrentModificationException if the
507       *         list has been modified elsewhere.
508       */
509      public E previous()
510      {
511        checkMod();
512        if (position == 0)
513          throw new NoSuchElementException();
514        lastReturned = --position;
515        return get(lastReturned);
516      }
517
518      /**
519       * Returns the index of the next element in the
520       * list, which will be retrieved by <code>next()</code>
521       *
522       * @return The index of the next element.
523       */
524      public int nextIndex()
525      {
526        return position;
527      }
528
529      /**
530       * Returns the index of the previous element in the
531       * list, which will be retrieved by <code>previous()</code>
532       *
533       * @return The index of the previous element.
534       */
535      public int previousIndex()
536      {
537        return position - 1;
538      }
539
540     /**
541      * Removes the last object retrieved by <code>next()</code>
542      * or <code>previous()</code> from the list, if the list
543      * supports object removal.
544      *
545      * @throws IllegalStateException if the iterator is positioned
546      *         before the start of the list or the last object has already
547      *         been removed.
548      * @throws UnsupportedOperationException if the list does
549      *         not support removing elements.
550      * @throws ConcurrentModificationException if the list
551      *         has been modified elsewhere.
552      */
553      public void remove()
554      {
555        checkMod();
556        if (lastReturned < 0)
557          throw new IllegalStateException();
558        AbstractList.this.remove(lastReturned);
559        size--;
560        position = lastReturned;
561        lastReturned = -1;
562        knownMod = modCount;
563      }
564
565     /**
566      * Replaces the last object retrieved by <code>next()</code>
567      * or <code>previous</code> with o, if the list supports object
568      * replacement and an add or remove operation has not already
569      * been performed.
570      *
571      * @throws IllegalStateException if the iterator is positioned
572      *         before the start of the list or the last object has already
573      *         been removed.
574      * @throws UnsupportedOperationException if the list doesn't support
575      *         the addition or removal of elements.
576      * @throws ClassCastException if the type of o is not a valid type
577      *         for this list.
578      * @throws IllegalArgumentException if something else related to o
579      *         prevents its addition.
580      * @throws ConcurrentModificationException if the list
581      *         has been modified elsewhere.
582      */
583      public void set(E o)
584      {
585        checkMod();
586        if (lastReturned < 0)
587          throw new IllegalStateException();
588        AbstractList.this.set(lastReturned, o);
589      }
590
591      /**
592       * Adds the supplied object before the element that would be returned
593       * by a call to <code>next()</code>, if the list supports addition.
594       * 
595       * @param o The object to add to the list.
596       * @throws UnsupportedOperationException if the list doesn't support
597       *         the addition of new elements.
598       * @throws ClassCastException if the type of o is not a valid type
599       *         for this list.
600       * @throws IllegalArgumentException if something else related to o
601       *         prevents its addition.
602       * @throws ConcurrentModificationException if the list
603       *         has been modified elsewhere.
604       */
605      public void add(E o)
606      {
607        checkMod();
608        AbstractList.this.add(position++, o);
609        size++;
610        lastReturned = -1;
611        knownMod = modCount;
612      }
613    };
614  }
615
616  /**
617   * Remove the element at a given position in this list (optional operation).
618   * Shifts all remaining elements to the left to fill the gap. This
619   * implementation always throws an UnsupportedOperationException.
620   * If you want fail-fast iterators, be sure to increment modCount when
621   * overriding this.
622   *
623   * @param index the position within the list of the object to remove
624   * @return the object that was removed
625   * @throws UnsupportedOperationException if this list does not support the
626   *         remove operation
627   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
628   * @see #modCount
629   */
630  public E remove(int index)
631  {
632    throw new UnsupportedOperationException();
633  }
634
635  /**
636   * Remove a subsection of the list. This is called by the clear and
637   * removeRange methods of the class which implements subList, which are
638   * difficult for subclasses to override directly. Therefore, this method
639   * should be overridden instead by the more efficient implementation, if one
640   * exists. Overriding this can reduce quadratic efforts to constant time
641   * in some cases!
642   * <p>
643   *
644   * This implementation first checks for illegal or out of range arguments. It
645   * then obtains a ListIterator over the list using listIterator(fromIndex).
646   * It then calls next() and remove() on this iterator repeatedly, toIndex -
647   * fromIndex times.
648   *
649   * @param fromIndex the index, inclusive, to remove from.
650   * @param toIndex the index, exclusive, to remove to.
651   * @throws UnsupportedOperationException if the list does
652   *         not support removing elements.
653   */
654  protected void removeRange(int fromIndex, int toIndex)
655  {
656    ListIterator<E> itr = listIterator(fromIndex);
657    for (int index = fromIndex; index < toIndex; index++)
658      {
659        itr.next();
660        itr.remove();
661      }
662  }
663
664  /**
665   * Replace an element of this list with another object (optional operation).
666   * This implementation always throws an UnsupportedOperationException.
667   *
668   * @param index the position within this list of the element to be replaced
669   * @param o the object to replace it with
670   * @return the object that was replaced
671   * @throws UnsupportedOperationException if this list does not support the
672   *         set operation
673   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
674   * @throws ClassCastException if o cannot be added to this list due to its
675   *         type
676   * @throws IllegalArgumentException if o cannot be added to this list for
677   *         some other reason
678   */
679  public E set(int index, E o)
680  {
681    throw new UnsupportedOperationException();
682  }
683
684  /**
685   * Obtain a List view of a subsection of this list, from fromIndex
686   * (inclusive) to toIndex (exclusive). If the two indices are equal, the
687   * sublist is empty. The returned list should be modifiable if and only
688   * if this list is modifiable. Changes to the returned list should be
689   * reflected in this list. If this list is structurally modified in
690   * any way other than through the returned list, the result of any subsequent
691   * operations on the returned list is undefined.
692   * <p>
693   *
694   * This implementation returns a subclass of AbstractList. It stores, in
695   * private fields, the offset and size of the sublist, and the expected
696   * modCount of the backing list. If the backing list implements RandomAccess,
697   * the sublist will also.
698   * <p>
699   *
700   * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
701   * <code>add(int, Object)</code>, <code>remove(int)</code>,
702   * <code>addAll(int, Collection)</code> and
703   * <code>removeRange(int, int)</code> methods all delegate to the
704   * corresponding methods on the backing abstract list, after
705   * bounds-checking the index and adjusting for the offset. The
706   * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
707   * The <code>listIterator(int)</code> method returns a "wrapper object"
708   * over a list iterator on the backing list, which is created with the
709   * corresponding method on the backing list. The <code>iterator()</code>
710   * method merely returns listIterator(), and the <code>size()</code> method
711   * merely returns the subclass's size field.
712   * <p>
713   *
714   * All methods first check to see if the actual modCount of the backing
715   * list is equal to its expected value, and throw a
716   * ConcurrentModificationException if it is not. 
717   *
718   * @param fromIndex the index that the returned list should start from
719   *        (inclusive)
720   * @param toIndex the index that the returned list should go to (exclusive)
721   * @return a List backed by a subsection of this list
722   * @throws IndexOutOfBoundsException if fromIndex &lt; 0
723   *         || toIndex &gt; size()
724   * @throws IllegalArgumentException if fromIndex &gt; toIndex
725   * @see ConcurrentModificationException
726   * @see RandomAccess
727   */
728  public List<E> subList(int fromIndex, int toIndex)
729  {
730    // This follows the specification of AbstractList, but is inconsistent
731    // with the one in List. Don't you love Sun's inconsistencies?
732    if (fromIndex > toIndex)
733      throw new IllegalArgumentException(fromIndex + " > " + toIndex);
734    if (fromIndex < 0 || toIndex > size())
735      throw new IndexOutOfBoundsException();
736
737    if (this instanceof RandomAccess)
738      return new RandomAccessSubList<E>(this, fromIndex, toIndex);
739    return new SubList<E>(this, fromIndex, toIndex);
740  }
741
742  /**
743   * This class follows the implementation requirements set forth in
744   * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
745   * by using a non-public top-level class in the same package.
746   *
747   * @author Original author unknown
748   * @author Eric Blake (ebb9@email.byu.edu)
749   */
750  private static class SubList<E> extends AbstractList<E>
751  {
752    // Package visible, for use by iterator.
753    /** The original list. */
754    final AbstractList<E> backingList;
755    /** The index of the first element of the sublist. */
756    final int offset;
757    /** The size of the sublist. */
758    int size;
759    
760    /**
761     * Construct the sublist.
762     *
763     * @param backing the list this comes from
764     * @param fromIndex the lower bound, inclusive
765     * @param toIndex the upper bound, exclusive
766     */
767    SubList(AbstractList<E> backing, int fromIndex, int toIndex)
768    {
769      backingList = backing;
770      modCount = backing.modCount;
771      offset = fromIndex;
772      size = toIndex - fromIndex;
773    }
774    
775    /**
776     * This method checks the two modCount fields to ensure that there has
777     * not been a concurrent modification, returning if all is okay.
778     *
779     * @throws ConcurrentModificationException if the backing list has been
780     *         modified externally to this sublist
781     */
782    // This can be inlined. Package visible, for use by iterator.
783    void checkMod()
784    {
785      if (modCount != backingList.modCount)
786        throw new ConcurrentModificationException();
787    }
788    
789    /**
790     * This method checks that a value is between 0 and size (inclusive). If
791     * it is not, an exception is thrown.
792     *
793     * @param index the value to check
794     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
795     */
796    // This will get inlined, since it is private.
797    private void checkBoundsInclusive(int index)
798    {
799      if (index < 0 || index > size)
800        throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
801                                            + size);
802    }
803    
804    /**
805     * This method checks that a value is between 0 (inclusive) and size
806     * (exclusive). If it is not, an exception is thrown.
807     *
808     * @param index the value to check
809     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
810     */
811    // This will get inlined, since it is private.
812    private void checkBoundsExclusive(int index)
813    {
814      if (index < 0 || index >= size)
815        throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
816                                            + size);
817    }
818    
819    /**
820     * Specified by AbstractList.subList to return the private field size.
821     *
822     * @return the sublist size
823     * @throws ConcurrentModificationException if the backing list has been
824     *         modified externally to this sublist
825     */
826    public int size()
827    {
828      checkMod();
829      return size;
830    }
831    
832    /**
833     * Specified by AbstractList.subList to delegate to the backing list.
834     *
835     * @param index the location to modify
836     * @param o the new value
837     * @return the old value
838     * @throws ConcurrentModificationException if the backing list has been
839     *         modified externally to this sublist
840     * @throws UnsupportedOperationException if the backing list does not
841     *         support the set operation
842     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
843     * @throws ClassCastException if o cannot be added to the backing list due
844     *         to its type
845     * @throws IllegalArgumentException if o cannot be added to the backing list
846     *         for some other reason
847     */
848    public E set(int index, E o)
849    {
850      checkMod();
851      checkBoundsExclusive(index);
852      return backingList.set(index + offset, o);
853    }
854    
855    /**
856     * Specified by AbstractList.subList to delegate to the backing list.
857     *
858     * @param index the location to get from
859     * @return the object at that location
860     * @throws ConcurrentModificationException if the backing list has been
861     *         modified externally to this sublist
862     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
863     */
864    public E get(int index)
865    {
866      checkMod();
867      checkBoundsExclusive(index);
868      return backingList.get(index + offset);
869    }
870    
871    /**
872     * Specified by AbstractList.subList to delegate to the backing list.
873     *
874     * @param index the index to insert at
875     * @param o the object to add
876     * @throws ConcurrentModificationException if the backing list has been
877     *         modified externally to this sublist
878     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
879     * @throws UnsupportedOperationException if the backing list does not
880     *         support the add operation.
881     * @throws ClassCastException if o cannot be added to the backing list due
882     *         to its type.
883     * @throws IllegalArgumentException if o cannot be added to the backing
884     *         list for some other reason.
885     */
886    public void add(int index, E o)
887    {
888      checkMod();
889      checkBoundsInclusive(index);
890      backingList.add(index + offset, o);
891      size++;
892      modCount = backingList.modCount;
893    }
894    
895    /**
896     * Specified by AbstractList.subList to delegate to the backing list.
897     *
898     * @param index the index to remove
899     * @return the removed object
900     * @throws ConcurrentModificationException if the backing list has been
901     *         modified externally to this sublist
902     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
903     * @throws UnsupportedOperationException if the backing list does not
904     *         support the remove operation
905     */
906    public E remove(int index)
907    {
908      checkMod();
909      checkBoundsExclusive(index);
910      E o = backingList.remove(index + offset);
911      size--;
912      modCount = backingList.modCount;
913      return o;
914    }
915    
916    /**
917     * Specified by AbstractList.subList to delegate to the backing list.
918     * This does no bounds checking, as it assumes it will only be called
919     * by trusted code like clear() which has already checked the bounds.
920     *
921     * @param fromIndex the lower bound, inclusive
922     * @param toIndex the upper bound, exclusive
923     * @throws ConcurrentModificationException if the backing list has been
924     *         modified externally to this sublist
925     * @throws UnsupportedOperationException if the backing list does
926     *         not support removing elements.
927     */
928    protected void removeRange(int fromIndex, int toIndex)
929    {
930      checkMod();
931      
932      backingList.removeRange(offset + fromIndex, offset + toIndex);
933      size -= toIndex - fromIndex;
934      modCount = backingList.modCount;
935    }
936    
937    /**
938     * Specified by AbstractList.subList to delegate to the backing list.
939     *
940     * @param index the location to insert at
941     * @param c the collection to insert
942     * @return true if this list was modified, in other words, c is non-empty
943     * @throws ConcurrentModificationException if the backing list has been
944     *         modified externally to this sublist
945     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
946     * @throws UnsupportedOperationException if this list does not support the
947     *         addAll operation
948     * @throws ClassCastException if some element of c cannot be added to this
949     *         list due to its type
950     * @throws IllegalArgumentException if some element of c cannot be added
951     *         to this list for some other reason
952     * @throws NullPointerException if the specified collection is null
953     */
954    public boolean addAll(int index, Collection<? extends E> c)
955    {
956      checkMod();
957      checkBoundsInclusive(index);
958      int csize = c.size();
959      boolean result = backingList.addAll(offset + index, c);
960      size += csize;
961      modCount = backingList.modCount;
962      return result;
963    }
964    
965    /**
966     * Specified by AbstractList.subList to return addAll(size, c).
967     *
968     * @param c the collection to insert
969     * @return true if this list was modified, in other words, c is non-empty
970     * @throws ConcurrentModificationException if the backing list has been
971     *         modified externally to this sublist
972     * @throws UnsupportedOperationException if this list does not support the
973     *         addAll operation
974     * @throws ClassCastException if some element of c cannot be added to this
975     *         list due to its type
976     * @throws IllegalArgumentException if some element of c cannot be added
977     *         to this list for some other reason
978     * @throws NullPointerException if the specified collection is null
979     */
980    public boolean addAll(Collection<? extends E> c)
981    {
982      return addAll(size, c);
983    }
984    
985    /**
986     * Specified by AbstractList.subList to return listIterator().
987     *
988     * @return an iterator over the sublist
989     */
990    public Iterator<E> iterator()
991    {
992      return listIterator();
993    }
994    
995    /**
996     * Specified by AbstractList.subList to return a wrapper around the
997     * backing list's iterator.
998     *
999     * @param index the start location of the iterator
1000     * @return a list iterator over the sublist
1001     * @throws ConcurrentModificationException if the backing list has been
1002     *         modified externally to this sublist
1003     * @throws IndexOutOfBoundsException if the value is out of range
1004     */
1005    public ListIterator<E> listIterator(final int index)
1006    {
1007      checkMod();
1008      checkBoundsInclusive(index);
1009      
1010      return new ListIterator<E>()
1011        {
1012          private final ListIterator<E> i
1013            = backingList.listIterator(index + offset);
1014          private int position = index;
1015          
1016          /**
1017           * Tests to see if there are any more objects to
1018           * return.
1019           *
1020           * @return True if the end of the list has not yet been
1021           *         reached.
1022           */
1023          public boolean hasNext()
1024          {
1025              return position < size;
1026          }
1027          
1028          /**
1029           * Tests to see if there are objects prior to the
1030           * current position in the list.
1031           *
1032           * @return True if objects exist prior to the current
1033           *         position of the iterator.
1034           */
1035          public boolean hasPrevious()
1036          {
1037              return position > 0;
1038          }
1039          
1040          /**
1041           * Retrieves the next object from the list.
1042           *
1043           * @return The next object.
1044           * @throws NoSuchElementException if there are no
1045           *         more objects to retrieve.
1046           * @throws ConcurrentModificationException if the
1047           *         list has been modified elsewhere.
1048           */
1049          public E next()
1050          {
1051              if (position == size)
1052                throw new NoSuchElementException();
1053              position++;
1054              return i.next();
1055          }
1056
1057          /**
1058           * Retrieves the previous object from the list.
1059           *
1060           * @return The next object.
1061           * @throws NoSuchElementException if there are no
1062           *         previous objects to retrieve.
1063           * @throws ConcurrentModificationException if the
1064           *         list has been modified elsewhere.
1065           */
1066          public E previous()
1067          {
1068              if (position == 0)
1069                throw new NoSuchElementException();
1070              position--;
1071              return i.previous();
1072          }
1073          
1074          /**
1075           * Returns the index of the next element in the
1076           * list, which will be retrieved by <code>next()</code>
1077           *
1078           * @return The index of the next element.
1079           */
1080          public int nextIndex()
1081          {
1082              return i.nextIndex() - offset;
1083          }
1084          
1085          /**
1086           * Returns the index of the previous element in the
1087           * list, which will be retrieved by <code>previous()</code>
1088           *
1089           * @return The index of the previous element.
1090           */
1091          public int previousIndex()
1092          {
1093              return i.previousIndex() - offset;
1094          }
1095          
1096          /**
1097           * Removes the last object retrieved by <code>next()</code>
1098           * from the list, if the list supports object removal.
1099           *
1100           * @throws IllegalStateException if the iterator is positioned
1101           *         before the start of the list or the last object has already
1102           *         been removed.
1103           * @throws UnsupportedOperationException if the list does
1104           *         not support removing elements.
1105           */
1106          public void remove()
1107          {
1108              i.remove();
1109              size--;
1110              position = nextIndex();
1111              modCount = backingList.modCount;
1112          }
1113          
1114          
1115          /**
1116           * Replaces the last object retrieved by <code>next()</code>
1117           * or <code>previous</code> with o, if the list supports object
1118           * replacement and an add or remove operation has not already
1119           * been performed.
1120           *
1121           * @throws IllegalStateException if the iterator is positioned
1122           *         before the start of the list or the last object has already
1123           *         been removed.
1124           * @throws UnsupportedOperationException if the list doesn't support
1125           *         the addition or removal of elements.
1126           * @throws ClassCastException if the type of o is not a valid type
1127           *         for this list.
1128           * @throws IllegalArgumentException if something else related to o
1129           *         prevents its addition.
1130           * @throws ConcurrentModificationException if the list
1131           *         has been modified elsewhere.
1132           */
1133          public void set(E o)
1134          {
1135              i.set(o);
1136          }
1137          
1138          /**
1139           * Adds the supplied object before the element that would be returned
1140           * by a call to <code>next()</code>, if the list supports addition.
1141           * 
1142           * @param o The object to add to the list.
1143           * @throws UnsupportedOperationException if the list doesn't support
1144           *         the addition of new elements.
1145           * @throws ClassCastException if the type of o is not a valid type
1146           *         for this list.
1147           * @throws IllegalArgumentException if something else related to o
1148           *         prevents its addition.
1149           * @throws ConcurrentModificationException if the list
1150           *         has been modified elsewhere.
1151           */
1152          public void add(E o)
1153          {
1154              i.add(o);
1155              size++;
1156              position++;
1157              modCount = backingList.modCount;
1158          }
1159          
1160          // Here is the reason why the various modCount fields are mostly
1161          // ignored in this wrapper listIterator.
1162          // If the backing listIterator is failfast, then the following holds:
1163          //   Using any other method on this list will call a corresponding
1164          //   method on the backing list *after* the backing listIterator
1165          //   is created, which will in turn cause a ConcurrentModException
1166          //   when this listIterator comes to use the backing one. So it is
1167          //   implicitly failfast.
1168          // If the backing listIterator is NOT failfast, then the whole of
1169          //   this list isn't failfast, because the modCount field of the
1170          //   backing list is not valid. It would still be *possible* to
1171          //   make the iterator failfast wrt modifications of the sublist
1172          //   only, but somewhat pointless when the list can be changed under
1173          //   us.
1174          // Either way, no explicit handling of modCount is needed.
1175          // However modCount = backingList.modCount must be executed in add
1176          // and remove, and size must also be updated in these two methods,
1177          // since they do not go through the corresponding methods of the subList.
1178        };
1179    }
1180  } // class SubList
1181
1182  /**
1183   * This class is a RandomAccess version of SubList, as required by
1184   * {@link AbstractList#subList(int, int)}.
1185   *
1186   * @author Eric Blake (ebb9@email.byu.edu)
1187   */
1188  private static final class RandomAccessSubList<E> extends SubList<E>
1189    implements RandomAccess
1190  {
1191    /**
1192     * Construct the sublist.
1193     *
1194     * @param backing the list this comes from
1195     * @param fromIndex the lower bound, inclusive
1196     * @param toIndex the upper bound, exclusive
1197     */
1198    RandomAccessSubList(AbstractList<E> backing, int fromIndex, int toIndex)
1199    {
1200      super(backing, fromIndex, toIndex);
1201    }
1202  } // class RandomAccessSubList
1203  
1204} // class AbstractList