--- jsr166/src/test/tck/ArrayDequeTest.java	2009/11/16 05:30:07	1.7
+++ jsr166/src/test/tck/ArrayDequeTest.java	2021/01/26 13:33:05	1.59
@@ -1,41 +1,90 @@
 /*
- * 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
+ * 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.*;
-import java.util.concurrent.*;
+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 JSR166TestCase.itemFor(i); }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNulls() { return false; }
+        }
+        return newTestSuite(ArrayDequeTest.class,
+                            CollectionTest.testSuite(new Implementation()));
     }
 
     /**
-     * Create a queue of given size containing consecutive
-     * Integers 0 ... n.
-     */
-    private ArrayDeque populatedDeque(int n) {
-        ArrayDeque q = new ArrayDeque();
+     * Returns a new deque of given size containing consecutive
+     * Items 0 ... n - 1.
+     */
+    private static ArrayDeque<Item> populatedDeque(int n) {
+        // Randomize various aspects of memory layout, including
+        // capacity slop and wraparound.
+        final ArrayDeque<Item> q;
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        switch (rnd.nextInt(6)) {
+        case 0: q = new ArrayDeque<Item>();      break;
+        case 1: q = new ArrayDeque<Item>(0);     break;
+        case 2: q = new ArrayDeque<Item>(1);     break;
+        case 3: q = new ArrayDeque<Item>(Math.max(0, n - 1)); break;
+        case 4: q = new ArrayDeque<Item>(n);     break;
+        case 5: q = new ArrayDeque<Item>(n + 1); break;
+        default: throw new AssertionError();
+        }
+        switch (rnd.nextInt(3)) {
+        case 0:
+            q.addFirst(fortytwo);
+            mustEqual(42, q.removeLast());
+            break;
+        case 1:
+            q.addLast(fortytwo);
+            mustEqual(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());
-	assertEquals(n, q.size());
+        if (rnd.nextBoolean())
+            for (int i = 0; i < n; i++)
+                assertTrue(q.offerLast(itemFor(i)));
+        else
+            for (int i = n; --i >= 0; )
+                q.addFirst(itemFor(i));
+        mustEqual(n, q.size());
+        if (n > 0) {
+            assertFalse(q.isEmpty());
+            mustEqual(0, q.peekFirst());
+            mustEqual((n - 1), q.peekLast());
+        }
         return q;
     }
 
     /**
-     * new queue is empty
+     * new deque is empty
      */
     public void testConstructor1() {
-        assertEquals(0, new ArrayDeque().size());
+        mustEqual(0, new ArrayDeque<Item>().size());
     }
 
     /**
@@ -43,37 +92,51 @@ public class ArrayDequeTest extends JSR1
      */
     public void testConstructor3() {
         try {
-            ArrayDeque q = new ArrayDeque((Collection)null);
+            new ArrayDeque<Object>((Collection<Object>)null);
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } catch (NullPointerException success) {}
     }
 
     /**
-     * Queue contains all elements of collection used to initialize
+     * Initializing from Collection of null elements throws NPE
+     */
+    public void testConstructor4() {
+        try {
+            new ArrayDeque<Item>(Arrays.asList(new Item[SIZE]));
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
 
+    /**
+     * Initializing from Collection with some null elements throws NPE
      */
-    public void testConstructor6() {
+    public void testConstructor5() {
+        Item[] items = new Item[2]; items[0] = zero;
         try {
-            Integer[] ints = new Integer[SIZE];
-            for (int i = 0; i < SIZE; ++i)
-                ints[i] = new Integer(i);
-            ArrayDeque q = new ArrayDeque(Arrays.asList(ints));
-            for (int i = 0; i < SIZE; ++i)
-                assertEquals(ints[i], q.pollFirst());
-        }
-        finally {}
+            new ArrayDeque<Item>(Arrays.asList(items));
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * Deque contains all elements of collection used to initialize
+     */
+    public void testConstructor6() {
+        Item[] items = defaultItems;
+        ArrayDeque<Item> q = new ArrayDeque<Item>(Arrays.asList(items));
+        for (int i = 0; i < SIZE; ++i)
+            mustEqual(items[i], q.pollFirst());
     }
 
     /**
      * isEmpty is true before add, false after
      */
     public void testEmpty() {
-        ArrayDeque q = new ArrayDeque();
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
         assertTrue(q.isEmpty());
-        q.add(new Integer(1));
+        q.add(one);
         assertFalse(q.isEmpty());
-        q.add(new Integer(2));
+        q.add(two);
         q.removeFirst();
         q.removeFirst();
         assertTrue(q.isEmpty());
@@ -83,14 +146,14 @@ public class ArrayDequeTest extends JSR1
      * size changes when elements added and removed
      */
     public void testSize() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(SIZE-i, q.size());
+            mustEqual(SIZE - i, q.size());
             q.removeFirst();
         }
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, q.size());
-            q.add(new Integer(i));
+            mustEqual(i, q.size());
+            mustAdd(q, i);
         }
     }
 
@@ -98,287 +161,460 @@ public class ArrayDequeTest extends JSR1
      * push(null) throws NPE
      */
     public void testPushNull() {
-	try {
-            ArrayDeque q = new ArrayDeque(1);
+        ArrayDeque<Item> q = new ArrayDeque<Item>(1);
+        try {
             q.push(null);
             shouldThrow();
-        } catch (NullPointerException success) { }
+        } catch (NullPointerException success) {}
     }
 
     /**
-     * peekFirst returns element inserted with push
+     * peekFirst() returns element inserted with push
      */
     public void testPush() {
-        ArrayDeque q = populatedDeque(3);
+        ArrayDeque<Item> q = populatedDeque(3);
         q.pollLast();
-	q.push(four);
-	assertEquals(four,q.peekFirst());
+        q.push(four);
+        assertSame(four, q.peekFirst());
     }
 
     /**
-     *  pop removes next element, or throws NSEE if empty
+     * pop() removes next element, or throws NSEE if empty
      */
     public void testPop() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.pop()).intValue());
+            mustEqual(i, q.pop());
         }
         try {
             q.pop();
             shouldThrow();
-        } catch (NoSuchElementException success) {
-	}
+        } catch (NoSuchElementException success) {}
     }
 
     /**
      * offer(null) throws NPE
      */
