< prev index next >
src/java.base/share/classes/java/util/ArrayList.java
Print this page
rev 13964 : [mq]: 8079136-Nested-SubLists
@@ -430,12 +430,11 @@
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
- rangeCheck(index);
-
+ Objects.checkIndex(index, size);
return elementData(index);
}
/**
* Replaces the element at the specified position in this list with
@@ -445,12 +444,11 @@
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
- rangeCheck(index);
-
+ Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
@@ -509,11 +507,11 @@
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
- rangeCheck(index);
+ Objects.checkIndex(index, size);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
@@ -678,21 +676,10 @@
}
size = newSize;
}
/**
- * Checks if the given index is in range. If not, throws an appropriate
- * runtime exception. This method does *not* check if the index is
- * negative: It is always used immediately prior to an array access,
- * which throws an ArrayIndexOutOfBoundsException if index is negative.
- */
- private void rangeCheck(int index) {
- if (index >= size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
- /**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
@@ -852,12 +839,11 @@
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ListIterator<E> listIterator(int index) {
- if (index < 0 || index > size)
- throw new IndexOutOfBoundsException("Index: "+index);
+ rangeCheckForAdd(index);
return new ListItr(index);
}
/**
* Returns a list iterator over the elements in this list (in proper
@@ -1040,80 +1026,79 @@
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
- return new SubList(this, 0, fromIndex, toIndex);
+ return 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 + ")");
- }
-
- private class SubList extends AbstractList<E> implements RandomAccess {
- private final AbstractList<E> parent;
- private final int parentOffset;
+ private static class SubList<E> extends AbstractList<E> implements RandomAccess {
+ private final ArrayList<E> root;
+ private final SubList<E> parent;
private final int offset;
- int size;
+ private int size;
- SubList(AbstractList<E> parent,
- int offset, int fromIndex, int toIndex) {
+ /**
+ * Constructs a sublist of an arbitrary ArrayList.
+ */
+ public SubList(ArrayList<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.
+ */
+ private SubList(SubList<E> parent, int fromIndex, int toIndex) {
+ this.root = parent.root;
this.parent = parent;
- this.parentOffset = fromIndex;
- this.offset = offset + fromIndex;
+ this.offset = parent.offset + fromIndex;
this.size = toIndex - fromIndex;
- this.modCount = ArrayList.this.modCount;
+ this.modCount = root.modCount;
}
- public E set(int index, E e) {
- rangeCheck(index);
+ public E set(int index, E element) {
+ Objects.checkIndex(index, size);
checkForComodification();
- E oldValue = ArrayList.this.elementData(offset + index);
- ArrayList.this.elementData[offset + index] = e;
+ E oldValue = root.elementData(offset + index);
+ root.elementData[offset + index] = element;
return oldValue;
}
public E get(int index) {
- rangeCheck(index);
+ Objects.checkIndex(index, size);
checkForComodification();
- return ArrayList.this.elementData(offset + index);
+ return root.elementData(offset + index);
}
public int size() {
checkForComodification();
- return this.size;
+ return size;
}
- public void add(int index, E e) {
+ public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
- parent.add(parentOffset + index, e);
- this.modCount = parent.modCount;
- this.size++;
+ root.add(offset + index, element);
+ updateSizeAndModCount(1);
}
public E remove(int index) {
- rangeCheck(index);
+ Objects.checkIndex(index, size);
checkForComodification();
- E result = parent.remove(parentOffset + index);
- this.modCount = parent.modCount;
- this.size--;
+ E result = root.remove(offset + index);
+ updateSizeAndModCount(-1);
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
- parent.removeRange(parentOffset + fromIndex,
- parentOffset + toIndex);
- this.modCount = parent.modCount;
- this.size -= toIndex - fromIndex;
+ root.removeRange(offset + fromIndex, offset + toIndex);
+ updateSizeAndModCount(fromIndex - toIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
@@ -1121,31 +1106,28 @@
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
-
checkForComodification();
- parent.addAll(parentOffset + index, c);
- this.modCount = parent.modCount;
- this.size += cSize;
+ root.addAll(offset + index, c);
+ updateSizeAndModCount(cSize);
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
- public ListIterator<E> listIterator(final int index) {
+ public ListIterator<E> listIterator(int index) {
checkForComodification();
rangeCheckForAdd(index);
- final int offset = this.offset;
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
- int expectedModCount = ArrayList.this.modCount;
+ int expectedModCount = root.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@@ -1153,11 +1135,11 @@
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
- Object[] elementData = ArrayList.this.elementData;
+ Object[] elementData = root.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
@@ -1170,11 +1152,11 @@
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
- Object[] elementData = ArrayList.this.elementData;
+ Object[] elementData = root.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@@ -1185,11 +1167,11 @@
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
- final Object[] elementData = ArrayList.this.elementData;
+ final Object[] elementData = root.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
@@ -1214,11 +1196,11 @@
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
- expectedModCount = ArrayList.this.modCount;
+ expectedModCount = root.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@@ -1226,11 +1208,11 @@
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
- ArrayList.this.set(offset + lastRet, e);
+ root.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@@ -1240,31 +1222,26 @@
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
- expectedModCount = ArrayList.this.modCount;
+ expectedModCount = root.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
- if (expectedModCount != ArrayList.this.modCount)
+ if (root.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
- return new SubList(this, offset, fromIndex, toIndex);
- }
-
- private void rangeCheck(int index) {
- if (index < 0 || index >= this.size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
@@ -1273,14 +1250,23 @@
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
}
private void checkForComodification() {
- if (ArrayList.this.modCount != this.modCount)
+ if (root.modCount != 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);
+ }
+
public Spliterator<E> spliterator() {
checkForComodification();
return new Spliterator<>() {
private int index = offset; // current index, modified on advance/split
@@ -1297,32 +1283,32 @@
}
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
- new ArrayListSpliterator<>(ArrayList.this, lo, index = mid,
+ new ArrayListSpliterator<>(root, lo, index = mid,
expectedModCount);
}
public boolean tryAdvance(Consumer<? super E> action) {
Objects.requireNonNull(action);
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
- @SuppressWarnings("unchecked") E e = (E)elementData[i];
+ @SuppressWarnings("unchecked") E e = (E)root.elementData[i];
action.accept(e);
- if (ArrayList.this.modCount != expectedModCount)
+ if (root.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
int i, hi, mc; // hoist accesses and checks from loop
- ArrayList<E> lst = ArrayList.this;
+ ArrayList<E> lst = root;
Object[] a;
if ((a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = modCount;
hi = offset + size;
< prev index next >