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 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/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 */
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 */
110 public boolean add(E e) {
111 add(size(), e);
112 return true;
113 }
114
115 /**
116 * {@inheritDoc}
117 *
118 * @throws IndexOutOfBoundsException {@inheritDoc}
119 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 /**
346 * Index of element to be returned by subsequent call to next.
347 */
348 int cursor = 0;
349
350 /**
351 * Index of element returned by most recent call to next or
352 * previous. Reset to -1 if this element is deleted by a call
353 * to remove.
354 */
355 int lastRet = -1;
356
357 /**
358 * The modCount value that the iterator believes that the backing
359 * List should have. If this expectation is violated, the iterator
360 * has detected concurrent modification.
361 */
362 int expectedModCount = modCount;
363
364 public boolean hasNext() {
365 return cursor != size();
366 }
367
368 public E next() {
369 checkForComodification();
370 try {
371 int i = cursor;
372 E next = get(i);
373 lastRet = i;
374 cursor = i + 1;
375 return next;
376 } catch (IndexOutOfBoundsException e) {
377 checkForComodification();
378 throw new NoSuchElementException();
379 }
380 }
381
382 public void remove() {
383 if (lastRet < 0)
384 throw new IllegalStateException();
385 checkForComodification();
386
387 try {
388 AbstractList.this.remove(lastRet);
389 if (lastRet < cursor)
390 cursor--;
391 lastRet = -1;
392 expectedModCount = modCount;
393 } catch (IndexOutOfBoundsException e) {
394 throw new ConcurrentModificationException();
395 }
396 }
397
398 final void checkForComodification() {
399 if (modCount != expectedModCount)
400 throw new ConcurrentModificationException();
401 }
402 }
403
404 private class ListItr extends Itr implements ListIterator<E> {
405 ListItr(int index) {
406 cursor = index;
407 }
408
409 public boolean hasPrevious() {
410 return cursor != 0;
411 }
412
413 public E previous() {
414 checkForComodification();
415 try {
416 int i = cursor - 1;
417 E previous = get(i);
418 lastRet = cursor = i;
419 return previous;
420 } catch (IndexOutOfBoundsException e) {
421 checkForComodification();
422 throw new NoSuchElementException();
423 }
424 }
425
426 public int nextIndex() {
427 return cursor;
428 }
429
430 public int previousIndex() {
431 return cursor-1;
432 }
433
434 public void set(E e) {
435 if (lastRet < 0)
436 throw new IllegalStateException();
437 checkForComodification();
438
439 try {
440 AbstractList.this.set(lastRet, e);
441 expectedModCount = modCount;
442 } catch (IndexOutOfBoundsException ex) {
443 throw new ConcurrentModificationException();
444 }
445 }
446
447 public void add(E e) {
448 checkForComodification();
449
450 try {
451 int i = cursor;
452 AbstractList.this.add(i, e);
453 lastRet = -1;
454 cursor = i + 1;
455 expectedModCount = modCount;
456 } catch (IndexOutOfBoundsException ex) {
457 throw new ConcurrentModificationException();
458 }
459 }
460 }
461
462 /**
463 * {@inheritDoc}
464 *
465 * @implSpec
466 * This implementation returns a list that subclasses
467 * {@code AbstractList}. The subclass stores, in private fields, the
468 * size of the subList (which can change over its lifetime), and the
469 * expected {@code modCount} value of the backing list. There are two
470 * variants of the subclass, one of which implements {@code RandomAccess}.
471 * If this list implements {@code RandomAccess} the returned list will
472 * be an instance of the subclass that implements {@code RandomAccess}.
473 *
474 * <p>The subclass's {@code set(int, E)}, {@code get(int)},
475 * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
476 * Collection)} and {@code removeRange(int, int)} methods all
477 * delegate to the corresponding methods on the backing abstract list,
478 * after bounds-checking the index and adjusting for the offset. The
479 * {@code addAll(Collection c)} method merely returns {@code addAll(size,
480 * c)}.
481 *
482 * <p>The {@code listIterator(int)} method returns a "wrapper object"
483 * over a list iterator on the backing list, which is created with the
484 * corresponding method on the backing list. The {@code iterator} method
485 * merely returns {@code listIterator()}, and the {@code size} method
486 * merely returns the subclass's {@code size} field.
487 *
488 * <p>All methods first check to see if the actual {@code modCount} of
489 * the backing list is equal to its expected value, and throw a
490 * {@code ConcurrentModificationException} if it is not.
491 *
492 * @throws IndexOutOfBoundsException if an endpoint index value is out of range
493 * {@code (fromIndex < 0 || toIndex > size)}
494 * @throws IllegalArgumentException if the endpoint indices are out of order
495 * {@code (fromIndex > toIndex)}
496 */
497 public List<E> subList(int fromIndex, int toIndex) {
498 subListRangeCheck(fromIndex, toIndex, size());
499 return (this instanceof RandomAccess ?
500 new RandomAccessSubList<>(this, fromIndex, toIndex) :
501 new SubList<>(this, fromIndex, toIndex));
502 }
503
504 static void subListRangeCheck(int fromIndex, int toIndex, int size) {
505 if (fromIndex < 0)
506 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
507 if (toIndex > size)
508 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
509 if (fromIndex > toIndex)
510 throw new IllegalArgumentException("fromIndex(" + fromIndex +
511 ") > toIndex(" + toIndex + ")");
512 }
513
514 // Comparison and hashing
515
516 /**
517 * Compares the specified object with this list for equality. Returns
518 * {@code true} if and only if the specified object is also a list, both
519 * lists have the same size, and all corresponding pairs of elements in
520 * the two lists are <i>equal</i>. (Two elements {@code e1} and
521 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null :
522 * e1.equals(e2))}.) In other words, two lists are defined to be
523 * equal if they contain the same elements in the same order.
524 *
525 * @implSpec
526 * This implementation first checks if the specified object is this
527 * list. If so, it returns {@code true}; if not, it checks if the
528 * specified object is a list. If not, it returns {@code false}; if so,
529 * it iterates over both lists, comparing corresponding pairs of elements.
530 * If any comparison returns {@code false}, this method returns
531 * {@code false}. If either iterator runs out of elements before the
532 * other it returns {@code false} (as the lists are of unequal length);
533 * otherwise it returns {@code true} when the iterations complete.
534 *
535 * @param o the object to be compared for equality with this list
536 * @return {@code true} if the specified object is equal to this list
537 */
538 public boolean equals(Object o) {
539 if (o == this)
540 return true;
541 if (!(o instanceof List))
542 return false;
543
544 ListIterator<E> e1 = listIterator();
545 ListIterator<?> e2 = ((List<?>) o).listIterator();
546 while (e1.hasNext() && e2.hasNext()) {
547 E o1 = e1.next();
548 Object o2 = e2.next();
549 if (!(o1==null ? o2==null : o1.equals(o2)))
550 return false;
551 }
552 return !(e1.hasNext() || e2.hasNext());
553 }
554
555 /**
556 * Returns the hash code value for this list.
557 *
558 * @implSpec
559 * This implementation uses exactly the code that is used to define the
560 * list hash function in the documentation for the {@link List#hashCode}
561 * method.
562 *
563 * @return the hash code value for this list
564 */
565 public int hashCode() {
566 int hashCode = 1;
567 for (E e : this)
568 hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
569 return hashCode;
570 }
571
572 /**
573 * Removes from this list all of the elements whose index is between
574 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
575 * Shifts any succeeding elements to the left (reduces their index).
576 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
577 * (If {@code toIndex==fromIndex}, this operation has no effect.)
578 *
579 * <p>This method is called by the {@code clear} operation on this list
580 * and its subLists. Overriding this method to take advantage of
581 * the internals of the list implementation can <i>substantially</i>
582 * improve the performance of the {@code clear} operation on this list
583 * and its subLists.
584 *
585 * @implSpec
586 * This implementation gets a list iterator positioned before
587 * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
588 * followed by {@code ListIterator.remove} until the entire range has
589 * been removed. <b>Note: if {@code ListIterator.remove} requires linear
590 * time, this implementation requires quadratic time.</b>
591 *
592 * @param fromIndex index of first element to be removed
593 * @param toIndex index after last element to be removed
594 */
595 protected void removeRange(int fromIndex, int toIndex) {
596 ListIterator<E> it = listIterator(fromIndex);
597 for (int i=0, n=toIndex-fromIndex; i<n; i++) {
598 it.next();
599 it.remove();
600 }
601 }
602
603 /**
604 * The number of times this list has been <i>structurally modified</i>.
605 * Structural modifications are those that change the size of the
606 * list, or otherwise perturb it in such a fashion that iterations in
607 * progress may yield incorrect results.
608 *
609 * <p>This field is used by the iterator and list iterator implementation
610 * returned by the {@code iterator} and {@code listIterator} methods.
611 * If the value of this field changes unexpectedly, the iterator (or list
612 * iterator) will throw a {@code ConcurrentModificationException} in
613 * response to the {@code next}, {@code remove}, {@code previous},
614 * {@code set} or {@code add} operations. This provides
615 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
616 * the face of concurrent modification during iteration.
617 *
618 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
619 * wishes to provide fail-fast iterators (and list iterators), then it
620 * merely has to increment this field in its {@code add(int, E)} and
621 * {@code remove(int)} methods (and any other methods that it overrides
622 * that result in structural modifications to the list). A single call to
623 * {@code add(int, E)} or {@code remove(int)} must add no more than
624 * one to this field, or the iterators (and list iterators) will throw
625 * bogus {@code ConcurrentModificationExceptions}. If an implementation
626 * does not wish to provide fail-fast iterators, this field may be
627 * ignored.
628 */
629 protected transient int modCount = 0;
630
631 private void rangeCheckForAdd(int index) {
632 if (index < 0 || index > size())
633 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
634 }
635
636 private String outOfBoundsMsg(int index) {
637 return "Index: "+index+", Size: "+size();
638 }
639
640 /**
641 * An index-based split-by-two, lazily initialized Spliterator covering
642 * a List that access elements via {@link List#get}.
643 *
644 * If access results in an IndexOutOfBoundsException then a
645 * ConcurrentModificationException is thrown instead (since the list has
646 * been structurally modified while traversing).
647 *
648 * If the List is an instance of AbstractList then concurrent modification
649 * checking is performed using the AbstractList's modCount field.
650 */
651 static final class RandomAccessSpliterator<E> implements Spliterator<E> {
652
653 private final List<E> list;
654 private int index; // current index, modified on advance/split
655 private int fence; // -1 until used; then one past last index
656
657 // The following fields are valid if covering an AbstractList
658 private final AbstractList<E> alist;
659 private int expectedModCount; // initialized when fence set
660
661 RandomAccessSpliterator(List<E> list) {
662 assert list instanceof RandomAccess;
663
664 this.list = list;
665 this.index = 0;
666 this.fence = -1;
667
668 this.alist = list instanceof AbstractList ? (AbstractList<E>) list : null;
669 this.expectedModCount = alist != null ? alist.modCount : 0;
670 }
671
672 /** Create new spliterator covering the given range */
673 private RandomAccessSpliterator(RandomAccessSpliterator<E> parent,
674 int origin, int fence) {
675 this.list = parent.list;
676 this.index = origin;
677 this.fence = fence;
678
679 this.alist = parent.alist;
680 this.expectedModCount = parent.expectedModCount;
681 }
682
683 private int getFence() { // initialize fence to size on first use
684 int hi;
685 List<E> lst = list;
686 if ((hi = fence) < 0) {
687 if (alist != null) {
688 expectedModCount = alist.modCount;
689 }
690 hi = fence = lst.size();
691 }
692 return hi;
693 }
694
695 public Spliterator<E> trySplit() {
696 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
697 return (lo >= mid) ? null : // divide range in half unless too small
698 new RandomAccessSpliterator<>(this, lo, index = mid);
699 }
700
701 public boolean tryAdvance(Consumer<? super E> action) {
702 if (action == null)
703 throw new NullPointerException();
704 int hi = getFence(), i = index;
705 if (i < hi) {
706 index = i + 1;
707 action.accept(get(list, i));
708 checkAbstractListModCount(alist, expectedModCount);
709 return true;
710 }
711 return false;
712 }
713
714 public void forEachRemaining(Consumer<? super E> action) {
715 Objects.requireNonNull(action);
716 List<E> lst = list;
717 int hi = getFence();
718 int i = index;
719 index = hi;
720 for (; i < hi; i++) {
721 action.accept(get(lst, i));
722 }
723 checkAbstractListModCount(alist, expectedModCount);
724 }
725
726 public long estimateSize() {
727 return (long) (getFence() - index);
728 }
729
730 public int characteristics() {
731 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
732 }
733
734 private static <E> E get(List<E> list, int i) {
735 try {
736 return list.get(i);
737 } catch (IndexOutOfBoundsException ex) {
738 throw new ConcurrentModificationException();
739 }
740 }
741
742 static void checkAbstractListModCount(AbstractList<?> alist, int expectedModCount) {
743 if (alist != null && alist.modCount != expectedModCount) {
744 throw new ConcurrentModificationException();
745 }
746 }
747 }
748
749 private static class SubList<E> extends AbstractList<E> {
750 private final AbstractList<E> root;
751 private final SubList<E> parent;
752 private final int offset;
753 protected int size;
754
755 /**
756 * Constructs a sublist of an arbitrary AbstractList, which is
757 * not a SubList itself.
758 */
759 public SubList(AbstractList<E> root, int fromIndex, int toIndex) {
760 this.root = root;
761 this.parent = null;
762 this.offset = fromIndex;
763 this.size = toIndex - fromIndex;
764 this.modCount = root.modCount;
765 }
766
767 /**
768 * Constructs a sublist of another SubList.
769 */
770 protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
771 this.root = parent.root;
772 this.parent = parent;
773 this.offset = parent.offset + fromIndex;
774 this.size = toIndex - fromIndex;
775 this.modCount = root.modCount;
776 }
777
778 public E set(int index, E element) {
779 Objects.checkIndex(index, size);
780 checkForComodification();
781 return root.set(offset + index, element);
782 }
783
784 public E get(int index) {
785 Objects.checkIndex(index, size);
786 checkForComodification();
787 return root.get(offset + index);
788 }
789
790 public int size() {
791 checkForComodification();
792 return size;
793 }
794
795 public void add(int index, E element) {
796 rangeCheckForAdd(index);
797 checkForComodification();
798 root.add(offset + index, element);
799 updateSizeAndModCount(1);
800 }
801
802 public E remove(int index) {
803 Objects.checkIndex(index, size);
804 checkForComodification();
805 E result = root.remove(offset + index);
806 updateSizeAndModCount(-1);
807 return result;
808 }
809
810 protected void removeRange(int fromIndex, int toIndex) {
811 checkForComodification();
812 root.removeRange(offset + fromIndex, offset + toIndex);
813 updateSizeAndModCount(fromIndex - toIndex);
814 }
815
816 public boolean addAll(Collection<? extends E> c) {
817 return addAll(size, c);
818 }
819
820 public boolean addAll(int index, Collection<? extends E> c) {
821 rangeCheckForAdd(index);
822 int cSize = c.size();
823 if (cSize==0)
824 return false;
825 checkForComodification();
826 root.addAll(offset + index, c);
827 updateSizeAndModCount(cSize);
828 return true;
829 }
830
831 public Iterator<E> iterator() {
832 return listIterator();
833 }
834
835 public ListIterator<E> listIterator(int index) {
836 checkForComodification();
837 rangeCheckForAdd(index);
838
839 return new ListIterator<E>() {
840 private final ListIterator<E> i =
841 root.listIterator(offset + index);
842
843 public boolean hasNext() {
844 return nextIndex() < size;
845 }
846
847 public E next() {
848 if (hasNext())
849 return i.next();
850 else
851 throw new NoSuchElementException();
852 }
853
854 public boolean hasPrevious() {
855 return previousIndex() >= 0;
856 }
857
858 public E previous() {
859 if (hasPrevious())
860 return i.previous();
861 else
862 throw new NoSuchElementException();
863 }
864
865 public int nextIndex() {
866 return i.nextIndex() - offset;
867 }
868
869 public int previousIndex() {
870 return i.previousIndex() - offset;
871 }
872
873 public void remove() {
874 i.remove();
875 updateSizeAndModCount(-1);
876 }
877
878 public void set(E e) {
879 i.set(e);
880 }
881
882 public void add(E e) {
883 i.add(e);
884 updateSizeAndModCount(1);
885 }
886 };
887 }
888
889 public List<E> subList(int fromIndex, int toIndex) {
890 subListRangeCheck(fromIndex, toIndex, size);
891 return new SubList<>(this, fromIndex, toIndex);
892 }
893
894 private void rangeCheckForAdd(int index) {
895 if (index < 0 || index > size)
896 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
897 }
898
899 private String outOfBoundsMsg(int index) {
900 return "Index: "+index+", Size: "+size;
901 }
902
903 private void checkForComodification() {
904 if (root.modCount != this.modCount)
905 throw new ConcurrentModificationException();
906 }
907
908 private void updateSizeAndModCount(int sizeChange) {
909 SubList<E> slist = this;
910 do {
911 slist.size += sizeChange;
912 slist.modCount = root.modCount;
913 slist = slist.parent;
914 } while (slist != null);
915 }
916 }
917
918 private static class RandomAccessSubList<E>
919 extends SubList<E> implements RandomAccess {
920
921 /**
922 * Constructs a sublist of an arbitrary AbstractList, which is
923 * not a RandomAccessSubList itself.
924 */
925 RandomAccessSubList(AbstractList<E> root,
926 int fromIndex, int toIndex) {
927 super(root, fromIndex, toIndex);
928 }
929
930 /**
931 * Constructs a sublist of another RandomAccessSubList.
932 */
933 RandomAccessSubList(RandomAccessSubList<E> parent,
934 int fromIndex, int toIndex) {
935 super(parent, fromIndex, toIndex);
936 }
937
938 public List<E> subList(int fromIndex, int toIndex) {
939 subListRangeCheck(fromIndex, toIndex, size);
940 return new RandomAccessSubList<>(this, fromIndex, toIndex);
941 }
942 }
943 }