+    public void testOfferNull() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        try {
+            q.offer(null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * offerFirst(null) throws NPE
+     */
     public void testOfferFirstNull() {
-	try {
-            ArrayDeque q = new ArrayDeque();
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        try {
             q.offerFirst(null);
             shouldThrow();
-        } catch (NullPointerException success) {
-        }
+        } catch (NullPointerException success) {}
     }
 
     /**
-     * OfferFirst succeeds
+     * offerLast(null) throws NPE
+     */
+    public void testOfferLastNull() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        try {
+            q.offerLast(null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * offer(x) succeeds
+     */
+    public void testOffer() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        assertTrue(q.offer(zero));
+        assertTrue(q.offer(one));
+        assertSame(zero, q.peekFirst());
+        assertSame(one, q.peekLast());
+    }
+
+    /**
+     * offerFirst(x) succeeds
      */
     public void testOfferFirst() {
-        ArrayDeque q = new ArrayDeque();
-        assertTrue(q.offerFirst(new Integer(0)));
-        assertTrue(q.offerFirst(new Integer(1)));
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        assertTrue(q.offerFirst(zero));
+        assertTrue(q.offerFirst(one));
+        assertSame(one, q.peekFirst());
+        assertSame(zero, q.peekLast());
     }
 
     /**
-     * OfferLast succeeds
+     * offerLast(x) succeeds
      */
     public void testOfferLast() {
-        ArrayDeque q = new ArrayDeque();
-        assertTrue(q.offerLast(new Integer(0)));
-        assertTrue(q.offerLast(new Integer(1)));
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        assertTrue(q.offerLast(zero));
+        assertTrue(q.offerLast(one));
+        assertSame(zero, q.peekFirst());
+        assertSame(one, q.peekLast());
+    }
+
+    /**
+     * add(null) throws NPE
+     */
+    public void testAddNull() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        try {
+            q.add(null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * addFirst(null) throws NPE
+     */
+    public void testAddFirstNull() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        try {
+            q.addFirst(null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
     }
 
     /**
-     * add succeeds
+     * addLast(null) throws NPE
+     */
+    public void testAddLastNull() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        try {
+            q.addLast(null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * add(x) succeeds
      */
     public void testAdd() {
-        ArrayDeque q = new ArrayDeque();
-        for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, q.size());
-            assertTrue(q.add(new Integer(i)));
-        }
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        assertTrue(q.add(zero));
+        assertTrue(q.add(one));
+        assertSame(zero, q.peekFirst());
+        assertSame(one, q.peekLast());
+    }
+
+    /**
+     * addFirst(x) succeeds
+     */
+    public void testAddFirst() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        q.addFirst(zero);
+        q.addFirst(one);
+        assertSame(one, q.peekFirst());
+        assertSame(zero, q.peekLast());
+    }
+
+    /**
+     * addLast(x) succeeds
+     */
+    public void testAddLast() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        q.addLast(zero);
+        q.addLast(one);
+        assertSame(zero, q.peekFirst());
+        assertSame(one, q.peekLast());
     }
 
     /**
      * addAll(null) throws NPE
      */
     public void testAddAll1() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
         try {
-            ArrayDeque q = new ArrayDeque();
             q.addAll(null);
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } catch (NullPointerException success) {}
     }
 
     /**
-     * Queue contains all elements, in traversal order, of successful addAll
+     * addAll of a collection with null elements throws NPE
      */
-    public void testAddAll5() {
+    public void testAddAll2() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
         try {
-            Integer[] empty = new Integer[0];
-            Integer[] ints = new Integer[SIZE];
-            for (int i = 0; i < SIZE; ++i)
-                ints[i] = new Integer(i);
-            ArrayDeque q = new ArrayDeque();
-            assertFalse(q.addAll(Arrays.asList(empty)));
-            assertTrue(q.addAll(Arrays.asList(ints)));
-            for (int i = 0; i < SIZE; ++i)
-                assertEquals(ints[i], q.pollFirst());
-        }
-        finally {}
+            q.addAll(Arrays.asList(new Item[SIZE]));
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * addAll of a collection with any null elements throws NPE after
+     * possibly adding some elements
+     */
+    public void testAddAll3() {
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        Item[] items = new Item[2]; items[0] = zero;
+        try {
+            q.addAll(Arrays.asList(items));
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * Deque contains all elements, in traversal order, of successful addAll
+     */
+    public void testAddAll5() {
+        Item[] empty = new Item[0];
+        Item[] items = defaultItems;
+        ArrayDeque<Item> q = new ArrayDeque<Item>();
+        assertFalse(q.addAll(Arrays.asList(empty)));
+        assertTrue(q.addAll(Arrays.asList(items)));
+        for (int i = 0; i < SIZE; ++i)
+            mustEqual(items[i], q.pollFirst());
     }
 
     /**
-     *  pollFirst succeeds unless empty
+     * pollFirst() succeeds unless empty
      */
     public void testPollFirst() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.pollFirst()).intValue());
+            mustEqual(i, q.pollFirst());
         }
-	assertNull(q.pollFirst());
+        assertNull(q.pollFirst());
     }
 
     /**
-     *  pollLast succeeds unless empty
+     * pollLast() succeeds unless empty
      */
     public void testPollLast() {
-        ArrayDeque q = populatedDeque(SIZE);
-        for (int i = SIZE-1; i >= 0; --i) {
-            assertEquals(i, ((Integer)q.pollLast()).intValue());
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        for (int i = SIZE - 1; i >= 0; --i) {
+            mustEqual(i, q.pollLast());
         }
-	assertNull(q.pollLast());
+        assertNull(q.pollLast());
     }
 
     /**
-     *  poll succeeds unless empty
+     * poll() succeeds unless empty
      */
     public void testPoll() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.poll()).intValue());
+            mustEqual(i, q.poll());
         }
