libjava/classpath/java/util/AbstractList.java

   1 /* AbstractList.java -- Abstract implementation of most of List
   2    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GNU Classpath.
   6
   7 GNU Classpath is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU Classpath is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Classpath; see the file COPYING.  If not, write to the
  19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301 USA.
  21
  22 Linking this library statically or dynamically with other modules is
  23 making a combined work based on this library.  Thus, the terms and
  24 conditions of the GNU General Public License cover the whole
  25 combination.
  26
  27 As a special exception, the copyright holders of this library give you
  28 permission to link this library with independent modules to produce an
  29 executable, regardless of the license terms of these independent
  30 modules, and to copy and distribute the resulting executable under
  31 terms of your choice, provided that you also meet, for each linked
  32 independent module, the terms and conditions of the license of that
  33 module.  An independent module is a module which is not derived from
  34 or based on this library.  If you modify this library, you may extend
  35 this exception to your version of the library, but you are not
  36 obligated to do so.  If you do not wish to do so, delete this
  37 exception statement from your version. */
  38
  39
  40 package java.util;
  41
  42 /**
  43  * A basic implementation of most of the methods in the List interface to make
  44  * it easier to create a List based on a random-access data structure. If
  45  * the list is sequential (such as a linked list), use AbstractSequentialList.
  46  * To create an unmodifiable list, it is only necessary to override the
  47  * size() and get(int) methods (this contrasts with all other abstract
  48  * collection classes which require an iterator to be provided). To make the
  49  * list modifiable, the set(int, Object) method should also be overridden, and
  50  * to make the list resizable, the add(int, Object) and remove(int) methods
  51  * should be overridden too. Other methods should be overridden if the
  52  * backing data structure allows for a more efficient implementation.
  53  * The precise implementation used by AbstractList is documented, so that
  54  * subclasses can tell which methods could be implemented more efficiently.
  55  * <p>
  56  *
  57  * As recommended by Collection and List, the subclass should provide at
  58  * least a no-argument and a Collection constructor. This class is not
  59  * synchronized.
  60  *
  61  * @author Original author unknown
  62  * @author Bryce McKinlay
  63  * @author Eric Blake (ebb9@email.byu.edu)
  64  * @see Collection
  65  * @see List
  66  * @see AbstractSequentialList
  67  * @see AbstractCollection
  68  * @see ListIterator
  69  * @since 1.2
  70  * @status updated to 1.4
  71  */
  72 public abstract class AbstractList<E>
  73   extends AbstractCollection<E>
  74   implements List<E>
  75 {
  76   /**
  77    * A count of the number of structural modifications that have been made to
  78    * the list (that is, insertions and removals). Structural modifications
  79    * are ones which change the list size or affect how iterations would
  80    * behave. This field is available for use by Iterator and ListIterator,
  81    * in order to throw a {@link ConcurrentModificationException} in response
  82    * to the next operation on the iterator. This <i>fail-fast</i> behavior
  83    * saves the user from many subtle bugs otherwise possible from concurrent
  84    * modification during iteration.
  85    * <p>
  86    *
  87    * To make lists fail-fast, increment this field by just 1 in the
  88    * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
  89    * Otherwise, this field may be ignored.
  90    */
  91   protected transient int modCount;
  92
  93   /**
  94    * The main constructor, for use by subclasses.
  95    */
  96   protected AbstractList()
  97   {
  98   }
  99
 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;
 248 Iterator i = list.iterator();
 249 while (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