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 < 0 || index >= 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 < 0 || index > 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 < 0 || index > 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index >= 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 < 0 723: * || toIndex > size() 724: * @throws IllegalArgumentException if fromIndex > 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index >= 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 < 0 || index >= 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index > 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