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