--- jsr166/src/test/tck/ArrayDequeTest.java 2013/05/30 03:28:55 1.28 +++ jsr166/src/test/tck/ArrayDequeTest.java 2017/03/11 17:33:32 1.55 @@ -1,39 +1,82 @@ /* - * Written by Doug Lea with assistance from members of JCP JSR-166 - * Expert Group and released to the public domain, as explained at + * 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 junit.framework.*; -import java.util.Arrays; import java.util.ArrayDeque; +import java.util.Arrays; import java.util.Collection; import java.util.Deque; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Queue; import java.util.Random; +import java.util.concurrent.ThreadLocalRandom; + +import junit.framework.Test; public class ArrayDequeTest extends JSR166TestCase { public static void main(String[] args) { - junit.textui.TestRunner.run(suite()); + main(suite(), args); } public static Test suite() { - return new TestSuite(ArrayDequeTest.class); + class Implementation implements CollectionImplementation { + public Class klazz() { return ArrayDeque.class; } + public Collection emptyCollection() { return populatedDeque(0); } + public Object makeElement(int i) { return i; } + public boolean isConcurrent() { return false; } + public boolean permitsNulls() { return false; } + } + return newTestSuite(ArrayDequeTest.class, + CollectionTest.testSuite(new Implementation())); } /** * Returns a new deque of given size containing consecutive - * Integers 0 ... n. + * Integers 0 ... n - 1. */ - private ArrayDeque populatedDeque(int n) { - ArrayDeque q = new ArrayDeque(); + private static ArrayDeque populatedDeque(int n) { + // Randomize various aspects of memory layout, including + // capacity slop and wraparound. + final ArrayDeque q; + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + switch (rnd.nextInt(6)) { + case 0: q = new ArrayDeque(); break; + case 1: q = new ArrayDeque(0); break; + case 2: q = new ArrayDeque(1); break; + case 3: q = new ArrayDeque(Math.max(0, n - 1)); break; + case 4: q = new ArrayDeque(n); break; + case 5: q = new ArrayDeque(n + 1); break; + default: throw new AssertionError(); + } + switch (rnd.nextInt(3)) { + case 0: + q.addFirst(42); + assertEquals((Integer) 42, q.removeLast()); + break; + case 1: + q.addLast(42); + assertEquals((Integer) 42, q.removeFirst()); + break; + case 2: /* do nothing */ break; + default: throw new AssertionError(); + } assertTrue(q.isEmpty()); - for (int i = 0; i < n; ++i) - assertTrue(q.offerLast(new Integer(i))); - assertFalse(q.isEmpty()); + if (rnd.nextBoolean()) + for (int i = 0; i < n; i++) + assertTrue(q.offerLast((Integer) i)); + else + for (int i = n; --i >= 0; ) + q.addFirst((Integer) i); assertEquals(n, q.size()); + if (n > 0) { + assertFalse(q.isEmpty()); + assertEquals((Integer) 0, q.peekFirst()); + assertEquals((Integer) (n - 1), q.peekLast()); + } return q; } @@ -49,7 +92,7 @@ public class ArrayDequeTest extends JSR1 */ public void testConstructor3() { try { - ArrayDeque q = new ArrayDeque((Collection)null); + new ArrayDeque((Collection)null); shouldThrow(); } catch (NullPointerException success) {} } @@ -59,8 +102,7 @@ public class ArrayDequeTest extends JSR1 */ public void testConstructor4() { try { - Integer[] ints = new Integer[SIZE]; - ArrayDeque q = new ArrayDeque(Arrays.asList(ints)); + new ArrayDeque(Arrays.asList(new Integer[SIZE])); shouldThrow(); } catch (NullPointerException success) {} } @@ -69,11 +111,11 @@ public class ArrayDequeTest extends JSR1 * Initializing from Collection with some null elements throws NPE */ public void testConstructor5() { + Integer[] ints = new Integer[SIZE]; + for (int i = 0; i < SIZE - 1; ++i) + ints[i] = new Integer(i); try { - Integer[] ints = new Integer[SIZE]; - for (int i = 0; i < SIZE-1; ++i) - ints[i] = new Integer(i); - ArrayDeque q = new ArrayDeque(Arrays.asList(ints)); + new ArrayDeque(Arrays.asList(ints)); shouldThrow(); } catch (NullPointerException success) {} } @@ -110,7 +152,7 @@ public class ArrayDequeTest extends JSR1 public void testSize() { ArrayDeque q = populatedDeque(SIZE); for (int i = 0; i < SIZE; ++i) { - assertEquals(SIZE-i, q.size()); + assertEquals(SIZE - i, q.size()); q.removeFirst(); } for (int i = 0; i < SIZE; ++i) { @@ -123,8 +165,8 @@ public class ArrayDequeTest extends JSR1 * push(null) throws NPE */ public void testPushNull() { + ArrayDeque q = new ArrayDeque(1); try { - ArrayDeque q = new ArrayDeque(1); q.push(null); shouldThrow(); } catch (NullPointerException success) {} @@ -158,8 +200,8 @@ public class ArrayDequeTest extends JSR1 * offer(null) throws NPE */ public void testOfferNull() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); q.offer(null); shouldThrow(); } catch (NullPointerException success) {} @@ -169,8 +211,8 @@ public class ArrayDequeTest extends JSR1 * offerFirst(null) throws NPE */ public void testOfferFirstNull() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); q.offerFirst(null); shouldThrow(); } catch (NullPointerException success) {} @@ -180,8 +222,8 @@ public class ArrayDequeTest extends JSR1 * offerLast(null) throws NPE */ public void testOfferLastNull() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); q.offerLast(null); shouldThrow(); } catch (NullPointerException success) {} @@ -224,8 +266,8 @@ public class ArrayDequeTest extends JSR1 * add(null) throws NPE */ public void testAddNull() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); q.add(null); shouldThrow(); } catch (NullPointerException success) {} @@ -235,8 +277,8 @@ public class ArrayDequeTest extends JSR1 * addFirst(null) throws NPE */ public void testAddFirstNull() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); q.addFirst(null); shouldThrow(); } catch (NullPointerException success) {} @@ -246,8 +288,8 @@ public class ArrayDequeTest extends JSR1 * addLast(null) throws NPE */ public void testAddLastNull() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); q.addLast(null); shouldThrow(); } catch (NullPointerException success) {} @@ -290,8 +332,8 @@ public class ArrayDequeTest extends JSR1 * addAll(null) throws NPE */ public void testAddAll1() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); q.addAll(null); shouldThrow(); } catch (NullPointerException success) {} @@ -301,10 +343,9 @@ public class ArrayDequeTest extends JSR1 * addAll of a collection with null elements throws NPE */ public void testAddAll2() { + ArrayDeque q = new ArrayDeque(); try { - ArrayDeque q = new ArrayDeque(); - Integer[] ints = new Integer[SIZE]; - q.addAll(Arrays.asList(ints)); + q.addAll(Arrays.asList(new Integer[SIZE])); shouldThrow(); } catch (NullPointerException success) {} } @@ -314,11 +355,11 @@ public class ArrayDequeTest extends JSR1 * possibly adding some elements */ public void testAddAll3() { + ArrayDeque q = new ArrayDeque(); + Integer[] ints = new Integer[SIZE]; + for (int i = 0; i < SIZE - 1; ++i) + ints[i] = new Integer(i); try { - ArrayDeque q = new ArrayDeque(); - Integer[] ints = new Integer[SIZE]; - for (int i = 0; i < SIZE-1; ++i) - ints[i] = new Integer(i); q.addAll(Arrays.asList(ints)); shouldThrow(); } catch (NullPointerException success) {} @@ -355,7 +396,7 @@ public class ArrayDequeTest extends JSR1 */ public void testPollLast() { ArrayDeque q = populatedDeque(SIZE); - for (int i = SIZE-1; i >= 0; --i) { + for (int i = SIZE - 1; i >= 0; --i) { assertEquals(i, q.pollLast()); } assertNull(q.pollLast()); @@ -391,18 +432,18 @@ public class ArrayDequeTest extends JSR1 */ public void testRemoveElement() { ArrayDeque q = populatedDeque(SIZE); - for (int i = 1; i < SIZE; i+=2) { + for (int i = 1; i < SIZE; i += 2) { assertTrue(q.contains(i)); assertTrue(q.remove(i)); assertFalse(q.contains(i)); - assertTrue(q.contains(i-1)); + assertTrue(q.contains(i - 1)); } - for (int i = 0; i < SIZE; i+=2) { + for (int i = 0; i < SIZE; i += 2) { assertTrue(q.contains(i)); assertTrue(q.remove(i)); assertFalse(q.contains(i)); - assertFalse(q.remove(i+1)); - assertFalse(q.contains(i+1)); + assertFalse(q.remove(i + 1)); + assertFalse(q.contains(i + 1)); } assertTrue(q.isEmpty()); } @@ -440,7 +481,7 @@ public class ArrayDequeTest extends JSR1 */ public void testPeekLast() { ArrayDeque q = populatedDeque(SIZE); - for (int i = SIZE-1; i >= 0; --i) { + for (int i = SIZE - 1; i >= 0; --i) { assertEquals(i, q.peekLast()); assertEquals(i, q.pollLast()); assertTrue(q.peekLast() == null || @@ -484,7 +525,7 @@ public class ArrayDequeTest extends JSR1 */ public void testLastElement() { ArrayDeque q = populatedDeque(SIZE); - for (int i = SIZE-1; i >= 0; --i) { + for (int i = SIZE - 1; i >= 0; --i) { assertEquals(i, q.getLast()); assertEquals(i, q.pollLast()); } @@ -529,30 +570,48 @@ public class ArrayDequeTest extends JSR1 * removeFirstOccurrence(x) removes x and returns true if present */ public void testRemoveFirstOccurrence() { - ArrayDeque q = populatedDeque(SIZE); - for (int i = 1; i < SIZE; i+=2) { - assertTrue(q.removeFirstOccurrence(new Integer(i))); + Deque q = populatedDeque(SIZE); + assertFalse(q.removeFirstOccurrence(null)); + for (int i = 1; i < SIZE; i += 2) { + assertTrue(q.removeFirstOccurrence(i)); + assertFalse(q.contains(i)); } - for (int i = 0; i < SIZE; i+=2) { - assertTrue(q.removeFirstOccurrence(new Integer(i))); - assertFalse(q.removeFirstOccurrence(new Integer(i+1))); + for (int i = 0; i < SIZE; i += 2) { + assertTrue(q.removeFirstOccurrence(i)); + assertFalse(q.removeFirstOccurrence(i + 1)); + assertFalse(q.contains(i)); + assertFalse(q.contains(i + 1)); } assertTrue(q.isEmpty()); + assertFalse(q.removeFirstOccurrence(null)); + assertFalse(q.removeFirstOccurrence(42)); + q = new ArrayDeque(); + assertFalse(q.removeFirstOccurrence(null)); + assertFalse(q.removeFirstOccurrence(42)); } /** * removeLastOccurrence(x) removes x and returns true if present */ public void testRemoveLastOccurrence() { - ArrayDeque q = populatedDeque(SIZE); - for (int i = 1; i < SIZE; i+=2) { - assertTrue(q.removeLastOccurrence(new Integer(i))); + Deque q = populatedDeque(SIZE); + assertFalse(q.removeLastOccurrence(null)); + for (int i = 1; i < SIZE; i += 2) { + assertTrue(q.removeLastOccurrence(i)); + assertFalse(q.contains(i)); } - for (int i = 0; i < SIZE; i+=2) { - assertTrue(q.removeLastOccurrence(new Integer(i))); - assertFalse(q.removeLastOccurrence(new Integer(i+1))); + for (int i = 0; i < SIZE; i += 2) { + assertTrue(q.removeLastOccurrence(i)); + assertFalse(q.removeLastOccurrence(i + 1)); + assertFalse(q.contains(i)); + assertFalse(q.contains(i + 1)); } assertTrue(q.isEmpty()); + assertFalse(q.removeLastOccurrence(null)); + assertFalse(q.removeLastOccurrence(42)); + q = new ArrayDeque(); + assertFalse(q.removeLastOccurrence(null)); + assertFalse(q.removeLastOccurrence(42)); } /** @@ -605,7 +664,7 @@ public class ArrayDequeTest extends JSR1 boolean changed = q.retainAll(p); assertEquals(changed, (i > 0)); assertTrue(q.containsAll(p)); - assertEquals(SIZE-i, q.size()); + assertEquals(SIZE - i, q.size()); p.removeFirst(); } } @@ -618,96 +677,64 @@ public class ArrayDequeTest extends JSR1 ArrayDeque q = populatedDeque(SIZE); ArrayDeque p = populatedDeque(i); assertTrue(q.removeAll(p)); - assertEquals(SIZE-i, q.size()); + assertEquals(SIZE - i, q.size()); for (int j = 0; j < i; ++j) { assertFalse(q.contains(p.removeFirst())); } } } - void checkToArray(ArrayDeque q) { + void checkToArray(ArrayDeque q) { int size = q.size(); - Object[] o = q.toArray(); - assertEquals(size, o.length); + Object[] a1 = q.toArray(); + assertEquals(size, a1.length); + Integer[] a2 = q.toArray(new Integer[0]); + assertEquals(size, a2.length); + Integer[] a3 = q.toArray(new Integer[Math.max(0, size - 1)]); + assertEquals(size, a3.length); + Integer[] a4 = new Integer[size]; + assertSame(a4, q.toArray(a4)); + Integer[] a5 = new Integer[size + 1]; + Arrays.fill(a5, 42); + assertSame(a5, q.toArray(a5)); + Integer[] a6 = new Integer[size + 2]; + Arrays.fill(a6, 42); + assertSame(a6, q.toArray(a6)); + Object[][] as = { a1, a2, a3, a4, a5, a6 }; + for (Object[] a : as) { + if (a.length > size) assertNull(a[size]); + if (a.length > size + 1) assertEquals(42, a[size + 1]); + } Iterator it = q.iterator(); + Integer s = q.peekFirst(); for (int i = 0; i < size; i++) { Integer x = (Integer) it.next(); - assertEquals((Integer)o[0] + i, (int) x); - assertSame(o[i], x); + assertEquals(s + i, (int) x); + for (Object[] a : as) + assertSame(a1[i], x); } } /** - * toArray() contains all elements in FIFO order + * toArray() and toArray(a) contain all elements in FIFO order */ public void testToArray() { - ArrayDeque q = new ArrayDeque(); - for (int i = 0; i < SIZE; i++) { + final int size = ThreadLocalRandom.current().nextInt(10); + ArrayDeque q = new ArrayDeque<>(size); + for (int i = 0; i < size; i++) { checkToArray(q); q.addLast(i); } // Provoke wraparound - for (int i = 0; i < SIZE; i++) { + int added = size * 2; + for (int i = 0; i < added; i++) { checkToArray(q); - assertEquals(i, q.poll()); - q.addLast(SIZE+i); + assertEquals((Integer) i, q.poll()); + q.addLast(size + i); } - for (int i = 0; i < SIZE; i++) { - checkToArray(q); - assertEquals(SIZE+i, q.poll()); - } - } - - void checkToArray2(ArrayDeque q) { - int size = q.size(); - Integer[] a1 = size == 0 ? null : new Integer[size-1]; - Integer[] a2 = new Integer[size]; - Integer[] a3 = new Integer[size+2]; - if (size > 0) Arrays.fill(a1, 42); - Arrays.fill(a2, 42); - Arrays.fill(a3, 42); - Integer[] b1 = size == 0 ? null : (Integer[]) q.toArray(a1); - Integer[] b2 = (Integer[]) q.toArray(a2); - Integer[] b3 = (Integer[]) q.toArray(a3); - assertSame(a2, b2); - assertSame(a3, b3); - Iterator it = q.iterator(); for (int i = 0; i < size; i++) { - Integer x = (Integer) it.next(); - assertSame(b1[i], x); - assertEquals(b1[0] + i, (int) x); - assertSame(b2[i], x); - assertSame(b3[i], x); - } - assertNull(a3[size]); - assertEquals(42, (int) a3[size+1]); - if (size > 0) { - assertNotSame(a1, b1); - assertEquals(size, b1.length); - for (int i = 0; i < a1.length; i++) { - assertEquals(42, (int) a1[i]); - } - } - } - - /** - * toArray(a) contains all elements in FIFO order - */ - public void testToArray2() { - ArrayDeque q = new ArrayDeque(); - for (int i = 0; i < SIZE; i++) { - checkToArray2(q); - q.addLast(i); - } - // Provoke wraparound - for (int i = 0; i < SIZE; i++) { - checkToArray2(q); - assertEquals(i, q.poll()); - q.addLast(SIZE+i); - } - for (int i = 0; i < SIZE; i++) { - checkToArray2(q); - assertEquals(SIZE+i, q.poll()); + checkToArray(q); + assertEquals((Integer) (added + i), q.poll()); } } @@ -726,13 +753,17 @@ public class ArrayDequeTest extends JSR1 /** * toArray(incompatible array type) throws ArrayStoreException */ - public void testToArray1_BadArg() { + public void testToArray_incompatibleArrayType() { ArrayDeque l = new ArrayDeque(); l.add(new Integer(5)); try { l.toArray(new String[10]); shouldThrow(); } catch (ArrayStoreException success) {} + try { + l.toArray(new String[0]); + shouldThrow(); + } catch (ArrayStoreException success) {} } /** @@ -740,13 +771,21 @@ public class ArrayDequeTest extends JSR1 */ public void testIterator() { ArrayDeque q = populatedDeque(SIZE); - int i = 0; Iterator it = q.iterator(); - while (it.hasNext()) { + int i; + for (i = 0; it.hasNext(); i++) assertTrue(q.contains(it.next())); - ++i; - } assertEquals(i, SIZE); + assertIteratorExhausted(it); + } + + /** + * iterator of empty collection has no elements + */ + public void testEmptyIterator() { + Deque c = new ArrayDeque(); + assertIteratorExhausted(c.iterator()); + assertIteratorExhausted(c.descendingIterator()); } /** @@ -773,18 +812,18 @@ public class ArrayDequeTest extends JSR1 final Random rng = new Random(); for (int iters = 0; iters < 100; ++iters) { int max = rng.nextInt(5) + 2; - int split = rng.nextInt(max-1) + 1; + int split = rng.nextInt(max - 1) + 1; for (int j = 1; j <= max; ++j) q.add(new Integer(j)); Iterator it = q.iterator(); for (int j = 1; j <= split; ++j) assertEquals(it.next(), new Integer(j)); it.remove(); - assertEquals(it.next(), new Integer(split+1)); + assertEquals(it.next(), new Integer(split + 1)); for (int j = 1; j <= split; ++j) q.remove(new Integer(j)); it = q.iterator(); - for (int j = split+1; j <= max; ++j) { + for (int j = split + 1; j <= max; ++j) { assertEquals(it.next(), new Integer(j)); it.remove(); } @@ -841,18 +880,18 @@ public class ArrayDequeTest extends JSR1 final Random rng = new Random(); for (int iters = 0; iters < 100; ++iters) { int max = rng.nextInt(5) + 2; - int split = rng.nextInt(max-1) + 1; + int split = rng.nextInt(max - 1) + 1; for (int j = max; j >= 1; --j) q.add(new Integer(j)); Iterator it = q.descendingIterator(); for (int j = 1; j <= split; ++j) assertEquals(it.next(), new Integer(j)); it.remove(); - assertEquals(it.next(), new Integer(split+1)); + assertEquals(it.next(), new Integer(split + 1)); for (int j = 1; j <= split; ++j) q.remove(new Integer(j)); it = q.descendingIterator(); - for (int j = split+1; j <= max; ++j) { + for (int j = split + 1; j <= max; ++j) { assertEquals(it.next(), new Integer(j)); it.remove(); } @@ -882,6 +921,7 @@ public class ArrayDequeTest extends JSR1 assertNotSame(y, x); assertEquals(x.size(), y.size()); assertEquals(x.toString(), y.toString()); + assertEquals(Arrays.toString(x.toArray()), Arrays.toString(y.toArray())); assertTrue(Arrays.equals(x.toArray(), y.toArray())); while (!x.isEmpty()) { assertFalse(y.isEmpty()); @@ -890,4 +930,39 @@ public class ArrayDequeTest extends JSR1 assertTrue(y.isEmpty()); } + /** + * A cloned deque has same elements in same order + */ + public void testClone() throws Exception { + ArrayDeque x = populatedDeque(SIZE); + ArrayDeque y = x.clone(); + + assertNotSame(y, x); + assertEquals(x.size(), y.size()); + assertEquals(x.toString(), y.toString()); + assertTrue(Arrays.equals(x.toArray(), y.toArray())); + while (!x.isEmpty()) { + assertFalse(y.isEmpty()); + assertEquals(x.remove(), y.remove()); + } + assertTrue(y.isEmpty()); + } + + /** + * remove(null), contains(null) always return false + */ + public void testNeverContainsNull() { + Deque[] qs = { + new ArrayDeque(), + populatedDeque(2), + }; + + for (Deque q : qs) { + assertFalse(q.contains(null)); + assertFalse(q.remove(null)); + assertFalse(q.removeFirstOccurrence(null)); + assertFalse(q.removeLastOccurrence(null)); + } + } + }