test/loops/DequeBash.java

/*
 * Written by Josh Bloch of Google Inc. and released to the public domain,
 * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
 */

import java.io.*;
import java.util.*;

/**
 * Interface-based Deque tester.  This test currently makes three
 * assumptions about the implementation under test:
 *
 *   1) It has no size limitation.
 *   2) It implements Serializable.
 *   3) It has a conventional (Collection) constructor.
 *
 * All of these assumptions could be relaxed.
 */
public class DequeBash {
    static int seed = 7;
    static int nextTail =  0;
    static int nextHead = -1;
    static int size() { return nextTail - nextHead - 1; }

    static int random(int bound) {
        int x = seed;
        int t = (x % 127773) * 16807 - (x / 127773) * 2836;
        seed = (t > 0) ? t : t + 0x7fffffff;
        return (t & 0x7fffffff) % bound;
    }

    static int random() {
        int x = seed;
        int t = (x % 127773) * 16807 - (x / 127773) * 2836;
        seed = (t > 0) ? t : t + 0x7fffffff;
        return (t & 0x7fffffff);
    }

    public static void main(String[] args) throws Exception {
        Class<?> cls = Class.forName(args[0]);
        int n = 1000000;

        for (int j = 0; j < 3; ++j) {
            @SuppressWarnings("unchecked")
            Deque<Integer> deque = (Deque<Integer>) cls.newInstance();
            nextTail =  0;
            nextHead = -1;
            long start = System.nanoTime();
            mainTest(deque, n);
            long end = System.nanoTime();
            long elapsedTimeMillis = (end - start) / (1000L * 1000L);
            System.out.printf("Time: %d ms%n", elapsedTimeMillis);
            if (deque.isEmpty()) System.out.print(" ");
        }

    }

    static void mainTest(Deque<Integer> deque, int n) throws Exception {
        /*
         * Perform a random sequence of operations, keeping contiguous
         * sequence of integers on the deque.
         */
        for (int i = 0; i < n; i++) {
            sizeTests(deque);
            randomOp(deque);

            // Test iterator occasionally
            if ((i & 1023) == 0) {
                testIter(deque);
                testDescendingIter(deque);
            }

            // Test serialization and copying
            if ((i & 4095) == 0) {
                testEqual(deque, serialClone(deque));
                testEqual(deque, copyConstructorClone(deque));
            }

            // Test fancy removal stuff once in a blue moon
            if ((i & 8191) == 0)
                testRemove(deque);

        }

        // Stupid tests for clear, toString
        deque.clear();
        testEmpty(deque);
        Collection<Integer> c = Arrays.asList(1, 2, 3);
        deque.addAll(c);
        if (!deque.toString().equals("[1, 2, 3]"))
            throw new Exception("Deque.toString():  " + deque.toString());
    }

    static void testIter(Deque<Integer> deque) throws Exception {
        int next = nextHead + 1;
        int count = 0;
        for (int j : deque) {
            if (j != next++)
                throw new Exception("Element "+ j + " != " + (next-1));
            count++;
        }
        if (count != size())
            throw new Exception("Count " + count + " != " + size());
    }

    static void testDescendingIter(Deque<Integer> deque) throws Exception {
        int next = deque.size() + nextHead;
        int count = 0;
        for (Iterator<Integer> it = deque.descendingIterator(); it.hasNext();) {
            int j = it.next();
            if (j != next--)
                throw new Exception("Element "+ j + " != " + (next-1));
            count++;
        }
        if (count != size())
            throw new Exception("Count " + count + " != " + size());
    }

    static void sizeTests(Deque<Integer> deque) throws Exception {
        if (deque.size() != size())
            throw new Exception("Size: " + deque.size() +
                                ", expecting " + size());
        if (deque.isEmpty() != (size() == 0))
            throw new Exception(
                                "IsEmpty " + deque.isEmpty() + ", size " + size());
        // Check head and tail
        if (size() == 0)
            testEmpty(deque);
        else
            nonEmptyTest(deque);

    }

