001/* AbstractList.java -- Abstract implementation of most of List 002 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 003 Free Software Foundation, Inc. 004 005This file is part of GNU Classpath. 006 007GNU Classpath is free software; you can redistribute it and/or modify 008it under the terms of the GNU General Public License as published by 009the Free Software Foundation; either version 2, or (at your option) 010any later version. 011 012GNU Classpath is distributed in the hope that it will be useful, but 013WITHOUT ANY WARRANTY; without even the implied warranty of 014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015General Public License for more details. 016 017You should have received a copy of the GNU General Public License 018along with GNU Classpath; see the file COPYING. If not, write to the 019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02002110-1301 USA. 021 022Linking this library statically or dynamically with other modules is 023making a combined work based on this library. Thus, the terms and 024conditions of the GNU General Public License cover the whole 025combination. 026 027As a special exception, the copyright holders of this library give you 028permission to link this library with independent modules to produce an 029executable, regardless of the license terms of these independent 030modules, and to copy and distribute the resulting executable under 031terms of your choice, provided that you also meet, for each linked 032independent module, the terms and conditions of the license of that 033module. An independent module is a module which is not derived from 034or based on this library. If you modify this library, you may extend 035this exception to your version of the library, but you are not 036obligated to do so. If you do not wish to do so, delete this 037exception statement from your version. */ 038 039 040package java.util; 041 042/** 043 * A basic implementation of most of the methods in the List interface to make 044 * it easier to create a List based on a random-access data structure. If 045 * the list is sequential (such as a linked list), use AbstractSequentialList. 046 * To create an unmodifiable list, it is only necessary to override the 047 * size() and get(int) methods (this contrasts with all other abstract 048 * collection classes which require an iterator to be provided). To make the 049 * list modifiable, the set(int, Object) method should also be overridden, and 050 * to make the list resizable, the add(int, Object) and remove(int) methods 051 * should be overridden too. Other methods should be overridden if the 052 * backing data structure allows for a more efficient implementation. 053 * The precise implementation used by AbstractList is documented, so that 054 * subclasses can tell which methods could be implemented more efficiently. 055 * <p> 056 * 057 * As recommended by Collection and List, the subclass should provide at 058 * least a no-argument and a Collection constructor. This class is not 059 * synchronized. 060 * 061 * @author Original author unknown 062 * @author Bryce McKinlay 063 * @author Eric Blake (ebb9@email.byu.edu) 064 * @see Collection 065 * @see List 066 * @see AbstractSequentialList 067 * @see AbstractCollection 068 * @see ListIterator 069 * @since 1.2 070 * @status updated to 1.4 071 */ 072public abstract class AbstractList<E> 073 extends AbstractCollection<E> 074 implements List<E> 075{ 076 /** 077 * A count of the number of structural modifications that have been made to 078 * the list (that is, insertions and removals). Structural modifications 079 * are ones which change the list size or affect how iterations would 080 * behave. This field is available for use by Iterator and ListIterator, 081 * in order to throw a {@link ConcurrentModificationException} in response 082 * to the next operation on the iterator. This <i>fail-fast</i> behavior 083 * saves the user from many subtle bugs otherwise possible from concurrent 084 * modification during iteration. 085 * <p> 086 * 087 * To make lists fail-fast, increment this field by just 1 in the 088 * <code>add(int, Object)</code> and <code>remove(int)</code> methods. 089 * Otherwise, this field may be ignored. 090 */ 091 protected transient int modCount; 092 093 /** 094 * The main constructor, for use by subclasses. 095 */ 096 protected AbstractList() 097 { 098 } 099 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; 248Iterator i = list.iterator(); 249while (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