Source for java.util.AbstractList

   1: /* AbstractList.java -- Abstract implementation of most of List
   2:    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2005  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., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 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:        */
 331:       public boolean hasNext()
 332:       {
 333:         return pos < size;
 334:       }
 335: 
 336:       /**
 337:        * Retrieves the next object from the list.
 338:        *
 339:        * @return The next object.
 340:        * @throws NoSuchElementException if there are
 341:        *         no more objects to retrieve.
 342:        * @throws ConcurrentModificationException if the
 343:        *         list has been modified elsewhere.
 344:        */
 345:       public Object next()
 346:       {
 347:         checkMod();
 348:         if (pos == size)
 349:           throw new NoSuchElementException();
 350:         last = pos;
 351:         return get(pos++);
 352:       }
 353: 
 354:       /**
 355:        * Removes the last object retrieved by <code>next()</code>
 356:        * from the list, if the list supports object removal.
 357:        *
 358:        * @throws ConcurrentModificationException if the list
 359:        *         has been modified elsewhere.
 360:        * @throws IllegalStateException if the iterator is positioned
 361:        *         before the start of the list or the last object has already
 362:        *         been removed.
 363:        * @throws UnsupportedOperationException if the list does
 364:        *         not support removing elements.
 365:        */
 366:       public void remove()
 367:       {
 368:         checkMod();
 369:         if (last < 0)
 370:           throw new IllegalStateException();
 371:         AbstractList.this.remove(last);
 372:         pos--;
 373:         size--;
 374:         last = -1;
 375:         knownMod = modCount;
 376:       }
 377:     };
 378:   }
 379: 
 380:   /**
 381:    * Obtain the last index at which a given object is to be found in this
 382:    * list. This implementation grabs listIterator(size()), then searches
 383:    * backwards for a match or returns -1.
 384:    *
 385:    * @return the greatest integer n such that <code>o == null ? get(n) == null
 386:    *         : o.equals(get(n))</code>, or -1 if there is no such index
 387:    */
 388:   public int lastIndexOf(Object o)
 389:   {
 390:     int pos = size();
 391:     ListIterator itr = listIterator(pos);
 392:     while (--pos >= 0)
 393:       if (equals(o, itr.previous()))
 394:         return pos;
 395:     return -1;
 396:   }
 397: 
 398:   /**
 399:    * Obtain a ListIterator over this list, starting at the beginning. This
 400:    * implementation returns listIterator(0).
 401:    *
 402:    * @return a ListIterator over the elements of this list, in order, starting
 403:    *         at the beginning
 404:    */
 405:   public ListIterator listIterator()
 406:   {
 407:     return listIterator(0);
 408:   }
 409: 
 410:   /**
 411:    * Obtain a ListIterator over this list, starting at a given position.
 412:    * A first call to next() would return the same as get(index), and a
 413:    * first call to previous() would return the same as get(index - 1).
 414:    * <p>
 415:    *
 416:    * This implementation uses size(), get(int), set(int, Object),
 417:    * add(int, Object), and remove(int) of the backing list, and does not
 418:    * support remove, set, or add unless the list does. This implementation
 419:    * is fail-fast if you correctly maintain modCount.
 420:    *
 421:    * @param index the position, between 0 and size() inclusive, to begin the
 422:    *        iteration from
 423:    * @return a ListIterator over the elements of this list, in order, starting
 424:    *         at index
 425:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 426:    * @see #modCount
 427:    */
 428:   public ListIterator listIterator(final int index)
 429:   {
 430:     if (index < 0 || index > size())
 431:       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 432:                                           + size());
 433: 
 434:     return new ListIterator()
 435:     {
 436:       private int knownMod = modCount;
 437:       private int position = index;
 438:       private int lastReturned = -1;
 439:       private int size = size();
 440: 
 441:       // This will get inlined, since it is private.
 442:       /**
 443:        * Checks for modifications made to the list from
 444:        * elsewhere while iteration is in progress.
 445:        *
 446:        * @throws ConcurrentModificationException if the
 447:        *         list has been modified elsewhere.
 448:        */
 449:       private void checkMod()
 450:       {
 451:         if (knownMod != modCount)
 452:           throw new ConcurrentModificationException();
 453:       }
 454: 
 455:       /**
 456:        * Tests to see if there are any more objects to
 457:        * return.
 458:        *
 459:        * @return True if the end of the list has not yet been
 460:        *         reached.
 461:        */
 462:       public boolean hasNext()
 463:       {
 464:         return position < size;
 465:       }
 466: 
 467:       /**
 468:        * Tests to see if there are objects prior to the
 469:        * current position in the list.
 470:        *
 471:        * @return True if objects exist prior to the current
 472:        *         position of the iterator.
 473:        */
 474:       public boolean hasPrevious()
 475:       {
 476:         return position > 0;
 477:       }
 478: 
 479:       /**
 480:        * Retrieves the next object from the list.
 481:        *
 482:        * @return The next object.
 483:        * @throws NoSuchElementException if there are no
 484:        *         more objects to retrieve.
 485:        * @throws ConcurrentModificationException if the
 486:        *         list has been modified elsewhere.
 487:        */
 488:       public Object next()
 489:       {
 490:         checkMod();
 491:         if (position == size)
 492:           throw new NoSuchElementException();
 493:         lastReturned = position;
 494:         return get(position++);
 495:       }
 496: 
 497:       /**
 498:        * Retrieves the previous object from the list.
 499:        *
 500:        * @return The next object.
 501:        * @throws NoSuchElementException if there are no
 502:        *         previous objects to retrieve.
 503:        * @throws ConcurrentModificationException if the
 504:        *         list has been modified elsewhere.
 505:        */
 506:       public Object previous()
 507:       {
 508:         checkMod();
 509:         if (position == 0)
 510:           throw new NoSuchElementException();
 511:         lastReturned = --position;
 512:         return get(lastReturned);
 513:       }
 514: 
 515:       /**
 516:        * Returns the index of the next element in the
 517:        * list, which will be retrieved by <code>next()</code>
 518:        *
 519:        * @return The index of the next element.
 520:        */
 521:       public int nextIndex()
 522:       {
 523:         return position;
 524:       }
 525: 
 526:       /**
 527:        * Returns the index of the previous element in the
 528:        * list, which will be retrieved by <code>previous()</code>
 529:        *
 530:        * @return The index of the previous element.
 531:        */
 532:       public int previousIndex()
 533:       {
 534:         return position - 1;
 535:       }
 536: 
 537:      /**
 538:       * Removes the last object retrieved by <code>next()</code>
 539:       * or <code>previous()</code> from the list, if the list
 540:       * supports object removal.
 541:       *
 542:       * @throws IllegalStateException if the iterator is positioned
 543:       *         before the start of the list or the last object has already
 544:       *         been removed.
 545:       * @throws UnsupportedOperationException if the list does
 546:       *         not support removing elements.
 547:       * @throws ConcurrentModificationException if the list
 548:       *         has been modified elsewhere.
 549:       */
 550:       public void remove()
 551:       {
 552:         checkMod();
 553:         if (lastReturned < 0)
 554:           throw new IllegalStateException();
 555:         AbstractList.this.remove(lastReturned);
 556:         size--;
 557:         position = lastReturned;
 558:         lastReturned = -1;
 559:         knownMod = modCount;
 560:       }
 561: 
 562:      /**
 563:       * Replaces the last object retrieved by <code>next()</code>
 564:       * or <code>previous</code> with o, if the list supports object
 565:       * replacement and an add or remove operation has not already
 566:       * been performed.
 567:       *
 568:       * @throws IllegalStateException if the iterator is positioned
 569:       *         before the start of the list or the last object has already
 570:       *         been removed.
 571:       * @throws UnsupportedOperationException if the list doesn't support
 572:       *         the addition or removal of elements.
 573:       * @throws ClassCastException if the type of o is not a valid type
 574:       *         for this list.
 575:       * @throws IllegalArgumentException if something else related to o
 576:       *         prevents its addition.
 577:       * @throws ConcurrentModificationException if the list
 578:       *         has been modified elsewhere.
 579:       */
 580:       public void set(Object o)
 581:       {
 582:         checkMod();
 583:         if (lastReturned < 0)
 584:           throw new IllegalStateException();
 585:         AbstractList.this.set(lastReturned, o);
 586:       }
 587: 
 588:       /**
 589:        * Adds the supplied object before the element that would be returned
 590:        * by a call to <code>next()</code>, if the list supports addition.
 591:        * 
 592:        * @param o The object to add to the list.
 593:        * @throws UnsupportedOperationException if the list doesn't support
 594:        *         the addition of new elements.
 595:        * @throws ClassCastException if the type of o is not a valid type
 596:        *         for this list.
 597:        * @throws IllegalArgumentException if something else related to o
 598:        *         prevents its addition.
 599:        * @throws ConcurrentModificationException if the list
 600:        *         has been modified elsewhere.
 601:        */
 602:       public void add(Object o)
 603:       {
 604:         checkMod();
 605:         AbstractList.this.add(position++, o);
 606:         size++;
 607:         lastReturned = -1;
 608:         knownMod = modCount;
 609:       }
 610:     };
 611:   }
 612: 
 613:   /**
 614:    * Remove the element at a given position in this list (optional operation).
 615:    * Shifts all remaining elements to the left to fill the gap. This
 616:    * implementation always throws an UnsupportedOperationException.
 617:    * If you want fail-fast iterators, be sure to increment modCount when
 618:    * overriding this.
 619:    *
 620:    * @param index the position within the list of the object to remove
 621:    * @return the object that was removed
 622:    * @throws UnsupportedOperationException if this list does not support the
 623:    *         remove operation
 624:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 625:    * @see #modCount
 626:    */
 627:   public Object remove(int index)
 628:   {
 629:     throw new UnsupportedOperationException();
 630:   }
 631: 
 632:   /**
 633:    * Remove a subsection of the list. This is called by the clear and
 634:    * removeRange methods of the class which implements subList, which are
 635:    * difficult for subclasses to override directly. Therefore, this method
 636:    * should be overridden instead by the more efficient implementation, if one
 637:    * exists. Overriding this can reduce quadratic efforts to constant time
 638:    * in some cases!
 639:    * <p>
 640:    *
 641:    * This implementation first checks for illegal or out of range arguments. It
 642:    * then obtains a ListIterator over the list using listIterator(fromIndex).
 643:    * It then calls next() and remove() on this iterator repeatedly, toIndex -
 644:    * fromIndex times.
 645:    *
 646:    * @param fromIndex the index, inclusive, to remove from.
 647:    * @param toIndex the index, exclusive, to remove to.
 648:    * @throws UnsupportedOperationException if the list does
 649:    *         not support removing elements.
 650:    */
 651:   protected void removeRange(int fromIndex, int toIndex)
 652:   {
 653:     ListIterator itr = listIterator(fromIndex);
 654:     for (int index = fromIndex; index < toIndex; index++)
 655:       {
 656:         itr.next();
 657:         itr.remove();
 658:       }
 659:   }
 660: 
 661:   /**
 662:    * Replace an element of this list with another object (optional operation).
 663:    * This implementation always throws an UnsupportedOperationException.
 664:    *
 665:    * @param index the position within this list of the element to be replaced
 666:    * @param o the object to replace it with
 667:    * @return the object that was replaced
 668:    * @throws UnsupportedOperationException if this list does not support the
 669:    *         set operation
 670:    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 671:    * @throws ClassCastException if o cannot be added to this list due to its
 672:    *         type
 673:    * @throws IllegalArgumentException if o cannot be added to this list for
 674:    *         some other reason
 675:    */
 676:   public Object set(int index, Object o)
 677:   {
 678:     throw new UnsupportedOperationException();
 679:   }
 680: 
 681:   /**
 682:    * Obtain a List view of a subsection of this list, from fromIndex
 683:    * (inclusive) to toIndex (exclusive). If the two indices are equal, the
 684:    * sublist is empty. The returned list should be modifiable if and only
 685:    * if this list is modifiable. Changes to the returned list should be
 686:    * reflected in this list. If this list is structurally modified in
 687:    * any way other than through the returned list, the result of any subsequent
 688:    * operations on the returned list is undefined.
 689:    * <p>
 690:    *
 691:    * This implementation returns a subclass of AbstractList. It stores, in
 692:    * private fields, the offset and size of the sublist, and the expected
 693:    * modCount of the backing list. If the backing list implements RandomAccess,
 694:    * the sublist will also.
 695:    * <p>
 696:    *
 697:    * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
 698:    * <code>add(int, Object)</code>, <code>remove(int)</code>,
 699:    * <code>addAll(int, Collection)</code> and
 700:    * <code>removeRange(int, int)</code> methods all delegate to the
 701:    * corresponding methods on the backing abstract list, after
 702:    * bounds-checking the index and adjusting for the offset. The
 703:    * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
 704:    * The <code>listIterator(int)</code> method returns a "wrapper object"
 705:    * over a list iterator on the backing list, which is created with the
 706:    * corresponding method on the backing list. The <code>iterator()</code>
 707:    * method merely returns listIterator(), and the <code>size()</code> method
 708:    * merely returns the subclass's size field.
 709:    * <p>
 710:    *
 711:    * All methods first check to see if the actual modCount of the backing
 712:    * list is equal to its expected value, and throw a
 713:    * ConcurrentModificationException if it is not. 
 714:    *
 715:    * @param fromIndex the index that the returned list should start from
 716:    *        (inclusive)
 717:    * @param toIndex the index that the returned list should go to (exclusive)
 718:    * @return a List backed by a subsection of this list
 719:    * @throws IndexOutOfBoundsException if fromIndex &lt; 0
 720:    *         || toIndex &gt; size()
 721:    * @throws IllegalArgumentException if fromIndex &gt; toIndex
 722:    * @see ConcurrentModificationException
 723:    * @see RandomAccess
 724:    */
 725:   public List subList(int fromIndex, int toIndex)
 726:   {
 727:     // This follows the specification of AbstractList, but is inconsistent
 728:     // with the one in List. Don't you love Sun's inconsistencies?
 729:     if (fromIndex > toIndex)
 730:       throw new IllegalArgumentException(fromIndex + " > " + toIndex);
 731:     if (fromIndex < 0 || toIndex > size())
 732:       throw new IndexOutOfBoundsException();
 733: 
 734:     if (this instanceof RandomAccess)
 735:       return new RandomAccessSubList(this, fromIndex, toIndex);
 736:     return new SubList(this, fromIndex, toIndex);
 737:   }
 738: 
 739:   /**
 740:    * This class follows the implementation requirements set forth in
 741:    * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
 742:    * by using a non-public top-level class in the same package.
 743:    *
 744:    * @author Original author unknown
 745:    * @author Eric Blake (ebb9@email.byu.edu)
 746:    */
 747:   private static class SubList extends AbstractList
 748:   {
 749:     // Package visible, for use by iterator.
 750:     /** The original list. */
 751:     final AbstractList backingList;
 752:     /** The index of the first element of the sublist. */
 753:     final int offset;
 754:     /** The size of the sublist. */
 755:     int size;
 756: 
 757:     /**
 758:      * Construct the sublist.
 759:      *
 760:      * @param backing the list this comes from
 761:      * @param fromIndex the lower bound, inclusive
 762:      * @param toIndex the upper bound, exclusive
 763:      */
 764:     SubList(AbstractList backing, int fromIndex, int toIndex)
 765:     {
 766:       backingList = backing;
 767:       modCount = backing.modCount;
 768:       offset = fromIndex;
 769:       size = toIndex - fromIndex;
 770:     }
 771: 
 772:     /**
 773:      * This method checks the two modCount fields to ensure that there has
 774:      * not been a concurrent modification, returning if all is okay.
 775:      *
 776:      * @throws ConcurrentModificationException if the backing list has been
 777:      *         modified externally to this sublist
 778:      */
 779:     // This can be inlined. Package visible, for use by iterator.
 780:     void checkMod()
 781:     {
 782:       if (modCount != backingList.modCount)
 783:         throw new ConcurrentModificationException();
 784:     }
 785: 
 786:     /**
 787:      * This method checks that a value is between 0 and size (inclusive). If
 788:      * it is not, an exception is thrown.
 789:      *
 790:      * @param index the value to check
 791:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 792:      */
 793:     // This will get inlined, since it is private.
 794:     private void checkBoundsInclusive(int index)
 795:     {
 796:       if (index < 0 || index > size)
 797:         throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 798:                                             + size);
 799:     }
 800: 
 801:     /**
 802:      * This method checks that a value is between 0 (inclusive) and size
 803:      * (exclusive). If it is not, an exception is thrown.
 804:      *
 805:      * @param index the value to check
 806:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 807:      */
 808:     // This will get inlined, since it is private.
 809:     private void checkBoundsExclusive(int index)
 810:     {
 811:       if (index < 0 || index >= size)
 812:         throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
 813:                                             + size);
 814:     }
 815: 
 816:     /**
 817:      * Specified by AbstractList.subList to return the private field size.
 818:      *
 819:      * @return the sublist size
 820:      * @throws ConcurrentModificationException if the backing list has been
 821:      *         modified externally to this sublist
 822:      */
 823:     public int size()
 824:     {
 825:       checkMod();
 826:       return size;
 827:     }
 828: 
 829:     /**
 830:      * Specified by AbstractList.subList to delegate to the backing list.
 831:      *
 832:      * @param index the location to modify
 833:      * @param o the new value
 834:      * @return the old value
 835:      * @throws ConcurrentModificationException if the backing list has been
 836:      *         modified externally to this sublist
 837:      * @throws UnsupportedOperationException if the backing list does not
 838:      *         support the set operation
 839:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 840:      * @throws ClassCastException if o cannot be added to the backing list due
 841:      *         to its type
 842:      * @throws IllegalArgumentException if o cannot be added to the backing list
 843:      *         for some other reason
 844:      */
 845:     public Object set(int index, Object o)
 846:     {
 847:       checkMod();
 848:       checkBoundsExclusive(index);
 849:       return backingList.set(index + offset, o);
 850:     }
 851: 
 852:     /**
 853:      * Specified by AbstractList.subList to delegate to the backing list.
 854:      *
 855:      * @param index the location to get from
 856:      * @return the object at that location
 857:      * @throws ConcurrentModificationException if the backing list has been
 858:      *         modified externally to this sublist
 859:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 860:      */
 861:     public Object get(int index)
 862:     {
 863:       checkMod();
 864:       checkBoundsExclusive(index);
 865:       return backingList.get(index + offset);
 866:     }
 867: 
 868:     /**
 869:      * Specified by AbstractList.subList to delegate to the backing list.
 870:      *
 871:      * @param index the index to insert at
 872:      * @param o the object to add
 873:      * @throws ConcurrentModificationException if the backing list has been
 874:      *         modified externally to this sublist
 875:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 876:      * @throws UnsupportedOperationException if the backing list does not
 877:      *         support the add operation.
 878:      * @throws ClassCastException if o cannot be added to the backing list due
 879:      *         to its type.
 880:      * @throws IllegalArgumentException if o cannot be added to the backing
 881:      *         list for some other reason.
 882:      */
 883:     public void add(int index, Object o)
 884:     {
 885:       checkMod();
 886:       checkBoundsInclusive(index);
 887:       backingList.add(index + offset, o);
 888:       size++;
 889:       modCount = backingList.modCount;
 890:     }
 891: 
 892:     /**
 893:      * Specified by AbstractList.subList to delegate to the backing list.
 894:      *
 895:      * @param index the index to remove
 896:      * @return the removed object
 897:      * @throws ConcurrentModificationException if the backing list has been
 898:      *         modified externally to this sublist
 899:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 900:      * @throws UnsupportedOperationException if the backing list does not
 901:      *         support the remove operation
 902:      */
 903:     public Object remove(int index)
 904:     {
 905:       checkMod();
 906:       checkBoundsExclusive(index);
 907:       Object o = backingList.remove(index + offset);
 908:       size--;
 909:       modCount = backingList.modCount;
 910:       return o;
 911:     }
 912: 
 913:     /**
 914:      * Specified by AbstractList.subList to delegate to the backing list.
 915:      * This does no bounds checking, as it assumes it will only be called
 916:      * by trusted code like clear() which has already checked the bounds.
 917:      *
 918:      * @param fromIndex the lower bound, inclusive
 919:      * @param toIndex the upper bound, exclusive
 920:      * @throws ConcurrentModificationException if the backing list has been
 921:      *         modified externally to this sublist
 922:      * @throws UnsupportedOperationException if the backing list does
 923:      *         not support removing elements.
 924:      */
 925:     protected void removeRange(int fromIndex, int toIndex)
 926:     {
 927:       checkMod();
 928: 
 929:       backingList.removeRange(offset + fromIndex, offset + toIndex);
 930:       size -= toIndex - fromIndex;
 931:       modCount = backingList.modCount;
 932:     }
 933: 
 934:     /**
 935:      * Specified by AbstractList.subList to delegate to the backing list.
 936:      *
 937:      * @param index the location to insert at
 938:      * @param c the collection to insert
 939:      * @return true if this list was modified, in other words, c is non-empty
 940:      * @throws ConcurrentModificationException if the backing list has been
 941:      *         modified externally to this sublist
 942:      * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 943:      * @throws UnsupportedOperationException if this list does not support the
 944:      *         addAll operation
 945:      * @throws ClassCastException if some element of c cannot be added to this
 946:      *         list due to its type
 947:      * @throws IllegalArgumentException if some element of c cannot be added
 948:      *         to this list for some other reason
 949:      * @throws NullPointerException if the specified collection is null
 950:      */
 951:     public boolean addAll(int index, Collection c)
 952:     {
 953:       checkMod();
 954:       checkBoundsInclusive(index);
 955:       int csize = c.size();
 956:       boolean result = backingList.addAll(offset + index, c);
 957:       size += csize;
 958:       modCount = backingList.modCount;
 959:       return result;
 960:     }
 961: 
 962:     /**
 963:      * Specified by AbstractList.subList to return addAll(size, c).
 964:      *
 965:      * @param c the collection to insert
 966:      * @return true if this list was modified, in other words, c is non-empty
 967:      * @throws ConcurrentModificationException if the backing list has been
 968:      *         modified externally to this sublist
 969:      * @throws UnsupportedOperationException if this list does not support the
 970:      *         addAll operation
 971:      * @throws ClassCastException if some element of c cannot be added to this
 972:      *         list due to its type
 973:      * @throws IllegalArgumentException if some element of c cannot be added
 974:      *         to this list for some other reason
 975:      * @throws NullPointerException if the specified collection is null
 976:      */
 977:     public boolean addAll(Collection c)
 978:     {
 979:       return addAll(size, c);
 980:     }
 981: 
 982:     /**
 983:      * Specified by AbstractList.subList to return listIterator().
 984:      *
 985:      * @return an iterator over the sublist
 986:      */
 987:     public Iterator iterator()
 988:     {
 989:       return listIterator();
 990:     }
 991: 
 992:     /**
 993:      * Specified by AbstractList.subList to return a wrapper around the
 994:      * backing list's iterator.
 995:      *
 996:      * @param index the start location of the iterator
 997:      * @return a list iterator over the sublist
 998:      * @throws ConcurrentModificationException if the backing list has been
 999:      *         modified externally to this sublist
1000:      * @throws IndexOutOfBoundsException if the value is out of range
1001:      */
1002:     public ListIterator listIterator(final int index)
1003:     {
1004:       checkMod();
1005:       checkBoundsInclusive(index);
1006: 
1007:       return new ListIterator()
1008:       {
1009:         private final ListIterator i = backingList.listIterator(index + offset);
1010:         private int position = index;
1011: 
1012:         /**
1013:          * Tests to see if there are any more objects to
1014:          * return.
1015:          *
1016:          * @return True if the end of the list has not yet been
1017:          *         reached.
1018:          */
1019:         public boolean hasNext()
1020:         {
1021:           return position < size;
1022:         }
1023: 
1024:         /**
1025:          * Tests to see if there are objects prior to the
1026:          * current position in the list.
1027:          *
1028:          * @return True if objects exist prior to the current
1029:          *         position of the iterator.
1030:          */
1031:         public boolean hasPrevious()
1032:         {
1033:           return position > 0;
1034:         }
1035: 
1036:         /**
1037:          * Retrieves the next object from the list.
1038:          *
1039:          * @return The next object.
1040:          * @throws NoSuchElementException if there are no
1041:          *         more objects to retrieve.
1042:          * @throws ConcurrentModificationException if the
1043:          *         list has been modified elsewhere.
1044:          */
1045:         public Object next()
1046:         {
1047:           if (position == size)
1048:             throw new NoSuchElementException();
1049:           position++;
1050:           return i.next();
1051:         }
1052: 
1053:         /**
1054:          * Retrieves the previous object from the list.
1055:          *
1056:          * @return The next object.
1057:          * @throws NoSuchElementException if there are no
1058:          *         previous objects to retrieve.
1059:          * @throws ConcurrentModificationException if the
1060:          *         list has been modified elsewhere.
1061:          */
1062:         public Object previous()
1063:         {
1064:           if (position == 0)
1065:             throw new NoSuchElementException();
1066:           position--;
1067:           return i.previous();
1068:         }
1069: 
1070:         /**
1071:          * Returns the index of the next element in the
1072:          * list, which will be retrieved by <code>next()</code>
1073:          *
1074:          * @return The index of the next element.
1075:          */
1076:         public int nextIndex()
1077:         {
1078:           return i.nextIndex() - offset;
1079:         }
1080: 
1081:         /**
1082:          * Returns the index of the previous element in the
1083:          * list, which will be retrieved by <code>previous()</code>
1084:          *
1085:          * @return The index of the previous element.
1086:          */
1087:         public int previousIndex()
1088:         {
1089:           return i.previousIndex() - offset;
1090:         }
1091: 
1092:         /**
1093:          * Removes the last object retrieved by <code>next()</code>
1094:          * from the list, if the list supports object removal.
1095:          *
1096:          * @throws IllegalStateException if the iterator is positioned
1097:          *         before the start of the list or the last object has already
1098:          *         been removed.
1099:          * @throws UnsupportedOperationException if the list does
1100:          *         not support removing elements.
1101:          */
1102:         public void remove()
1103:         {
1104:           i.remove();
1105:           size--;
1106:           position = nextIndex();
1107:           modCount = backingList.modCount;
1108:         }
1109: 
1110: 
1111:        /**
1112:         * Replaces the last object retrieved by <code>next()</code>
1113:         * or <code>previous</code> with o, if the list supports object
1114:         * replacement and an add or remove operation has not already
1115:         * been performed.
1116:         *
1117:         * @throws IllegalStateException if the iterator is positioned
1118:         *         before the start of the list or the last object has already
1119:         *         been removed.
1120:         * @throws UnsupportedOperationException if the list doesn't support
1121:         *         the addition or removal of elements.
1122:         * @throws ClassCastException if the type of o is not a valid type
1123:         *         for this list.
1124:         * @throws IllegalArgumentException if something else related to o
1125:         *         prevents its addition.
1126:         * @throws ConcurrentModificationException if the list
1127:         *         has been modified elsewhere.
1128:         */
1129:         public void set(Object o)
1130:         {
1131:           i.set(o);
1132:         }
1133: 
1134:         /**
1135:          * Adds the supplied object before the element that would be returned
1136:          * by a call to <code>next()</code>, if the list supports addition.
1137:          * 
1138:          * @param o The object to add to the list.
1139:          * @throws UnsupportedOperationException if the list doesn't support
1140:          *         the addition of new elements.
1141:          * @throws ClassCastException if the type of o is not a valid type
1142:          *         for this list.
1143:          * @throws IllegalArgumentException if something else related to o
1144:          *         prevents its addition.
1145:          * @throws ConcurrentModificationException if the list
1146:          *         has been modified elsewhere.
1147:          */
1148:         public void add(Object o)
1149:         {
1150:           i.add(o);
1151:           size++;
1152:           position++;
1153:           modCount = backingList.modCount;
1154:         }
1155: 
1156:         // Here is the reason why the various modCount fields are mostly
1157:         // ignored in this wrapper listIterator.
1158:         // If the backing listIterator is failfast, then the following holds:
1159:         //   Using any other method on this list will call a corresponding
1160:         //   method on the backing list *after* the backing listIterator
1161:         //   is created, which will in turn cause a ConcurrentModException
1162:         //   when this listIterator comes to use the backing one. So it is
1163:         //   implicitly failfast.
1164:         // If the backing listIterator is NOT failfast, then the whole of
1165:         //   this list isn't failfast, because the modCount field of the
1166:         //   backing list is not valid. It would still be *possible* to
1167:         //   make the iterator failfast wrt modifications of the sublist
1168:         //   only, but somewhat pointless when the list can be changed under
1169:         //   us.
1170:         // Either way, no explicit handling of modCount is needed.
1171:         // However modCount = backingList.modCount must be executed in add
1172:         // and remove, and size must also be updated in these two methods,
1173:         // since they do not go through the corresponding methods of the subList.
1174:       };
1175:     }
1176:   } // class SubList
1177: 
1178:   /**
1179:    * This class is a RandomAccess version of SubList, as required by
1180:    * {@link AbstractList#subList(int, int)}.
1181:    *
1182:    * @author Eric Blake (ebb9@email.byu.edu)
1183:    */
1184:   private static final class RandomAccessSubList extends SubList
1185:     implements RandomAccess
1186:   {
1187:     /**
1188:      * Construct the sublist.
1189:      *
1190:      * @param backing the list this comes from
1191:      * @param fromIndex the lower bound, inclusive
1192:      * @param toIndex the upper bound, exclusive
1193:      */
1194:     RandomAccessSubList(AbstractList backing, int fromIndex, int toIndex)
1195:     {
1196:       super(backing, fromIndex, toIndex);
1197:     }
1198:   } // class RandomAccessSubList
1199: 
1200: } // class AbstractList