--- a/jdk/src/java.base/share/classes/java/util/AbstractList.java Thu Mar 31 06:30:39 2016 +0100
+++ b/jdk/src/java.base/share/classes/java/util/AbstractList.java Thu Mar 31 17:30:31 2016 +0300
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * 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
@@ -462,10 +462,9 @@
* @implSpec
* This implementation returns a list that subclasses
* {@code AbstractList}. The subclass stores, in private fields, the
- * offset of the subList within the backing list, 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}.
+ * 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}.
*
@@ -493,11 +492,22 @@
* {@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
/**
@@ -623,174 +633,199 @@
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size();
}
-}
+
+ 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;
-class SubList<E> extends AbstractList<E> {
- private final AbstractList<E> l;
- private final int offset;
- private 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);
+ }
- 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 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 set(int index, E element) {
- rangeCheck(index);
- checkForComodification();
- return l.set(index+offset, element);
- }
+ 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 E get(int index) {
- rangeCheck(index);
- checkForComodification();
- return l.get(index+offset);
- }
+ public boolean addAll(Collection<? extends E> c) {
+ return addAll(size, c);
+ }
- public int size() {
- checkForComodification();
- return size;
- }
+ 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 void add(int index, E element) {
- rangeCheckForAdd(index);
- checkForComodification();
- l.add(index+offset, element);
- this.modCount = l.modCount;
- size++;
- }
+ 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 remove(int index) {
- rangeCheck(index);
- checkForComodification();
- E result = l.remove(index+offset);
- this.modCount = l.modCount;
- size--;
- return result;
- }
+ 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;
+ }
- protected void removeRange(int fromIndex, int toIndex) {
- checkForComodification();
- l.removeRange(fromIndex+offset, toIndex+offset);
- this.modCount = l.modCount;
- size -= (toIndex-fromIndex);
- }
+ public void remove() {
+ i.remove();
+ updateSizeAndModCount(-1);
+ }
+
+ public void set(E e) {
+ i.set(e);
+ }
- public boolean addAll(Collection<? extends E> c) {
- return addAll(size, c);
- }
+ 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);
+ }
- public boolean addAll(int index, Collection<? extends E> c) {
- rangeCheckForAdd(index);
- int cSize = c.size();
- if (cSize==0)
- return false;
+ 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;
+ }
- checkForComodification();
- l.addAll(offset+index, c);
- this.modCount = l.modCount;
- size += cSize;
- return true;
- }
+ private void checkForComodification() {
+ if (root.modCount != this.modCount)
+ throw new ConcurrentModificationException();
+ }
- public Iterator<E> iterator() {
- return listIterator();
+ private void updateSizeAndModCount(int sizeChange) {
+ SubList<E> slist = this;
+ do {
+ slist.size += sizeChange;
+ slist.modCount = root.modCount;
+ slist = slist.parent;
+ } while (slist != null);
+ }
}
- 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;
- }
-
- public E next() {
- if (hasNext())
- return i.next();
- else
- throw new NoSuchElementException();
- }
+ private static class RandomAccessSubList<E>
+ extends SubList<E> implements RandomAccess {
- 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;
- }
+ /**
+ * 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);
+ }
- 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++;
- }
- };
- }
+ /**
+ * 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) {
- return new SubList<>(this, fromIndex, toIndex);
- }
-
- private void rangeCheck(int index) {
- if (index < 0 || index >= size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
- 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 (this.modCount != l.modCount)
- throw new ConcurrentModificationException();
+ public List<E> subList(int fromIndex, int toIndex) {
+ subListRangeCheck(fromIndex, toIndex, size);
+ return new RandomAccessSubList<>(this, fromIndex, toIndex);
+ }
}
}
-
-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);
- }
-}
--- a/jdk/src/java.base/share/classes/java/util/ArrayList.java Thu Mar 31 06:30:39 2016 +0100
+++ b/jdk/src/java.base/share/classes/java/util/ArrayList.java Thu Mar 31 17:30:31 2016 +0300
@@ -432,8 +432,7 @@
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
- rangeCheck(index);
-
+ Objects.checkIndex(index, size);
return elementData(index);
}
@@ -447,8 +446,7 @@
* @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;
@@ -511,7 +509,7 @@
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
- rangeCheck(index);
+ Objects.checkIndex(index, size);
modCount++;
E oldValue = elementData(index);
@@ -680,17 +678,6 @@
}
/**
- * 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) {
@@ -854,8 +841,7 @@
* @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);
}
@@ -1042,76 +1028,75 @@
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
- return 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 + ")");
+ return new SubList<>(this, fromIndex, 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) {
- this.parent = parent;
- this.parentOffset = fromIndex;
- this.offset = offset + fromIndex;
+ /**
+ * 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 = ArrayList.this.modCount;
+ this.modCount = root.modCount;
}
- public E set(int index, E e) {
- rangeCheck(index);
+ /**
+ * Constructs a sublist of another SubList.
+ */
+ private 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();
- 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) {
@@ -1123,11 +1108,9 @@
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;
}
@@ -1135,15 +1118,14 @@
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;
@@ -1155,7 +1137,7 @@
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;
@@ -1172,7 +1154,7 @@
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;
@@ -1187,7 +1169,7 @@
if (i >= size) {
return;
}
- final Object[] elementData = ArrayList.this.elementData;
+ final Object[] elementData = root.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
@@ -1216,7 +1198,7 @@
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
- expectedModCount = ArrayList.this.modCount;
+ expectedModCount = root.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
@@ -1228,7 +1210,7 @@
checkForComodification();
try {
- ArrayList.this.set(offset + lastRet, e);
+ root.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
@@ -1242,14 +1224,14 @@
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();
}
};
@@ -1257,12 +1239,7 @@
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) {
@@ -1275,13 +1252,24 @@
}
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();
+ // ArrayListSpliterator is not used because late-binding logic
+ // is different here
return new Spliterator<>() {
private int index = offset; // current index, modified on advance/split
private int fence = -1; // -1 until used; then one past last index
@@ -1298,8 +1286,9 @@
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ // ArrayListSpliterator could be used here as the source is already bound
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);
}
@@ -1308,9 +1297,9 @@
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;
}
@@ -1320,7 +1309,7 @@
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) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/List/SubList.java Thu Mar 31 17:30:31 2016 +0300
@@ -0,0 +1,676 @@
+/*
+ * Copyright (c) 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.
+ *
+ * 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.
+ */
+
+/*
+ * @test
+ * @bug 8079136
+ * @library /lib/testlibrary
+ * @build jdk.testlibrary.*
+ * @run testng SubList
+ * @summary Basic functionality of sublists
+ * @key randomness
+ */
+
+import java.util.AbstractList;
+import java.util.Arrays;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Random;
+import java.util.Vector;
+
+import org.testng.annotations.Test;
+import org.testng.annotations.DataProvider;
+
+import jdk.testlibrary.RandomFactory;
+
+
+public class SubList extends org.testng.Assert {
+
+ final Random rnd = RandomFactory.getRandom();
+
+ @Test(dataProvider = "modifiable")
+ public void testAdd(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ Integer e = rnd.nextInt();
+ subList.add(e);
+ assertEquals(list.get(to), e);
+ assertEquals(subList.size(), to - from + 1);
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModAdd(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.add(42);
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodAdd(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ subList.add(42);
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testAddAtPos(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ int i = rnd.nextInt(1 + to - from);
+ Integer e = rnd.nextInt();
+ subList.add(i, e);
+ assertEquals(list.get(from + i), e);
+ assertEquals(subList.size(), to - from + 1);
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModAddAtPos(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ int i = rnd.nextInt(1 + to - from);
+ subList.add(i, 42);
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodAddAtPos(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ int i = rnd.nextInt(1 + to - from);
+ subList.add(i, 42);
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testClear(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ subList.clear();
+ assertTrue(subList.isEmpty());
+ assertEquals(subList.size(), 0);
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModClear(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.clear();
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodClear(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ subList.clear();
+ }
+
+ @Test(dataProvider = "all")
+ public void testEquals(List<Integer> list, int from, int to) {
+ List<Integer> subList1 = list.subList(from, to);
+ List<Integer> subList2 = list.subList(from, to);
+ assertTrue(subList1.equals(subList2));
+ assertEquals(subList1.hashCode(), subList2.hashCode());
+ for (int i = 0; i != 16; ++i) {
+ int from3 = rnd.nextInt(1 + list.size());
+ int to3 = from3 + rnd.nextInt(1 + list.size() - from3);
+ boolean equal = (to - from) == (to3 - from3);
+ for (int j = 0; j < to - from && j < to3 - from3; ++j)
+ equal &= list.get(from + j) == list.get(from3 + j);
+ List<Integer> subList3 = list.subList(from3, to3);
+ assertEquals(subList1.equals(subList3), equal);
+ }
+ }
+
+// @Test(dataProvider = "modifiable",
+// expectedExceptions = ConcurrentModificationException.class)
+// public void testModEquals(List<Integer> list, int from, int to) {
+// List<Integer> subList = list.subList(from, to);
+// list.add(42);
+// subList.equals(subList);
+// }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModHashCode(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.hashCode();
+ }
+
+ @Test(dataProvider = "all")
+ public void testGet(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ for (int i = 0; i < to - from; ++i)
+ assertEquals(list.get(from + i), subList.get(i));
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModGet(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.get(from);
+ }
+
+ @Test(dataProvider = "all")
+ public void testIndexOf(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ if (from < to) {
+ Integer e = list.get(from);
+ int j = subList.indexOf(e);
+ assertTrue(j == 0);
+ }
+ for (int i = 0; i < list.size(); ++i) {
+ Integer e = list.get(i);
+ int j = subList.indexOf(e);
+ if (i < from || i >= to) {
+ assertTrue(j == -1 || subList.get(j) == e);
+ } else {
+ assertTrue(j >= 0);
+ assertTrue(j <= i - from);
+ assertEquals(subList.get(j), e);
+ }
+ }
+ for (int i = 0; i < 16; ++i) {
+ Integer r = rnd.nextInt();
+ if (list.contains(r)) continue;
+ int j = subList.indexOf(r);
+ assertTrue(j == -1);
+ }
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModIndexOf(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.indexOf(from);
+ }
+
+ @Test(dataProvider = "all")
+ public void testIterator(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ Iterator<Integer> it = subList.iterator();
+ for (int i = from; i < to; ++i) {
+ assertTrue(it.hasNext());
+ assertEquals(list.get(i), it.next());
+ }
+ assertFalse(it.hasNext());
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModIteratorNext(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ Iterator<Integer> it = subList.iterator();
+ list.add(42);
+ it.next();
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testIteratorRemove(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ Iterator<Integer> it = subList.iterator();
+ for (int i = from; i < to; ++i) {
+ assertTrue(it.hasNext());
+ assertEquals(list.get(from), it.next());
+ it.remove();
+ }
+ assertFalse(it.hasNext());
+ assertTrue(subList.isEmpty());
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModIteratorRemove(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ Iterator<Integer> it = subList.iterator();
+ it.next();
+ list.add(42);
+ it.remove();
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodIteratorRemove(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ Iterator<Integer> it = subList.iterator();
+ it.next();
+ it.remove();
+ }
+
+ @Test(dataProvider = "all")
+ public void testIteratorForEachRemaining(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ for (int k = 0; k < 16; ++k) {
+ int r = from + rnd.nextInt(1 + to - from);
+ Iterator<Integer> it = subList.iterator();
+ for (int i = from; i < to; ++i) {
+ assertTrue(it.hasNext());
+ if (i == r) {
+ Iterator<Integer> jt = list.listIterator(r);
+ it.forEachRemaining(x ->
+ assertTrue(jt.hasNext() && x == jt.next()));
+ break;
+ }
+ assertEquals(list.get(i), it.next());
+ }
+ it.forEachRemaining(x -> fail());
+ }
+ }
+
+ @Test(dataProvider = "all")
+ public void testLastIndexOf(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ if (from < to) {
+ Integer e = list.get(to - 1);
+ int j = subList.lastIndexOf(e);
+ assertTrue(j == to - from - 1);
+ }
+ for (int i = 0; i < list.size(); ++i) {
+ Integer e = list.get(i);
+ int j = subList.lastIndexOf(e);
+ if (i < from || i >= to) {
+ assertTrue(j == -1 || subList.get(j) == e);
+ } else {
+ assertTrue(j >= 0 && j >= i - from);
+ assertEquals(subList.get(j), e);
+ }
+ }
+ for (int i = 0; i < 16; ++i) {
+ Integer r = rnd.nextInt();
+ if (list.contains(r)) continue;
+ int j = subList.lastIndexOf(r);
+ assertTrue(j == -1);
+ }
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModLastIndexOf(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.lastIndexOf(42);
+ }
+
+ @Test(dataProvider = "unresizable")
+ public void testListIterator(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ for (int i = from; i < to; ++i) {
+ assertTrue(it.hasNext());
+ assertTrue(it.nextIndex() == i - from);
+ assertEquals(list.get(i), it.next());
+ }
+ assertFalse(it.hasNext());
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModListIteratorNext(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ list.add(42);
+ it.next();
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testListIteratorSet(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ for (int i = from; i < to; ++i) {
+ assertTrue(it.hasNext());
+ assertTrue(it.nextIndex() == i - from);
+ assertEquals(list.get(i), it.next());
+ Integer e = rnd.nextInt();
+ it.set(e);
+ assertEquals(list.get(i), e);
+ }
+ assertFalse(it.hasNext());
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModListIteratorSet(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ it.next();
+ list.add(42);
+ it.set(42);
+ }
+
+ @Test(dataProvider = "unsettable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodListIteratorSet(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ it.next();
+ it.set(42);
+ }
+
+ @Test(dataProvider = "unresizable")
+ public void testListIteratorPrevious(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator(subList.size());
+ for (int i = to - 1; i >= from; --i) {
+ assertTrue(it.hasPrevious());
+ assertTrue(it.previousIndex() == i - from);
+ assertEquals(list.get(i), it.previous());
+ }
+ assertFalse(it.hasPrevious());
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModListIteratorPrevious(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator(to - from);
+ list.add(42);
+ it.previous();
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testListIteratorSetPrevious(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator(subList.size());
+ for (int i = to - 1; i >= from; --i) {
+ assertTrue(it.hasPrevious());
+ assertTrue(it.previousIndex() == i - from);
+ assertEquals(list.get(i), it.previous());
+ Integer e = rnd.nextInt();
+ it.set(e);
+ assertEquals(list.get(i), e);
+ }
+ assertFalse(it.hasPrevious());
+ }
+
+ @Test(dataProvider = "unsettable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodListIteratorSetPrevious(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator(to - from);
+ it.previous();
+ it.set(42);
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testListIteratorAdd(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ for (int i = 0; i < 16; ++i) {
+ int r = rnd.nextInt(1 + subList.size());
+ ListIterator<Integer> it = subList.listIterator(r);
+ Integer e = rnd.nextInt();
+ it.add(e);
+ assertEquals(it.previous(), e);
+ assertEquals(list.get(from + r), e);
+ }
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodListIteratorAdd(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ int r = rnd.nextInt(1 + subList.size());
+ ListIterator<Integer> it = subList.listIterator(r);
+ it.add(42);
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModListIteratorAdd(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ it.next();
+ list.add(42);
+ it.add(42);
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testListIteratorRemoveNext(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ for (int i = from; i < to; ++i) {
+ assertTrue(it.hasNext());
+ assertTrue(it.nextIndex() == 0);
+ assertEquals(list.get(from), it.next());
+ it.remove();
+ }
+ assertFalse(it.hasNext());
+ assertTrue(subList.isEmpty());
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodListIteratorRemoveNext(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ it.next();
+ it.remove();
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModListIteratorRemove(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator();
+ it.next();
+ list.add(42);
+ it.remove();
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testListIteratorRemovePrevious(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator(subList.size());
+ for (int i = to - 1; i >= from; --i) {
+ assertTrue(it.hasPrevious());
+ assertTrue(it.previousIndex() == i - from);
+ assertEquals(list.get(i), it.previous());
+ it.remove();
+ }
+ assertFalse(it.hasPrevious());
+ assertTrue(subList.isEmpty());
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodListIteratorRemovePrevious(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ ListIterator<Integer> it = subList.listIterator(subList.size());
+ it.previous();
+ it.remove();
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testRemove(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ for (int i = 0; i < 16; ++i) {
+ if (subList.isEmpty()) break;
+ int r = rnd.nextInt(subList.size());
+ Integer e = list.get(from + r);
+ assertEquals(subList.remove(r), e);
+ }
+ }
+
+ @Test(dataProvider = "unresizable",
+ expectedExceptions = UnsupportedOperationException.class)
+ public void testUnmodRemove(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ int r = rnd.nextInt(subList.size());
+ subList.remove(r);
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModRemove(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.remove(0);
+ }
+
+ @Test(dataProvider = "modifiable")
+ public void testSet(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ for (int i = 0; i < to - from; ++i) {
+ Integer e0 = list.get(from + i);
+ Integer e1 = rnd.nextInt();
+ assertEquals(subList.set(i, e1), e0);
+ assertEquals(list.get(from + i), e1);
+ }
+ }
+
+ @Test(dataProvider = "modifiable",
+ expectedExceptions = ConcurrentModificationException.class)
+ public void testModSet(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ list.add(42);
+ subList.set(0, 42);
+ }
+
+ @Test(dataProvider = "all")
+ public void testSubList(List<Integer> list, int from, int to) {
+ List<Integer> subList = list.subList(from, to);
+ for (int i = 0; i < 16 && from < to; ++i) {
+ int from1 = rnd.nextInt(to - from);
+ int to1 = from1 + 1 + rnd.nextInt(to - from - from1);
+ List<Integer> subSubList = subList.subList(from1, to1);
+ for (int j = 0; j < to1 - from1; ++j)
+ assertEquals(list.get(from + from1 + j), subSubList.get(j));
+ }
+ }
+
+ /**
+ * All kinds of lists
+ */
+ @DataProvider
+ public static Object[][] all() {
+ Object[][] l1 = modifiable();
+ Object[][] l2 = unresizable();
+ Object[][] res = Arrays.copyOf(l1, l1.length + l2.length);
+ System.arraycopy(l2, 0, res, l1.length, l2.length);
+ return res;
+ }
+
+ /**
+ * Lists that allow any modifications: resizing and setting values
+ */
+ @DataProvider
+ public static Object[][] modifiable() {
+ final List<Integer> c1 = Arrays.asList(42);
+ final List<Integer> c9 = Arrays.asList(40, 41, 42, 43, 44, 45, -1,
+ Integer.MIN_VALUE, 1000500);
+
+ return new Object[][] {
+ {new ArrayList<>(c1), 0, 1},
+ {new LinkedList<>(c1), 0, 1},
+ {new Vector<>(c1), 0, 1},
+ {new ArrayList<>(c1).subList(0, 1), 0, 1},
+ {new LinkedList<>(c1).subList(0, 1), 0, 1},
+ {new Vector<>(c1).subList(0, 1), 0, 1},
+ {Collections.checkedList(new ArrayList<>(c1), Integer.class), 0, 1},
+ {Collections.checkedList(new LinkedList<>(c1), Integer.class), 0, 1},
+ {Collections.checkedList(new Vector<>(c1), Integer.class), 0, 1},
+ {Collections.synchronizedList(new ArrayList<>(c1)), 0, 1},
+ {Collections.synchronizedList(new LinkedList<>(c1)), 0, 1},
+ {Collections.synchronizedList(new Vector<>(c1)), 0, 1},
+
+ {new ArrayList<>(c9), 2, 5},
+ {new LinkedList<>(c9), 2, 5},
+ {new Vector<>(c9), 2, 5},
+ {new ArrayList<>(c9).subList(1, 8), 1, 4},
+ {new LinkedList<>(c9).subList(1, 8), 1, 4},
+ {new Vector<>(c9).subList(1, 8), 1, 4},
+ {Collections.checkedList(new ArrayList<>(c9), Integer.class), 2, 5},
+ {Collections.checkedList(new LinkedList<>(c9), Integer.class), 2, 5},
+ {Collections.checkedList(new Vector<>(c9), Integer.class), 2, 5},
+ {Collections.synchronizedList(new ArrayList<>(c9)), 2, 5},
+ {Collections.synchronizedList(new LinkedList<>(c9)), 2, 5},
+ {Collections.synchronizedList(new Vector<>(c9)), 2, 5},
+ };
+ }
+
+ /**
+ * Lists that don't allow resizing, but allow setting values
+ */
+ @DataProvider
+ public static Object[][] unresizable() {
+ final List<Integer> c1 = Arrays.asList(42);
+ final List<Integer> c9 = Arrays.asList(40, 41, 42, 43, 44, 45, -1,
+ Integer.MIN_VALUE, 1000500);
+
+ Object[][] l1 = unsettable();
+ Object[][] l2 = {
+ {c1, 0, 1},
+ {c1.subList(0, 1), 0, 1},
+ {Collections.checkedList(c1, Integer.class), 0, 1},
+ {Collections.synchronizedList(c1), 0, 1},
+ {c9, 0, 4},
+ {c9, 4, 6},
+ {c9.subList(1, 8), 1, 4},
+ {c9.subList(1, 8), 0, 7},
+ {Collections.checkedList(c9, Integer.class), 3, 6},
+ {Collections.synchronizedList(c9), 3, 5},
+ };
+ Object[][] res = Arrays.copyOf(l1, l1.length + l2.length);
+ System.arraycopy(l2, 0, res, l1.length, l2.length);
+ return res;
+ }
+
+ /**
+ * Lists that don't allow either resizing or setting values
+ */
+ @DataProvider
+ public static Object[][] unsettable() {
+ final List<Integer> c1 = Arrays.asList(42);
+ final List<Integer> c9 = Arrays.asList(40, 41, 42, 43, 44, 45, -1,
+ Integer.MIN_VALUE, 1000500);
+
+ return new Object[][] {
+ {new MyList(1), 0, 1},
+ {new MyList(1).subList(0, 1), 0, 1},
+ {Collections.singletonList(42), 0, 1},
+ {Collections.singletonList(42).subList(0, 1), 0, 1},
+ {Collections.unmodifiableList(c1), 0, 1},
+ {Collections.unmodifiableList(new ArrayList<>(c1)), 0, 1},
+ {Collections.unmodifiableList(new LinkedList<>(c1)), 0, 1},
+ {Collections.unmodifiableList(new Vector<>(c1)), 0, 1},
+
+ {new MyList(9), 3, 6},
+ {new MyList(9).subList(2, 8), 3, 6},
+ {Collections.unmodifiableList(c9), 3, 6},
+ {Collections.unmodifiableList(new ArrayList<>(c9)), 3, 6},
+ {Collections.unmodifiableList(new LinkedList<>(c9)), 3, 6},
+ {Collections.unmodifiableList(new Vector<>(c9)), 3, 6},
+ };
+ }
+
+ static class MyList extends AbstractList<Integer> {
+ private int size;
+ MyList(int s) { size = s; }
+ public Integer get(int index) { return 42; }
+ public int size() { return size; }
+ }
+}