libjava/java/util/AbstractList.java

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