-	assertNull(q.poll());
+        assertNull(q.poll());
     }
 
     /**
-     *  remove removes next element, or throws NSEE if empty
+     * remove() removes next element, or throws NSEE if empty
      */
     public void testRemove() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.remove()).intValue());
+            mustEqual(i, q.remove());
         }
         try {
             q.remove();
             shouldThrow();
-        } catch (NoSuchElementException success) {
-	}
+        } catch (NoSuchElementException success) {}
+    }
+
+    /**
+     * remove(x) removes x and returns true if present
+     */
+    public void testRemoveElement() {
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        for (int i = 1; i < SIZE; i += 2) {
+            mustContain(q, i);
+            mustRemove(q, i);
+            mustNotContain(q, i);
+            mustContain(q, i - 1);
+        }
+        for (int i = 0; i < SIZE; i += 2) {
+            mustContain(q, i);
+            mustRemove(q, i);
+            mustNotContain(q, i);
+            mustNotRemove(q, i + 1);
+            mustNotContain(q, i + 1);
+        }
+        assertTrue(q.isEmpty());
     }
 
     /**
-     *  peekFirst returns next element, or null if empty
+     * peekFirst() returns next element, or null if empty
      */
     public void testPeekFirst() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.peekFirst()).intValue());
-            q.pollFirst();
+            mustEqual(i, q.peekFirst());
+            mustEqual(i, q.pollFirst());
             assertTrue(q.peekFirst() == null ||
-                       i != ((Integer)q.peekFirst()).intValue());
+                       !q.peekFirst().equals(i));
         }
