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