1 /* 2 * Copyright (c) 1997, 2016, 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 public abstract 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 * size of the subList (which can change over its lifetime), and the 466 * expected {@code modCount} value of the backing list. There are two 467 * variants of the subclass, one of which implements {@code RandomAccess}. 468 * If this list implements {@code RandomAccess} the returned list will 469 * be an instance of the subclass that implements {@code RandomAccess}. 470 * 471 * <p>The subclass's {@code set(int, E)}, {@code get(int)}, 472 * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int, 473 * Collection)} and {@code removeRange(int, int)} methods all 474 * delegate to the corresponding methods on the backing abstract list, 475 * after bounds-checking the index and adjusting for the offset. The 476 * {@code addAll(Collection c)} method merely returns {@code addAll(size, 477 * c)}. 478 * 479 * <p>The {@code listIterator(int)} method returns a "wrapper object" 480 * over a list iterator on the backing list, which is created with the 481 * corresponding method on the backing list. The {@code iterator} method 482 * merely returns {@code listIterator()}, and the {@code size} method 483 * merely returns the subclass's {@code size} field. 484 * 485 * <p>All methods first check to see if the actual {@code modCount} of 486 * the backing list is equal to its expected value, and throw a 487 * {@code ConcurrentModificationException} if it is not. 488 * 489 * @throws IndexOutOfBoundsException if an endpoint index value is out of range 490 * {@code (fromIndex < 0 || toIndex > size)} 491 * @throws IllegalArgumentException if the endpoint indices are out of order 492 * {@code (fromIndex > toIndex)} 493 */ 494 public List<E> subList(int fromIndex, int toIndex) { 495 subListRangeCheck(fromIndex, toIndex, size()); 496 return (this instanceof RandomAccess ? 497 new RandomAccessSubList<>(this, fromIndex, toIndex) : 498 new SubList<>(this, fromIndex, toIndex)); 499 } 500 501 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 502 if (fromIndex < 0) 503 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 504 if (toIndex > size) 505 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 506 if (fromIndex > toIndex) 507 throw new IllegalArgumentException("fromIndex(" + fromIndex + 508 ") > toIndex(" + toIndex + ")"); 509 } 510 511 // Comparison and hashing 512 513 /** 514 * Compares the specified object with this list for equality. Returns 515 * {@code true} if and only if the specified object is also a list, both 516 * lists have the same size, and all corresponding pairs of elements in 517 * the two lists are <i>equal</i>. (Two elements {@code e1} and 518 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null : 519 * e1.equals(e2))}.) In other words, two lists are defined to be 520 * equal if they contain the same elements in the same order. 521 * 522 * @implSpec 523 * This implementation first checks if the specified object is this 524 * list. If so, it returns {@code true}; if not, it checks if the 525 * specified object is a list. If not, it returns {@code false}; if so, 526 * it iterates over both lists, comparing corresponding pairs of elements. 527 * If any comparison returns {@code false}, this method returns 528 * {@code false}. If either iterator runs out of elements before the 529 * other it returns {@code false} (as the lists are of unequal length); 530 * otherwise it returns {@code true} when the iterations complete. 531 * 532 * @param o the object to be compared for equality with this list 533 * @return {@code true} if the specified object is equal to this list 534 */ 535 public boolean equals(Object o) { 536 if (o == this) 537 return true; 538 if (!(o instanceof List)) 539 return false; 540 541 ListIterator<E> e1 = listIterator(); 542 ListIterator<?> e2 = ((List<?>) o).listIterator(); 543 while (e1.hasNext() && e2.hasNext()) { 544 E o1 = e1.next(); 545 Object o2 = e2.next(); 546 if (!(o1==null ? o2==null : o1.equals(o2))) 547 return false; 548 } 549 return !(e1.hasNext() || e2.hasNext()); 550 } 551 552 /** 553 * Returns the hash code value for this list. 554 * 555 * @implSpec 556 * This implementation uses exactly the code that is used to define the 557 * list hash function in the documentation for the {@link List#hashCode} 558 * method. 559 * 560 * @return the hash code value for this list 561 */ 562 public int hashCode() { 563 int hashCode = 1; 564 for (E e : this) 565 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 566 return hashCode; 567 } 568 569 /** 570 * Removes from this list all of the elements whose index is between 571 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 572 * Shifts any succeeding elements to the left (reduces their index). 573 * This call shortens the list by {@code (toIndex - fromIndex)} elements. 574 * (If {@code toIndex==fromIndex}, this operation has no effect.) 575 * 576 * <p>This method is called by the {@code clear} operation on this list 577 * and its subLists. Overriding this method to take advantage of 578 * the internals of the list implementation can <i>substantially</i> 579 * improve the performance of the {@code clear} operation on this list 580 * and its subLists. 581 * 582 * @implSpec 583 * This implementation gets a list iterator positioned before 584 * {@code fromIndex}, and repeatedly calls {@code ListIterator.next} 585 * followed by {@code ListIterator.remove} until the entire range has 586 * been removed. <b>Note: if {@code ListIterator.remove} requires linear 587 * time, this implementation requires quadratic time.</b> 588 * 589 * @param fromIndex index of first element to be removed 590 * @param toIndex index after last element to be removed 591 */ 592 protected void removeRange(int fromIndex, int toIndex) { 593 ListIterator<E> it = listIterator(fromIndex); 594 for (int i=0, n=toIndex-fromIndex; i<n; i++) { 595 it.next(); 596 it.remove(); 597 } 598 } 599 600 /** 601 * The number of times this list has been <i>structurally modified</i>. 602 * Structural modifications are those that change the size of the 603 * list, or otherwise perturb it in such a fashion that iterations in 604 * progress may yield incorrect results. 605 * 606 * <p>This field is used by the iterator and list iterator implementation 607 * returned by the {@code iterator} and {@code listIterator} methods. 608 * If the value of this field changes unexpectedly, the iterator (or list 609 * iterator) will throw a {@code ConcurrentModificationException} in 610 * response to the {@code next}, {@code remove}, {@code previous}, 611 * {@code set} or {@code add} operations. This provides 612 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in 613 * the face of concurrent modification during iteration. 614 * 615 * <p><b>Use of this field by subclasses is optional.</b> If a subclass 616 * wishes to provide fail-fast iterators (and list iterators), then it 617 * merely has to increment this field in its {@code add(int, E)} and 618 * {@code remove(int)} methods (and any other methods that it overrides 619 * that result in structural modifications to the list). A single call to 620 * {@code add(int, E)} or {@code remove(int)} must add no more than 621 * one to this field, or the iterators (and list iterators) will throw 622 * bogus {@code ConcurrentModificationExceptions}. If an implementation 623 * does not wish to provide fail-fast iterators, this field may be 624 * ignored. 625 */ 626 protected transient int modCount = 0; 627 628 private void rangeCheckForAdd(int index) { 629 if (index < 0 || index > size()) 630 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 631 } 632 633 private String outOfBoundsMsg(int index) { 634 return "Index: "+index+", Size: "+size(); 635 } 636 637 private static class SubList<E> extends AbstractList<E> { 638 private final AbstractList<E> root; 639 private final SubList<E> parent; 640 private final int offset; 641 protected int size; 642 643 /** 644 * Constructs a sublist of an arbitrary AbstractList, which is 645 * not a SubList itself. 646 */ 647 public SubList(AbstractList<E> root, int fromIndex, int toIndex) { 648 this.root = root; 649 this.parent = null; 650 this.offset = fromIndex; 651 this.size = toIndex - fromIndex; 652 this.modCount = root.modCount; 653 } 654 655 /** 656 * Constructs a sublist of another SubList. 657 */ 658 protected SubList(SubList<E> parent, int fromIndex, int toIndex) { 659 this.root = parent.root; 660 this.parent = parent; 661 this.offset = parent.offset + fromIndex; 662 this.size = toIndex - fromIndex; 663 this.modCount = root.modCount; 664 } 665 666 public E set(int index, E element) { 667 Objects.checkIndex(index, size); 668 checkForComodification(); 669 return root.set(offset + index, element); 670 } 671 672 public E get(int index) { 673 Objects.checkIndex(index, size); 674 checkForComodification(); 675 return root.get(offset + index); 676 } 677 678 public int size() { 679 checkForComodification(); 680 return size; 681 } 682 683 public void add(int index, E element) { 684 rangeCheckForAdd(index); 685 checkForComodification(); 686 root.add(offset + index, element); 687 updateSizeAndModCount(1); 688 } 689 690 public E remove(int index) { 691 Objects.checkIndex(index, size); 692 checkForComodification(); 693 E result = root.remove(offset + index); 694 updateSizeAndModCount(-1); 695 return result; 696 } 697 698 protected void removeRange(int fromIndex, int toIndex) { 699 checkForComodification(); 700 root.removeRange(offset + fromIndex, offset + toIndex); 701 updateSizeAndModCount(fromIndex - toIndex); 702 } 703 704 public boolean addAll(Collection<? extends E> c) { 705 return addAll(size, c); 706 } 707 708 public boolean addAll(int index, Collection<? extends E> c) { 709 rangeCheckForAdd(index); 710 int cSize = c.size(); 711 if (cSize==0) 712 return false; 713 checkForComodification(); 714 root.addAll(offset + index, c); 715 updateSizeAndModCount(cSize); 716 return true; 717 } 718 719 public Iterator<E> iterator() { 720 return listIterator(); 721 } 722 723 public ListIterator<E> listIterator(int index) { 724 checkForComodification(); 725 rangeCheckForAdd(index); 726 727 return new ListIterator<E>() { 728 private final ListIterator<E> i = 729 root.listIterator(offset + index); 730 731 public boolean hasNext() { 732 return nextIndex() < size; 733 } 734 735 public E next() { 736 if (hasNext()) 737 return i.next(); 738 else 739 throw new NoSuchElementException(); 740 } 741 742 public boolean hasPrevious() { 743 return previousIndex() >= 0; 744 } 745 746 public E previous() { 747 if (hasPrevious()) 748 return i.previous(); 749 else 750 throw new NoSuchElementException(); 751 } 752 753 public int nextIndex() { 754 return i.nextIndex() - offset; 755 } 756 757 public int previousIndex() { 758 return i.previousIndex() - offset; 759 } 760 761 public void remove() { 762 i.remove(); 763 updateSizeAndModCount(-1); 764 } 765 766 public void set(E e) { 767 i.set(e); 768 } 769 770 public void add(E e) { 771 i.add(e); 772 updateSizeAndModCount(1); 773 } 774 }; 775 } 776 777 public List<E> subList(int fromIndex, int toIndex) { 778 subListRangeCheck(fromIndex, toIndex, size); 779 return new SubList<>(this, fromIndex, toIndex); 780 } 781 782 private void rangeCheckForAdd(int index) { 783 if (index < 0 || index > size) 784 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 785 } 786 787 private String outOfBoundsMsg(int index) { 788 return "Index: "+index+", Size: "+size; 789 } 790 791 private void checkForComodification() { 792 if (root.modCount != this.modCount) 793 throw new ConcurrentModificationException(); 794 } 795 796 private void updateSizeAndModCount(int sizeChange) { 797 SubList<E> slist = this; 798 do { 799 slist.size += sizeChange; 800 slist.modCount = root.modCount; 801 slist = slist.parent; 802 } while (slist != null); 803 } 804 } 805 806 private static class RandomAccessSubList<E> 807 extends SubList<E> implements RandomAccess { 808 809 /** 810 * Constructs a sublist of an arbitrary AbstractList, which is 811 * not a RandomAccessSubList itself. 812 */ 813 RandomAccessSubList(AbstractList<E> root, 814 int fromIndex, int toIndex) { 815 super(root, fromIndex, toIndex); 816 } 817 818 /** 819 * Constructs a sublist of another RandomAccessSubList. 820 */ 821 RandomAccessSubList(RandomAccessSubList<E> parent, 822 int fromIndex, int toIndex) { 823 super(parent, fromIndex, toIndex); 824 } 825 826 public List<E> subList(int fromIndex, int toIndex) { 827 subListRangeCheck(fromIndex, toIndex, size); 828 return new RandomAccessSubList<>(this, fromIndex, toIndex); 829 } 830 } 831 }