Robust/src/ClassLibrary/MGC/gnu/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 Object/*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, Object/*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(Object/*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 Object/*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 Object/*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 Object/*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(Object/*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(Object/*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 Object/*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 Object/*E*/ set(int index, Object/*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       throw new UnsupportedOperationException();
 741   }
 742
 743   /**
 744    * This class follows the implementation requirements set forth in
 745    * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
 746    * by using a non-public top-level class in the same package.
 747    *
 748    * @author Original author unknown
 749    * @author Eric Blake (ebb9@email.byu.edu)
 750    */
 751 //  private static class SubList/*<E>*/ extends AbstractList/*<E>*/
 752 //  {
 753 //    // Package visible, for use by iterator.
 754 //    /** The original list. */
 755 //    final AbstractList/*<E>*/ backingList;
 756 //    /** The index of the first element of the sublist. */
 757 //    final int offset;
 758 //    /** The size of the sublist. */
 759 //    int size;
 760 //
 761 //    /**
 762 //     * Construct the sublist.
 763 //     *
 764 //     * @param backing the list this comes from
 765 //     * @param fromIndex the lower bound, inclusive
 766 //     * @param toIndex the upper bound, exclusive
 767 //     */
 768 //    SubList(AbstractList/*<E>*/ backing, int fromIndex, int toIndex)
 769 //    {
 770 //      backingList = backing;
 771 //      modCount = backing.modCount;
 772 //      offset = fromIndex;
 773 //      size = toIndex - fromIndex;
 774 //    }
 775 //
 776 //    /**
 777 //     * This method checks the two modCount fields to ensure that there has
 778 //     * not been a concurrent modification, returning if all is okay.
 779 //     *
 780 //     * @throws ConcurrentModificationException if the backing list has been
 781 //     *         modified externally to this sublist
 782 //     */
 783 //    // This can be inlined. Package visible, for use by iterator.
 784 //    void checkMod()
 785 //    {
 786 //      if (modCount != backingList.modCount)
 787 //      throw new ConcurrentModificationException();
 788 //    }
 789 //
 790 //    /**
 791 //     * This method checks that a value is between 0 and size (inclusive). If
 792 //     * it is not, an exception is thrown.
 793 //     *
 794 //     * @param index the value to check
 795 //     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 796 //     */
 797 //    // This will get inlined, since it is private.
 798 //    private void checkBoundsInclusive(int index)
 799 //    {
 800 //      if (index < 0 || index > size)
 801 //      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 802 //                                          + size);
 803 //    }
 804 //
 805 //    /**
 806 //     * This method checks that a value is between 0 (inclusive) and size
 807 //     * (exclusive). If it is not, an exception is thrown.
 808 //     *
 809 //     * @param index the value to check
 810 //     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 811 //     */
 812 //    // This will get inlined, since it is private.
 813 //    private void checkBoundsExclusive(int index)
 814 //    {
 815 //      if (index < 0 || index >= size)
 816 //      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 817 //                                          + size);
 818 //    }
 819 //
 820 //    /**
 821 //     * Specified by AbstractList.subList to return the private field size.
 822 //     *
 823 //     * @return the sublist size
 824 //     * @throws ConcurrentModificationException if the backing list has been
 825 //     *         modified externally to this sublist
 826 //     */
 827 //    public int size()
 828 //    {
 829 //      checkMod();
 830 //      return size;
 831 //    }
 832 //
 833 //    /**
 834 //     * Specified by AbstractList.subList to delegate to the backing list.
 835 //     *
 836 //     * @param index the location to modify
 837 //     * @param o the new value
 838 //     * @return the old value
 839 //     * @throws ConcurrentModificationException if the backing list has been
 840 //     *         modified externally to this sublist
 841 //     * @throws UnsupportedOperationException if the backing list does not
 842 //     *         support the set operation
 843 //     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 844 //     * @throws ClassCastException if o cannot be added to the backing list due
 845 //     *         to its type
 846 //     * @throws IllegalArgumentException if o cannot be added to the backing list
 847 //     *         for some other reason
 848 //     */
 849 //    public Object/*E*/ set(int index, Object/*E*/ o)
 850 //    {
 851 //      checkMod();
 852 //      checkBoundsExclusive(index);
 853 //      return backingList.set(index + offset, o);
 854 //    }
 855 //
 856 //    /**
 857 //     * Specified by AbstractList.subList to delegate to the backing list.
 858 //     *
 859 //     * @param index the location to get from
 860 //     * @return the object at that location
 861 //     * @throws ConcurrentModificationException if the backing list has been
 862 //     *         modified externally to this sublist
 863 //     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 864 //     */
 865 //    public Object/*E*/ get(int index)
 866 //    {
 867 //      checkMod();
 868 //      checkBoundsExclusive(index);
 869 //      return backingList.get(index + offset);
 870 //    }
 871 //
 872 //    /**
 873 //     * Specified by AbstractList.subList to delegate to the backing list.
 874 //     *
 875 //     * @param index the index to insert at
 876 //     * @param o the object to add
 877 //     * @throws ConcurrentModificationException if the backing list has been
 878 //     *         modified externally to this sublist
 879 //     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 880 //     * @throws UnsupportedOperationException if the backing list does not
 881 //     *         support the add operation.
 882 //     * @throws ClassCastException if o cannot be added to the backing list due
 883 //     *         to its type.
 884 //     * @throws IllegalArgumentException if o cannot be added to the backing
 885 //     *         list for some other reason.
 886 //     */
 887 //    public void add(int index, Object/*E*/ o)
 888 //    {
 889 //      checkMod();
 890 //      checkBoundsInclusive(index);
 891 //      backingList.add(index + offset, o);
 892 //      size++;
 893 //      modCount = backingList.modCount;
 894 //    }
 895 //
 896 //    /**
 897 //     * Specified by AbstractList.subList to delegate to the backing list.
 898 //     *
 899 //     * @param index the index to remove
 900 //     * @return the removed object
 901 //     * @throws ConcurrentModificationException if the backing list has been
 902 //     *         modified externally to this sublist
 903 //     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 904 //     * @throws UnsupportedOperationException if the backing list does not
 905 //     *         support the remove operation
 906 //     */
 907 //    public Object/*E*/ remove(int index)
 908 //    {
 909 //      checkMod();
 910 //      checkBoundsExclusive(index);
 911 //      Object/*E*/ o = backingList.remove(index + offset);
 912 //      size--;
 913 //      modCount = backingList.modCount;
 914 //      return o;
 915 //    }
 916 //
 917 //    /**
 918 //     * Specified by AbstractList.subList to delegate to the backing list.
 919 //     * This does no bounds checking, as it assumes it will only be called
 920 //     * by trusted code like clear() which has already checked the bounds.
 921 //     *
 922 //     * @param fromIndex the lower bound, inclusive
 923 //     * @param toIndex the upper bound, exclusive
 924 //     * @throws ConcurrentModificationException if the backing list has been
 925 //     *         modified externally to this sublist
 926 //     * @throws UnsupportedOperationException if the backing list does
 927 //     *         not support removing elements.
 928 //     */
 929 //    protected void removeRange(int fromIndex, int toIndex)
 930 //    {
 931 //      checkMod();
 932 //
 933 //      backingList.removeRange(offset + fromIndex, offset + toIndex);
 934 //      size -= toIndex - fromIndex;
 935 //      modCount = backingList.modCount;
 936 //    }
 937 //
 938 //    /**
 939 //     * Specified by AbstractList.subList to delegate to the backing list.
 940 //     *
 941 //     * @param index the location to insert at
 942 //     * @param c the collection to insert
 943 //     * @return true if this list was modified, in other words, c is non-empty
 944 //     * @throws ConcurrentModificationException if the backing list has been
 945 //     *         modified externally to this sublist
 946 //     * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 947 //     * @throws UnsupportedOperationException if this list does not support the
 948 //     *         addAll operation
 949 //     * @throws ClassCastException if some element of c cannot be added to this
 950 //     *         list due to its type
 951 //     * @throws IllegalArgumentException if some element of c cannot be added
 952 //     *         to this list for some other reason
 953 //     * @throws NullPointerException if the specified collection is null
 954 //     */
 955 //    public boolean addAll(int index, Collection/*<? extends E>*/ c)
 956 //    {
 957 //      checkMod();
 958 //      checkBoundsInclusive(index);
 959 //      int csize = c.size();
 960 //      boolean result = backingList.addAll(offset + index, c);
 961 //      size += csize;
 962 //      modCount = backingList.modCount;
 963 //      return result;
 964 //    }
 965 //
 966 //    /**
 967 //     * Specified by AbstractList.subList to return addAll(size, c).
 968 //     *
 969 //     * @param c the collection to insert
 970 //     * @return true if this list was modified, in other words, c is non-empty
 971 //     * @throws ConcurrentModificationException if the backing list has been
 972 //     *         modified externally to this sublist
 973 //     * @throws UnsupportedOperationException if this list does not support the
 974 //     *         addAll operation
 975 //     * @throws ClassCastException if some element of c cannot be added to this
 976 //     *         list due to its type
 977 //     * @throws IllegalArgumentException if some element of c cannot be added
 978 //     *         to this list for some other reason
 979 //     * @throws NullPointerException if the specified collection is null
 980 //     */
 981 //    public boolean addAll(Collection/*<? extends E>*/ c)
 982 //    {
 983 //      return addAll(size, c);
 984 //    }
 985 //
 986 //    /**
 987 //     * Specified by AbstractList.subList to return listIterator().
 988 //     *
 989 //     * @return an iterator over the sublist
 990 //     */
 991 //    public Iterator/*<E>*/ iterator()
 992 //    {
 993 //      return listIterator();
 994 //    }
 995 //
 996 //    /**
 997 //     * Specified by AbstractList.subList to return a wrapper around the
 998 //     * backing list's iterator.
 999 //     *
1000 //     * @param index the start location of the iterator
1001 //     * @return a list iterator over the sublist
1002 //     * @throws ConcurrentModificationException if the backing list has been
1003 //     *         modified externally to this sublist
1004 //     * @throws IndexOutOfBoundsException if the value is out of range
1005 //     */
1006 //    public ListIterator/*<E>*/ listIterator(final int index)
1007 //    {
1008 //      checkMod();
1009 //      checkBoundsInclusive(index);
1010 //
1011 //      return new ListIterator/*<E>*/()
1012 //      {
1013 //        private final ListIterator/*<E>*/ i
1014 //          = backingList.listIterator(index + offset);
1015 //        private int position = index;
1016 //
1017 //        /**
1018 //         * Tests to see if there are any more objects to
1019 //         * return.
1020 //         *
1021 //         * @return True if the end of the list has not yet been
1022 //         *         reached.
1023 //         */
1024 //        public boolean hasNext()
1025 //        {
1026 //            return position < size;
1027 //        }
1028 //
1029 //        /**
1030 //         * Tests to see if there are objects prior to the
1031 //         * current position in the list.
1032 //         *
1033 //         * @return True if objects exist prior to the current
1034 //         *         position of the iterator.
1035 //         */
1036 //        public boolean hasPrevious()
1037 //        {
1038 //            return position > 0;
1039 //        }
1040 //
1041 //        /**
1042 //         * Retrieves the next object from the list.
1043 //         *
1044 //         * @return The next object.
1045 //         * @throws NoSuchElementException if there are no
1046 //         *         more objects to retrieve.
1047 //         * @throws ConcurrentModificationException if the
1048 //         *         list has been modified elsewhere.
1049 //         */
1050 //        public Object/*E*/ next()
1051 //        {
1052 //            if (position == size)
1053 //              throw new NoSuchElementException();
1054 //            position++;
1055 //            return i.next();
1056 //        }
1057 //
1058 //        /**
1059 //         * Retrieves the previous object from the list.
1060 //         *
1061 //         * @return The next object.
1062 //         * @throws NoSuchElementException if there are no
1063 //         *         previous objects to retrieve.
1064 //         * @throws ConcurrentModificationException if the
1065 //         *         list has been modified elsewhere.
1066 //         */
1067 //        public Object/*E*/ previous()
1068 //        {
1069 //            if (position == 0)
1070 //              throw new NoSuchElementException();
1071 //            position--;
1072 //            return i.previous();
1073 //        }
1074 //
1075 //        /**
1076 //         * Returns the index of the next element in the
1077 //         * list, which will be retrieved by <code>next()</code>
1078 //         *
1079 //         * @return The index of the next element.
1080 //         */
1081 //        public int nextIndex()
1082 //        {
1083 //            return i.nextIndex() - offset;
1084 //        }
1085 //
1086 //        /**
1087 //         * Returns the index of the previous element in the
1088 //         * list, which will be retrieved by <code>previous()</code>
1089 //         *
1090 //         * @return The index of the previous element.
1091 //         */
1092 //        public int previousIndex()
1093 //        {
1094 //            return i.previousIndex() - offset;
1095 //        }
1096 //
1097 //        /**
1098 //         * Removes the last object retrieved by <code>next()</code>
1099 //         * from the list, if the list supports object removal.
1100 //         *
1101 //         * @throws IllegalStateException if the iterator is positioned
1102 //         *         before the start of the list or the last object has already
1103 //         *         been removed.
1104 //         * @throws UnsupportedOperationException if the list does
1105 //         *         not support removing elements.
1106 //         */
1107 //        public void remove()
1108 //        {
1109 //            i.remove();
1110 //            size--;
1111 //            position = nextIndex();
1112 //            modCount = backingList.modCount;
1113 //        }
1114 //
1115 //
1116 //        /**
1117 //         * Replaces the last object retrieved by <code>next()</code>
1118 //         * or <code>previous</code> with o, if the list supports object
1119 //         * replacement and an add or remove operation has not already
1120 //         * been performed.
1121 //         *
1122 //         * @throws IllegalStateException if the iterator is positioned
1123 //         *         before the start of the list or the last object has already
1124 //         *         been removed.
1125 //         * @throws UnsupportedOperationException if the list doesn't support
1126 //         *         the addition or removal of elements.
1127 //         * @throws ClassCastException if the type of o is not a valid type
1128 //         *         for this list.
1129 //         * @throws IllegalArgumentException if something else related to o
1130 //         *         prevents its addition.
1131 //         * @throws ConcurrentModificationException if the list
1132 //         *         has been modified elsewhere.
1133 //         */
1134 //        public void set(Object/*E*/ o)
1135 //        {
1136 //            i.set(o);
1137 //        }
1138 //
1139 //        /**
1140 //         * Adds the supplied object before the element that would be returned
1141 //         * by a call to <code>next()</code>, if the list supports addition.
1142 //         *
1143 //         * @param o The object to add to the list.
1144 //         * @throws UnsupportedOperationException if the list doesn't support
1145 //         *         the addition of new elements.
1146 //         * @throws ClassCastException if the type of o is not a valid type
1147 //         *         for this list.
1148 //         * @throws IllegalArgumentException if something else related to o
1149 //         *         prevents its addition.
1150 //         * @throws ConcurrentModificationException if the list
1151 //         *         has been modified elsewhere.
1152 //         */
1153 //        public void add(Object/*E*/ o)
1154 //        {
1155 //            i.add(o);
1156 //            size++;
1157 //            position++;
1158 //            modCount = backingList.modCount;
1159 //        }
1160 //
1161 //        // Here is the reason why the various modCount fields are mostly
1162 //        // ignored in this wrapper listIterator.
1163 //        // If the backing listIterator is failfast, then the following holds:
1164 //        //   Using any other method on this list will call a corresponding
1165 //        //   method on the backing list *after* the backing listIterator
1166 //        //   is created, which will in turn cause a ConcurrentModException
1167 //        //   when this listIterator comes to use the backing one. So it is
1168 //        //   implicitly failfast.
1169 //        // If the backing listIterator is NOT failfast, then the whole of
1170 //        //   this list isn't failfast, because the modCount field of the
1171 //        //   backing list is not valid. It would still be *possible* to
1172 //        //   make the iterator failfast wrt modifications of the sublist
1173 //        //   only, but somewhat pointless when the list can be changed under
1174 //        //   us.
1175 //        // Either way, no explicit handling of modCount is needed.
1176 //        // However modCount = backingList.modCount must be executed in add
1177 //        // and remove, and size must also be updated in these two methods,
1178 //        // since they do not go through the corresponding methods of the subList.
1179 //      };
1180 //    }
1181 //  } // class SubList
1182
1183   /**
1184    * This class is a RandomAccess version of SubList, as required by
1185    * {@link AbstractList#subList(int, int)}.
1186    *
1187    * @author Eric Blake (ebb9@email.byu.edu)
1188    */
1189 //  private static final class RandomAccessSubList<E> extends SubList<E>
1190 //    implements RandomAccess
1191 //  {
1192 //    /**
1193 //     * Construct the sublist.
1194 //     *
1195 //     * @param backing the list this comes from
1196 //     * @param fromIndex the lower bound, inclusive
1197 //     * @param toIndex the upper bound, exclusive
1198 //     */
1199 //    RandomAccessSubList(AbstractList<E> backing, int fromIndex, int toIndex)
1200 //    {
1201 //      super(backing, fromIndex, toIndex);
1202 //    }
1203 //  } // class RandomAccessSubList
1204
1205 } // class AbstractList