--- jsr166/src/test/tck/ArrayDequeTest.java 2010/11/04 01:04:54 1.19 +++ jsr166/src/test/tck/ArrayDequeTest.java 2015/05/24 01:42:14 1.38 @@ -1,21 +1,24 @@ /* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain + * http://creativecommons.org/publicdomain/zero/1.0/ */ -import junit.framework.*; -import java.io.BufferedInputStream; -import java.io.BufferedOutputStream; -import java.io.ByteArrayInputStream; -import java.io.ByteArrayOutputStream; -import java.io.ObjectInputStream; -import java.io.ObjectOutputStream; -import java.util.*; +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 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() { @@ -23,11 +26,11 @@ public class ArrayDequeTest extends JSR1 } /** - * Create a deque of given size containing consecutive + * Returns a new deque of given size containing consecutive * Integers 0 ... n. */ - private ArrayDeque populatedDeque(int n) { - ArrayDeque q = new ArrayDeque(); + private ArrayDeque populatedDeque(int n) { + ArrayDeque q = new ArrayDeque(); assertTrue(q.isEmpty()); for (int i = 0; i < n; ++i) assertTrue(q.offerLast(new Integer(i))); @@ -48,7 +51,7 @@ public class ArrayDequeTest extends JSR1 */ public void testConstructor3() { try { - ArrayDeque q = new ArrayDeque((Collection)null); + new ArrayDeque((Collection)null); shouldThrow(); } catch (NullPointerException success) {} } @@ -58,8 +61,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) {} } @@ -68,11 +70,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) {} } @@ -109,7 +111,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) { @@ -122,8 +124,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) {} @@ -157,8 +159,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) {} @@ -168,8 +170,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) {} @@ -179,8 +181,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) {} @@ -223,8 +225,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) {} @@ -234,8 +236,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) {} @@ -245,8 +247,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) {} @@ -289,8 +291,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) {} @@ -300,10 +302,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) {} } @@ -313,11 +314,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) {} @@ -354,7 +355,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()); @@ -390,12 +391,18 @@ public class ArrayDequeTest extends JSR1 */ public void testRemoveElement() { ArrayDeque q = populatedDeque(SIZE); - for (int i = 1; i < SIZE; i+=2) { - assertTrue(q.remove(new Integer(i))); - } - for (int i = 0; i < SIZE; i+=2) { - assertTrue(q.remove(new Integer(i))); - assertFalse(q.remove(new Integer(i+1))); + 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)); + } + 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)); } assertTrue(q.isEmpty()); } @@ -433,7 +440,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 || @@ -477,7 +484,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()); } @@ -488,7 +495,6 @@ public class ArrayDequeTest extends JSR1 assertNull(q.peekLast()); } - /** * removeFirst() removes first element, or throws NSEE if empty */ @@ -524,12 +530,12 @@ public class ArrayDequeTest extends JSR1 */ public void testRemoveFirstOccurrence() { ArrayDeque q = populatedDeque(SIZE); - for (int i = 1; i < SIZE; i+=2) { + for (int i = 1; i < SIZE; i += 2) { assertTrue(q.removeFirstOccurrence(new Integer(i))); } - for (int i = 0; i < SIZE; i+=2) { + 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()); } @@ -539,12 +545,12 @@ public class ArrayDequeTest extends JSR1 */ public void testRemoveLastOccurrence() { ArrayDeque q = populatedDeque(SIZE); - for (int i = 1; i < SIZE; i+=2) { + for (int i = 1; i < SIZE; i += 2) { assertTrue(q.removeLastOccurrence(new Integer(i))); } - for (int i = 0; i < SIZE; i+=2) { + 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()); } @@ -599,7 +605,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(); } } @@ -612,32 +618,97 @@ 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) { + int size = q.size(); + Object[] o = q.toArray(); + assertEquals(size, o.length); + Iterator it = q.iterator(); + for (int i = 0; i < size; i++) { + Integer x = (Integer) it.next(); + assertEquals((Integer)o[0] + i, (int) x); + assertSame(o[i], x); + } + } + /** * toArray() contains all elements in FIFO order */ public void testToArray() { - ArrayDeque q = populatedDeque(SIZE); - Object[] o = q.toArray(); - for (int i = 0; i < o.length; i++) - assertSame(o[i], q.pollFirst()); + ArrayDeque q = new ArrayDeque(); + for (int i = 0; i < SIZE; i++) { + checkToArray(q); + q.addLast(i); + } + // Provoke wraparound + for (int i = 0; i < SIZE; i++) { + checkToArray(q); + assertEquals(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 = populatedDeque(SIZE); - Integer[] ints = new Integer[SIZE]; - assertSame(ints, q.toArray(ints)); - for (int i = 0; i < ints.length; i++) - assertSame(ints[i], q.remove()); + 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()); + } } /** @@ -669,13 +740,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()); } /** @@ -702,18 +781,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(); } @@ -770,18 +849,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(); } @@ -790,7 +869,6 @@ public class ArrayDequeTest extends JSR1 } } - /** * toString() contains toStrings of elements */ @@ -798,7 +876,7 @@ public class ArrayDequeTest extends JSR1 ArrayDeque q = populatedDeque(SIZE); String s = q.toString(); for (int i = 0; i < SIZE; ++i) { - assertTrue(s.indexOf(String.valueOf(i)) >= 0); + assertTrue(s.contains(String.valueOf(i))); } } @@ -806,18 +884,35 @@ public class ArrayDequeTest extends JSR1 * A deserialized serialized deque has same elements in same order */ public void testSerialization() throws Exception { - ArrayDeque q = populatedDeque(SIZE); - ByteArrayOutputStream bout = new ByteArrayOutputStream(10000); - ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout)); - out.writeObject(q); - out.close(); - - ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray()); - ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin)); - ArrayDeque r = (ArrayDeque)in.readObject(); - assertEquals(q.size(), r.size()); - while (!q.isEmpty()) - assertEquals(q.remove(), r.remove()); + Queue x = populatedDeque(SIZE); + Queue y = serialClone(x); + + 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)); + } } }