util/List/ListDefaults.java

/*
 * Copyright (c) 2012, 2014, 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.
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
import static org.testng.Assert.fail;

import java.util.ConcurrentModificationException;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;

/**
 * @test
 * @summary Unit tests for extension methods on List
 * @bug 8023367 8037106
 * @library ../Collection/testlibrary
 * @build CollectionAsserts CollectionSupplier ExtendsAbstractList
 * @run testng ListDefaults
 */
public class ListDefaults {

    // Suppliers of lists that can support structural modifications
    private static final List<Function<Collection, List>> LIST_STRUCT_MOD_SUPPLIERS = Arrays.asList(
            java.util.ArrayList::new,
            java.util.LinkedList::new,
            java.util.Vector::new,
            java.util.concurrent.CopyOnWriteArrayList::new,
            ExtendsAbstractList::new
    );

    // Suppliers of lists that can support in place modifications
    private static final List<Function<Collection, List>> LIST_SUPPLIERS = Arrays.asList(
            java.util.ArrayList::new,
            java.util.LinkedList::new,
            java.util.Vector::new,
            java.util.concurrent.CopyOnWriteArrayList::new,
            ExtendsAbstractList::new,
            c -> Arrays.asList(c.toArray())
    );

    // Suppliers of lists supporting CMEs
    private static final List<Function<Collection, List>> LIST_CME_SUPPLIERS = Arrays.asList(
            java.util.ArrayList::new,
            java.util.Vector::new
    );

    private static final Predicate<Integer> pEven = x -> 0 == x % 2;
    private static final Predicate<Integer> pOdd = x -> 1 == x % 2;

    private static final Comparator<Integer> BIT_COUNT_COMPARATOR =
            (x, y) -> Integer.bitCount(x) - Integer.bitCount(y);

    private static final Comparator<AtomicInteger> ATOMIC_INTEGER_COMPARATOR =
            (x, y) -> x.intValue() - y.intValue();

    private static final int SIZE = 100;
    private static final int SUBLIST_FROM = 20;
    private static final int SUBLIST_TO = SIZE - 5;
    private static final int SUBLIST_SIZE = SUBLIST_TO - SUBLIST_FROM;

    // call the callback for each recursive subList
    private void trimmedSubList(final List<Integer> list, final Consumer<List<Integer>> callback) {
        int size = list.size();
        if (size > 1) {
            // trim 1 element from both ends
            final List<Integer> subList = list.subList(1, size - 1);
            callback.accept(subList);
            trimmedSubList(subList, callback);
        }
    }

    @DataProvider(name="listProvider", parallel=true)
    public static Object[][] listCases() {
        final List<Object[]> cases = new LinkedList<>();
        cases.add(new Object[] { Collections.emptyList() });
        cases.add(new Object[] { new ArrayList<>() });
        cases.add(new Object[] { new LinkedList<>() });
        cases.add(new Object[] { new Vector<>() });
        cases.add(new Object[] { new Stack<>() });
        cases.add(new Object[] { new CopyOnWriteArrayList<>() });
        cases.add(new Object[] { Arrays.asList() });

        List<Integer> l = Arrays.asList(42);
        cases.add(new Object[] { new ArrayList<>(l) });
        cases.add(new Object[] { new LinkedList<>(l) });
        cases.add(new Object[] { new Vector<>(l) });
        Stack<Integer> s = new Stack<>(); s.addAll(l);
        cases.add(new Object[]{s});
        cases.add(new Object[] { new CopyOnWriteArrayList<>(l) });
        cases.add(new Object[] { l });
        return cases.toArray(new Object[0][cases.size()]);
    }

    @Test(dataProvider = "listProvider")
    public void testProvidedWithNull(final List<Integer> list) {
        try {
            list.forEach(null);
            fail("expected NPE not thrown");
        } catch (NullPointerException npe) {}
        try {
            list.replaceAll(null);
            fail("expected NPE not thrown");
        } catch (NullPointerException npe) {}
        try {
            list.removeIf(null);
            fail("expected NPE not thrown");
        } catch (NullPointerException npe) {}
        try {
            list.sort(null);
        } catch (Throwable t) {
            fail("Exception not expected: " + t);
        }
    }

