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