    static void nonEmptyTest(Deque<Integer> deque) throws Exception {
        if (deque.getFirst() != nextHead + 1)
            throw new Exception("getFirst got: " +
                                deque.getFirst() + " expecting " + (nextHead + 1));
        if (deque.element() != nextHead + 1)
            throw new Exception("element got: " + deque.element() +
                                " expecting " + (nextHead + 1));
        if (deque.peekFirst() != nextHead + 1)
            throw new Exception("peekFirst got: "+deque.peekFirst() +
                                " expecting " + (nextHead + 1));
        if (deque.peek() != nextHead + 1)
            throw new Exception("peek got: " +  deque.peek() +
                                " expecting " + (nextHead + 1));

        if (deque.peekLast() != nextTail - 1)
            throw new Exception("peekLast got: " + deque.peekLast() +
                                " expecting " + (nextTail - 1));
        if (deque.getLast() != nextTail - 1)
            throw new Exception("getLast got: " +
                                deque.getLast() + " expecting " + (nextTail - 1));
    }

    static void randomOp(Deque<Integer> deque) throws Exception {

        // Perform a random operation
        switch (random() & 3) {
        case 0:
            switch (random() & 3) {
            case 0: deque.addLast(nextTail++);   break;
            case 1: deque.offerLast(nextTail++); break;
            case 2: deque.offer(nextTail++);     break;
            case 3: deque.add(nextTail++);       break;
            default: throw new Exception("How'd we get here");
            }
            break;
        case 1:
            if (size() == 0) {
                int result = 666;
                boolean threw = false;
                try {
                    switch (random(3)) {
                    case 0: result = deque.removeFirst(); break;
                    case 1: result = deque.remove();      break;
                    case 2: result = deque.pop();         break;
                    default: throw new Exception("How'd we get here");
                    }
                } catch (NoSuchElementException e) {
                    threw = true;
                }
                if (!threw)
                    throw new Exception("Remove-no exception: " + result);
            } else { // deque nonempty
                int result = -1;
                switch (random(5)) {
                case 0: result = deque.removeFirst(); break;
                case 1: result = deque.remove();      break;
                case 2: result = deque.pop();         break;
                case 3: result = deque.pollFirst();   break;
                case 4: result = deque.poll();        break;
                default: throw new Exception("How'd we get here");
                }
                if (result != ++nextHead)
                    throw new Exception(
                                        "Removed "+ result + " expecting "+(nextHead - 1));
            }
            break;
        case 2:
            switch (random(3)) {
            case 0: deque.addFirst(nextHead--);   break;
            case 1: deque.offerFirst(nextHead--); break;
            case 2: deque.push(nextHead--);       break;
            default: throw new Exception("How'd we get here");
            }
            break;
        case 3:
            if (size() == 0) {
                int result = -1;
                boolean threw = false;
                try {
                    result = deque.removeLast();
                } catch (NoSuchElementException e) {
                    threw = true;
                }
                if (!threw)
                    throw new Exception("Remove-no exception: " + result);
            } else { // deque nonempty
                int result = ((random() & 1) == 0 ?
                              deque.removeLast() : deque.pollLast());
                if (result != --nextTail)
                    throw new Exception(
                        "Removed "+ result + " expecting "+(nextTail + 1));
            }
            break;
        default:
            throw new Exception("How'd we get here");
        }
    }