-	assertNull(q.peekFirst());
+        assertNull(q.peekFirst());
     }
 
     /**
-     *  peek returns next element, or null if empty
+     * peek() returns next element, or null if empty
      */
     public void testPeek() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.peek()).intValue());
-            q.poll();
+            mustEqual(i, q.peek());
+            mustEqual(i, q.poll());
             assertTrue(q.peek() == null ||
-                       i != ((Integer)q.peek()).intValue());
+                       !q.peek().equals(i));
         }
-	assertNull(q.peek());
+        assertNull(q.peek());
     }
 
     /**
-     *  peekLast returns next element, or null if empty
+     * peekLast() returns next element, or null if empty
      */
     public void testPeekLast() {
-        ArrayDeque q = populatedDeque(SIZE);
-        for (int i = SIZE-1; i >= 0; --i) {
-            assertEquals(i, ((Integer)q.peekLast()).intValue());
-            q.pollLast();
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        for (int i = SIZE - 1; i >= 0; --i) {
+            mustEqual(i, q.peekLast());
+            mustEqual(i, q.pollLast());
             assertTrue(q.peekLast() == null ||
-                       i != ((Integer)q.peekLast()).intValue());
+                       !q.peekLast().equals(i));
         }
-	assertNull(q.peekLast());
+        assertNull(q.peekLast());
     }
 
     /**
-     * getFirst returns next getFirst, or throws NSEE if empty
+     * element() returns first element, or throws NSEE if empty
+     */
+    public void testElement() {
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        for (int i = 0; i < SIZE; ++i) {
+            mustEqual(i, q.element());
+            mustEqual(i, q.poll());
+        }
+        try {
+            q.element();
+            shouldThrow();
+        } catch (NoSuchElementException success) {}
+    }
+
+    /**
+     * getFirst() returns first element, or throws NSEE if empty
      */
     public void testFirstElement() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.getFirst()).intValue());
-            q.pollFirst();
+            mustEqual(i, q.getFirst());
+            mustEqual(i, q.pollFirst());
         }
         try {
             q.getFirst();
             shouldThrow();
-        }
-        catch (NoSuchElementException success) {}
+        } catch (NoSuchElementException success) {}
     }
 
     /**
-     *  getLast returns next element, or throws NSEE if empty
+     * getLast() returns last element, or throws NSEE if empty
      */
     public void testLastElement() {
-        ArrayDeque q = populatedDeque(SIZE);
-        for (int i = SIZE-1; i >= 0; --i) {
-            assertEquals(i, ((Integer)q.getLast()).intValue());
-            q.pollLast();
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        for (int i = SIZE - 1; i >= 0; --i) {
+            mustEqual(i, q.getLast());
+            mustEqual(i, q.pollLast());
         }
         try {
             q.getLast();
             shouldThrow();
-        }
-        catch (NoSuchElementException success) {}
-	assertNull(q.peekLast());
+        } catch (NoSuchElementException success) {}
+        assertNull(q.peekLast());
     }
 
-
     /**
-     *  removeFirst removes next element, or throws NSEE if empty
+     * removeFirst() removes first element, or throws NSEE if empty
      */
     public void testRemoveFirst() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.removeFirst()).intValue());
