--- jsr166/src/test/tck/ArrayDequeTest.java 2015/05/23 00:53:08 1.36 +++ jsr166/src/test/tck/ArrayDequeTest.java 2016/10/17 01:34:10 1.44 @@ -1,17 +1,20 @@ /* - * 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 java.util.ArrayDeque; import java.util.Arrays; import java.util.Collection; +import java.util.Collections; 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; import junit.framework.TestSuite; @@ -22,20 +25,60 @@ public class ArrayDequeTest extends JSR1 } public static Test suite() { - return new TestSuite(ArrayDequeTest.class); + class Implementation implements CollectionImplementation { + public Class klazz() { return ArrayDeque.class; } + public Collection emptyCollection() { return new ArrayDeque(); } + 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(); + // Randomize various aspects of memory layout, including + // filled-to-capacity 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; } @@ -395,14 +438,14 @@ public class ArrayDequeTest extends JSR1 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) { 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()); } @@ -530,14 +573,20 @@ public class ArrayDequeTest extends JSR1 */ public void testRemoveFirstOccurrence() { ArrayDeque q = populatedDeque(SIZE); + assertFalse(q.removeFirstOccurrence(null)); for (int i = 1; i < SIZE; i += 2) { assertTrue(q.removeFirstOccurrence(new Integer(i))); } for (int i = 0; i < SIZE; i += 2) { assertTrue(q.removeFirstOccurrence(new Integer(i))); - assertFalse(q.removeFirstOccurrence(new Integer(i+1))); + assertFalse(q.removeFirstOccurrence(new Integer(i + 1))); } assertTrue(q.isEmpty()); + assertFalse(q.removeFirstOccurrence(null)); + assertFalse(q.removeFirstOccurrence(42)); + q = new ArrayDeque(); + assertFalse(q.removeFirstOccurrence(null)); + assertFalse(q.removeFirstOccurrence(42)); } /** @@ -545,14 +594,20 @@ public class ArrayDequeTest extends JSR1 */ public void testRemoveLastOccurrence() { ArrayDeque q = populatedDeque(SIZE); + assertFalse(q.removeLastOccurrence(null)); for (int i = 1; i < SIZE; i += 2) { assertTrue(q.removeLastOccurrence(new Integer(i))); } for (int i = 0; i < SIZE; i += 2) { assertTrue(q.removeLastOccurrence(new Integer(i))); - assertFalse(q.removeLastOccurrence(new Integer(i+1))); + assertFalse(q.removeLastOccurrence(new Integer(i + 1))); } assertTrue(q.isEmpty()); + assertFalse(q.removeLastOccurrence(null)); + assertFalse(q.removeLastOccurrence(42)); + q = new ArrayDeque(); + assertFalse(q.removeLastOccurrence(null)); + assertFalse(q.removeLastOccurrence(42)); } /** @@ -660,13 +715,13 @@ public class ArrayDequeTest extends JSR1 void checkToArray2(ArrayDeque q) { int size = q.size(); - Integer[] a1 = size == 0 ? null : new Integer[size-1]; + Integer[] a1 = (size == 0) ? null : new Integer[size - 1]; Integer[] a2 = new Integer[size]; - Integer[] a3 = new Integer[size+2]; + 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[] b1 = (size == 0) ? null : (Integer[]) q.toArray(a1); Integer[] b2 = (Integer[]) q.toArray(a2); Integer[] b3 = (Integer[]) q.toArray(a3); assertSame(a2, b2); @@ -680,7 +735,7 @@ public class ArrayDequeTest extends JSR1 assertSame(b3[i], x); } assertNull(a3[size]); - assertEquals(42, (int) a3[size+1]); + assertEquals(42, (int) a3[size + 1]); if (size > 0) { assertNotSame(a1, b1); assertEquals(size, b1.length); @@ -781,18 +836,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(); } @@ -849,18 +904,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(); } @@ -899,6 +954,24 @@ public class ArrayDequeTest extends JSR1 } /** + * 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() { @@ -915,4 +988,33 @@ public class ArrayDequeTest extends JSR1 } } + /** + * Handle capacities near Integer.MAX_VALUE. + * ant -Dvmoptions=-Xmx24g -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ArrayDequeTest -Djsr166.methodFilter=testHuge tck + */ + public void testHuge() { + if (! (testImplementationDetails + && expensiveTests + && Runtime.getRuntime().freeMemory() > 21_000_000_000L)) + return; + int maxSize = Integer.MAX_VALUE - 8; + ArrayDeque q; + + q = new ArrayDeque<>(maxSize); + + assertThrows(OutOfMemoryError.class, + () -> new ArrayDeque<>(Integer.MAX_VALUE)); + + q = populatedDeque(0); + q.addAll(Collections.nCopies(maxSize - 2, (Integer) 42)); + assertEquals((Integer) 42, q.peekFirst()); + assertEquals((Integer) 42, q.peekLast()); + assertEquals(maxSize - 2, q.size()); + q.addFirst((Integer) 0); + q.addLast((Integer) 1); + assertEquals((Integer) 0, q.peekFirst()); + assertEquals((Integer) 1, q.peekLast()); + assertEquals(maxSize, q.size()); + } + }