Source for java.util.AbstractList

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