test/tck/CollectionTest.java

/*
 * Written by Doug Lea and Martin Buchholz with assistance from
 * members of JCP JSR-166 Expert Group and released to the public
 * domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Spliterator;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Consumer;
import java.util.function.Predicate;

import junit.framework.Test;

/**
 * Contains tests applicable to all Collection implementations.
 */
public class CollectionTest extends JSR166TestCase {
    final CollectionImplementation impl;

    /** Tests are parameterized by a Collection implementation. */
    CollectionTest(CollectionImplementation impl, String methodName) {
        super(methodName);
        this.impl = impl;
    }

    public static Test testSuite(CollectionImplementation impl) {
        return newTestSuite
            (parameterizedTestSuite(CollectionTest.class,
                                    CollectionImplementation.class,
                                    impl),
             jdk8ParameterizedTestSuite(CollectionTest.class,
                                        CollectionImplementation.class,
                                        impl));
    }

    /** Checks properties of empty collections. */
    public void testEmptyMeansEmpty() {
        Collection c = impl.emptyCollection();
        assertTrue(c.isEmpty());
        assertEquals(0, c.size());
        assertEquals("[]", c.toString());
        {
            Object[] a = c.toArray();
            assertEquals(0, a.length);
            assertSame(Object[].class, a.getClass());
        }
        {
            Object[] a = new Object[0];
            assertSame(a, c.toArray(a));
        }
        {
            Integer[] a = new Integer[0];
            assertSame(a, c.toArray(a));
        }
        {
            Integer[] a = { 1, 2, 3};
            assertSame(a, c.toArray(a));
            assertNull(a[0]);
            assertSame(2, a[1]);
            assertSame(3, a[2]);
        }
        assertIteratorExhausted(c.iterator());
        Consumer alwaysThrows = (e) -> { throw new AssertionError(); };
        c.forEach(alwaysThrows);
        c.iterator().forEachRemaining(alwaysThrows);
        c.spliterator().forEachRemaining(alwaysThrows);
        assertFalse(c.spliterator().tryAdvance(alwaysThrows));
        if (Queue.class.isAssignableFrom(impl.klazz())) {
            Queue q = (Queue) c;
            assertNull(q.peek());
            assertNull(q.poll());
        }
        if (Deque.class.isAssignableFrom(impl.klazz())) {
            Deque d = (Deque) c;
            assertNull(d.peekFirst());
            assertNull(d.peekLast());
            assertNull(d.pollFirst());
            assertNull(d.pollLast());
            assertIteratorExhausted(d.descendingIterator());
        }
    }

    public void testNullPointerExceptions() {
        Collection c = impl.emptyCollection();
        assertThrows(
            NullPointerException.class,
            () -> c.addAll(null),
            () -> c.containsAll(null),
            () -> c.retainAll(null),
            () -> c.removeAll(null),
            () -> c.removeIf(null),
            () -> c.toArray(null));

        if (!impl.permitsNulls()) {
            assertThrows(
                NullPointerException.class,
                () -> c.add(null));
        }
        if (!impl.permitsNulls()
            && Queue.class.isAssignableFrom(impl.klazz())) {
            Queue q = (Queue) c;
            assertThrows(
                NullPointerException.class,
                () -> q.offer(null));
        }
        if (!impl.permitsNulls()
            && Deque.class.isAssignableFrom(impl.klazz())) {
            Deque d = (Deque) c;
            assertThrows(
                NullPointerException.class,
                () -> d.addFirst(null),
                () -> d.addLast(null),
                () -> d.offerFirst(null),
                () -> d.offerLast(null),
                () -> d.push(null));
        }
    }

    public void testNoSuchElementExceptions() {
        Collection c = impl.emptyCollection();
        assertThrows(
            NoSuchElementException.class,
            () -> c.iterator().next());

        if (Queue.class.isAssignableFrom(impl.klazz())) {
            Queue q = (Queue) c;
            assertThrows(
                NoSuchElementException.class,
                () -> q.element(),
                () -> q.remove());
        }
        if (Deque.class.isAssignableFrom(impl.klazz())) {
            Deque d = (Deque) c;
            assertThrows(
                NoSuchElementException.class,
                () -> d.getFirst(),
                () -> d.getLast(),
                () -> d.removeFirst(),
                () -> d.removeLast(),
                () -> d.pop(),
                () -> d.descendingIterator().next());
        }
    }

