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 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       private void checkMod()
 312       {
 313         if (knownMod != modCount)
 314           throw new ConcurrentModificationException();
 315       }
 316
 317       public boolean hasNext()
 318       {
 319         checkMod();
 320         return pos < size;
 321       }
 322
 323       public Object next()
 324       {
 325         checkMod();
 326         if (pos == size)
 327           throw new NoSuchElementException();
 328         last = pos;
 329         return get(pos++);
 330       }
 331
 332       public void remove()
 333       {
 334         checkMod();
 335         if (last < 0)
 336           throw new IllegalStateException();
 337         AbstractList.this.remove(last);
 338         pos--;
 339         size--;
 340         last = -1;
 341         knownMod = modCount;
 342       }
 343     };
 344   }
 345
 346   /**
 347    * Obtain the last index at which a given object is to be found in this
 348    * list. This implementation grabs listIterator(size()), then searches
 349    * backwards for a match or returns -1.
 350    *
 351    * @return the greatest integer n such that <code>o == null ? get(n) == null
 352    *         : o.equals(get(n))</code>, or -1 if there is no such index
 353    */
 354   public int lastIndexOf(Object o)
 355   {
 356     int pos = size();
 357     ListIterator itr = listIterator(pos);
 358     while (--pos >= 0)
 359       if (equals(o, itr.previous()))
 360         return pos;
 361     return -1;
 362   }
 363
 364   /**
 365    * Obtain a ListIterator over this list, starting at the beginning. This
 366    * implementation returns listIterator(0).
 367    *
 368    * @return a ListIterator over the elements of this list, in order, starting
 369    *         at the beginning
 370    */
 371   public ListIterator listIterator()
 372   {
 373     return listIterator(0);
 374   }
 375
 376   /**
 377    * Obtain a ListIterator over this list, starting at a given position.
 378    * A first call to next() would return the same as get(index), and a
 379    * first call to previous() would return the same as get(index - 1).
 380    * <p>
 381    *
 382    * This implementation uses size(), get(int), set(int, Object),
 383    * add(int, Object), and remove(int) of the backing list, and does not
 384    * support remove, set, or add unless the list does. This implementation
 385    * is fail-fast if you correctly maintain modCount.
 386    *
 387    * @param index the position, between 0 and size() inclusive, to begin the
 388    *        iteration from
 389    * @return a ListIterator over the elements of this list, in order, starting
 390    *         at index
 391    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 392    * @see #modCount
 393    */
 394   public ListIterator listIterator(final int index)
 395   {
 396     if (index < 0 || index > size())
 397       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 398                                           + size());
 399
 400     return new ListIterator()
 401     {
 402       private int knownMod = modCount;
 403       private int position = index;
 404       private int lastReturned = -1;
 405       private int size = size();
 406
 407       // This will get inlined, since it is private.
 408       private void checkMod()
 409       {
 410         if (knownMod != modCount)
 411           throw new ConcurrentModificationException();
 412       }
 413
 414       public boolean hasNext()
 415       {
 416         checkMod();
 417         return position < size;
 418       }
 419
 420       public boolean hasPrevious()
 421       {
 422         checkMod();
 423         return position > 0;
 424       }
 425
 426       public Object next()
 427       {
 428         checkMod();
 429         if (position == size)
 430           throw new NoSuchElementException();
 431         lastReturned = position;
 432         return get(position++);
 433       }
 434
 435       public Object previous()
 436       {
 437         checkMod();
 438         if (position == 0)
 439           throw new NoSuchElementException();
 440         lastReturned = --position;
 441         return get(lastReturned);
 442       }
 443
 444       public int nextIndex()
 445       {
 446         checkMod();
 447         return position;
 448       }
 449
 450       public int previousIndex()
 451       {
 452         checkMod();
 453         return position - 1;
 454       }
 455
 456       public void remove()
 457       {
 458         checkMod();
 459         if (lastReturned < 0)
 460           throw new IllegalStateException();
 461         AbstractList.this.remove(lastReturned);
 462         size--;
 463         position = lastReturned;
 464         lastReturned = -1;
 465         knownMod = modCount;
 466       }
 467
 468       public void set(Object o)
 469       {
 470         checkMod();
 471         if (lastReturned < 0)
 472           throw new IllegalStateException();
 473         AbstractList.this.set(lastReturned, o);
 474       }
 475
 476       public void add(Object o)
 477       {
 478         checkMod();
 479         AbstractList.this.add(position++, o);
 480         size++;
 481         lastReturned = -1;
 482         knownMod = modCount;
 483       }
 484     };
 485   }
 486
 487   /**
 488    * Remove the element at a given position in this list (optional operation).
 489    * Shifts all remaining elements to the left to fill the gap. This
 490    * implementation always throws an UnsupportedOperationException.
 491    * If you want fail-fast iterators, be sure to increment modCount when
 492    * overriding this.
 493    *
 494    * @param index the position within the list of the object to remove
 495    * @return the object that was removed
 496    * @throws UnsupportedOperationException if this list does not support the
 497    *         remove operation
 498    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 499    * @see #modCount
 500    */
 501   public Object remove(int index)
 502   {
 503     throw new UnsupportedOperationException();
 504   }
 505
 506   /**
 507    * Remove a subsection of the list. This is called by the clear and
 508    * removeRange methods of the class which implements subList, which are
 509    * difficult for subclasses to override directly. Therefore, this method
 510    * should be overridden instead by the more efficient implementation, if one
 511    * exists. Overriding this can reduce quadratic efforts to constant time
 512    * in some cases!
 513    * <p>
 514    *
 515    * This implementation first checks for illegal or out of range arguments. It
 516    * then obtains a ListIterator over the list using listIterator(fromIndex).
 517    * It then calls next() and remove() on this iterator repeatedly, toIndex -
 518    * fromIndex times.
 519    *
 520    * @param fromIndex the index, inclusive, to remove from.
 521    * @param toIndex the index, exclusive, to remove to.
 522    */
 523   protected void removeRange(int fromIndex, int toIndex)
 524   {
 525     ListIterator itr = listIterator(fromIndex);
 526     for (int index = fromIndex; index < toIndex; index++)
 527       {
 528         itr.next();
 529         itr.remove();
 530       }
 531   }
 532
 533   /**
 534    * Replace an element of this list with another object (optional operation).
 535    * This implementation always throws an UnsupportedOperationException.
 536    *
 537    * @param index the position within this list of the element to be replaced
 538    * @param o the object to replace it with
 539    * @return the object that was replaced
 540    * @throws UnsupportedOperationException if this list does not support the
 541    *         set operation
 542    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 543    * @throws ClassCastException if o cannot be added to this list due to its
 544    *         type
 545    * @throws IllegalArgumentException if o cannot be added to this list for
 546    *         some other reason
 547    */
 548   public Object set(int index, Object o)
 549   {
 550     throw new UnsupportedOperationException();
 551   }
 552
 553   /**
 554    * Obtain a List view of a subsection of this list, from fromIndex
 555    * (inclusive) to toIndex (exclusive). If the two indices are equal, the
 556    * sublist is empty. The returned list should be modifiable if and only
 557    * if this list is modifiable. Changes to the returned list should be
 558    * reflected in this list. If this list is structurally modified in
 559    * any way other than through the returned list, the result of any subsequent
 560    * operations on the returned list is undefined.
 561    * <p>
 562    *
 563    * This implementation returns a subclass of AbstractList. It stores, in
 564    * private fields, the offset and size of the sublist, and the expected
 565    * modCount of the backing list. If the backing list implements RandomAccess,
 566    * the sublist will also.
 567    * <p>
 568    *
 569    * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
 570    * <code>add(int, Object)</code>, <code>remove(int)</code>,
 571    * <code>addAll(int, Collection)</code> and
 572    * <code>removeRange(int, int)</code> methods all delegate to the
 573    * corresponding methods on the backing abstract list, after
 574    * bounds-checking the index and adjusting for the offset. The
 575    * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
 576    * The <code>listIterator(int)</code> method returns a "wrapper object"
 577    * over a list iterator on the backing list, which is created with the
 578    * corresponding method on the backing list. The <code>iterator()</code>
 579    * method merely returns listIterator(), and the <code>size()</code> method
 580    * merely returns the subclass's size field.
 581    * <p>
 582    *
 583    * All methods first check to see if the actual modCount of the backing
 584    * list is equal to its expected value, and throw a
 585    * ConcurrentModificationException if it is not.
 586    *
 587    * @param fromIndex the index that the returned list should start from
 588    *        (inclusive)
 589    * @param toIndex the index that the returned list should go to (exclusive)
 590    * @return a List backed by a subsection of this list
 591    * @throws IndexOutOfBoundsException if fromIndex &lt; 0
 592    *         || toIndex &gt; size()
 593    * @throws IllegalArgumentException if fromIndex &gt; toIndex
 594    * @see ConcurrentModificationException
 595    * @see RandomAccess
 596    */
 597   public List subList(int fromIndex, int toIndex)
 598   {
 599     // This follows the specification of AbstractList, but is inconsistent
 600     // with the one in List. Don't you love Sun's inconsistencies?
 601     if (fromIndex > toIndex)
 602       throw new IllegalArgumentException(fromIndex + " > " + toIndex);
 603     if (fromIndex < 0 || toIndex > size())
 604       throw new IndexOutOfBoundsException();
 605
 606     if (this instanceof RandomAccess)
 607       return new RandomAccessSubList(this, fromIndex, toIndex);
 608     return new SubList(this, fromIndex, toIndex);
 609   }
 610
 611 } // class AbstractList
 612
 613
 614 /**
 615  * This class follows the implementation requirements set forth in
 616  * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
 617  * by using a non-public top-level class in the same package.
 618  *
 619  * @author Original author unknown
 620  * @author Eric Blake <ebb9@email.byu.edu>
 621  */
 622 class SubList extends AbstractList
 623 {
 624   // Package visible, for use by iterator.
 625   /** The original list. */
 626   final AbstractList backingList;
 627   /** The index of the first element of the sublist. */
 628   final int offset;
 629   /** The size of the sublist. */
 630   int size;
 631
 632   /**
 633    * Construct the sublist.
 634    *
 635    * @param backing the list this comes from
 636    * @param fromIndex the lower bound, inclusive
 637    * @param toIndex the upper bound, exclusive
 638    */
 639   SubList(AbstractList backing, int fromIndex, int toIndex)
 640   {
 641     backingList = backing;
 642     modCount = backing.modCount;
 643     offset = fromIndex;
 644     size = toIndex - fromIndex;
 645   }
 646
 647   /**
 648    * This method checks the two modCount fields to ensure that there has
 649    * not been a concurrent modification, returning if all is okay.
 650    *
 651    * @throws ConcurrentModificationException if the backing list has been
 652    *         modified externally to this sublist
 653    */
 654   // This can be inlined. Package visible, for use by iterator.
 655   void checkMod()
 656   {
 657     if (modCount != backingList.modCount)
 658       throw new ConcurrentModificationException();
 659   }
 660
 661   /**
 662    * This method checks that a value is between 0 and size (inclusive). If
 663    * it is not, an exception is thrown.
 664    *
 665    * @param index the value to check
 666    * @throws IndexOutOfBoundsException if the value is out of range
 667    */
 668   // This will get inlined, since it is private.
 669   private void checkBoundsInclusive(int index)
 670   {
 671     if (index < 0 || index > size)
 672       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 673                                           + size);
 674   }
 675
 676   /**
 677    * This method checks that a value is between 0 (inclusive) and size
 678    * (exclusive). If it is not, an exception is thrown.
 679    *
 680    * @param index the value to check
 681    * @throws IndexOutOfBoundsException if the value is out of range
 682    */
 683   // This will get inlined, since it is private.
 684   private void checkBoundsExclusive(int index)
 685   {
 686     if (index < 0 || index >= size)
 687       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 688                                           + size);
 689   }
 690
 691   /**
 692    * Specified by AbstractList.subList to return the private field size.
 693    *
 694    * @return the sublist size
 695    */
 696   public int size()
 697   {
 698     checkMod();
 699     return size;
 700   }
 701
 702   /**
 703    * Specified by AbstractList.subList to delegate to the backing list.
 704    *
 705    * @param index the location to modify
 706    * @param o the new value
 707    * @return the old value
 708    */
 709   public Object set(int index, Object o)
 710   {
 711     checkMod();
 712     checkBoundsExclusive(index);
 713     return backingList.set(index + offset, o);
 714   }
 715
 716   /**
 717    * Specified by AbstractList.subList to delegate to the backing list.
 718    *
 719    * @param index the location to get from
 720    * @return the object at that location
 721    */
 722   public Object get(int index)
 723   {
 724     checkMod();
 725     checkBoundsExclusive(index);
 726     return backingList.get(index + offset);
 727   }
 728
 729   /**
 730    * Specified by AbstractList.subList to delegate to the backing list.
 731    *
 732    * @param index the index to insert at
 733    * @param o the object to add
 734    */
 735   public void add(int index, Object o)
 736   {
 737     checkMod();
 738     checkBoundsInclusive(index);
 739     backingList.add(index + offset, o);
 740     size++;
 741     modCount = backingList.modCount;
 742   }
 743
 744   /**
 745    * Specified by AbstractList.subList to delegate to the backing list.
 746    *
 747    * @param index the index to remove
 748    * @return the removed object
 749    */
 750   public Object remove(int index)
 751   {
 752     checkMod();
 753     checkBoundsExclusive(index);
 754     Object o = backingList.remove(index + offset);
 755     size--;
 756     modCount = backingList.modCount;
 757     return o;
 758   }
 759
 760   /**
 761    * Specified by AbstractList.subList to delegate to the backing list.
 762    * This does no bounds checking, as it assumes it will only be called
 763    * by trusted code like clear() which has already checked the bounds.
 764    *
 765    * @param fromIndex the lower bound, inclusive
 766    * @param toIndex the upper bound, exclusive
 767    */
 768   protected void removeRange(int fromIndex, int toIndex)
 769   {
 770     checkMod();
 771
 772     backingList.removeRange(offset + fromIndex, offset + toIndex);
 773     size -= toIndex - fromIndex;
 774     modCount = backingList.modCount;
 775   }
 776
 777   /**
 778    * Specified by AbstractList.subList to delegate to the backing list.
 779    *
 780    * @param index the location to insert at
 781    * @param c the collection to insert
 782    * @return true if this list was modified, in other words, c is non-empty
 783    */
 784   public boolean addAll(int index, Collection c)
 785   {
 786     checkMod();
 787     checkBoundsInclusive(index);
 788     int csize = c.size();
 789     boolean result = backingList.addAll(offset + index, c);
 790     size += csize;
 791     modCount = backingList.modCount;
 792     return result;
 793   }
 794
 795   /**
 796    * Specified by AbstractList.subList to return addAll(size, c).
 797    *
 798    * @param c the collection to insert
 799    * @return true if this list was modified, in other words, c is non-empty
 800    */
 801   public boolean addAll(Collection c)
 802   {
 803     return addAll(size, c);
 804   }
 805
 806   /**
 807    * Specified by AbstractList.subList to return listIterator().
 808    *
 809    * @return an iterator over the sublist
 810    */
 811   public Iterator iterator()
 812   {
 813     return listIterator();
 814   }
 815
 816   /**
 817    * Specified by AbstractList.subList to return a wrapper around the
 818    * backing list's iterator.
 819    *
 820    * @param index the start location of the iterator
 821    * @return a list iterator over the sublist
 822    */
 823   public ListIterator listIterator(final int index)
 824   {
 825     checkMod();
 826     checkBoundsInclusive(index);
 827
 828     return new ListIterator()
 829     {
 830       private final ListIterator i = backingList.listIterator(index + offset);
 831       private int position = index;
 832
 833       public boolean hasNext()
 834       {
 835         checkMod();
 836         return position < size;
 837       }
 838
 839       public boolean hasPrevious()
 840       {
 841         checkMod();
 842         return position > 0;
 843       }
 844
 845       public Object next()
 846       {
 847         if (position == size)
 848           throw new NoSuchElementException();
 849         position++;
 850         return i.next();
 851       }
 852
 853       public Object previous()
 854       {
 855         if (position == 0)
 856           throw new NoSuchElementException();
 857         position--;
 858         return i.previous();
 859       }
 860
 861       public int nextIndex()
 862       {
 863         return i.nextIndex() - offset;
 864       }
 865
 866       public int previousIndex()
 867       {
 868         return i.previousIndex() - offset;
 869       }
 870
 871       public void remove()
 872       {
 873         i.remove();
 874         size--;
 875         position = nextIndex();
 876         modCount = backingList.modCount;
 877       }
 878
 879       public void set(Object o)
 880       {
 881         i.set(o);
 882       }
 883
 884       public void add(Object o)
 885       {
 886         i.add(o);
 887         size++;
 888         position++;
 889         modCount = backingList.modCount;
 890       }
 891
 892       // Here is the reason why the various modCount fields are mostly
 893       // ignored in this wrapper listIterator.
 894       // If the backing listIterator is failfast, then the following holds:
 895       //   Using any other method on this list will call a corresponding
 896       //   method on the backing list *after* the backing listIterator
 897       //   is created, which will in turn cause a ConcurrentModException
 898       //   when this listIterator comes to use the backing one. So it is
 899       //   implicitly failfast.
 900       // If the backing listIterator is NOT failfast, then the whole of
 901       //   this list isn't failfast, because the modCount field of the
 902       //   backing list is not valid. It would still be *possible* to
 903       //   make the iterator failfast wrt modifications of the sublist
 904       //   only, but somewhat pointless when the list can be changed under
 905       //   us.
 906       // Either way, no explicit handling of modCount is needed.
 907       // However modCount = backingList.modCount must be executed in add
 908       // and remove, and size must also be updated in these two methods,
 909       // since they do not go through the corresponding methods of the subList.
 910     };
 911   }
 912 } // class SubList
 913
 914 /**
 915  * This class is a RandomAccess version of SubList, as required by
 916  * {@link AbstractList#subList(int, int)}.
 917  *
 918  * @author Eric Blake <ebb9@email.byu.edu>
 919  */
 920 final class RandomAccessSubList extends SubList
 921   implements RandomAccess
 922 {
 923   /**
 924    * Construct the sublist.
 925    *
 926    * @param backing the list this comes from
 927    * @param fromIndex the lower bound, inclusive
 928    * @param toIndex the upper bound, exclusive
 929    */
 930   RandomAccessSubList(AbstractList backing, int fromIndex, int toIndex)
 931   {
 932     super(backing, fromIndex, toIndex);
 933   }
 934 } // class RandomAccessSubList