    private static void testEqual(Deque<Integer> d1, Deque<Integer> d2)
        throws Exception
    {
        if (d1.size() != d2.size())
            throw new Exception("Size " + d1.size() + " != " + d2.size());
        Iterator<Integer> it = d2.iterator();
        for (int i : d1) {
            int j = it.next();
            if (j != i)
                throw new Exception("Element " + j + " != " + i);
        }

        for (int i : d1)
            if (!d2.contains(i))
                throw new Exception("d2 doesn't contain " + i);
        for (int i : d2)
            if (!d1.contains(i))
                throw new Exception("d2 doesn't contain " + i);

        if (d1.contains(Integer.MIN_VALUE))
            throw new Exception("d2 contains Integer.MIN_VALUE");
        if (d2.contains(Integer.MIN_VALUE))
            throw new Exception("d2 contains Integer.MIN_VALUE");
        if (d1.contains(null))
            throw new Exception("d1 contains null");
        if (d2.contains(null))
            throw new Exception("d2 contains null");

        if (!d1.containsAll(d2))
            throw new Exception("d1 doesn't contain all of d2");
        if (!d2.containsAll(d1))
            throw new Exception("d2 doesn't contain all of d1");
        Collection<Integer> c = Collections.singleton(Integer.MIN_VALUE);
        if (d1.containsAll(c))
            throw new Exception("d1 contains all of {Integer.MIN_VALUE }");
        if (d2.containsAll(c))
            throw new Exception("d2 contains all of {Integer.MIN_VALUE }");
    }

    @SuppressWarnings("unchecked")
    private static <T> T copyConstructorClone(T o) throws Exception {
        return (T) o.getClass().getConstructor(Collection.class).newInstance(o);
    }

    @SuppressWarnings("unchecked")
    private static <T> T serialClone(T o) throws Exception {
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(bos);
        oos.writeObject(o);
        oos.flush();
        oos.close();
        ByteArrayInputStream bin =
            new ByteArrayInputStream(bos.toByteArray());
        ObjectInputStream ois = new ObjectInputStream(bin);
            return (T) ois.readObject();
    }

    private static void testRemove(Deque<Integer> deque) throws Exception {
        Deque<Integer> copy = ((random() & 1) == 0) ?
            copyConstructorClone(deque) :
            serialClone(deque);

        int numRemoved = 0;
        for (Iterator<Integer> it = copy.iterator(); it.hasNext(); ) {
            if ((it.next() & 1) == 0) {
                it.remove();
                numRemoved++;
            }
        }

        if (copy.size() + numRemoved != size())
            throw new Exception((copy.size() + numRemoved) + " != " + size());
        for (int i : copy)
            if ((i & 1) == 0)
                throw new Exception("Even number still present: " + i);

        List<Integer> elements = Arrays.asList(copy.toArray(new Integer[0]));
        Collections.shuffle(elements);
        for (int e : elements) {
            if (!copy.contains(e))
                throw new Exception(e + " missing.");

            boolean removed = false;
            switch (random(3)) {
                case 0:  removed = copy.remove(e);                break;
                case 1:  removed = copy.removeFirstOccurrence(e); break;
                case 2:  removed = copy.removeLastOccurrence(e);  break;
                default: throw new Exception("How'd we get here");
            }
            if (!removed)
                throw new Exception(e + " not removed.");

            if (copy.contains(e))
                throw new Exception(e + " present after removal.");
        }

        testEmpty(copy);

        copy = copyConstructorClone(deque);
        copy.retainAll(deque);
        testEqual(deque, copy);
        copy.removeAll(deque);
        testEmpty(copy);
    }

    static boolean checkedThrows;

