1 /* 2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 /** 29 * This class provides a skeletal implementation of the {@link List} 30 * interface to minimize the effort required to implement this interface 31 * backed by a "random access" data store (such as an array). For sequential 32 * access data (such as a linked list), {@link AbstractSequentialList} should 33 * be used in preference to this class. 34 * 35 * <p>To implement an unmodifiable list, the programmer needs only to extend 36 * this class and provide implementations for the {@link #get(int)} and 37 * {@link List#size() size()} methods. 38 * 39 * <p>To implement a modifiable list, the programmer must additionally 40 * override the {@link #set(int, Object) set(int, E)} method (which otherwise 41 * throws an {@code UnsupportedOperationException}). If the list is 42 * variable-size the programmer must additionally override the 43 * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods. 44 * 45 * <p>The programmer should generally provide a void (no argument) and collection 46 * constructor, as per the recommendation in the {@link Collection} interface 47 * specification. 48 * 49 * <p>Unlike the other abstract collection implementations, the programmer does 50 * <i>not</i> have to provide an iterator implementation; the iterator and 51 * list iterator are implemented by this class, on top of the "random access" 52 * methods: 53 * {@link #get(int)}, 54 * {@link #set(int, Object) set(int, E)}, 55 * {@link #add(int, Object) add(int, E)} and 56 * {@link #remove(int)}. 57 * 58 * <p>The documentation for each non-abstract method in this class describes its 59 * implementation in detail. Each of these methods may be overridden if the 60 * collection being implemented admits a more efficient implementation. 61 * 62 * <p>This class is a member of the 63 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 64 * Java Collections Framework</a>. 65 * 66 * @author Josh Bloch 67 * @author Neal Gafter 68 * @since 1.2 69 */ 70 71 public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 72 /** 73 * Sole constructor. (For invocation by subclass constructors, typically 74 * implicit.) 75 */ 76 protected AbstractList() { 77 } 78 79 /** 80 * Appends the specified element to the end of this list (optional 81 * operation). 82 * 83 * <p>Lists that support this operation may place limitations on what 84 * elements may be added to this list. In particular, some 85 * lists will refuse to add null elements, and others will impose 86 * restrictions on the type of elements that may be added. List 87 * classes should clearly specify in their documentation any restrictions 88 * on what elements may be added. 89 * 90 * @implSpec 91 * This implementation calls {@code add(size(), e)}. 92 * 93 * <p>Note that this implementation throws an 94 * {@code UnsupportedOperationException} unless 95 * {@link #add(int, Object) add(int, E)} is overridden. 96 * 97 * @param e element to be appended to this list 98 * @return {@code true} (as specified by {@link Collection#add}) 99 * @throws UnsupportedOperationException if the {@code add} operation 100 * is not supported by this list 101 * @throws ClassCastException if the class of the specified element 102 * prevents it from being added to this list 103 * @throws NullPointerException if the specified element is null and this 104 * list does not permit null elements 105 * @throws IllegalArgumentException if some property of this element 106 * prevents it from being added to this list 107 */ 108 public boolean add(E e) { 109 add(size(), e); 110 return true; 111 } 112 113 /** 114 * {@inheritDoc} 115 * 116 * @throws IndexOutOfBoundsException {@inheritDoc} 117 */ 118 abstract public E get(int index); 119 120 /** 121 * {@inheritDoc} 122 * 123 * @implSpec 124 * This implementation always throws an 125 * {@code UnsupportedOperationException}. 126 * 127 * @throws UnsupportedOperationException {@inheritDoc} 128 * @throws ClassCastException {@inheritDoc} 129 * @throws NullPointerException {@inheritDoc} 130 * @throws IllegalArgumentException {@inheritDoc} 131 * @throws IndexOutOfBoundsException {@inheritDoc} 132 */ 133 public E set(int index, E element) { 134 throw new UnsupportedOperationException(); 135 } 136 137 /** 138 * {@inheritDoc} 139 * 140 * @implSpec 141 * This implementation always throws an 142 * {@code UnsupportedOperationException}. 143 * 144 * @throws UnsupportedOperationException {@inheritDoc} 145 * @throws ClassCastException {@inheritDoc} 146 * @throws NullPointerException {@inheritDoc} 147 * @throws IllegalArgumentException {@inheritDoc} 148 * @throws IndexOutOfBoundsException {@inheritDoc} 149 */ 150 public void add(int index, E element) { 151 throw new UnsupportedOperationException(); 152 } 153 154 /** 155 * {@inheritDoc} 156 * 157 * @implSpec 158 * This implementation always throws an 159 * {@code UnsupportedOperationException}. 160 * 161 * @throws UnsupportedOperationException {@inheritDoc} 162 * @throws IndexOutOfBoundsException {@inheritDoc} 163 */ 164 public E remove(int index) { 165 throw new UnsupportedOperationException(); 166 } 167 168 169 // Search Operations 170 171 /** 172 * {@inheritDoc} 173 * 174 * @implSpec 175 * This implementation first gets a list iterator (with 176 * {@code listIterator()}). Then, it iterates over the list until the 177 * specified element is found or the end of the list is reached. 178 * 179 * @throws ClassCastException {@inheritDoc} 180 * @throws NullPointerException {@inheritDoc} 181 */ 182 public int indexOf(Object o) { 183 ListIterator<E> it = listIterator(); 184 if (o==null) { 185 while (it.hasNext()) 186 if (it.next()==null) 187 return it.previousIndex(); 188 } else { 189 while (it.hasNext()) 190 if (o.equals(it.next())) 191 return it.previousIndex(); 192 } 193 return -1; 194 } 195 196 /** 197 * {@inheritDoc} 198 * 199 * @implSpec 200 * This implementation first gets a list iterator that points to the end 201 * of the list (with {@code listIterator(size())}). Then, it iterates 202 * backwards over the list until the specified element is found, or the 203 * beginning of the list is reached. 204 * 205 * @throws ClassCastException {@inheritDoc} 206 * @throws NullPointerException {@inheritDoc} 207 */ 208 public int lastIndexOf(Object o) { 209 ListIterator<E> it = listIterator(size()); 210 if (o==null) { 211 while (it.hasPrevious()) 212 if (it.previous()==null) 213 return it.nextIndex(); 214 } else { 215 while (it.hasPrevious()) 216 if (o.equals(it.previous())) 217 return it.nextIndex(); 218 } 219 return -1; 220 } 221 222 223 // Bulk Operations 224 225 /** 226 * Removes all of the elements from this list (optional operation). 227 * The list will be empty after this call returns. 228 * 229 * @implSpec 230 * This implementation calls {@code removeRange(0, size())}. 231 * 232 * <p>Note that this implementation throws an 233 * {@code UnsupportedOperationException} unless {@code remove(int 234 * index)} or {@code removeRange(int fromIndex, int toIndex)} is 235 * overridden. 236 * 237 * @throws UnsupportedOperationException if the {@code clear} operation 238 * is not supported by this list 239 */ 240 public void clear() { 241 removeRange(0, size()); 242 } 243 244 /** 245 * {@inheritDoc} 246 * 247 * @implSpec 248 * This implementation gets an iterator over the specified collection 249 * and iterates over it, inserting the elements obtained from the 250 * iterator into this list at the appropriate position, one at a time, 251 * using {@code add(int, E)}. 252 * Many implementations will override this method for efficiency. 253 * 254 * <p>Note that this implementation throws an 255 * {@code UnsupportedOperationException} unless 256 * {@link #add(int, Object) add(int, E)} is overridden. 257 * 258 * @throws UnsupportedOperationException {@inheritDoc} 259 * @throws ClassCastException {@inheritDoc} 260 * @throws NullPointerException {@inheritDoc} 261 * @throws IllegalArgumentException {@inheritDoc} 262 * @throws IndexOutOfBoundsException {@inheritDoc} 263 */ 264 public boolean addAll(int index, Collection<? extends E> c) { 265 rangeCheckForAdd(index); 266 boolean modified = false; 267 for (E e : c) { 268 add(index++, e); 269 modified = true; 270 } 271 return modified; 272 } 273 274 275 // Iterators 276 277 /** 278 * Returns an iterator over the elements in this list in proper sequence. 279 * 280 * @implSpec 281 * This implementation returns a straightforward implementation of the 282 * iterator interface, relying on the backing list's {@code size()}, 283 * {@code get(int)}, and {@code remove(int)} methods. 284 * 285 * <p>Note that the iterator returned by this method will throw an 286 * {@link UnsupportedOperationException} in response to its 287 * {@code remove} method unless the list's {@code remove(int)} method is 288 * overridden. 289 * 290 * <p>This implementation can be made to throw runtime exceptions in the 291 * face of concurrent modification, as described in the specification 292 * for the (protected) {@link #modCount} field. 293 * 294 * @return an iterator over the elements in this list in proper sequence 295 */ 296 public Iterator<E> iterator() { 297 return new Itr(); 298 } 299 300 /** 301 * {@inheritDoc} 302 * 303 * @implSpec 304 * This implementation returns {@code listIterator(0)}. 305 * 306 * @see #listIterator(int) 307 */ 308 public ListIterator<E> listIterator() { 309 return listIterator(0); 310 } 311 312 /** 313 * {@inheritDoc} 314 * 315 * @implSpec 316 * This implementation returns a straightforward implementation of the 317 * {@code ListIterator} interface that extends the implementation of the 318 * {@code Iterator} interface returned by the {@code iterator()} method. 319 * The {@code ListIterator} implementation relies on the backing list's 320 * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)} 321 * and {@code remove(int)} methods. 322 * 323 * <p>Note that the list iterator returned by this implementation will 324 * throw an {@link UnsupportedOperationException} in response to its 325 * {@code remove}, {@code set} and {@code add} methods unless the 326 * list's {@code remove(int)}, {@code set(int, E)}, and 327 * {@code add(int, E)} methods are overridden. 328 * 329 * <p>This implementation can be made to throw runtime exceptions in the 330 * face of concurrent modification, as described in the specification for 331 * the (protected) {@link #modCount} field. 332 * 333 * @throws IndexOutOfBoundsException {@inheritDoc} 334 */ 335 public ListIterator<E> listIterator(final int index) { 336 rangeCheckForAdd(index); 337 338 return new ListItr(index); 339 } 340 341 private class Itr implements Iterator<E> { 342 /** 343 * Index of element to be returned by subsequent call to next. 344 */ 345 int cursor = 0; 346 347 /** 348 * Index of element returned by most recent call to next or 349 * previous. Reset to -1 if this element is deleted by a call 350 * to remove. 351 */ 352 int lastRet = -1; 353 354 /** 355 * The modCount value that the iterator believes that the backing 356 * List should have. If this expectation is violated, the iterator 357 * has detected concurrent modification. 358 */ 359 int expectedModCount = modCount; 360 361 public boolean hasNext() { 362 return cursor != size(); 363 } 364 365 public E next() { 366 checkForComodification(); 367 try { 368 int i = cursor; 369 E next = get(i); 370 lastRet = i; 371 cursor = i + 1; 372 return next; 373 } catch (IndexOutOfBoundsException e) { 374 checkForComodification(); 375 throw new NoSuchElementException(); 376 } 377 } 378 379 public void remove() { 380 if (lastRet < 0) 381 throw new IllegalStateException(); 382 checkForComodification(); 383 384 try { 385 AbstractList.this.remove(lastRet); 386 if (lastRet < cursor) 387 cursor--; 388 lastRet = -1; 389 expectedModCount = modCount; 390 } catch (IndexOutOfBoundsException e) { 391 throw new ConcurrentModificationException(); 392 } 393 } 394 395 final void checkForComodification() { 396 if (modCount != expectedModCount) 397 throw new ConcurrentModificationException(); 398 } 399 } 400 401 private class ListItr extends Itr implements ListIterator<E> { 402 ListItr(int index) { 403 cursor = index; 404 } 405 406 public boolean hasPrevious() { 407 return cursor != 0; 408 } 409 410 public E previous() { 411 checkForComodification(); 412 try { 413 int i = cursor - 1; 414 E previous = get(i); 415 lastRet = cursor = i; 416 return previous; 417 } catch (IndexOutOfBoundsException e) { 418 checkForComodification(); 419 throw new NoSuchElementException(); 420 } 421 } 422 423 public int nextIndex() { 424 return cursor; 425 } 426 427 public int previousIndex() { 428 return cursor-1; 429 } 430 431 public void set(E e) { 432 if (lastRet < 0) 433 throw new IllegalStateException(); 434 checkForComodification(); 435 436 try { 437 AbstractList.this.set(lastRet, e); 438 expectedModCount = modCount; 439 } catch (IndexOutOfBoundsException ex) { 440 throw new ConcurrentModificationException(); 441 } 442 } 443 444 public void add(E e) { 445 checkForComodification(); 446 447 try { 448 int i = cursor; 449 AbstractList.this.add(i, e); 450 lastRet = -1; 451 cursor = i + 1; 452 expectedModCount = modCount; 453 } catch (IndexOutOfBoundsException ex) { 454 throw new ConcurrentModificationException(); 455 } 456 } 457 } 458 459 /** 460 * {@inheritDoc} 461 * 462 * @implSpec 463 * This implementation returns a list that subclasses 464 * {@code AbstractList}. The subclass stores, in private fields, the 465 * offset of the subList within the backing list, the size of the subList 466 * (which can change over its lifetime), and the expected 467 * {@code modCount} value of the backing list. There are two variants 468 * of the subclass, one of which implements {@code RandomAccess}. 469 * If this list implements {@code RandomAccess} the returned list will 470 * be an instance of the subclass that implements {@code RandomAccess}. 471 * 472 * <p>The subclass's {@code set(int, E)}, {@code get(int)}, 473 * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int, 474 * Collection)} and {@code removeRange(int, int)} methods all 475 * delegate to the corresponding methods on the backing abstract list, 476 * after bounds-checking the index and adjusting for the offset. The 477 * {@code addAll(Collection c)} method merely returns {@code addAll(size, 478 * c)}. 479 * 480 * <p>The {@code listIterator(int)} method returns a "wrapper object" 481 * over a list iterator on the backing list, which is created with the 482 * corresponding method on the backing list. The {@code iterator} method 483 * merely returns {@code listIterator()}, and the {@code size} method 484 * merely returns the subclass's {@code size} field. 485 * 486 * <p>All methods first check to see if the actual {@code modCount} of 487 * the backing list is equal to its expected value, and throw a 488 * {@code ConcurrentModificationException} if it is not. 489 * 490 * @throws IndexOutOfBoundsException if an endpoint index value is out of range 491 * {@code (fromIndex < 0 || toIndex > size)} 492 * @throws IllegalArgumentException if the endpoint indices are out of order 493 * {@code (fromIndex > toIndex)} 494 */ 495 public List<E> subList(int fromIndex, int toIndex) { 496 subListRangeCheck(fromIndex, toIndex, size()); 497 return (this instanceof RandomAccess ? 498 new RandomAccessSubList(this, 0, fromIndex, toIndex) : 499 new SubList(this, 0, fromIndex, toIndex)); 500 } 501 502 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 503 if (fromIndex < 0) 504 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 505 if (toIndex > size) 506 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 507 if (fromIndex > toIndex) 508 throw new IllegalArgumentException("fromIndex(" + fromIndex + 509 ") > toIndex(" + toIndex + ")"); 510 } 511 512 private class SubList extends AbstractList<E> { 513 final AbstractList<E> parent; 514 final int offset; 515 int size; 516 517 SubList(AbstractList<E> parent, 518 int offset, int fromIndex, int toIndex) { 519 this.parent = parent; 520 this.offset = offset + fromIndex; 521 this.size = toIndex - fromIndex; 522 this.modCount = AbstractList.this.modCount; 523 } 524 525 public E set(int index, E element) { 526 rangeCheck(index); 527 checkForComodification(); 528 return AbstractList.this.set(index + offset, element); 529 } 530 531 public E get(int index) { 532 rangeCheck(index); 533 checkForComodification(); 534 return AbstractList.this.get(index + offset); 535 } 536 537 public int size() { 538 checkForComodification(); 539 return size; 540 } 541 542 public void add(int index, E element) { 543 rangeCheckForAdd(index); 544 checkForComodification(); 545 AbstractList.this.add(index + offset, element); 546 updateSizeAndModCount(1, AbstractList.this.modCount); 547 } 548 549 public E remove(int index) { 550 rangeCheck(index); 551 checkForComodification(); 552 E result = AbstractList.this.remove(index + offset); 553 updateSizeAndModCount(-1, AbstractList.this.modCount); 554 return result; 555 } 556 557 protected void removeRange(int fromIndex, int toIndex) { 558 checkForComodification(); 559 AbstractList.this.removeRange(offset + fromIndex, 560 offset + toIndex); 561 updateSizeAndModCount(fromIndex - toIndex, 562 AbstractList.this.modCount); 563 } 564 565 public boolean addAll(Collection<? extends E> c) { 566 return addAll(size, c); 567 } 568 569 public boolean addAll(int index, Collection<? extends E> c) { 570 rangeCheckForAdd(index); 571 int cSize = c.size(); 572 if (cSize == 0) 573 return false; 574 checkForComodification(); 575 AbstractList.this.addAll(offset + index, c); 576 updateSizeAndModCount(cSize, 577 AbstractList.this.modCount); 578 return true; 579 } 580 581 public Iterator<E> iterator() { 582 return listIterator(); 583 } 584 585 public ListIterator<E> listIterator(final int index) { 586 checkForComodification(); 587 rangeCheckForAdd(index); 588 589 return new ListIterator<E>() { 590 private final ListIterator<E> i = 591 AbstractList.this.listIterator(offset + index); 592 593 public boolean hasNext() { 594 return nextIndex() < size; 595 } 596 597 public E next() { 598 if (hasNext()) 599 return i.next(); 600 else 601 throw new NoSuchElementException(); 602 } 603 604 public boolean hasPrevious() { 605 return previousIndex() >= 0; 606 } 607 608 public E previous() { 609 if (hasPrevious()) 610 return i.previous(); 611 else 612 throw new NoSuchElementException(); 613 } 614 615 public int nextIndex() { 616 return i.nextIndex() - offset; 617 } 618 619 public int previousIndex() { 620 return i.previousIndex() - offset; 621 } 622 623 public void remove() { 624 i.remove(); 625 updateSizeAndModCount(-1, 626 AbstractList.this.modCount); 627 } 628 629 public void set(E e) { 630 i.set(e); 631 } 632 633 public void add(E e) { 634 i.add(e); 635 updateSizeAndModCount(1, 636 AbstractList.this.modCount); 637 } 638 }; 639 } 640 641 public List<E> subList(int fromIndex, int toIndex) { 642 subListRangeCheck(fromIndex, toIndex, size); 643 return AbstractList.this.new SubList(this, offset, fromIndex, 644 toIndex); 645 } 646 647 private void rangeCheck(int index) { 648 if (index < 0 || index >= size) 649 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 650 } 651 652 private void rangeCheckForAdd(int index) { 653 if (index < 0 || index > size) 654 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 655 } 656 657 private String outOfBoundsMsg(int index) { 658 return "Index: " + index + ", Size: " + size; 659 } 660 661 private void checkForComodification() { 662 if (AbstractList.this.modCount != this.modCount) 663 throw new ConcurrentModificationException(); 664 } 665 666 private void updateSizeAndModCount(int sizeChange, int modCount) { 667 AbstractList<E> alist = this; 668 do { 669 SubList slist = (SubList)alist; 670 slist.size += sizeChange; 671 slist.modCount = modCount; 672 alist = slist.parent; 673 } while (alist instanceof AbstractList.SubList); 674 } 675 } 676 677 private class RandomAccessSubList extends SubList implements RandomAccess { 678 RandomAccessSubList(AbstractList<E> list, int offset, 679 int fromIndex, int toIndex) { 680 super(list, offset, fromIndex, toIndex); 681 } 682 683 public List<E> subList(int fromIndex, int toIndex) { 684 subListRangeCheck(fromIndex, toIndex, size); 685 return AbstractList.this.new RandomAccessSubList(this, offset, 686 fromIndex, toIndex); 687 } 688 } 689 690 // Comparison and hashing 691 692 /** 693 * Compares the specified object with this list for equality. Returns 694 * {@code true} if and only if the specified object is also a list, both 695 * lists have the same size, and all corresponding pairs of elements in 696 * the two lists are <i>equal</i>. (Two elements {@code e1} and 697 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null : 698 * e1.equals(e2))}.) In other words, two lists are defined to be 699 * equal if they contain the same elements in the same order. 700 * 701 * @implSpec 702 * This implementation first checks if the specified object is this 703 * list. If so, it returns {@code true}; if not, it checks if the 704 * specified object is a list. If not, it returns {@code false}; if so, 705 * it iterates over both lists, comparing corresponding pairs of elements. 706 * If any comparison returns {@code false}, this method returns 707 * {@code false}. If either iterator runs out of elements before the 708 * other it returns {@code false} (as the lists are of unequal length); 709 * otherwise it returns {@code true} when the iterations complete. 710 * 711 * @param o the object to be compared for equality with this list 712 * @return {@code true} if the specified object is equal to this list 713 */ 714 public boolean equals(Object o) { 715 if (o == this) 716 return true; 717 if (!(o instanceof List)) 718 return false; 719 720 ListIterator<E> e1 = listIterator(); 721 ListIterator<?> e2 = ((List<?>) o).listIterator(); 722 while (e1.hasNext() && e2.hasNext()) { 723 E o1 = e1.next(); 724 Object o2 = e2.next(); 725 if (!(o1==null ? o2==null : o1.equals(o2))) 726 return false; 727 } 728 return !(e1.hasNext() || e2.hasNext()); 729 } 730 731 /** 732 * Returns the hash code value for this list. 733 * 734 * @implSpec 735 * This implementation uses exactly the code that is used to define the 736 * list hash function in the documentation for the {@link List#hashCode} 737 * method. 738 * 739 * @return the hash code value for this list 740 */ 741 public int hashCode() { 742 int hashCode = 1; 743 for (E e : this) 744 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 745 return hashCode; 746 } 747 748 /** 749 * Removes from this list all of the elements whose index is between 750 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 751 * Shifts any succeeding elements to the left (reduces their index). 752 * This call shortens the list by {@code (toIndex - fromIndex)} elements. 753 * (If {@code toIndex==fromIndex}, this operation has no effect.) 754 * 755 * <p>This method is called by the {@code clear} operation on this list 756 * and its subLists. Overriding this method to take advantage of 757 * the internals of the list implementation can <i>substantially</i> 758 * improve the performance of the {@code clear} operation on this list 759 * and its subLists. 760 * 761 * @implSpec 762 * This implementation gets a list iterator positioned before 763 * {@code fromIndex}, and repeatedly calls {@code ListIterator.next} 764 * followed by {@code ListIterator.remove} until the entire range has 765 * been removed. <b>Note: if {@code ListIterator.remove} requires linear 766 * time, this implementation requires quadratic time.</b> 767 * 768 * @param fromIndex index of first element to be removed 769 * @param toIndex index after last element to be removed 770 */ 771 protected void removeRange(int fromIndex, int toIndex) { 772 ListIterator<E> it = listIterator(fromIndex); 773 for (int i=0, n=toIndex-fromIndex; i<n; i++) { 774 it.next(); 775 it.remove(); 776 } 777 } 778 779 /** 780 * The number of times this list has been <i>structurally modified</i>. 781 * Structural modifications are those that change the size of the 782 * list, or otherwise perturb it in such a fashion that iterations in 783 * progress may yield incorrect results. 784 * 785 * <p>This field is used by the iterator and list iterator implementation 786 * returned by the {@code iterator} and {@code listIterator} methods. 787 * If the value of this field changes unexpectedly, the iterator (or list 788 * iterator) will throw a {@code ConcurrentModificationException} in 789 * response to the {@code next}, {@code remove}, {@code previous}, 790 * {@code set} or {@code add} operations. This provides 791 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in 792 * the face of concurrent modification during iteration. 793 * 794 * <p><b>Use of this field by subclasses is optional.</b> If a subclass 795 * wishes to provide fail-fast iterators (and list iterators), then it 796 * merely has to increment this field in its {@code add(int, E)} and 797 * {@code remove(int)} methods (and any other methods that it overrides 798 * that result in structural modifications to the list). A single call to 799 * {@code add(int, E)} or {@code remove(int)} must add no more than 800 * one to this field, or the iterators (and list iterators) will throw 801 * bogus {@code ConcurrentModificationExceptions}. If an implementation 802 * does not wish to provide fail-fast iterators, this field may be 803 * ignored. 804 */ 805 protected transient int modCount = 0; 806 807 private void rangeCheckForAdd(int index) { 808 if (index < 0 || index > size()) 809 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 810 } 811 812 private String outOfBoundsMsg(int index) { 813 return "Index: " + index + ", Size: " + size(); 814 } 815 }