+            mustEqual(i, q.removeFirst());
         }
         try {
             q.removeFirst();
             shouldThrow();
-        } catch (NoSuchElementException success) {
-	}
+        } catch (NoSuchElementException success) {}
+        assertNull(q.peekFirst());
+    }
+
+    /**
+     * removeLast() removes last element, or throws NSEE if empty
+     */
+    public void testRemoveLast() {
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        for (int i = SIZE - 1; i >= 0; --i) {
+            mustEqual(i, q.removeLast());
+        }
+        try {
+            q.removeLast();
+            shouldThrow();
+        } catch (NoSuchElementException success) {}
+        assertNull(q.peekLast());
     }
 
     /**
      * 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)));
-        }
-        for (int i = 0; i < SIZE; i+=2) {
-            assertTrue(q.removeFirstOccurrence(new Integer(i)));
-            assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
+        Deque<Item> q = populatedDeque(SIZE);
+        assertFalse(q.removeFirstOccurrence(null));
+        for (int i = 1; i < SIZE; i += 2) {
+            assertTrue(q.removeFirstOccurrence(itemFor(i)));
+            mustNotContain(q, i);
+        }
+        for (int i = 0; i < SIZE; i += 2) {
+            assertTrue(q.removeFirstOccurrence(itemFor(i)));
+            assertFalse(q.removeFirstOccurrence(itemFor(i + 1)));
+            mustNotContain(q, i);
+            mustNotContain(q, i + 1);
         }
         assertTrue(q.isEmpty());
+        assertFalse(q.removeFirstOccurrence(null));
+        assertFalse(q.removeFirstOccurrence(fortytwo));
+        q = new ArrayDeque<Item>();
+        assertFalse(q.removeFirstOccurrence(null));
+        assertFalse(q.removeFirstOccurrence(fortytwo));
     }
 
     /**
      * 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)));
-        }
-        for (int i = 0; i < SIZE; i+=2) {
-            assertTrue(q.removeLastOccurrence(new Integer(i)));
-            assertFalse(q.removeLastOccurrence(new Integer(i+1)));
+        Deque<Item> q = populatedDeque(SIZE);
+        assertFalse(q.removeLastOccurrence(null));
+        for (int i = 1; i < SIZE; i += 2) {
+            assertTrue(q.removeLastOccurrence(itemFor(i)));
+            mustNotContain(q, i);
+        }
+        for (int i = 0; i < SIZE; i += 2) {
+            assertTrue(q.removeLastOccurrence(itemFor(i)));
+            assertFalse(q.removeLastOccurrence(itemFor(i + 1)));
+            mustNotContain(q, i);
+            mustNotContain(q, i + 1);
         }
         assertTrue(q.isEmpty());
+        assertFalse(q.removeLastOccurrence(null));
+        assertFalse(q.removeLastOccurrence(fortytwo));
+        q = new ArrayDeque<Item>();
+        assertFalse(q.removeLastOccurrence(null));
+        assertFalse(q.removeLastOccurrence(fortytwo));
     }
 
     /**
      * contains(x) reports true when elements added but not yet removed
      */
     public void testContains() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertTrue(q.contains(new Integer(i)));
-            q.pollFirst();
-            assertFalse(q.contains(new Integer(i)));
+            mustContain(q, i);
+            mustEqual(i, q.pollFirst());
+            mustNotContain(q, i);
         }
     }
 
@@ -386,11 +622,11 @@ public class ArrayDequeTest extends JSR1
      * clear removes all elements
      */
     public void testClear() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         q.clear();
         assertTrue(q.isEmpty());
-        assertEquals(0, q.size());
-        q.add(new Integer(1));
+        mustEqual(0, q.size());
+        mustAdd(q, one);
         assertFalse(q.isEmpty());
         q.clear();
         assertTrue(q.isEmpty());
@@ -400,12 +636,12 @@ public class ArrayDequeTest extends JSR1
      * containsAll(c) is true when c contains a subset of elements
      */
     public void testContainsAll() {
-        ArrayDeque q = populatedDeque(SIZE);
-        ArrayDeque p = new ArrayDeque();
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        ArrayDeque<Item> p = new ArrayDeque<Item>();
         for (int i = 0; i < SIZE; ++i) {
             assertTrue(q.containsAll(p));
             assertFalse(p.containsAll(q));
-            p.add(new Integer(i));
+            mustAdd(p, i);
         }
         assertTrue(p.containsAll(q));
     }
@@ -414,17 +650,13 @@ public class ArrayDequeTest extends JSR1
      * retainAll(c) retains only those elements of c and reports true if changed
      */
     public void testRetainAll() {
-        ArrayDeque q = populatedDeque(SIZE);
-        ArrayDeque p = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        ArrayDeque<Item> p = populatedDeque(SIZE);
         for (int i = 0; i < SIZE; ++i) {
             boolean changed = q.retainAll(p);
-            if (i == 0)
-                assertFalse(changed);
-            else
-                assertTrue(changed);
-
+            mustEqual(changed, (i > 0));
             assertTrue(q.containsAll(p));
-            assertEquals(SIZE-i, q.size());
+            mustEqual(SIZE - i, q.size());
             p.removeFirst();
         }
     }