    public void testRemoveIf() {
        Collection c = impl.emptyCollection();
        ThreadLocalRandom rnd = ThreadLocalRandom.current();
        int n = rnd.nextInt(6);
        for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
        AtomicReference threwAt = new AtomicReference(null);
        ArrayList survivors = new ArrayList(c);
        ArrayList accepts = new ArrayList();
        ArrayList rejects = new ArrayList();
        Predicate randomPredicate = (e) -> {
            assertNull(threwAt.get());
            switch (rnd.nextInt(3)) {
            case 0: accepts.add(e); return true;
            case 1: rejects.add(e); return false;
            case 2: threwAt.set(e); throw new ArithmeticException();
            default: throw new AssertionError();
            }
        };
        try {
            boolean modified = c.removeIf(randomPredicate);
            if (!modified) {
                assertNull(threwAt.get());
                assertEquals(n, rejects.size());
                assertEquals(0, accepts.size());
            }
        } catch (ArithmeticException ok) {}
        survivors.removeAll(accepts);
        if (n - accepts.size() != c.size()) {
            System.err.println(impl.klazz());
            System.err.println(c);
            System.err.println(accepts);
            System.err.println(rejects);
            System.err.println(survivors);
            System.err.println(threwAt.get());
        }
        assertEquals(n - accepts.size(), c.size());
        assertTrue(c.containsAll(survivors));
        assertTrue(survivors.containsAll(rejects));
        for (Object x : accepts) assertFalse(c.contains(x));
        if (threwAt.get() == null)
            assertEquals(accepts.size() + rejects.size(), n);
    }

    /**
     * Various ways of traversing a collection yield same elements
     */
    public void testIteratorEquivalence() {
        Collection c = impl.emptyCollection();
        ThreadLocalRandom rnd = ThreadLocalRandom.current();
        int n = rnd.nextInt(6);
        for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
        ArrayList iterated = new ArrayList();
        ArrayList iteratedForEachRemaining = new ArrayList();
        ArrayList spliterated = new ArrayList();
        ArrayList foreached = new ArrayList();
        for (Object x : c) iterated.add(x);
        c.iterator().forEachRemaining(e -> iteratedForEachRemaining.add(e));
        c.spliterator().forEachRemaining(e -> spliterated.add(e));
        c.forEach(e -> foreached.add(e));
        boolean ordered =
            c.spliterator().hasCharacteristics(Spliterator.ORDERED);
        if (c instanceof List || c instanceof Deque)
            assertTrue(ordered);
        if (ordered) {
            assertEquals(iterated, iteratedForEachRemaining);
            assertEquals(iterated, spliterated);
            assertEquals(iterated, foreached);
        } else {
            HashSet cset = new HashSet(c);
            assertEquals(cset, new HashSet(iterated));
            assertEquals(cset, new HashSet(iteratedForEachRemaining));
            assertEquals(cset, new HashSet(spliterated));
            assertEquals(cset, new HashSet(foreached));
        }
        if (c instanceof Deque) {
            Deque d = (Deque) c;
            ArrayList descending = new ArrayList();
            ArrayList descendingForEachRemaining = new ArrayList();
            for (Iterator it = d.descendingIterator(); it.hasNext(); )
                descending.add(it.next());
            d.descendingIterator().forEachRemaining(
                e -> descendingForEachRemaining.add(e));
            Collections.reverse(descending);
            Collections.reverse(descendingForEachRemaining);
            assertEquals(iterated, descending);
            assertEquals(iterated, descendingForEachRemaining);
        }
    }

