src/java.base/share/classes/java/util/AbstractList.java
Print this page
rev 11824 : [mq]: 8079136-NestedSubList
*** 491,706 ****
* {@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) {
return (this instanceof RandomAccess ?
! new RandomAccessSubList<>(this, fromIndex, toIndex) :
! new SubList<>(this, fromIndex, 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();
! }
! }
!
! class SubList<E> extends AbstractList<E> {
! private final AbstractList<E> l;
! private final int offset;
! private int size;
!
! SubList(AbstractList<E> list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
! if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
! l = list;
! offset = fromIndex;
! size = toIndex - fromIndex;
! this.modCount = l.modCount;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
! return l.set(index+offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
! return l.get(index+offset);
}
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
! l.add(index+offset, element);
! this.modCount = l.modCount;
! size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
! E result = l.remove(index+offset);
! this.modCount = l.modCount;
! size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
! l.removeRange(fromIndex+offset, toIndex+offset);
! this.modCount = l.modCount;
! size -= (toIndex-fromIndex);
}
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();
! l.addAll(offset+index, c);
! this.modCount = l.modCount;
! size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
--- 491,582 ----
* {@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, 0, fromIndex, toIndex) :
! new SubList(this, 0, 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 + ")");
! }
!
! private class SubList extends AbstractList<E> {
! final AbstractList<E> parent;
! final int offset;
! int size;
!
! SubList(AbstractList<E> parent,
! int offset, int fromIndex, int toIndex) {
! this.parent = parent;
! this.offset = offset + fromIndex;
! this.size = toIndex - fromIndex;
! this.modCount = AbstractList.this.modCount;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
! return AbstractList.this.set(index + offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
! return AbstractList.this.get(index + offset);
}
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
! AbstractList.this.add(index + offset, element);
! updateSizeAndModCount(1, AbstractList.this.modCount);
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
! E result = AbstractList.this.remove(index + offset);
! updateSizeAndModCount(-1, AbstractList.this.modCount);
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
! AbstractList.this.removeRange(offset + fromIndex,
! offset + toIndex);
! updateSizeAndModCount(fromIndex - toIndex,
! AbstractList.this.modCount);
}
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();
! AbstractList.this.addAll(offset + index, c);
! updateSizeAndModCount(cSize,
! AbstractList.this.modCount);
return true;
}
public Iterator<E> iterator() {
return listIterator();
*** 709,719 ****
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
! private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
--- 585,596 ----
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
! private final ListIterator<E> i =
! AbstractList.this.listIterator(offset + index);
public boolean hasNext() {
return nextIndex() < size;
}
*** 743,770 ****
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
! SubList.this.modCount = l.modCount;
! size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
! SubList.this.modCount = l.modCount;
! size++;
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
! return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
--- 620,649 ----
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
! updateSizeAndModCount(-1,
! AbstractList.this.modCount);
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
! updateSizeAndModCount(1,
! AbstractList.this.modCount);
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
! subListRangeCheck(fromIndex, toIndex, size);
! return AbstractList.this.new SubList(this, offset, fromIndex,
! toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
*** 774,796 ****
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
! return "Index: "+index+", Size: "+size;
}
private void checkForComodification() {
! if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
- }
! class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
! RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
! super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
! return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}
--- 653,815 ----
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
! return "Index: " + index + ", Size: " + size;
}
private void checkForComodification() {
! if (AbstractList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
! private void updateSizeAndModCount(int sizeChange, int modCount) {
! AbstractList<E> alist = this;
! do {
! SubList slist = (SubList)alist;
! slist.size += sizeChange;
! slist.modCount = modCount;
! alist = slist.parent;
! } while (alist instanceof AbstractList.SubList);
! }
! }
!
! private class RandomAccessSubList extends SubList implements RandomAccess {
! RandomAccessSubList(AbstractList<E> list, int offset,
! int fromIndex, int toIndex) {
! super(list, offset, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
! subListRangeCheck(fromIndex, toIndex, size);
! return AbstractList.this.new RandomAccessSubList(this, offset,
! fromIndex, 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();
}
}