src/java.base/share/classes/java/util/AbstractList.java
Print this page
rev 11824 : [mq]: 8079136-NestedSubList
@@ -491,216 +491,92 @@
* {@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));
+ new RandomAccessSubList(this, 0, fromIndex, toIndex) :
+ new SubList(this, 0, 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) {
+ static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
- if (toIndex > list.size())
+ if (toIndex > 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;
+ }
+
+ 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 l.set(index+offset, element);
+ return AbstractList.this.set(index + offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
- return l.get(index+offset);
+ return AbstractList.this.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++;
+ AbstractList.this.add(index + offset, element);
+ updateSizeAndModCount(1, AbstractList.this.modCount);
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
- E result = l.remove(index+offset);
- this.modCount = l.modCount;
- size--;
+ E result = AbstractList.this.remove(index + offset);
+ updateSizeAndModCount(-1, AbstractList.this.modCount);
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
- l.removeRange(fromIndex+offset, toIndex+offset);
- this.modCount = l.modCount;
- size -= (toIndex-fromIndex);
+ 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)
+ if (cSize == 0)
return false;
-
checkForComodification();
- l.addAll(offset+index, c);
- this.modCount = l.modCount;
- size += cSize;
+ AbstractList.this.addAll(offset + index, c);
+ updateSizeAndModCount(cSize,
+ AbstractList.this.modCount);
return true;
}
public Iterator<E> iterator() {
return listIterator();
@@ -709,11 +585,12 @@
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
- private final ListIterator<E> i = l.listIterator(index+offset);
+ private final ListIterator<E> i =
+ AbstractList.this.listIterator(offset + index);
public boolean hasNext() {
return nextIndex() < size;
}
@@ -743,28 +620,30 @@
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
- SubList.this.modCount = l.modCount;
- size--;
+ updateSizeAndModCount(-1,
+ AbstractList.this.modCount);
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
- SubList.this.modCount = l.modCount;
- size++;
+ updateSizeAndModCount(1,
+ AbstractList.this.modCount);
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
- return new SubList<>(this, fromIndex, 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,23 +653,163 @@
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
- return "Index: "+index+", Size: "+size;
+ return "Index: " + index + ", Size: " + size;
}
private void checkForComodification() {
- if (this.modCount != l.modCount)
+ if (AbstractList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
-}
-class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
- RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
- super(list, fromIndex, toIndex);
+ 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) {
- return new RandomAccessSubList<>(this, fromIndex, 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();
}
}