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