@@ -434,116 +666,157 @@ public class ArrayDequeTest extends JSR1
      */
     public void testRemoveAll() {
         for (int i = 1; i < SIZE; ++i) {
-            ArrayDeque q = populatedDeque(SIZE);
-            ArrayDeque p = populatedDeque(i);
+            ArrayDeque<Item> q = populatedDeque(SIZE);
+            ArrayDeque<Item> p = populatedDeque(i);
             assertTrue(q.removeAll(p));
-            assertEquals(SIZE-i, q.size());
+            mustEqual(SIZE - i, q.size());
             for (int j = 0; j < i; ++j) {
-                Integer I = (Integer)(p.removeFirst());
-                assertFalse(q.contains(I));
+                mustNotContain(q, p.removeFirst());
             }
         }
     }
 
+    void checkToArray(ArrayDeque<Item> q) {
+        int size = q.size();
+        Object[] a1 = q.toArray();
+        mustEqual(size, a1.length);
+        Item[] a2 = q.toArray(new Item[0]);
+        mustEqual(size, a2.length);
+        Item[] a3 = q.toArray(new Item[Math.max(0, size - 1)]);
+        mustEqual(size, a3.length);
+        Item[] a4 = new Item[size];
+        assertSame(a4, q.toArray(a4));
+        Item[] a5 = new Item[size + 1];
+        Arrays.fill(a5, fortytwo);
+        assertSame(a5, q.toArray(a5));
+        Item[] a6 = new Item[size + 2];
+        Arrays.fill(a6, fortytwo);
+        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) mustEqual(fortytwo, a[size + 1]);
+        }
+        Iterator<? extends Item> it = q.iterator();
+        Item s = q.peekFirst();
+        for (int i = 0; i < size; i++) {
+            Item x = (Item) it.next();
+            mustEqual(s.value + i, x);
+            for (Object[] a : as)
+                assertSame(a[i], x);
+        }
+    }
+
     /**
-     *  toArray contains all elements
+     * toArray() and toArray(a) contain all elements in FIFO order
      */
     public void testToArray() {
-        ArrayDeque q = populatedDeque(SIZE);
-	Object[] o = q.toArray();
-        Arrays.sort(o);
-	for (int i = 0; i < o.length; i++)
-	    assertEquals(o[i], q.pollFirst());
+        final int size = ThreadLocalRandom.current().nextInt(10);
+        ArrayDeque<Item> q = new ArrayDeque<>(size);
+        for (int i = 0; i < size; i++) {
+            checkToArray(q);
+            q.addLast(itemFor(i));
+        }
+        // Provoke wraparound
+        int added = size * 2;
+        for (int i = 0; i < added; i++) {
+            checkToArray(q);
+            mustEqual(i, q.poll());
+            q.addLast(itemFor(size + i));
+        }
+        for (int i = 0; i < size; i++) {
+            checkToArray(q);
+            mustEqual((added + i), q.poll());
+        }
     }
 
     /**
-     *  toArray(a) contains all elements
+     * toArray(null) throws NullPointerException
      */
