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.lang.reflect.Constructor;
import java.util.ConcurrentModificationException;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;

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