--- jsr166/src/test/tck/ArrayDequeTest.java 2014/12/31 20:09:08 1.31 +++ jsr166/src/test/tck/ArrayDequeTest.java 2016/10/17 00:59:53 1.43 @@ -7,35 +7,77 @@ 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; 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 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; } @@ -51,7 +93,7 @@ public class ArrayDequeTest extends JSR1 */ public void testConstructor3() { try { - ArrayDeque q = new ArrayDeque((Collection)null); + new ArrayDeque((Collection)null); shouldThrow(); } catch (NullPointerException success) {} } @@ -61,8 +103,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) {} } @@ -71,11 +112,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) {} } @@ -112,7 +153,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) { @@ -125,8 +166,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) {} @@ -160,8 +201,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) {} @@ -171,8 +212,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) {} @@ -182,8 +223,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) {} @@ -226,8 +267,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) {} @@ -237,8 +278,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) {} @@ -248,8 +289,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) {} @@ -292,8 +333,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) {} @@ -303,10 +344,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) {} } @@ -316,11 +356,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) {} @@ -357,7 +397,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()); @@ -397,14 +437,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()); } @@ -442,7 +482,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 || @@ -486,7 +526,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()); } @@ -532,14 +572,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)); } /** @@ -547,14 +593,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)); } /** @@ -607,7 +659,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(); } } @@ -620,7 +672,7 @@ 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())); } @@ -652,23 +704,23 @@ public class ArrayDequeTest extends JSR1 for (int i = 0; i < SIZE; i++) { checkToArray(q); assertEquals(i, q.poll()); - q.addLast(SIZE+i); + q.addLast(SIZE + i); } for (int i = 0; i < SIZE; i++) { checkToArray(q); - assertEquals(SIZE+i, q.poll()); + assertEquals(SIZE + i, q.poll()); } } 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); @@ -682,7 +734,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); @@ -705,11 +757,11 @@ public class ArrayDequeTest extends JSR1 for (int i = 0; i < SIZE; i++) { checkToArray2(q); assertEquals(i, q.poll()); - q.addLast(SIZE+i); + q.addLast(SIZE + i); } for (int i = 0; i < SIZE; i++) { checkToArray2(q); - assertEquals(SIZE+i, q.poll()); + assertEquals(SIZE + i, q.poll()); } } @@ -742,13 +794,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()); } /** @@ -775,18 +835,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(); } @@ -843,18 +903,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(); } @@ -893,6 +953,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() { @@ -909,4 +987,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()); + } + }