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