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.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 */
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 * 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
363 public boolean hasNext() {
364 return cursor != size();
365 }
366
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
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
397 final void checkForComodification() {
398 if (modCount != expectedModCount)
399 throw new ConcurrentModificationException();
400 }
401 }
402
403 private class ListItr extends Itr implements ListIterator<E> {
404 ListItr(int index) {
405 cursor = index;
406 }
407
408 public boolean hasPrevious() {
409 return cursor != 0;
410 }
411
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
425 public int nextIndex() {
426 return cursor;
427 }
428
429 public int previousIndex() {
430 return cursor-1;
431 }
432
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
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 */
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
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 */
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 */
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 */
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
630 private void rangeCheckForAdd(int index) {
631 if (index < 0 || index > size())
632 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
633 }
634
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
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 */
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
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
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
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
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
725 public long estimateSize() {
726 return (long) (getFence() - index);
727 }
728
729 public int characteristics() {
730 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
731 }
732
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
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 */
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 */
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
777 public E set(int index, E element) {
778 Objects.checkIndex(index, size);
779 checkForComodification();
780 return root.set(offset + index, element);
781 }
782
783 public E get(int index) {
784 Objects.checkIndex(index, size);
785 checkForComodification();
786 return root.get(offset + index);
787 }
788
789 public int size() {
790 checkForComodification();
791 return size;
792 }
793
794 public void add(int index, E element) {
795 rangeCheckForAdd(index);
796 checkForComodification();
797 root.add(offset + index, element);
798 updateSizeAndModCount(1);
799 }
800
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
809 protected void removeRange(int fromIndex, int toIndex) {
810 checkForComodification();
811 root.removeRange(offset + fromIndex, offset + toIndex);
812 updateSizeAndModCount(fromIndex - toIndex);
813 }
814
815 public boolean addAll(Collection<? extends E> c) {
816 return addAll(size, c);
817 }
818
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
830 public Iterator<E> iterator() {
831 return listIterator();
832 }
833
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
888 public List<E> subList(int fromIndex, int toIndex) {
889 subListRangeCheck(fromIndex, toIndex, size);
890 return new SubList<>(this, fromIndex, toIndex);
891 }
892
893 private void rangeCheckForAdd(int index) {
894 if (index < 0 || index > size)
895 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
896 }
897
898 private String outOfBoundsMsg(int index) {
899 return "Index: "+index+", Size: "+size;
900 }
901
902 private void checkForComodification() {
903 if (root.modCount != this.modCount)
904 throw new ConcurrentModificationException();
905 }
906
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 */
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 */
932 RandomAccessSubList(RandomAccessSubList<E> parent,
933 int fromIndex, int toIndex) {
934 super(parent, fromIndex, toIndex);
935 }
936
937 public List<E> subList(int fromIndex, int toIndex) {
938 subListRangeCheck(fromIndex, toIndex, size);
939 return new RandomAccessSubList<>(this, fromIndex, toIndex);
940 }
941 }
942 }