| /* |
| * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package java.util; |
| |
| import java.util.function.Consumer; |
| |
| /** |
| * This class provides a skeletal implementation of the {@link List} |
| * interface to minimize the effort required to implement this interface |
| * backed by a "random access" data store (such as an array). For sequential |
| * access data (such as a linked list), {@link AbstractSequentialList} should |
| * be used in preference to this class. |
| * |
| * <p>To implement an unmodifiable list, the programmer needs only to extend |
| * this class and provide implementations for the {@link #get(int)} and |
| * {@link List#size() size()} methods. |
| * |
| * <p>To implement a modifiable list, the programmer must additionally |
| * override the {@link #set(int, Object) set(int, E)} method (which otherwise |
| * throws an {@code UnsupportedOperationException}). If the list is |
| * variable-size the programmer must additionally override the |
| * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods. |
| * |
| * <p>The programmer should generally provide a void (no argument) and collection |
| * constructor, as per the recommendation in the {@link Collection} interface |
| * specification. |
| * |
| * <p>Unlike the other abstract collection implementations, the programmer does |
| * <i>not</i> have to provide an iterator implementation; the iterator and |
| * list iterator are implemented by this class, on top of the "random access" |
| * methods: |
| * {@link #get(int)}, |
| * {@link #set(int, Object) set(int, E)}, |
| * {@link #add(int, Object) add(int, E)} and |
| * {@link #remove(int)}. |
| * |
| * <p>The documentation for each non-abstract method in this class describes its |
| * implementation in detail. Each of these methods may be overridden if the |
| * collection being implemented admits a more efficient implementation. |
| * |
| * <p>This class is a member of the |
| * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework"> |
| * Java Collections Framework</a>. |
| * |
| * @author Josh Bloch |
| * @author Neal Gafter |
| * @since 1.2 |
| */ |
| |
| public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { |
| /** |
| * Sole constructor. (For invocation by subclass constructors, typically |
| * implicit.) |
| */ |
| protected AbstractList() { |
| } |
| |
| /** |
| * Appends the specified element to the end of this list (optional |
| * operation). |
| * |
| * <p>Lists that support this operation may place limitations on what |
| * elements may be added to this list. In particular, some |
| * lists will refuse to add null elements, and others will impose |
| * restrictions on the type of elements that may be added. List |
| * classes should clearly specify in their documentation any restrictions |
| * on what elements may be added. |
| * |
| * @implSpec |
| * This implementation calls {@code add(size(), e)}. |
| * |
| * <p>Note that this implementation throws an |
| * {@code UnsupportedOperationException} unless |
| * {@link #add(int, Object) add(int, E)} is overridden. |
| * |
| * @param e element to be appended to this list |
| * @return {@code true} (as specified by {@link Collection#add}) |
| * @throws UnsupportedOperationException if the {@code add} operation |
| * is not supported by this list |
| * @throws ClassCastException if the class of the specified element |
| * prevents it from being added to this list |
| * @throws NullPointerException if the specified element is null and this |
| * list does not permit null elements |
| * @throws IllegalArgumentException if some property of this element |
| * prevents it from being added to this list |
| */ |
| public boolean add(E e) { |
| add(size(), e); |
| return true; |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public abstract E get(int index); |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation always throws an |
| * {@code UnsupportedOperationException}. |
| * |
| * @throws UnsupportedOperationException {@inheritDoc} |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException {@inheritDoc} |
| * @throws IllegalArgumentException {@inheritDoc} |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public E set(int index, E element) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation always throws an |
| * {@code UnsupportedOperationException}. |
| * |
| * @throws UnsupportedOperationException {@inheritDoc} |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException {@inheritDoc} |
| * @throws IllegalArgumentException {@inheritDoc} |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public void add(int index, E element) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation always throws an |
| * {@code UnsupportedOperationException}. |
| * |
| * @throws UnsupportedOperationException {@inheritDoc} |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public E remove(int index) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| |
| // Search Operations |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation first gets a list iterator (with |
| * {@code listIterator()}). Then, it iterates over the list until the |
| * specified element is found or the end of the list is reached. |
| * |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException {@inheritDoc} |
| */ |
| public int indexOf(Object o) { |
| ListIterator<E> it = listIterator(); |
| if (o==null) { |
| while (it.hasNext()) |
| if (it.next()==null) |
| return it.previousIndex(); |
| } else { |
| while (it.hasNext()) |
| if (o.equals(it.next())) |
| return it.previousIndex(); |
| } |
| return -1; |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation first gets a list iterator that points to the end |
| * of the list (with {@code listIterator(size())}). Then, it iterates |
| * backwards over the list until the specified element is found, or the |
| * beginning of the list is reached. |
| * |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException {@inheritDoc} |
| */ |
| public int lastIndexOf(Object o) { |
| ListIterator<E> it = listIterator(size()); |
| if (o==null) { |
| while (it.hasPrevious()) |
| if (it.previous()==null) |
| return it.nextIndex(); |
| } else { |
| while (it.hasPrevious()) |
| if (o.equals(it.previous())) |
| return it.nextIndex(); |
| } |
| return -1; |
| } |
| |
| |
| // Bulk Operations |
| |
| /** |
| * Removes all of the elements from this list (optional operation). |
| * The list will be empty after this call returns. |
| * |
| * @implSpec |
| * This implementation calls {@code removeRange(0, size())}. |
| * |
| * <p>Note that this implementation throws an |
| * {@code UnsupportedOperationException} unless {@code remove(int |
| * index)} or {@code removeRange(int fromIndex, int toIndex)} is |
| * overridden. |
| * |
| * @throws UnsupportedOperationException if the {@code clear} operation |
| * is not supported by this list |
| */ |
| public void clear() { |
| removeRange(0, size()); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation gets an iterator over the specified collection |
| * and iterates over it, inserting the elements obtained from the |
| * iterator into this list at the appropriate position, one at a time, |
| * using {@code add(int, E)}. |
| * Many implementations will override this method for efficiency. |
| * |
| * <p>Note that this implementation throws an |
| * {@code UnsupportedOperationException} unless |
| * {@link #add(int, Object) add(int, E)} is overridden. |
| * |
| * @throws UnsupportedOperationException {@inheritDoc} |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException {@inheritDoc} |
| * @throws IllegalArgumentException {@inheritDoc} |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public boolean addAll(int index, Collection<? extends E> c) { |
| rangeCheckForAdd(index); |
| boolean modified = false; |
| for (E e : c) { |
| add(index++, e); |
| modified = true; |
| } |
| return modified; |
| } |
| |
| |
| // Iterators |
| |
| /** |
| * Returns an iterator over the elements in this list in proper sequence. |
| * |
| * @implSpec |
| * This implementation returns a straightforward implementation of the |
| * iterator interface, relying on the backing list's {@code size()}, |
| * {@code get(int)}, and {@code remove(int)} methods. |
| * |
| * <p>Note that the iterator returned by this method will throw an |
| * {@link UnsupportedOperationException} in response to its |
| * {@code remove} method unless the list's {@code remove(int)} method is |
| * overridden. |
| * |
| * <p>This implementation can be made to throw runtime exceptions in the |
| * face of concurrent modification, as described in the specification |
| * for the (protected) {@link #modCount} field. |
| * |
| * @return an iterator over the elements in this list in proper sequence |
| */ |
| public Iterator<E> iterator() { |
| return new Itr(); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation returns {@code listIterator(0)}. |
| * |
| * @see #listIterator(int) |
| */ |
| public ListIterator<E> listIterator() { |
| return listIterator(0); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation returns a straightforward implementation of the |
| * {@code ListIterator} interface that extends the implementation of the |
| * {@code Iterator} interface returned by the {@code iterator()} method. |
| * The {@code ListIterator} implementation relies on the backing list's |
| * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)} |
| * and {@code remove(int)} methods. |
| * |
| * <p>Note that the list iterator returned by this implementation will |
| * throw an {@link UnsupportedOperationException} in response to its |
| * {@code remove}, {@code set} and {@code add} methods unless the |
| * list's {@code remove(int)}, {@code set(int, E)}, and |
| * {@code add(int, E)} methods are overridden. |
| * |
| * <p>This implementation can be made to throw runtime exceptions in the |
| * face of concurrent modification, as described in the specification for |
| * the (protected) {@link #modCount} field. |
| * |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public ListIterator<E> listIterator(final int index) { |
| rangeCheckForAdd(index); |
| |
| return new ListItr(index); |
| } |
| |
| private class Itr implements Iterator<E> { |
| /** |
| * Index of element to be returned by subsequent call to next. |
| */ |
| int cursor = 0; |
| |
| /** |
| * Index of element returned by most recent call to next or |
| * previous. Reset to -1 if this element is deleted by a call |
| * to remove. |
| */ |
| int lastRet = -1; |
| |
| /** |
| * The modCount value that the iterator believes that the backing |
| * List should have. If this expectation is violated, the iterator |
| * has detected concurrent modification. |
| */ |
| int expectedModCount = modCount; |
| |
| public boolean hasNext() { |
| return cursor != size(); |
| } |
| |
| public E next() { |
| checkForComodification(); |
| try { |
| int i = cursor; |
| E next = get(i); |
| lastRet = i; |
| cursor = i + 1; |
| return next; |
| } catch (IndexOutOfBoundsException e) { |
| checkForComodification(); |
| throw new NoSuchElementException(); |
| } |
| } |
| |
| public void remove() { |
| if (lastRet < 0) |
| throw new IllegalStateException(); |
| checkForComodification(); |
| |
| try { |
| AbstractList.this.remove(lastRet); |
| if (lastRet < cursor) |
| cursor--; |
| lastRet = -1; |
| expectedModCount = modCount; |
| } catch (IndexOutOfBoundsException e) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| final void checkForComodification() { |
| if (modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| private class ListItr extends Itr implements ListIterator<E> { |
| ListItr(int index) { |
| cursor = index; |
| } |
| |
| public boolean hasPrevious() { |
| return cursor != 0; |
| } |
| |
| public E previous() { |
| checkForComodification(); |
| try { |
| int i = cursor - 1; |
| E previous = get(i); |
| lastRet = cursor = i; |
| return previous; |
| } catch (IndexOutOfBoundsException e) { |
| checkForComodification(); |
| throw new NoSuchElementException(); |
| } |
| } |
| |
| public int nextIndex() { |
| return cursor; |
| } |
| |
| public int previousIndex() { |
| return cursor-1; |
| } |
| |
| public void set(E e) { |
| if (lastRet < 0) |
| throw new IllegalStateException(); |
| checkForComodification(); |
| |
| try { |
| AbstractList.this.set(lastRet, e); |
| expectedModCount = modCount; |
| } catch (IndexOutOfBoundsException ex) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| public void add(E e) { |
| checkForComodification(); |
| |
| try { |
| int i = cursor; |
| AbstractList.this.add(i, e); |
| lastRet = -1; |
| cursor = i + 1; |
| expectedModCount = modCount; |
| } catch (IndexOutOfBoundsException ex) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @implSpec |
| * This implementation returns a list that subclasses |
| * {@code AbstractList}. The subclass stores, in private fields, the |
| * size of the subList (which can change over its lifetime), and the |
| * expected {@code modCount} value of the backing list. There are two |
| * variants of the subclass, one of which implements {@code RandomAccess}. |
| * If this list implements {@code RandomAccess} the returned list will |
| * be an instance of the subclass that implements {@code RandomAccess}. |
| * |
| * <p>The subclass's {@code set(int, E)}, {@code get(int)}, |
| * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int, |
| * Collection)} and {@code removeRange(int, int)} methods all |
| * delegate to the corresponding methods on the backing abstract list, |
| * after bounds-checking the index and adjusting for the offset. The |
| * {@code addAll(Collection c)} method merely returns {@code addAll(size, |
| * c)}. |
| * |
| * <p>The {@code listIterator(int)} method returns a "wrapper object" |
| * over a list iterator on the backing list, which is created with the |
| * corresponding method on the backing list. The {@code iterator} method |
| * merely returns {@code listIterator()}, and the {@code size} method |
| * merely returns the subclass's {@code size} field. |
| * |
| * <p>All methods first check to see if the actual {@code modCount} of |
| * the backing list is equal to its expected value, and throw a |
| * {@code ConcurrentModificationException} if it is not. |
| * |
| * @throws IndexOutOfBoundsException if an endpoint index value is out of range |
| * {@code (fromIndex < 0 || toIndex > size)} |
| * @throws IllegalArgumentException if the endpoint indices are out of order |
| * {@code (fromIndex > toIndex)} |
| */ |
| public List<E> subList(int fromIndex, int toIndex) { |
| subListRangeCheck(fromIndex, toIndex, size()); |
| return (this instanceof RandomAccess ? |
| new RandomAccessSubList<>(this, fromIndex, toIndex) : |
| new SubList<>(this, fromIndex, toIndex)); |
| } |
| |
| static void subListRangeCheck(int fromIndex, int toIndex, int size) { |
| if (fromIndex < 0) |
| throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); |
| if (toIndex > size) |
| throw new IndexOutOfBoundsException("toIndex = " + toIndex); |
| if (fromIndex > toIndex) |
| throw new IllegalArgumentException("fromIndex(" + fromIndex + |
| ") > toIndex(" + toIndex + ")"); |
| } |
| |
| // Comparison and hashing |
| |
| /** |
| * Compares the specified object with this list for equality. Returns |
| * {@code true} if and only if the specified object is also a list, both |
| * lists have the same size, and all corresponding pairs of elements in |
| * the two lists are <i>equal</i>. (Two elements {@code e1} and |
| * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null : |
| * e1.equals(e2))}.) In other words, two lists are defined to be |
| * equal if they contain the same elements in the same order. |
| * |
| * @implSpec |
| * This implementation first checks if the specified object is this |
| * list. If so, it returns {@code true}; if not, it checks if the |
| * specified object is a list. If not, it returns {@code false}; if so, |
| * it iterates over both lists, comparing corresponding pairs of elements. |
| * If any comparison returns {@code false}, this method returns |
| * {@code false}. If either iterator runs out of elements before the |
| * other it returns {@code false} (as the lists are of unequal length); |
| * otherwise it returns {@code true} when the iterations complete. |
| * |
| * @param o the object to be compared for equality with this list |
| * @return {@code true} if the specified object is equal to this list |
| */ |
| public boolean equals(Object o) { |
| if (o == this) |
| return true; |
| if (!(o instanceof List)) |
| return false; |
| |
| ListIterator<E> e1 = listIterator(); |
| ListIterator<?> e2 = ((List<?>) o).listIterator(); |
| while (e1.hasNext() && e2.hasNext()) { |
| E o1 = e1.next(); |
| Object o2 = e2.next(); |
| if (!(o1==null ? o2==null : o1.equals(o2))) |
| return false; |
| } |
| return !(e1.hasNext() || e2.hasNext()); |
| } |
| |
| /** |
| * Returns the hash code value for this list. |
| * |
| * @implSpec |
| * This implementation uses exactly the code that is used to define the |
| * list hash function in the documentation for the {@link List#hashCode} |
| * method. |
| * |
| * @return the hash code value for this list |
| */ |
| public int hashCode() { |
| int hashCode = 1; |
| for (E e : this) |
| hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); |
| return hashCode; |
| } |
| |
| /** |
| * Removes from this list all of the elements whose index is between |
| * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. |
| * Shifts any succeeding elements to the left (reduces their index). |
| * This call shortens the list by {@code (toIndex - fromIndex)} elements. |
| * (If {@code toIndex==fromIndex}, this operation has no effect.) |
| * |
| * <p>This method is called by the {@code clear} operation on this list |
| * and its subLists. Overriding this method to take advantage of |
| * the internals of the list implementation can <i>substantially</i> |
| * improve the performance of the {@code clear} operation on this list |
| * and its subLists. |
| * |
| * @implSpec |
| * This implementation gets a list iterator positioned before |
| * {@code fromIndex}, and repeatedly calls {@code ListIterator.next} |
| * followed by {@code ListIterator.remove} until the entire range has |
| * been removed. <b>Note: if {@code ListIterator.remove} requires linear |
| * time, this implementation requires quadratic time.</b> |
| * |
| * @param fromIndex index of first element to be removed |
| * @param toIndex index after last element to be removed |
| */ |
| protected void removeRange(int fromIndex, int toIndex) { |
| ListIterator<E> it = listIterator(fromIndex); |
| for (int i=0, n=toIndex-fromIndex; i<n; i++) { |
| it.next(); |
| it.remove(); |
| } |
| } |
| |
| /** |
| * The number of times this list has been <i>structurally modified</i>. |
| * Structural modifications are those that change the size of the |
| * list, or otherwise perturb it in such a fashion that iterations in |
| * progress may yield incorrect results. |
| * |
| * <p>This field is used by the iterator and list iterator implementation |
| * returned by the {@code iterator} and {@code listIterator} methods. |
| * If the value of this field changes unexpectedly, the iterator (or list |
| * iterator) will throw a {@code ConcurrentModificationException} in |
| * response to the {@code next}, {@code remove}, {@code previous}, |
| * {@code set} or {@code add} operations. This provides |
| * <i>fail-fast</i> behavior, rather than non-deterministic behavior in |
| * the face of concurrent modification during iteration. |
| * |
| * <p><b>Use of this field by subclasses is optional.</b> If a subclass |
| * wishes to provide fail-fast iterators (and list iterators), then it |
| * merely has to increment this field in its {@code add(int, E)} and |
| * {@code remove(int)} methods (and any other methods that it overrides |
| * that result in structural modifications to the list). A single call to |
| * {@code add(int, E)} or {@code remove(int)} must add no more than |
| * one to this field, or the iterators (and list iterators) will throw |
| * bogus {@code ConcurrentModificationExceptions}. If an implementation |
| * does not wish to provide fail-fast iterators, this field may be |
| * ignored. |
| */ |
| protected transient int modCount = 0; |
| |
| private void rangeCheckForAdd(int index) { |
| if (index < 0 || index > size()) |
| throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
| } |
| |
| private String outOfBoundsMsg(int index) { |
| return "Index: "+index+", Size: "+size(); |
| } |
| |
| /** |
| * An index-based split-by-two, lazily initialized Spliterator covering |
| * a List that access elements via {@link List#get}. |
| * |
| * If access results in an IndexOutOfBoundsException then a |
| * ConcurrentModificationException is thrown instead (since the list has |
| * been structurally modified while traversing). |
| * |
| * If the List is an instance of AbstractList then concurrent modification |
| * checking is performed using the AbstractList's modCount field. |
| */ |
| static final class RandomAccessSpliterator<E> implements Spliterator<E> { |
| |
| private final List<E> list; |
| private int index; // current index, modified on advance/split |
| private int fence; // -1 until used; then one past last index |
| |
| // The following fields are valid if covering an AbstractList |
| private final AbstractList<E> alist; |
| private int expectedModCount; // initialized when fence set |
| |
| RandomAccessSpliterator(List<E> list) { |
| assert list instanceof RandomAccess; |
| |
| this.list = list; |
| this.index = 0; |
| this.fence = -1; |
| |
| this.alist = list instanceof AbstractList ? (AbstractList<E>) list : null; |
| this.expectedModCount = alist != null ? alist.modCount : 0; |
| } |
| |
| /** Create new spliterator covering the given range */ |
| private RandomAccessSpliterator(RandomAccessSpliterator<E> parent, |
| int origin, int fence) { |
| this.list = parent.list; |
| this.index = origin; |
| this.fence = fence; |
| |
| this.alist = parent.alist; |
| this.expectedModCount = parent.expectedModCount; |
| } |
| |
| private int getFence() { // initialize fence to size on first use |
| int hi; |
| List<E> lst = list; |
| if ((hi = fence) < 0) { |
| if (alist != null) { |
| expectedModCount = alist.modCount; |
| } |
| hi = fence = lst.size(); |
| } |
| return hi; |
| } |
| |
| public Spliterator<E> trySplit() { |
| int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
| return (lo >= mid) ? null : // divide range in half unless too small |
| new RandomAccessSpliterator<>(this, lo, index = mid); |
| } |
| |
| public boolean tryAdvance(Consumer<? super E> action) { |
| if (action == null) |
| throw new NullPointerException(); |
| int hi = getFence(), i = index; |
| if (i < hi) { |
| index = i + 1; |
| action.accept(get(list, i)); |
| checkAbstractListModCount(alist, expectedModCount); |
| return true; |
| } |
| return false; |
| } |
| |
| public void forEachRemaining(Consumer<? super E> action) { |
| Objects.requireNonNull(action); |
| List<E> lst = list; |
| int hi = getFence(); |
| int i = index; |
| index = hi; |
| for (; i < hi; i++) { |
| action.accept(get(lst, i)); |
| } |
| checkAbstractListModCount(alist, expectedModCount); |
| } |
| |
| public long estimateSize() { |
| return (long) (getFence() - index); |
| } |
| |
| public int characteristics() { |
| return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; |
| } |
| |
| private static <E> E get(List<E> list, int i) { |
| try { |
| return list.get(i); |
| } catch (IndexOutOfBoundsException ex) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| static void checkAbstractListModCount(AbstractList<?> alist, int expectedModCount) { |
| if (alist != null && alist.modCount != expectedModCount) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| } |
| |
| private static class SubList<E> extends AbstractList<E> { |
| private final AbstractList<E> root; |
| private final SubList<E> parent; |
| private final int offset; |
| protected int size; |
| |
| /** |
| * Constructs a sublist of an arbitrary AbstractList, which is |
| * not a SubList itself. |
| */ |
| public SubList(AbstractList<E> root, int fromIndex, int toIndex) { |
| this.root = root; |
| this.parent = null; |
| this.offset = fromIndex; |
| this.size = toIndex - fromIndex; |
| this.modCount = root.modCount; |
| } |
| |
| /** |
| * Constructs a sublist of another SubList. |
| */ |
| protected SubList(SubList<E> parent, int fromIndex, int toIndex) { |
| this.root = parent.root; |
| this.parent = parent; |
| this.offset = parent.offset + fromIndex; |
| this.size = toIndex - fromIndex; |
| this.modCount = root.modCount; |
| } |
| |
| public E set(int index, E element) { |
| Objects.checkIndex(index, size); |
| checkForComodification(); |
| return root.set(offset + index, element); |
| } |
| |
| public E get(int index) { |
| Objects.checkIndex(index, size); |
| checkForComodification(); |
| return root.get(offset + index); |
| } |
| |
| public int size() { |
| checkForComodification(); |
| return size; |
| } |
| |
| public void add(int index, E element) { |
| rangeCheckForAdd(index); |
| checkForComodification(); |
| root.add(offset + index, element); |
| updateSizeAndModCount(1); |
| } |
| |
| public E remove(int index) { |
| Objects.checkIndex(index, size); |
| checkForComodification(); |
| E result = root.remove(offset + index); |
| updateSizeAndModCount(-1); |
| return result; |
| } |
| |
| protected void removeRange(int fromIndex, int toIndex) { |
| checkForComodification(); |
| root.removeRange(offset + fromIndex, offset + toIndex); |
| updateSizeAndModCount(fromIndex - toIndex); |
| } |
| |
| public boolean addAll(Collection<? extends E> c) { |
| return addAll(size, c); |
| } |
| |
| public boolean addAll(int index, Collection<? extends E> c) { |
| rangeCheckForAdd(index); |
| int cSize = c.size(); |
| if (cSize==0) |
| return false; |
| checkForComodification(); |
| root.addAll(offset + index, c); |
| updateSizeAndModCount(cSize); |
| return true; |
| } |
| |
| public Iterator<E> iterator() { |
| return listIterator(); |
| } |
| |
| public ListIterator<E> listIterator(int index) { |
| checkForComodification(); |
| rangeCheckForAdd(index); |
| |
| return new ListIterator<E>() { |
| private final ListIterator<E> i = |
| root.listIterator(offset + index); |
| |
| public boolean hasNext() { |
| return nextIndex() < size; |
| } |
| |
| public E next() { |
| if (hasNext()) |
| return i.next(); |
| else |
| throw new NoSuchElementException(); |
| } |
| |
| public boolean hasPrevious() { |
| return previousIndex() >= 0; |
| } |
| |
| public E previous() { |
| if (hasPrevious()) |
| return i.previous(); |
| else |
| throw new NoSuchElementException(); |
| } |
| |
| public int nextIndex() { |
| return i.nextIndex() - offset; |
| } |
| |
| public int previousIndex() { |
| return i.previousIndex() - offset; |
| } |
| |
| public void remove() { |
| i.remove(); |
| updateSizeAndModCount(-1); |
| } |
| |
| public void set(E e) { |
| i.set(e); |
| } |
| |
| public void add(E e) { |
| i.add(e); |
| updateSizeAndModCount(1); |
| } |
| }; |
| } |
| |
| public List<E> subList(int fromIndex, int toIndex) { |
| subListRangeCheck(fromIndex, toIndex, size); |
| return new SubList<>(this, fromIndex, toIndex); |
| } |
| |
| private void rangeCheckForAdd(int index) { |
| if (index < 0 || index > size) |
| throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
| } |
| |
| private String outOfBoundsMsg(int index) { |
| return "Index: "+index+", Size: "+size; |
| } |
| |
| private void checkForComodification() { |
| if (root.modCount != this.modCount) |
| throw new ConcurrentModificationException(); |
| } |
| |
| private void updateSizeAndModCount(int sizeChange) { |
| SubList<E> slist = this; |
| do { |
| slist.size += sizeChange; |
| slist.modCount = root.modCount; |
| slist = slist.parent; |
| } while (slist != null); |
| } |
| } |
| |
| private static class RandomAccessSubList<E> |
| extends SubList<E> implements RandomAccess { |
| |
| /** |
| * Constructs a sublist of an arbitrary AbstractList, which is |
| * not a RandomAccessSubList itself. |
| */ |
| RandomAccessSubList(AbstractList<E> root, |
| int fromIndex, int toIndex) { |
| super(root, fromIndex, toIndex); |
| } |
| |
| /** |
| * Constructs a sublist of another RandomAccessSubList. |
| */ |
| RandomAccessSubList(RandomAccessSubList<E> parent, |
| int fromIndex, int toIndex) { |
| super(parent, fromIndex, toIndex); |
| } |
| |
| public List<E> subList(int fromIndex, int toIndex) { |
| subListRangeCheck(fromIndex, toIndex, size); |
| return new RandomAccessSubList<>(this, fromIndex, toIndex); |
| } |
| } |
| } |