    /**
     * Calling Iterator#remove() after Iterator#forEachRemaining
     * should remove last element
     */
    public void testRemoveAfterForEachRemaining() {
        Collection c = impl.emptyCollection();
        ThreadLocalRandom rnd = ThreadLocalRandom.current();
        {
            int n = 3 + rnd.nextInt(2);
            for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
            Iterator it = c.iterator();
            assertTrue(it.hasNext());
            assertEquals(impl.makeElement(0), it.next());
            assertTrue(it.hasNext());
            assertEquals(impl.makeElement(1), it.next());
            it.forEachRemaining((e) -> {});
            it.remove();
            assertEquals(n - 1, c.size());
            for (int i = 0; i < n - 1; i++)
                assertTrue(c.contains(impl.makeElement(i)));
            assertFalse(c.contains(impl.makeElement(n - 1)));
        }
        if (c instanceof Deque) {
            Deque d = (Deque) impl.emptyCollection();
            int n = 3 + rnd.nextInt(2);
            for (int i = 0; i < n; i++) d.add(impl.makeElement(i));
            Iterator it = d.descendingIterator();
            assertTrue(it.hasNext());
            assertEquals(impl.makeElement(n - 1), it.next());
            assertTrue(it.hasNext());
            assertEquals(impl.makeElement(n - 2), it.next());
            it.forEachRemaining((e) -> {});
            it.remove();
            assertEquals(n - 1, d.size());
            for (int i = 1; i < n; i++)
                assertTrue(d.contains(impl.makeElement(i)));
            assertFalse(d.contains(impl.makeElement(0)));
        }
    }

//     public void testCollectionDebugFail() {
//         fail(impl.klazz().getSimpleName());
//     }
}
Revision:	1.9
Committed:	Mon Oct 24 22:45:50 2016 UTC (7 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.8:	+91 -0 lines
Log Message:	add testRemoveAfterForEachRemaining, testIteratorEquivalence
#	User	Rev	Content
1	jsr166	1.1	/*
2			* Written by Doug Lea and Martin Buchholz with assistance from
3			* members of JCP JSR-166 Expert Group and released to the public
4			* domain, as explained at
5			* http://creativecommons.org/publicdomain/zero/1.0/
6			*/
7
8	jsr166	1.6	import java.util.ArrayList;
9	jsr166	1.1	import java.util.Collection;
10	jsr166	1.9	import java.util.Collections;
11	jsr166	1.2	import java.util.Deque;
12	jsr166	1.9	import java.util.HashSet;
13			import java.util.Iterator;
14			import java.util.List;
15	jsr166	1.2	import java.util.NoSuchElementException;
16			import java.util.Queue;
17	jsr166	1.9	import java.util.Spliterator;
18	jsr166	1.6	import java.util.concurrent.ThreadLocalRandom;
19			import java.util.concurrent.atomic.AtomicReference;
20	jsr166	1.3	import java.util.function.Consumer;
21	jsr166	1.6	import java.util.function.Predicate;
22	jsr166	1.1
23			import junit.framework.Test;
24
25			/**
26			* Contains tests applicable to all Collection implementations.
27			*/
28			public class CollectionTest extends JSR166TestCase {
29			final CollectionImplementation impl;
30
31			/** Tests are parameterized by a Collection implementation. */
32			CollectionTest(CollectionImplementation impl, String methodName) {
33			super(methodName);
34			this.impl = impl;
35			}
36
37			public static Test testSuite(CollectionImplementation impl) {
38			return newTestSuite
39			(parameterizedTestSuite(CollectionTest.class,
40			CollectionImplementation.class,
41			impl),
42			jdk8ParameterizedTestSuite(CollectionTest.class,
43			CollectionImplementation.class,
44			impl));
45			}
46
47	jsr166	1.2	/** Checks properties of empty collections. */
48	jsr166	1.1	public void testEmptyMeansEmpty() {
49	jsr166	1.2	Collection c = impl.emptyCollection();
50			assertTrue(c.isEmpty());
51			assertEquals(0, c.size());
52			assertEquals("[]", c.toString());
53	jsr166	1.8	{
54			Object[] a = c.toArray();
55			assertEquals(0, a.length);
56			assertSame(Object[].class, a.getClass());
57			}
58	jsr166	1.2	{
59			Object[] a = new Object[0];
60			assertSame(a, c.toArray(a));
61			}
62	jsr166	1.8	{
63			Integer[] a = new Integer[0];
64			assertSame(a, c.toArray(a));
65			}
66			{
67			Integer[] a = { 1, 2, 3};
68			assertSame(a, c.toArray(a));
69			assertNull(a[0]);
70			assertSame(2, a[1]);
71			assertSame(3, a[2]);
72			}
73	jsr166	1.5	assertIteratorExhausted(c.iterator());
74	jsr166	1.3	Consumer alwaysThrows = (e) -> { throw new AssertionError(); };
75			c.forEach(alwaysThrows);
76			c.iterator().forEachRemaining(alwaysThrows);
77			c.spliterator().forEachRemaining(alwaysThrows);
78			assertFalse(c.spliterator().tryAdvance(alwaysThrows));
79	jsr166	1.2	if (Queue.class.isAssignableFrom(impl.klazz())) {
80			Queue q = (Queue) c;
81			assertNull(q.peek());
82			assertNull(q.poll());
83			}
84			if (Deque.class.isAssignableFrom(impl.klazz())) {
85			Deque d = (Deque) c;
86			assertNull(d.peekFirst());
87			assertNull(d.peekLast());
88			assertNull(d.pollFirst());
89			assertNull(d.pollLast());
90	jsr166	1.5	assertIteratorExhausted(d.descendingIterator());
91	jsr166	1.2	}
92			}
93
94			public void testNullPointerExceptions() {
95			Collection c = impl.emptyCollection();
96			assertThrows(
97			NullPointerException.class,
98			() -> c.addAll(null),
99			() -> c.containsAll(null),
100			() -> c.retainAll(null),
101			() -> c.removeAll(null),
102	jsr166	1.8	() -> c.removeIf(null),
103			() -> c.toArray(null));
104	jsr166	1.2
105			if (!impl.permitsNulls()) {
106			assertThrows(
107			NullPointerException.class,
108			() -> c.add(null));
109			}
110			if (!impl.permitsNulls()
111			&& Queue.class.isAssignableFrom(impl.klazz())) {
112			Queue q = (Queue) c;
113			assertThrows(
114			NullPointerException.class,
115			() -> q.offer(null));
116			}
117			if (!impl.permitsNulls()
118			&& Deque.class.isAssignableFrom(impl.klazz())) {
119			Deque d = (Deque) c;
120			assertThrows(
121			NullPointerException.class,
122			() -> d.addFirst(null),
123			() -> d.addLast(null),
124			() -> d.offerFirst(null),
125			() -> d.offerLast(null),
126			() -> d.push(null));
127			}
128			}
129
130			public void testNoSuchElementExceptions() {
131			Collection c = impl.emptyCollection();
132	jsr166	1.3	assertThrows(
133			NoSuchElementException.class,
134			() -> c.iterator().next());
135	jsr166	1.2
136			if (Queue.class.isAssignableFrom(impl.klazz())) {
137			Queue q = (Queue) c;
138			assertThrows(
139			NoSuchElementException.class,
140			() -> q.element(),
141			() -> q.remove());
142			}
143			if (Deque.class.isAssignableFrom(impl.klazz())) {
144			Deque d = (Deque) c;
145			assertThrows(
146			NoSuchElementException.class,
147			() -> d.getFirst(),
148			() -> d.getLast(),
149			() -> d.removeFirst(),
150			() -> d.removeLast(),
151	jsr166	1.5	() -> d.pop(),
152			() -> d.descendingIterator().next());
153	jsr166	1.2	}
154	jsr166	1.1	}
155
156	jsr166	1.6	public void testRemoveIf() {
157			Collection c = impl.emptyCollection();
158			ThreadLocalRandom rnd = ThreadLocalRandom.current();
159			int n = rnd.nextInt(6);
160			for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
161			AtomicReference threwAt = new AtomicReference(null);
162			ArrayList survivors = new ArrayList(c);
163			ArrayList accepts = new ArrayList();
164			ArrayList rejects = new ArrayList();
165			Predicate randomPredicate = (e) -> {
166			assertNull(threwAt.get());
167			switch (rnd.nextInt(3)) {
168			case 0: accepts.add(e); return true;
169			case 1: rejects.add(e); return false;
170			case 2: threwAt.set(e); throw new ArithmeticException();
171			default: throw new AssertionError();
172			}
173			};
174			try {
175			boolean modified = c.removeIf(randomPredicate);
176			if (!modified) {
177			assertNull(threwAt.get());
178			assertEquals(n, rejects.size());
179			assertEquals(0, accepts.size());
180			}
181			} catch (ArithmeticException ok) {}
182			survivors.removeAll(accepts);
183	jsr166	1.7	if (n - accepts.size() != c.size()) {
184			System.err.println(impl.klazz());
185			System.err.println(c);
186			System.err.println(accepts);
187			System.err.println(rejects);
188			System.err.println(survivors);
189			System.err.println(threwAt.get());
190			}
191	jsr166	1.6	assertEquals(n - accepts.size(), c.size());
192			assertTrue(c.containsAll(survivors));
193			assertTrue(survivors.containsAll(rejects));
194			for (Object x : accepts) assertFalse(c.contains(x));
195			if (threwAt.get() == null)
196			assertEquals(accepts.size() + rejects.size(), n);
197			}
198
199	jsr166	1.9	/**
200			* Various ways of traversing a collection yield same elements
201			*/
202			public void testIteratorEquivalence() {
203			Collection c = impl.emptyCollection();
204			ThreadLocalRandom rnd = ThreadLocalRandom.current();
205			int n = rnd.nextInt(6);
206			for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
207			ArrayList iterated = new ArrayList();
208			ArrayList iteratedForEachRemaining = new ArrayList();
209			ArrayList spliterated = new ArrayList();
210			ArrayList foreached = new ArrayList();
211			for (Object x : c) iterated.add(x);
212			c.iterator().forEachRemaining(e -> iteratedForEachRemaining.add(e));
213			c.spliterator().forEachRemaining(e -> spliterated.add(e));
214			c.forEach(e -> foreached.add(e));
215			boolean ordered =
216			c.spliterator().hasCharacteristics(Spliterator.ORDERED);
217			if (c instanceof List \|\| c instanceof Deque)
218			assertTrue(ordered);
219			if (ordered) {
220			assertEquals(iterated, iteratedForEachRemaining);
221			assertEquals(iterated, spliterated);
222			assertEquals(iterated, foreached);
223			} else {
224			HashSet cset = new HashSet(c);
225			assertEquals(cset, new HashSet(iterated));
226			assertEquals(cset, new HashSet(iteratedForEachRemaining));
227			assertEquals(cset, new HashSet(spliterated));
228			assertEquals(cset, new HashSet(foreached));
229			}
230			if (c instanceof Deque) {
231			Deque d = (Deque) c;
232			ArrayList descending = new ArrayList();
233			ArrayList descendingForEachRemaining = new ArrayList();
234			for (Iterator it = d.descendingIterator(); it.hasNext(); )
235			descending.add(it.next());
236			d.descendingIterator().forEachRemaining(
237			e -> descendingForEachRemaining.add(e));
238			Collections.reverse(descending);
239			Collections.reverse(descendingForEachRemaining);
240			assertEquals(iterated, descending);
241			assertEquals(iterated, descendingForEachRemaining);
242			}
243			}
244
245			/**
246			* Calling Iterator#remove() after Iterator#forEachRemaining
247			* should remove last element
248			*/
249			public void testRemoveAfterForEachRemaining() {
250			Collection c = impl.emptyCollection();
251			ThreadLocalRandom rnd = ThreadLocalRandom.current();
252			{
253			int n = 3 + rnd.nextInt(2);
254			for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
255			Iterator it = c.iterator();
256			assertTrue(it.hasNext());
257			assertEquals(impl.makeElement(0), it.next());
258			assertTrue(it.hasNext());
259			assertEquals(impl.makeElement(1), it.next());
260			it.forEachRemaining((e) -> {});
261			it.remove();
262			assertEquals(n - 1, c.size());
263			for (int i = 0; i < n - 1; i++)
264			assertTrue(c.contains(impl.makeElement(i)));
265			assertFalse(c.contains(impl.makeElement(n - 1)));
266			}
267			if (c instanceof Deque) {
268			Deque d = (Deque) impl.emptyCollection();
269			int n = 3 + rnd.nextInt(2);
270			for (int i = 0; i < n; i++) d.add(impl.makeElement(i));
271			Iterator it = d.descendingIterator();
272			assertTrue(it.hasNext());
273			assertEquals(impl.makeElement(n - 1), it.next());
274			assertTrue(it.hasNext());
275			assertEquals(impl.makeElement(n - 2), it.next());
276			it.forEachRemaining((e) -> {});
277			it.remove();
278			assertEquals(n - 1, d.size());
279			for (int i = 1; i < n; i++)
280			assertTrue(d.contains(impl.makeElement(i)));
281			assertFalse(d.contains(impl.makeElement(0)));
282			}
283			}
284
285	jsr166	1.4	// public void testCollectionDebugFail() {
286			// fail(impl.klazz().getSimpleName());
287			// }
288	jsr166	1.1	}