    private static void testEmpty(Deque<Integer> deque) throws Exception {
        if (!deque.isEmpty())
            throw new Exception("Deque isn't empty");
        if (deque.size() != 0)
            throw new Exception("Deque size isn't zero");
        if (!(deque.pollFirst() == null))
            throw new Exception("pollFirst lies");
        if (!(deque.poll() == null))
            throw new Exception("poll lies");
        if (!(deque.peekFirst() == null))
            throw new Exception("peekFirst lies");
        if (!(deque.peek() == null))
            throw new Exception("peek lies");
        if (!(deque.pollLast() == null))
            throw new Exception("pollLast lies");
        if (!(deque.peekLast() == null))
            throw new Exception("peekLast lies");

        if (!checkedThrows) {
            checkedThrows = true;
            boolean threw = false;
            int result = 666;
            try {
                result = ((random() & 1) == 0 ?
                          deque.getFirst() : deque.element());
            } catch (NoSuchElementException e) {
                threw = true;
            }
            if (!threw)
                throw new Exception("getFirst-no exception: "+result);
            threw = false;
            try {
                result = deque.getLast();
            } catch (NoSuchElementException e) {
                threw = true;
            }
            if (!threw)
                throw new Exception("getLast-no exception: "+result);
        }

    }
}
Revision:	1.11
Committed:	Thu Jan 15 18:34:19 2015 UTC (9 years, 4 months ago) by jsr166
Branch:	MAIN
Changes since 1.10:	+0 -3 lines
Log Message:	delete extraneous blank lines
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Josh Bloch of Google Inc. and released to the public domain,
3	jsr166	1.7	* as explained at http://creativecommons.org/publicdomain/zero/1.0/.
4	dl	1.1	*/
5
6	jsr166	1.10	import java.io.*;
7	dl	1.1	import java.util.*;
8
9			/**
10			* Interface-based Deque tester. This test currently makes three
11			* assumptions about the implementation under test:
12			*
13			* 1) It has no size limitation.
14			* 2) It implements Serializable.
15			* 3) It has a conventional (Collection) constructor.
16			*
17			* All of these assumptions could be relaxed.
18			*/
19			public class DequeBash {
20			static int seed = 7;
21			static int nextTail = 0;
22			static int nextHead = -1;
23			static int size() { return nextTail - nextHead - 1; }
24
25	jsr166	1.3	static int random(int bound) {
26	dl	1.1	int x = seed;
27			int t = (x % 127773) * 16807 - (x / 127773) * 2836;
28	jsr166	1.4	seed = (t > 0) ? t : t + 0x7fffffff;
29	dl	1.1	return (t & 0x7fffffff) % bound;
30			}
31
32	jsr166	1.3	static int random() {
33	dl	1.1	int x = seed;
34			int t = (x % 127773) * 16807 - (x / 127773) * 2836;
35	jsr166	1.4	seed = (t > 0) ? t : t + 0x7fffffff;
36	dl	1.1	return (t & 0x7fffffff);
37			}
38
39	jsr166	1.9	public static void main(String[] args) throws Exception {
40	jsr166	1.6	Class<?> cls = Class.forName(args[0]);
41	dl	1.1	int n = 1000000;
42
43			for (int j = 0; j < 3; ++j) {
44	jsr166	1.6	@SuppressWarnings("unchecked")
45	dl	1.1	Deque<Integer> deque = (Deque<Integer>) cls.newInstance();
46			nextTail = 0;
47			nextHead = -1;
48	jsr166	1.6	long start = System.nanoTime();
49	dl	1.1	mainTest(deque, n);
50	jsr166	1.6	long end = System.nanoTime();
51			long elapsedTimeMillis = (end - start) / (1000L * 1000L);
52			System.out.printf("Time: %d ms%n", elapsedTimeMillis);
53	dl	1.1	if (deque.isEmpty()) System.out.print(" ");
54			}
55
56			}
57
58			static void mainTest(Deque<Integer> deque, int n) throws Exception {
59			/*
60			* Perform a random sequence of operations, keeping contiguous
61			* sequence of integers on the deque.
62			*/
63			for (int i = 0; i < n; i++) {
64			sizeTests(deque);
65			randomOp(deque);
66
67			// Test iterator occasionally
68	dl	1.2	if ((i & 1023) == 0) {
69	dl	1.1	testIter(deque);
70	dl	1.2	testDescendingIter(deque);
71			}
72	dl	1.1
73			// Test serialization and copying
74			if ((i & 4095) == 0) {
75	jsr166	1.6	testEqual(deque, serialClone(deque));
76			testEqual(deque, copyConstructorClone(deque));
77	dl	1.1	}
78	jsr166	1.3
79	dl	1.1	// Test fancy removal stuff once in a blue moon
80			if ((i & 8191) == 0)
81			testRemove(deque);
82	jsr166	1.3
83	jsr166	1.8	}
84	dl	1.1
85			// Stupid tests for clear, toString
86			deque.clear();
87			testEmpty(deque);
88			Collection<Integer> c = Arrays.asList(1, 2, 3);
89			deque.addAll(c);
90			if (!deque.toString().equals("[1, 2, 3]"))
91			throw new Exception("Deque.toString(): " + deque.toString());
92			}
93
94	jsr166	1.3	static void testIter(Deque<Integer> deque) throws Exception {
95	dl	1.1	int next = nextHead + 1;
96			int count = 0;
97			for (int j : deque) {
98			if (j != next++)
99			throw new Exception("Element "+ j + " != " + (next-1));
100			count++;
101			}
102			if (count != size())
103			throw new Exception("Count " + count + " != " + size());
104			}
105
106	jsr166	1.3	static void testDescendingIter(Deque<Integer> deque) throws Exception {
107	dl	1.2	int next = deque.size() + nextHead;
108			int count = 0;
109			for (Iterator<Integer> it = deque.descendingIterator(); it.hasNext();) {
110			int j = it.next();
111			if (j != next--)
112			throw new Exception("Element "+ j + " != " + (next-1));
113			count++;
114			}
115			if (count != size())
116			throw new Exception("Count " + count + " != " + size());
117			}
118
119	dl	1.1	static void sizeTests(Deque<Integer> deque) throws Exception {
120			if (deque.size() != size())
121			throw new Exception("Size: " + deque.size() +
122			", expecting " + size());
123			if (deque.isEmpty() != (size() == 0))
124			throw new Exception(
125			"IsEmpty " + deque.isEmpty() + ", size " + size());
126			// Check head and tail
127	jsr166	1.3	if (size() == 0)
128	dl	1.1	testEmpty(deque);
129	jsr166	1.3	else
130	dl	1.1	nonEmptyTest(deque);
131
132			}
133
134	jsr166	1.3	static void nonEmptyTest(Deque<Integer> deque) throws Exception {
135	dl	1.1	if (deque.getFirst() != nextHead + 1)
136	jsr166	1.3	throw new Exception("getFirst got: " +
137	dl	1.1	deque.getFirst() + " expecting " + (nextHead + 1));
138			if (deque.element() != nextHead + 1)
139			throw new Exception("element got: " + deque.element() +
140			" expecting " + (nextHead + 1));
141			if (deque.peekFirst() != nextHead + 1)
142			throw new Exception("peekFirst got: "+deque.peekFirst() +
143			" expecting " + (nextHead + 1));
144			if (deque.peek() != nextHead + 1)
145			throw new Exception("peek got: " + deque.peek() +
146			" expecting " + (nextHead + 1));
147	jsr166	1.3
148	dl	1.1	if (deque.peekLast() != nextTail - 1)
149			throw new Exception("peekLast got: " + deque.peekLast() +
150			" expecting " + (nextTail - 1));
151			if (deque.getLast() != nextTail - 1)
152	jsr166	1.3	throw new Exception("getLast got: " +
153	dl	1.1	deque.getLast() + " expecting " + (nextTail - 1));
154	jsr166	1.3	}
155
156	dl	1.1	static void randomOp(Deque<Integer> deque) throws Exception {
157	jsr166	1.3
158	dl	1.1	// Perform a random operation
159	jsr166	1.5	switch (random() & 3) {
160	dl	1.1	case 0:
161	jsr166	1.5	switch (random() & 3) {
162	dl	1.1	case 0: deque.addLast(nextTail++); break;
163			case 1: deque.offerLast(nextTail++); break;
164			case 2: deque.offer(nextTail++); break;
165			case 3: deque.add(nextTail++); break;
166			default: throw new Exception("How'd we get here");
167			}
168			break;
169			case 1:
170			if (size() == 0) {
171			int result = 666;
172			boolean threw = false;
173			try {
174	jsr166	1.5	switch (random(3)) {
175	dl	1.1	case 0: result = deque.removeFirst(); break;
176			case 1: result = deque.remove(); break;
177			case 2: result = deque.pop(); break;
178			default: throw new Exception("How'd we get here");
179			}
180	jsr166	1.4	} catch (NoSuchElementException e) {
181	dl	1.1	threw = true;
182			}
183			if (!threw)
184			throw new Exception("Remove-no exception: " + result);
185			} else { // deque nonempty
186			int result = -1;
187	jsr166	1.5	switch (random(5)) {
188	dl	1.1	case 0: result = deque.removeFirst(); break;
189			case 1: result = deque.remove(); break;
190			case 2: result = deque.pop(); break;
191			case 3: result = deque.pollFirst(); break;
192			case 4: result = deque.poll(); break;
193			default: throw new Exception("How'd we get here");
194			}
195			if (result != ++nextHead)
196			throw new Exception(
197			"Removed "+ result + " expecting "+(nextHead - 1));
198			}
199			break;
200			case 2:
201	jsr166	1.5	switch (random(3)) {
202	dl	1.1	case 0: deque.addFirst(nextHead--); break;
203			case 1: deque.offerFirst(nextHead--); break;
204			case 2: deque.push(nextHead--); break;
205			default: throw new Exception("How'd we get here");
206			}
207			break;
208			case 3:
209			if (size() == 0) {
210			int result = -1;
211			boolean threw = false;
212			try {
213			result = deque.removeLast();
214	jsr166	1.4	} catch (NoSuchElementException e) {
215	dl	1.1	threw = true;
216			}
217			if (!threw)
218			throw new Exception("Remove-no exception: " + result);
219			} else { // deque nonempty
220	jsr166	1.4	int result = ((random() & 1) == 0 ?
221	dl	1.1	deque.removeLast() : deque.pollLast());
222			if (result != --nextTail)
223			throw new Exception(
224	jsr166	1.4	"Removed "+ result + " expecting "+(nextTail + 1));
225	dl	1.1	}
226			break;
227			default:
228			throw new Exception("How'd we get here");
229			}
230			}
231
232			private static void testEqual(Deque<Integer> d1, Deque<Integer> d2)
233			throws Exception
234			{
235			if (d1.size() != d2.size())
236			throw new Exception("Size " + d1.size() + " != " + d2.size());
237			Iterator<Integer> it = d2.iterator();
238	jsr166	1.4	for (int i : d1) {
239	dl	1.1	int j = it.next();
240			if (j != i)
241			throw new Exception("Element " + j + " != " + i);
242			}
243
244	jsr166	1.4	for (int i : d1)
245	dl	1.1	if (!d2.contains(i))
246			throw new Exception("d2 doesn't contain " + i);
247	jsr166	1.4	for (int i : d2)
248	dl	1.1	if (!d1.contains(i))
249			throw new Exception("d2 doesn't contain " + i);
250
251			if (d1.contains(Integer.MIN_VALUE))
252			throw new Exception("d2 contains Integer.MIN_VALUE");
253			if (d2.contains(Integer.MIN_VALUE))
254			throw new Exception("d2 contains Integer.MIN_VALUE");
255			if (d1.contains(null))
256			throw new Exception("d1 contains null");
257			if (d2.contains(null))
258			throw new Exception("d2 contains null");
259
260			if (!d1.containsAll(d2))
261			throw new Exception("d1 doesn't contain all of d2");
262			if (!d2.containsAll(d1))
263			throw new Exception("d2 doesn't contain all of d1");
264			Collection<Integer> c = Collections.singleton(Integer.MIN_VALUE);
265			if (d1.containsAll(c))
266			throw new Exception("d1 contains all of {Integer.MIN_VALUE }");
267			if (d2.containsAll(c))
268			throw new Exception("d2 contains all of {Integer.MIN_VALUE }");
269			}
270
271	jsr166	1.6	@SuppressWarnings("unchecked")
272			private static <T> T copyConstructorClone(T o) throws Exception {
273			return (T) o.getClass().getConstructor(Collection.class).newInstance(o);
274			}
275
276			@SuppressWarnings("unchecked")
277			private static <T> T serialClone(T o) throws Exception {
278			ByteArrayOutputStream bos = new ByteArrayOutputStream();
279			ObjectOutputStream oos = new ObjectOutputStream(bos);
280			oos.writeObject(o);
281			oos.flush();
282			oos.close();
283			ByteArrayInputStream bin =
284			new ByteArrayInputStream(bos.toByteArray());
285			ObjectInputStream ois = new ObjectInputStream(bin);
286	dl	1.1	return (T) ois.readObject();
287			}
288
289			private static void testRemove(Deque<Integer> deque) throws Exception {
290	jsr166	1.6	Deque<Integer> copy = ((random() & 1) == 0) ?
291			copyConstructorClone(deque) :
292			serialClone(deque);
293	dl	1.1
294			int numRemoved = 0;
295			for (Iterator<Integer> it = copy.iterator(); it.hasNext(); ) {
296			if ((it.next() & 1) == 0) {
297			it.remove();
298			numRemoved++;
299			}
300			}
301
302			if (copy.size() + numRemoved != size())
303			throw new Exception((copy.size() + numRemoved) + " != " + size());
304			for (int i : copy)
305			if ((i & 1) == 0)
306			throw new Exception("Even number still present: " + i);
307
308			List<Integer> elements = Arrays.asList(copy.toArray(new Integer[0]));
309			Collections.shuffle(elements);
310			for (int e : elements) {
311			if (!copy.contains(e))
312			throw new Exception(e + " missing.");
313
314			boolean removed = false;
315	jsr166	1.5	switch (random(3)) {
316	dl	1.1	case 0: removed = copy.remove(e); break;
317			case 1: removed = copy.removeFirstOccurrence(e); break;
318			case 2: removed = copy.removeLastOccurrence(e); break;
319	jsr166	1.3	default: throw new Exception("How'd we get here");
320	dl	1.1	}
321			if (!removed)
322			throw new Exception(e + " not removed.");
323
324			if (copy.contains(e))
325			throw new Exception(e + " present after removal.");
326			}
327
328			testEmpty(copy);
329
330	jsr166	1.6	copy = copyConstructorClone(deque);
331	dl	1.1	copy.retainAll(deque);
332			testEqual(deque, copy);
333			copy.removeAll(deque);
334			testEmpty(copy);
335			}
336
337			static boolean checkedThrows;
338
339			private static void testEmpty(Deque<Integer> deque) throws Exception {
340			if (!deque.isEmpty())
341			throw new Exception("Deque isn't empty");
342			if (deque.size() != 0)
343			throw new Exception("Deque size isn't zero");
344			if (!(deque.pollFirst() == null))
345			throw new Exception("pollFirst lies");
346			if (!(deque.poll() == null))
347			throw new Exception("poll lies");
348			if (!(deque.peekFirst() == null))
349			throw new Exception("peekFirst lies");
350			if (!(deque.peek() == null))
351			throw new Exception("peek lies");
352			if (!(deque.pollLast() == null))
353			throw new Exception("pollLast lies");
354			if (!(deque.peekLast() == null))
355			throw new Exception("peekLast lies");
356
357			if (!checkedThrows) {
358			checkedThrows = true;
359			boolean threw = false;
360			int result = 666;
361			try {
362	jsr166	1.4	result = ((random() & 1) == 0 ?
363	dl	1.1	deque.getFirst() : deque.element());
364	jsr166	1.4	} catch (NoSuchElementException e) {
365	dl	1.1	threw = true;
366			}
367			if (!threw)
368			throw new Exception("getFirst-no exception: "+result);
369			threw = false;
370			try {
371			result = deque.getLast();
372	jsr166	1.4	} catch (NoSuchElementException e) {
373	dl	1.1	threw = true;
374			}
375			if (!threw)
376			throw new Exception("getLast-no exception: "+result);
377			}
378
379			}
380			}