-    public void testToArray2() {
-        ArrayDeque q = populatedDeque(SIZE);
-	Integer[] ints = new Integer[SIZE];
-	ints = (Integer[])q.toArray(ints);
-        Arrays.sort(ints);
-        for (int i = 0; i < ints.length; i++)
-            assertEquals(ints[i], q.pollFirst());
+    public void testToArray_NullArg() {
+        ArrayDeque<Item> l = new ArrayDeque<Item>();
+        l.add(zero);
+        try {
+            l.toArray((Object[])null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
     }
 
     /**
-     * toArray(null) throws NPE
+     * toArray(incompatible array type) throws ArrayStoreException
      */
-    public void testToArray_BadArg() {
-	try {
-	    ArrayDeque l = new ArrayDeque();
-	    l.add(new Object());
-	    Object o[] = l.toArray(null);
-	    shouldThrow();
-	} catch (NullPointerException success) {}
+    public void testToArray_incompatibleArrayType() {
+        ArrayDeque<Item> l = new ArrayDeque<Item>();
+        l.add(five);
+        try {
+            l.toArray(new String[10]);
+            shouldThrow();
+        } catch (ArrayStoreException success) {}
+        try {
+            l.toArray(new String[0]);
+            shouldThrow();
+        } catch (ArrayStoreException success) {}
     }
 
     /**
-     * toArray with incompatable aray type throws CCE
+     * Iterator iterates through all elements
      */
-    public void testToArray1_BadArg() {
-	try {
-	    ArrayDeque l = new ArrayDeque();
-	    l.add(new Integer(5));
-	    Object o[] = l.toArray(new String[10] );
-	    shouldThrow();
-	} catch (ArrayStoreException  success) {}
+    public void testIterator() {
+        ArrayDeque<Item> q = populatedDeque(SIZE);
+        Iterator<? extends Item> it = q.iterator();
+        int i;
+        for (i = 0; it.hasNext(); i++)
+            mustContain(q, it.next());
+        mustEqual(i, SIZE);
+        assertIteratorExhausted(it);
     }
 
     /**
-     *  iterator iterates through all elements
+     * iterator of empty collection has no elements
      */
-    public void testIterator() {
-        ArrayDeque q = populatedDeque(SIZE);
-        int i = 0;
-	Iterator it = q.iterator();
-        while (it.hasNext()) {
-            assertTrue(q.contains(it.next()));
-            ++i;
-        }
-        assertEquals(i, SIZE);
+    public void testEmptyIterator() {
+        Deque<Item> c = new ArrayDeque<Item>();
+        assertIteratorExhausted(c.iterator());
+        assertIteratorExhausted(c.descendingIterator());
     }
 
     /**
-     *  iterator ordering is FIFO
+     * Iterator ordering is FIFO
      */
     public void testIteratorOrdering() {
-        final ArrayDeque q = new ArrayDeque();
-        q.add(new Integer(1));
-        q.add(new Integer(2));
-        q.add(new Integer(3));
+        final ArrayDeque<Item> q = new ArrayDeque<Item>();
+        q.add(one);
+        q.add(two);
+        q.add(three);
         int k = 0;
-        for (Iterator it = q.iterator(); it.hasNext();) {
-            int i = ((Integer)(it.next())).intValue();
-            assertEquals(++k, i);
+        for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
+            mustEqual(++k, it.next());
         }
 
-        assertEquals(3, k);
+        mustEqual(3, k);
     }
 
     /**
-     * iterator.remove removes current element
+     * iterator.remove() removes current element
      */
-    public void testIteratorRemove () {
-        final ArrayDeque q = new ArrayDeque();
+    public void testIteratorRemove() {
+        final ArrayDeque<Item> q = new ArrayDeque<Item>();
         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();
+                mustAdd(q, j);
+            Iterator<? extends Item> it = q.iterator();
             for (int j = 1; j <= split; ++j)
-                assertEquals(it.next(), new Integer(j));
+                mustEqual(it.next(), j);
             it.remove();
-            assertEquals(it.next(), new Integer(split+1));
+            mustEqual(it.next(), split + 1);
             for (int j = 1; j <= split; ++j)
-                q.remove(new Integer(j));
+                q.remove(itemFor(j));
             it = q.iterator();
-            for (int j = split+1; j <= max; ++j) {
-                assertEquals(it.next(), new Integer(j));
+            for (int j = split + 1; j <= max; ++j) {
+                mustEqual(it.next(), j);
                 it.remove();
             }
             assertFalse(it.hasNext());
@@ -552,40 +825,39 @@ public class ArrayDequeTest extends JSR1
     }
 
     /**
-     *  Descending iterator iterates through all elements
+     * Descending iterator iterates through all elements
      */
     public void testDescendingIterator() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> q = populatedDeque(SIZE);
         int i = 0;
-	Iterator it = q.descendingIterator();
+        Iterator<? extends Item> it = q.descendingIterator();
         while (it.hasNext()) {
-            assertTrue(q.contains(it.next()));
+            mustContain(q, it.next());
             ++i;
         }
-        assertEquals(i, SIZE);
+        mustEqual(i, SIZE);
         assertFalse(it.hasNext());
         try {
             it.next();
-        } catch (NoSuchElementException success) {
-        }
+            shouldThrow();
+        } catch (NoSuchElementException success) {}
     }
 
     /**
-     *  Descending iterator ordering is reverse FIFO
+     * Descending iterator ordering is reverse FIFO
      */
     public void testDescendingIteratorOrdering() {
-        final ArrayDeque q = new ArrayDeque();
+        final ArrayDeque<Item> q = new ArrayDeque<Item>();
         for (int iters = 0; iters < 100; ++iters) {
-            q.add(new Integer(3));
-            q.add(new Integer(2));
-            q.add(new Integer(1));
+            q.add(three);
+            q.add(two);
+            q.add(one);
             int k = 0;
-            for (Iterator it = q.descendingIterator(); it.hasNext();) {
-                int i = ((Integer)(it.next())).intValue();
-                assertEquals(++k, i);
+            for (Iterator<? extends Item> it = q.descendingIterator(); it.hasNext();) {
+                mustEqual(++k, it.next());
             }
 
-            assertEquals(3, k);
+            mustEqual(3, k);
             q.remove();
             q.remove();
             q.remove();
@@ -593,26 +865,26 @@ public class ArrayDequeTest extends JSR1
     }
 
     /**
-     * descendingIterator.remove removes current element
+     * descendingIterator.remove() removes current element
      */
-    public void testDescendingIteratorRemove () {
-        final ArrayDeque q = new ArrayDeque();
+    public void testDescendingIteratorRemove() {
+        final ArrayDeque<Item> q = new ArrayDeque<Item>();
         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();
+                q.add(itemFor(j));
+            Iterator<? extends Item> it = q.descendingIterator();
             for (int j = 1; j <= split; ++j)
-                assertEquals(it.next(), new Integer(j));
+                mustEqual(it.next(), itemFor(j));
             it.remove();
-            assertEquals(it.next(), new Integer(split+1));
+            mustEqual(it.next(), itemFor(split + 1));
             for (int j = 1; j <= split; ++j)
-                q.remove(new Integer(j));
+                q.remove(itemFor(j));
             it = q.descendingIterator();
-            for (int j = split+1; j <= max; ++j) {
-                assertEquals(it.next(), new Integer(j));
+            for (int j = split + 1; j <= max; ++j) {
+                mustEqual(it.next(), j);
                 it.remove();
             }
             assertFalse(it.hasNext());
@@ -620,34 +892,69 @@ public class ArrayDequeTest extends JSR1
         }
     }
 
-
     /**
-     * toString contains toStrings of elements
+     * toString() contains toStrings of elements
      */
     public void testToString() {
-        ArrayDeque q = populatedDeque(SIZE);
+        ArrayDeque<Item> 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)));
         }
     }
 
     /**
-     * peekFirst returns element inserted with addFirst
+     * A deserialized/reserialized deque has same elements in same order
      */
-    public void testAddFirst() {
-        ArrayDeque q = populatedDeque(3);
-	q.addFirst(four);
-	assertEquals(four,q.peekFirst());
+    public void testSerialization() throws Exception {
+        Queue<Item> x = populatedDeque(SIZE);
+        Queue<Item> y = serialClone(x);
+
+        assertNotSame(y, x);
+        mustEqual(x.size(), y.size());
+        mustEqual(x.toString(), y.toString());
+        mustEqual(Arrays.toString(x.toArray()), Arrays.toString(y.toArray()));
+        assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+        while (!x.isEmpty()) {
+            assertFalse(y.isEmpty());
+            mustEqual(x.remove(), y.remove());
+        }
+        assertTrue(y.isEmpty());
     }
 
     /**
-     * peekLast returns element inserted with addLast
+     * A cloned deque has same elements in same order
      */
-    public void testAddLast() {
-        ArrayDeque q = populatedDeque(3);
-	q.addLast(four);
-	assertEquals(four,q.peekLast());
+    public void testClone() throws Exception {
+        ArrayDeque<Item> x = populatedDeque(SIZE);
+        ArrayDeque<Item> y = x.clone();
+
+        assertNotSame(y, x);
+        mustEqual(x.size(), y.size());
+        mustEqual(x.toString(), y.toString());
+        assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+        while (!x.isEmpty()) {
+            assertFalse(y.isEmpty());
+            mustEqual(x.remove(), y.remove());
+        }
+        assertTrue(y.isEmpty());
+    }
+
+    /**
+     * remove(null), contains(null) always return false
+     */
+    public void testNeverContainsNull() {
+        Deque<?>[] qs = {
+            new ArrayDeque<Object>(),
+            populatedDeque(2),
+        };
+
+        for (Deque<?> q : qs) {
+            assertFalse(q.contains(null));
+            assertFalse(q.remove(null));
+            assertFalse(q.removeFirstOccurrence(null));
+            assertFalse(q.removeLastOccurrence(null));
+        }
     }
 
 }