    @Test
    public void testForEach() {
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> original = test.expected;
            final List<Integer> list = test.collection;

            try {
                list.forEach(null);
                fail("expected NPE not thrown");
            } catch (NullPointerException npe) {}
            CollectionAsserts.assertContents(list, original);

            final List<Integer> actual = new LinkedList<>();
            list.forEach(actual::add);
            CollectionAsserts.assertContents(actual, list);
            CollectionAsserts.assertContents(actual, original);

            if (original.size() > SUBLIST_SIZE) {
                final List<Integer> subList = original.subList(SUBLIST_FROM, SUBLIST_TO);
                final List<Integer> actualSubList = new LinkedList<>();
                subList.forEach(actualSubList::add);
                assertEquals(actualSubList.size(), SUBLIST_SIZE);
                for (int i = 0; i < SUBLIST_SIZE; i++) {
                    assertEquals(actualSubList.get(i), original.get(i + SUBLIST_FROM));
                }
            }

            trimmedSubList(list, l -> {
                    final List<Integer> a = new LinkedList<>();
                    l.forEach(a::add);
                    CollectionAsserts.assertContents(a, l);
                });
        }
    }

    @Test
    public void testRemoveIf() {
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_STRUCT_MOD_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> original = test.expected;
            final List<Integer> list = test.collection;

            try {
                list.removeIf(null);
                fail("expected NPE not thrown");
            } catch (NullPointerException npe) {}
            CollectionAsserts.assertContents(list, original);

            final AtomicInteger offset = new AtomicInteger(1);
            while (list.size() > 0) {
                removeFirst(original, list, offset);
            }
        }

        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> original = test.expected;
            final List<Integer> list = test.collection;
            list.removeIf(pOdd);
            for (int i : list) {
                assertTrue((i % 2) == 0);
            }
            for (int i : original) {
                if (i % 2 == 0) {
                    assertTrue(list.contains(i));
                }
            }
            list.removeIf(pEven);
            assertTrue(list.isEmpty());
        }

        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> original = test.expected;
            final List<Integer> list = test.collection;
            final List<Integer> listCopy = new ArrayList<>(list);
            if (original.size() > SUBLIST_SIZE) {
                final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
                final List<Integer> subListCopy = new ArrayList<>(subList);
                listCopy.removeAll(subList);
                subList.removeIf(pOdd);
                for (int i : subList) {
                    assertTrue((i % 2) == 0);
                }
                for (int i : subListCopy) {
                    if (i % 2 == 0) {
                        assertTrue(subList.contains(i));
                    } else {
                        assertFalse(subList.contains(i));
                    }
                }
                subList.removeIf(pEven);
                assertTrue(subList.isEmpty());
                // elements outside the view should remain
                CollectionAsserts.assertContents(list, listCopy);
            }
        }

        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> list = test.collection;
            trimmedSubList(list, l -> {
                final List<Integer> copy = new ArrayList<>(l);
                l.removeIf(pOdd);
                for (int i : l) {
                    assertTrue((i % 2) == 0);
                }
                for (int i : copy) {
                    if (i % 2 == 0) {
                        assertTrue(l.contains(i));
                    } else {
                        assertFalse(l.contains(i));
                    }
                }
            });
        }
    }

    // remove the first element
    private void removeFirst(final List<Integer> original, final List<Integer> list, final AtomicInteger offset) {
        final AtomicBoolean first = new AtomicBoolean(true);
        list.removeIf(x -> first.getAndSet(false));
        CollectionAsserts.assertContents(original.subList(offset.getAndIncrement(), original.size()), list);
    }

    @Test
    public void testReplaceAll() {
        final int scale = 3;
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> original = test.expected;
            final List<Integer> list = test.collection;

            try {
                list.replaceAll(null);
                fail("expected NPE not thrown");
            } catch (NullPointerException npe) {}
            CollectionAsserts.assertContents(list, original);

            list.replaceAll(x -> scale * x);
            for (int i = 0; i < original.size(); i++) {
                assertTrue(list.get(i) == (scale * original.get(i)), "mismatch at index " + i);
            }

            if (original.size() > SUBLIST_SIZE) {
                final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
                subList.replaceAll(x -> x + 1);
                // verify elements in view [from, to) were replaced
                for (int i = 0; i < SUBLIST_SIZE; i++) {
                    assertTrue(subList.get(i) == ((scale * original.get(i + SUBLIST_FROM)) + 1),
                            "mismatch at sublist index " + i);
                }
                // verify that elements [0, from) remain unmodified
                for (int i = 0; i < SUBLIST_FROM; i++) {
                    assertTrue(list.get(i) == (scale * original.get(i)),
                            "mismatch at original index " + i);
                }
                // verify that elements [to, size) remain unmodified
                for (int i = SUBLIST_TO; i < list.size(); i++) {
                    assertTrue(list.get(i) == (scale * original.get(i)),
                            "mismatch at original index " + i);
                }
            }
        }

        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> list = test.collection;
            trimmedSubList(list, l -> {
                final List<Integer> copy = new ArrayList<>(l);
                final int offset = 5;
                l.replaceAll(x -> offset + x);
                for (int i = 0; i < copy.size(); i++) {
                    assertTrue(l.get(i) == (offset + copy.get(i)), "mismatch at index " + i);
                }
            });
        }
    }

    @Test
    public void testSort() {
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> original = test.expected;
            final List<Integer> list = test.collection;
            CollectionSupplier.shuffle(list);
            list.sort(Integer::compare);
            CollectionAsserts.assertSorted(list, Integer::compare);
            if (test.name.startsWith("reverse")) {
                Collections.reverse(list);
            }
            CollectionAsserts.assertContents(list, original);

            CollectionSupplier.shuffle(list);
            list.sort(null);
            CollectionAsserts.assertSorted(list, Comparator.naturalOrder());
            if (test.name.startsWith("reverse")) {
                Collections.reverse(list);
            }
            CollectionAsserts.assertContents(list, original);

            CollectionSupplier.shuffle(list);
            list.sort(Comparator.naturalOrder());
            CollectionAsserts.assertSorted(list, Comparator.naturalOrder());
            if (test.name.startsWith("reverse")) {
                Collections.reverse(list);
            }
            CollectionAsserts.assertContents(list, original);

            CollectionSupplier.shuffle(list);
            list.sort(Comparator.reverseOrder());
            CollectionAsserts.assertSorted(list, Comparator.reverseOrder());
            if (!test.name.startsWith("reverse")) {
                Collections.reverse(list);
            }
            CollectionAsserts.assertContents(list, original);

            CollectionSupplier.shuffle(list);
            list.sort(BIT_COUNT_COMPARATOR);
            CollectionAsserts.assertSorted(list, BIT_COUNT_COMPARATOR);
            // check sort by verifying that bitCount increases and never drops
            int minBitCount = 0;
            for (final Integer i : list) {
                int bitCount = Integer.bitCount(i);
                assertTrue(bitCount >= minBitCount);
                minBitCount = bitCount;
            }

            // Reuse the supplier to store AtomicInteger instead of Integer
            // Hence the use of raw type and cast
            List<AtomicInteger> incomparablesData = new ArrayList<>();
            for (int i = 0; i < test.expected.size(); i++) {
                incomparablesData.add(new AtomicInteger(i));
            }
            Function f = test.supplier;
            @SuppressWarnings("unchecked")
            List<AtomicInteger> incomparables = (List<AtomicInteger>) f.apply(incomparablesData);

            CollectionSupplier.shuffle(incomparables);
            incomparables.sort(ATOMIC_INTEGER_COMPARATOR);
            for (int i = 0; i < test.expected.size(); i++) {
                assertEquals(i, incomparables.get(i).intValue());
            }


            if (original.size() > SUBLIST_SIZE) {
                final List<Integer> copy = new ArrayList<>(list);
                final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
                CollectionSupplier.shuffle(subList);
                subList.sort(Comparator.naturalOrder());
                CollectionAsserts.assertSorted(subList, Comparator.naturalOrder());
                // verify that elements [0, from) remain unmodified
                for (int i = 0; i < SUBLIST_FROM; i++) {
                    assertTrue(list.get(i) == copy.get(i),
                            "mismatch at index " + i);
                }
                // verify that elements [to, size) remain unmodified
                for (int i = SUBLIST_TO; i < list.size(); i++) {
                    assertTrue(list.get(i) == copy.get(i),
                            "mismatch at index " + i);
                }
            }
        }

        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> list = test.collection;
            trimmedSubList(list, l -> {
                CollectionSupplier.shuffle(l);
                l.sort(Comparator.naturalOrder());
                CollectionAsserts.assertSorted(l, Comparator.naturalOrder());
            });
        }
    }

    @Test
    public void testForEachThrowsCME() {
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> list = test.collection;

            if (list.size() <= 1) {
                continue;
            }
            boolean gotException = false;
            try {
                // bad predicate that modifies its list, should throw CME
                list.forEach(list::add);
            } catch (ConcurrentModificationException cme) {
                gotException = true;
            }
            if (!gotException) {
                fail("expected CME was not thrown from " + test);
            }
        }
    }

    @Test
    public void testRemoveIfThrowsCME() {
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> list = test.collection;

            if (list.size() <= 1) {
                continue;
            }
            boolean gotException = false;
            try {
                // bad predicate that modifies its list, should throw CME
                list.removeIf(list::add);
            } catch (ConcurrentModificationException cme) {
                gotException = true;
            }
            if (!gotException) {
                fail("expected CME was not thrown from " + test);
            }
        }
    }

    @Test
    public void testReplaceAllThrowsCME() {
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> list = test.collection;

            if (list.size() <= 1) {
                continue;
            }
            boolean gotException = false;
            try {
                // bad predicate that modifies its list, should throw CME
                list.replaceAll(x -> {int n = 3 * x; list.add(n); return n;});
            } catch (ConcurrentModificationException cme) {
                gotException = true;
            }
            if (!gotException) {
                fail("expected CME was not thrown from " + test);
            }
        }
    }

    @Test
    public void testSortThrowsCME() {
        @SuppressWarnings("unchecked")
        final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
        for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
            final List<Integer> list = test.collection;

            if (list.size() <= 1) {
                continue;
            }
            boolean gotException = false;
            try {
                // bad predicate that modifies its list, should throw CME
                list.sort((x, y) -> {list.add(x); return x - y;});
            } catch (ConcurrentModificationException cme) {
                gotException = true;
            }
            if (!gotException) {
                fail("expected CME was not thrown from " + test);
            }
        }
    }

    private static final List<Integer> SLICED_EXPECTED = Arrays.asList(0, 1, 2, 3, 5, 6, 7, 8, 9);
    private static final List<Integer> SLICED_EXPECTED2 = Arrays.asList(0, 1, 2, 5, 6, 7, 8, 9);

    @DataProvider(name="shortIntListProvider", parallel=true)
    public static Object[][] intListCases() {
        final Integer[] DATA = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        final List<Object[]> cases = new LinkedList<>();
        cases.add(new Object[] { new ArrayList<>(Arrays.asList(DATA)) });
        cases.add(new Object[] { new LinkedList<>(Arrays.asList(DATA)) });
        cases.add(new Object[] { new Vector<>(Arrays.asList(DATA)) });
        cases.add(new Object[] { new CopyOnWriteArrayList<>(Arrays.asList(DATA)) });
        cases.add(new Object[] { new ExtendsAbstractList<>(Arrays.asList(DATA)) });
        return cases.toArray(new Object[0][cases.size()]);
    }

    @Test(dataProvider = "shortIntListProvider")
    public void testRemoveIfFromSlice(final List<Integer> list) {
        final List<Integer> sublist = list.subList(3, 6);
        assertTrue(sublist.removeIf(x -> x == 4));
        CollectionAsserts.assertContents(list, SLICED_EXPECTED);

        final List<Integer> sublist2 = list.subList(2, 5);
        assertTrue(sublist2.removeIf(x -> x == 3));
        CollectionAsserts.assertContents(list, SLICED_EXPECTED2);
    }
}
Revision:	1.4
Committed:	Thu Sep 28 02:15:44 2017 UTC (6 years, 7 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.3:	+0 -1 lines
Log Message:	removed unused imports
#	Content
1	/*
2	* Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.
3	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4	*
5	* This code is free software; you can redistribute it and/or modify it
6	* under the terms of the GNU General Public License version 2 only, as
7	* published by the Free Software Foundation.
8	*
9	* This code is distributed in the hope that it will be useful, but WITHOUT
10	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12	* version 2 for more details (a copy is included in the LICENSE file that
13	* accompanied this code).
14	*
15	* You should have received a copy of the GNU General Public License version
16	* 2 along with this work; if not, write to the Free Software Foundation,
17	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18	*
19	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20	* or visit www.oracle.com if you need additional information or have any
21	* questions.
22	*/
23
24	import java.util.ArrayList;
25	import java.util.Arrays;
26	import java.util.Collection;
27	import java.util.Collections;
28	import java.util.Comparator;
29	import java.util.List;
30	import java.util.LinkedList;
31	import java.util.Stack;
32	import java.util.Vector;
33	import java.util.concurrent.CopyOnWriteArrayList;
34	import java.util.concurrent.atomic.AtomicBoolean;
35	import java.util.concurrent.atomic.AtomicInteger;
36
37	import org.testng.annotations.DataProvider;
38	import org.testng.annotations.Test;
39
40	import static org.testng.Assert.assertEquals;
41	import static org.testng.Assert.assertFalse;
42	import static org.testng.Assert.assertTrue;
43	import static org.testng.Assert.fail;
44
45	import java.util.ConcurrentModificationException;
46	import java.util.function.Consumer;
47	import java.util.function.Function;
48	import java.util.function.Predicate;
49
50	/**
51	* @test
52	* @summary Unit tests for extension methods on List
53	* @bug 8023367 8037106
54	* @library ../Collection/testlibrary
55	* @build CollectionAsserts CollectionSupplier ExtendsAbstractList
56	* @run testng ListDefaults
57	*/
58	public class ListDefaults {
59
60	// Suppliers of lists that can support structural modifications
61	private static final List<Function<Collection, List>> LIST_STRUCT_MOD_SUPPLIERS = Arrays.asList(
62	java.util.ArrayList::new,
63	java.util.LinkedList::new,
64	java.util.Vector::new,
65	java.util.concurrent.CopyOnWriteArrayList::new,
66	ExtendsAbstractList::new
67	);
68
69	// Suppliers of lists that can support in place modifications
70	private static final List<Function<Collection, List>> LIST_SUPPLIERS = Arrays.asList(
71	java.util.ArrayList::new,
72	java.util.LinkedList::new,
73	java.util.Vector::new,
74	java.util.concurrent.CopyOnWriteArrayList::new,
75	ExtendsAbstractList::new,
76	c -> Arrays.asList(c.toArray())
77	);
78
79	// Suppliers of lists supporting CMEs
80	private static final List<Function<Collection, List>> LIST_CME_SUPPLIERS = Arrays.asList(
81	java.util.ArrayList::new,
82	java.util.Vector::new
83	);
84
85	private static final Predicate<Integer> pEven = x -> 0 == x % 2;
86	private static final Predicate<Integer> pOdd = x -> 1 == x % 2;
87
88	private static final Comparator<Integer> BIT_COUNT_COMPARATOR =
89	(x, y) -> Integer.bitCount(x) - Integer.bitCount(y);
90
91	private static final Comparator<AtomicInteger> ATOMIC_INTEGER_COMPARATOR =
92	(x, y) -> x.intValue() - y.intValue();
93
94	private static final int SIZE = 100;
95	private static final int SUBLIST_FROM = 20;
96	private static final int SUBLIST_TO = SIZE - 5;
97	private static final int SUBLIST_SIZE = SUBLIST_TO - SUBLIST_FROM;
98
99	// call the callback for each recursive subList
100	private void trimmedSubList(final List<Integer> list, final Consumer<List<Integer>> callback) {
101	int size = list.size();
102	if (size > 1) {
103	// trim 1 element from both ends
104	final List<Integer> subList = list.subList(1, size - 1);
105	callback.accept(subList);
106	trimmedSubList(subList, callback);
107	}
108	}
109
110	@DataProvider(name="listProvider", parallel=true)
111	public static Object[][] listCases() {
112	final List<Object[]> cases = new LinkedList<>();
113	cases.add(new Object[] { Collections.emptyList() });
114	cases.add(new Object[] { new ArrayList<>() });
115	cases.add(new Object[] { new LinkedList<>() });
116	cases.add(new Object[] { new Vector<>() });
117	cases.add(new Object[] { new Stack<>() });
118	cases.add(new Object[] { new CopyOnWriteArrayList<>() });
119	cases.add(new Object[] { Arrays.asList() });
120
121	List<Integer> l = Arrays.asList(42);
122	cases.add(new Object[] { new ArrayList<>(l) });
123	cases.add(new Object[] { new LinkedList<>(l) });
124	cases.add(new Object[] { new Vector<>(l) });
125	Stack<Integer> s = new Stack<>(); s.addAll(l);
126	cases.add(new Object[]{s});
127	cases.add(new Object[] { new CopyOnWriteArrayList<>(l) });
128	cases.add(new Object[] { l });
129	return cases.toArray(new Object[0][cases.size()]);
130	}
131
132	@Test(dataProvider = "listProvider")
133	public void testProvidedWithNull(final List<Integer> list) {
134	try {
135	list.forEach(null);
136	fail("expected NPE not thrown");
137	} catch (NullPointerException npe) {}
138	try {
139	list.replaceAll(null);
140	fail("expected NPE not thrown");
141	} catch (NullPointerException npe) {}
142	try {
143	list.removeIf(null);
144	fail("expected NPE not thrown");
145	} catch (NullPointerException npe) {}
146	try {
147	list.sort(null);
148	} catch (Throwable t) {
149	fail("Exception not expected: " + t);
150	}
151	}
152
153	@Test
154	public void testForEach() {
155	@SuppressWarnings("unchecked")
156	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_SUPPLIERS, SIZE);
157	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
158	final List<Integer> original = test.expected;
159	final List<Integer> list = test.collection;
160
161	try {
162	list.forEach(null);
163	fail("expected NPE not thrown");
164	} catch (NullPointerException npe) {}
165	CollectionAsserts.assertContents(list, original);
166
167	final List<Integer> actual = new LinkedList<>();
168	list.forEach(actual::add);
169	CollectionAsserts.assertContents(actual, list);
170	CollectionAsserts.assertContents(actual, original);
171
172	if (original.size() > SUBLIST_SIZE) {
173	final List<Integer> subList = original.subList(SUBLIST_FROM, SUBLIST_TO);
174	final List<Integer> actualSubList = new LinkedList<>();
175	subList.forEach(actualSubList::add);
176	assertEquals(actualSubList.size(), SUBLIST_SIZE);
177	for (int i = 0; i < SUBLIST_SIZE; i++) {
178	assertEquals(actualSubList.get(i), original.get(i + SUBLIST_FROM));
179	}
180	}
181
182	trimmedSubList(list, l -> {
183	final List<Integer> a = new LinkedList<>();
184	l.forEach(a::add);
185	CollectionAsserts.assertContents(a, l);
186	});
187	}
188	}
189
190	@Test
191	public void testRemoveIf() {
192	@SuppressWarnings("unchecked")
193	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_STRUCT_MOD_SUPPLIERS, SIZE);
194	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
195	final List<Integer> original = test.expected;
196	final List<Integer> list = test.collection;
197
198	try {
199	list.removeIf(null);
200	fail("expected NPE not thrown");
201	} catch (NullPointerException npe) {}
202	CollectionAsserts.assertContents(list, original);
203
204	final AtomicInteger offset = new AtomicInteger(1);
205	while (list.size() > 0) {
206	removeFirst(original, list, offset);
207	}
208	}
209
210	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
211	final List<Integer> original = test.expected;
212	final List<Integer> list = test.collection;
213	list.removeIf(pOdd);
214	for (int i : list) {
215	assertTrue((i % 2) == 0);
216	}
217	for (int i : original) {
218	if (i % 2 == 0) {
219	assertTrue(list.contains(i));
220	}
221	}
222	list.removeIf(pEven);
223	assertTrue(list.isEmpty());
224	}
225
226	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
227	final List<Integer> original = test.expected;
228	final List<Integer> list = test.collection;
229	final List<Integer> listCopy = new ArrayList<>(list);
230	if (original.size() > SUBLIST_SIZE) {
231	final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
232	final List<Integer> subListCopy = new ArrayList<>(subList);
233	listCopy.removeAll(subList);
234	subList.removeIf(pOdd);
235	for (int i : subList) {
236	assertTrue((i % 2) == 0);
237	}
238	for (int i : subListCopy) {
239	if (i % 2 == 0) {
240	assertTrue(subList.contains(i));
241	} else {
242	assertFalse(subList.contains(i));
243	}
244	}
245	subList.removeIf(pEven);
246	assertTrue(subList.isEmpty());
247	// elements outside the view should remain
248	CollectionAsserts.assertContents(list, listCopy);
249	}
250	}
251
252	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
253	final List<Integer> list = test.collection;
254	trimmedSubList(list, l -> {
255	final List<Integer> copy = new ArrayList<>(l);
256	l.removeIf(pOdd);
257	for (int i : l) {
258	assertTrue((i % 2) == 0);
259	}
260	for (int i : copy) {
261	if (i % 2 == 0) {
262	assertTrue(l.contains(i));
263	} else {
264	assertFalse(l.contains(i));
265	}
266	}
267	});
268	}
269	}
270
271	// remove the first element
272	private void removeFirst(final List<Integer> original, final List<Integer> list, final AtomicInteger offset) {
273	final AtomicBoolean first = new AtomicBoolean(true);
274	list.removeIf(x -> first.getAndSet(false));
275	CollectionAsserts.assertContents(original.subList(offset.getAndIncrement(), original.size()), list);
276	}
277
278	@Test
279	public void testReplaceAll() {
280	final int scale = 3;
281	@SuppressWarnings("unchecked")
282	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_SUPPLIERS, SIZE);
283	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
284	final List<Integer> original = test.expected;
285	final List<Integer> list = test.collection;
286
287	try {
288	list.replaceAll(null);
289	fail("expected NPE not thrown");
290	} catch (NullPointerException npe) {}
291	CollectionAsserts.assertContents(list, original);
292
293	list.replaceAll(x -> scale * x);
294	for (int i = 0; i < original.size(); i++) {
295	assertTrue(list.get(i) == (scale * original.get(i)), "mismatch at index " + i);
296	}
297
298	if (original.size() > SUBLIST_SIZE) {
299	final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
300	subList.replaceAll(x -> x + 1);
301	// verify elements in view [from, to) were replaced
302	for (int i = 0; i < SUBLIST_SIZE; i++) {
303	assertTrue(subList.get(i) == ((scale * original.get(i + SUBLIST_FROM)) + 1),
304	"mismatch at sublist index " + i);
305	}
306	// verify that elements [0, from) remain unmodified
307	for (int i = 0; i < SUBLIST_FROM; i++) {
308	assertTrue(list.get(i) == (scale * original.get(i)),
309	"mismatch at original index " + i);
310	}
311	// verify that elements [to, size) remain unmodified
312	for (int i = SUBLIST_TO; i < list.size(); i++) {
313	assertTrue(list.get(i) == (scale * original.get(i)),
314	"mismatch at original index " + i);
315	}
316	}
317	}
318
319	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
320	final List<Integer> list = test.collection;
321	trimmedSubList(list, l -> {
322	final List<Integer> copy = new ArrayList<>(l);
323	final int offset = 5;
324	l.replaceAll(x -> offset + x);
325	for (int i = 0; i < copy.size(); i++) {
326	assertTrue(l.get(i) == (offset + copy.get(i)), "mismatch at index " + i);
327	}
328	});
329	}
330	}
331
332	@Test
333	public void testSort() {
334	@SuppressWarnings("unchecked")
335	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_SUPPLIERS, SIZE);
336	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
337	final List<Integer> original = test.expected;
338	final List<Integer> list = test.collection;
339	CollectionSupplier.shuffle(list);
340	list.sort(Integer::compare);
341	CollectionAsserts.assertSorted(list, Integer::compare);
342	if (test.name.startsWith("reverse")) {
343	Collections.reverse(list);
344	}
345	CollectionAsserts.assertContents(list, original);
346
347	CollectionSupplier.shuffle(list);
348	list.sort(null);
349	CollectionAsserts.assertSorted(list, Comparator.naturalOrder());
350	if (test.name.startsWith("reverse")) {
351	Collections.reverse(list);
352	}
353	CollectionAsserts.assertContents(list, original);
354
355	CollectionSupplier.shuffle(list);
356	list.sort(Comparator.naturalOrder());
357	CollectionAsserts.assertSorted(list, Comparator.naturalOrder());
358	if (test.name.startsWith("reverse")) {
359	Collections.reverse(list);
360	}
361	CollectionAsserts.assertContents(list, original);
362
363	CollectionSupplier.shuffle(list);
364	list.sort(Comparator.reverseOrder());
365	CollectionAsserts.assertSorted(list, Comparator.reverseOrder());
366	if (!test.name.startsWith("reverse")) {
367	Collections.reverse(list);
368	}
369	CollectionAsserts.assertContents(list, original);
370
371	CollectionSupplier.shuffle(list);
372	list.sort(BIT_COUNT_COMPARATOR);
373	CollectionAsserts.assertSorted(list, BIT_COUNT_COMPARATOR);
374	// check sort by verifying that bitCount increases and never drops
375	int minBitCount = 0;
376	for (final Integer i : list) {
377	int bitCount = Integer.bitCount(i);
378	assertTrue(bitCount >= minBitCount);
379	minBitCount = bitCount;
380	}
381
382	// Reuse the supplier to store AtomicInteger instead of Integer
383	// Hence the use of raw type and cast
384	List<AtomicInteger> incomparablesData = new ArrayList<>();
385	for (int i = 0; i < test.expected.size(); i++) {
386	incomparablesData.add(new AtomicInteger(i));
387	}
388	Function f = test.supplier;
389	@SuppressWarnings("unchecked")
390	List<AtomicInteger> incomparables = (List<AtomicInteger>) f.apply(incomparablesData);
391
392	CollectionSupplier.shuffle(incomparables);
393	incomparables.sort(ATOMIC_INTEGER_COMPARATOR);
394	for (int i = 0; i < test.expected.size(); i++) {
395	assertEquals(i, incomparables.get(i).intValue());
396	}
397
398
399	if (original.size() > SUBLIST_SIZE) {
400	final List<Integer> copy = new ArrayList<>(list);
401	final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
402	CollectionSupplier.shuffle(subList);
403	subList.sort(Comparator.naturalOrder());
404	CollectionAsserts.assertSorted(subList, Comparator.naturalOrder());
405	// verify that elements [0, from) remain unmodified
406	for (int i = 0; i < SUBLIST_FROM; i++) {
407	assertTrue(list.get(i) == copy.get(i),
408	"mismatch at index " + i);
409	}
410	// verify that elements [to, size) remain unmodified
411	for (int i = SUBLIST_TO; i < list.size(); i++) {
412	assertTrue(list.get(i) == copy.get(i),
413	"mismatch at index " + i);
414	}
415	}
416	}
417
418	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
419	final List<Integer> list = test.collection;
420	trimmedSubList(list, l -> {
421	CollectionSupplier.shuffle(l);
422	l.sort(Comparator.naturalOrder());
423	CollectionAsserts.assertSorted(l, Comparator.naturalOrder());
424	});
425	}
426	}
427
428	@Test
429	public void testForEachThrowsCME() {
430	@SuppressWarnings("unchecked")
431	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
432	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
433	final List<Integer> list = test.collection;
434
435	if (list.size() <= 1) {
436	continue;
437	}
438	boolean gotException = false;
439	try {
440	// bad predicate that modifies its list, should throw CME
441	list.forEach(list::add);
442	} catch (ConcurrentModificationException cme) {
443	gotException = true;
444	}
445	if (!gotException) {
446	fail("expected CME was not thrown from " + test);
447	}
448	}
449	}
450
451	@Test
452	public void testRemoveIfThrowsCME() {
453	@SuppressWarnings("unchecked")
454	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
455	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
456	final List<Integer> list = test.collection;
457
458	if (list.size() <= 1) {
459	continue;
460	}
461	boolean gotException = false;
462	try {
463	// bad predicate that modifies its list, should throw CME
464	list.removeIf(list::add);
465	} catch (ConcurrentModificationException cme) {
466	gotException = true;
467	}
468	if (!gotException) {
469	fail("expected CME was not thrown from " + test);
470	}
471	}
472	}
473
474	@Test
475	public void testReplaceAllThrowsCME() {
476	@SuppressWarnings("unchecked")
477	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
478	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
479	final List<Integer> list = test.collection;
480
481	if (list.size() <= 1) {
482	continue;
483	}
484	boolean gotException = false;
485	try {
486	// bad predicate that modifies its list, should throw CME
487	list.replaceAll(x -> {int n = 3 * x; list.add(n); return n;});
488	} catch (ConcurrentModificationException cme) {
489	gotException = true;
490	}
491	if (!gotException) {
492	fail("expected CME was not thrown from " + test);
493	}
494	}
495	}
496
497	@Test
498	public void testSortThrowsCME() {
499	@SuppressWarnings("unchecked")
500	final CollectionSupplier<List<Integer>> supplier = new CollectionSupplier(LIST_CME_SUPPLIERS, SIZE);
501	for (final CollectionSupplier.TestCase<List<Integer>> test : supplier.get()) {
502	final List<Integer> list = test.collection;
503
504	if (list.size() <= 1) {
505	continue;
506	}
507	boolean gotException = false;
508	try {
509	// bad predicate that modifies its list, should throw CME
510	list.sort((x, y) -> {list.add(x); return x - y;});
511	} catch (ConcurrentModificationException cme) {
512	gotException = true;
513	}
514	if (!gotException) {
515	fail("expected CME was not thrown from " + test);
516	}
517	}
518	}
519
520	private static final List<Integer> SLICED_EXPECTED = Arrays.asList(0, 1, 2, 3, 5, 6, 7, 8, 9);
521	private static final List<Integer> SLICED_EXPECTED2 = Arrays.asList(0, 1, 2, 5, 6, 7, 8, 9);
522
523	@DataProvider(name="shortIntListProvider", parallel=true)
524	public static Object[][] intListCases() {
525	final Integer[] DATA = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
526	final List<Object[]> cases = new LinkedList<>();
527	cases.add(new Object[] { new ArrayList<>(Arrays.asList(DATA)) });
528	cases.add(new Object[] { new LinkedList<>(Arrays.asList(DATA)) });
529	cases.add(new Object[] { new Vector<>(Arrays.asList(DATA)) });
530	cases.add(new Object[] { new CopyOnWriteArrayList<>(Arrays.asList(DATA)) });
531	cases.add(new Object[] { new ExtendsAbstractList<>(Arrays.asList(DATA)) });
532	return cases.toArray(new Object[0][cases.size()]);
533	}
534
535	@Test(dataProvider = "shortIntListProvider")
536	public void testRemoveIfFromSlice(final List<Integer> list) {
537	final List<Integer> sublist = list.subList(3, 6);
538	assertTrue(sublist.removeIf(x -> x == 4));
539	CollectionAsserts.assertContents(list, SLICED_EXPECTED);
540
541	final List<Integer> sublist2 = list.subList(2, 5);
542	assertTrue(sublist2.removeIf(x -> x == 3));
543	CollectionAsserts.assertContents(list, SLICED_EXPECTED2);
544	}
545	}