test/loops/DequeBash.java

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

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

/**
 * 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) {
            Deque<Integer> deque = (Deque<Integer>) cls.newInstance();
            nextTail =  0;
            nextHead = -1;
            long start = System.currentTimeMillis();
            mainTest(deque, n);
            long end = System.currentTimeMillis();
            System.out.println("Time: " + (end - start) + "ms");
            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, deepCopy(deque));
                testEqual(deque, (Deque<Integer>) deque.getClass().
                          getConstructor(Collection.class).newInstance(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 }");
    }

    private static <T> T deepCopy(T o) {
        try {
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            ObjectOutputStream oos = new ObjectOutputStream(bos);
            oos.writeObject(o);
            oos.flush();
            ByteArrayInputStream bin = new ByteArrayInputStream(
                bos.toByteArray());
            ObjectInputStream ois = new ObjectInputStream(bin);
            return (T) ois.readObject();
        } catch (Exception e) {
            throw new IllegalArgumentException(e);
        }
    }

    private static void testRemove(Deque<Integer> deque) throws Exception {
        Deque<Integer> copy = null;
        switch(random() & 1) {
          case 0:
            copy = (Deque<Integer>) deque.getClass().
                getConstructor(Collection.class).newInstance(deque);
            break;
          case 1:
            copy = deepCopy(deque);
            break;
          default:
            throw new Exception("How'd we get here");
        }

        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 = (Deque<Integer>) deque.getClass().
            getConstructor(Collection.class).newInstance(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.4
Committed:	Mon Nov 2 23:42:46 2009 UTC (14 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.3:	+13 -13 lines
Log Message:	whitespace
#	Content
1	/*
2	* Written by Josh Bloch of Google Inc. and released to the public domain,
3	* as explained at http://creativecommons.org/licenses/publicdomain.
4	*/
5
6	import java.util.*;
7	import java.io.*;
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
26	static int random(int bound) {
27	int x = seed;
28	int t = (x % 127773) * 16807 - (x / 127773) * 2836;
29	seed = (t > 0) ? t : t + 0x7fffffff;
30	return (t & 0x7fffffff) % bound;
31	}
32
33	static int random() {
34	int x = seed;
35	int t = (x % 127773) * 16807 - (x / 127773) * 2836;
36	seed = (t > 0) ? t : t + 0x7fffffff;
37	return (t & 0x7fffffff);
38	}
39
40	public static void main(String args[]) throws Exception {
41	Class cls = Class.forName(args[0]);
42	int n = 1000000;
43
44	for (int j = 0; j < 3; ++j) {
45	Deque<Integer> deque = (Deque<Integer>) cls.newInstance();
46	nextTail = 0;
47	nextHead = -1;
48	long start = System.currentTimeMillis();
49	mainTest(deque, n);
50	long end = System.currentTimeMillis();
51	System.out.println("Time: " + (end - start) + "ms");
52	if (deque.isEmpty()) System.out.print(" ");
53	}
54
55	}
56
57	static void mainTest(Deque<Integer> deque, int n) throws Exception {
58	/*
59	* Perform a random sequence of operations, keeping contiguous
60	* sequence of integers on the deque.
61	*/
62	for (int i = 0; i < n; i++) {
63	sizeTests(deque);
64	randomOp(deque);
65
66	// Test iterator occasionally
67	if ((i & 1023) == 0) {
68	testIter(deque);
69	testDescendingIter(deque);
70	}
71
72	// Test serialization and copying
73	if ((i & 4095) == 0) {
74	testEqual(deque, deepCopy(deque));
75	testEqual(deque, (Deque<Integer>) deque.getClass().
76	getConstructor(Collection.class).newInstance(deque));
77	}
78
79	// Test fancy removal stuff once in a blue moon
80	if ((i & 8191) == 0)
81	testRemove(deque);
82
83	}
84
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	static void testIter(Deque<Integer> deque) throws Exception {
95	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	static void testDescendingIter(Deque<Integer> deque) throws Exception {
107	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	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	if (size() == 0)
128	testEmpty(deque);
129	else
130	nonEmptyTest(deque);
131
132	}
133
134	static void nonEmptyTest(Deque<Integer> deque) throws Exception {
135	if (deque.getFirst() != nextHead + 1)
136	throw new Exception("getFirst got: " +
137	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
148	if (deque.peekLast() != nextTail - 1)
149	throw new Exception("peekLast got: " + deque.peekLast() +
150	" expecting " + (nextTail - 1));
151	if (deque.getLast() != nextTail - 1)
152	throw new Exception("getLast got: " +
153	deque.getLast() + " expecting " + (nextTail - 1));
154	}
155
156
157	static void randomOp(Deque<Integer> deque) throws Exception {
158
159	// Perform a random operation
160	switch(random() & 3) {
161	case 0:
162	switch(random() & 3) {
163	case 0: deque.addLast(nextTail++); break;
164	case 1: deque.offerLast(nextTail++); break;
165	case 2: deque.offer(nextTail++); break;
166	case 3: deque.add(nextTail++); break;
167	default: throw new Exception("How'd we get here");
168	}
169	break;
170	case 1:
171	if (size() == 0) {
172	int result = 666;
173	boolean threw = false;
174	try {
175	switch(random(3)) {
176	case 0: result = deque.removeFirst(); break;
177	case 1: result = deque.remove(); break;
178	case 2: result = deque.pop(); break;
179	default: throw new Exception("How'd we get here");
180	}
181	} catch (NoSuchElementException e) {
182	threw = true;
183	}
184	if (!threw)
185	throw new Exception("Remove-no exception: " + result);
186	} else { // deque nonempty
187	int result = -1;
188	switch(random(5)) {
189	case 0: result = deque.removeFirst(); break;
190	case 1: result = deque.remove(); break;
191	case 2: result = deque.pop(); break;
192	case 3: result = deque.pollFirst(); break;
193	case 4: result = deque.poll(); break;
194	default: throw new Exception("How'd we get here");
195	}
196	if (result != ++nextHead)
197	throw new Exception(
198	"Removed "+ result + " expecting "+(nextHead - 1));
199	}
200	break;
201	case 2:
202	switch(random(3)) {
203	case 0: deque.addFirst(nextHead--); break;
204	case 1: deque.offerFirst(nextHead--); break;
205	case 2: deque.push(nextHead--); break;
206	default: throw new Exception("How'd we get here");
207	}
208	break;
209	case 3:
210	if (size() == 0) {
211	int result = -1;
212	boolean threw = false;
213	try {
214	result = deque.removeLast();
215	} catch (NoSuchElementException e) {
216	threw = true;
217	}
218	if (!threw)
219	throw new Exception("Remove-no exception: " + result);
220	} else { // deque nonempty
221	int result = ((random() & 1) == 0 ?
222	deque.removeLast() : deque.pollLast());
223	if (result != --nextTail)
224	throw new Exception(
225	"Removed "+ result + " expecting "+(nextTail + 1));
226	}
227	break;
228	default:
229	throw new Exception("How'd we get here");
230	}
231	}
232
233
234	private static void testEqual(Deque<Integer> d1, Deque<Integer> d2)
235	throws Exception
236	{
237	if (d1.size() != d2.size())
238	throw new Exception("Size " + d1.size() + " != " + d2.size());
239	Iterator<Integer> it = d2.iterator();
240	for (int i : d1) {
241	int j = it.next();
242	if (j != i)
243	throw new Exception("Element " + j + " != " + i);
244	}
245
246	for (int i : d1)
247	if (!d2.contains(i))
248	throw new Exception("d2 doesn't contain " + i);
249	for (int i : d2)
250	if (!d1.contains(i))
251	throw new Exception("d2 doesn't contain " + i);
252
253	if (d1.contains(Integer.MIN_VALUE))
254	throw new Exception("d2 contains Integer.MIN_VALUE");
255	if (d2.contains(Integer.MIN_VALUE))
256	throw new Exception("d2 contains Integer.MIN_VALUE");
257	if (d1.contains(null))
258	throw new Exception("d1 contains null");
259	if (d2.contains(null))
260	throw new Exception("d2 contains null");
261
262	if (!d1.containsAll(d2))
263	throw new Exception("d1 doesn't contain all of d2");
264	if (!d2.containsAll(d1))
265	throw new Exception("d2 doesn't contain all of d1");
266	Collection<Integer> c = Collections.singleton(Integer.MIN_VALUE);
267	if (d1.containsAll(c))
268	throw new Exception("d1 contains all of {Integer.MIN_VALUE }");
269	if (d2.containsAll(c))
270	throw new Exception("d2 contains all of {Integer.MIN_VALUE }");
271	}
272
273	private static <T> T deepCopy(T o) {
274	try {
275	ByteArrayOutputStream bos = new ByteArrayOutputStream();
276	ObjectOutputStream oos = new ObjectOutputStream(bos);
277	oos.writeObject(o);
278	oos.flush();
279	ByteArrayInputStream bin = new ByteArrayInputStream(
280	bos.toByteArray());
281	ObjectInputStream ois = new ObjectInputStream(bin);
282	return (T) ois.readObject();
283	} catch (Exception e) {
284	throw new IllegalArgumentException(e);
285	}
286	}
287
288	private static void testRemove(Deque<Integer> deque) throws Exception {
289	Deque<Integer> copy = null;
290	switch(random() & 1) {
291	case 0:
292	copy = (Deque<Integer>) deque.getClass().
293	getConstructor(Collection.class).newInstance(deque);
294	break;
295	case 1:
296	copy = deepCopy(deque);
297	break;
298	default:
299	throw new Exception("How'd we get here");
300	}
301
302	int numRemoved = 0;
303	for (Iterator<Integer> it = copy.iterator(); it.hasNext(); ) {
304	if ((it.next() & 1) == 0) {
305	it.remove();
306	numRemoved++;
307	}
308	}
309
310	if (copy.size() + numRemoved != size())
311	throw new Exception((copy.size() + numRemoved) + " != " + size());
312	for (int i : copy)
313	if ((i & 1) == 0)
314	throw new Exception("Even number still present: " + i);
315
316	List<Integer> elements = Arrays.asList(copy.toArray(new Integer[0]));
317	Collections.shuffle(elements);
318	for (int e : elements) {
319	if (!copy.contains(e))
320	throw new Exception(e + " missing.");
321
322	boolean removed = false;
323	switch(random(3)) {
324	case 0: removed = copy.remove(e); break;
325	case 1: removed = copy.removeFirstOccurrence(e); break;
326	case 2: removed = copy.removeLastOccurrence(e); break;
327	default: throw new Exception("How'd we get here");
328	}
329	if (!removed)
330	throw new Exception(e + " not removed.");
331
332	if (copy.contains(e))
333	throw new Exception(e + " present after removal.");
334	}
335
336	testEmpty(copy);
337
338	copy = (Deque<Integer>) deque.getClass().
339	getConstructor(Collection.class).newInstance(deque);
340	copy.retainAll(deque);
341	testEqual(deque, copy);
342	copy.removeAll(deque);
343	testEmpty(copy);
344	}
345
346	static boolean checkedThrows;
347
348	private static void testEmpty(Deque<Integer> deque) throws Exception {
349	if (!deque.isEmpty())
350	throw new Exception("Deque isn't empty");
351	if (deque.size() != 0)
352	throw new Exception("Deque size isn't zero");
353	if (!(deque.pollFirst() == null))
354	throw new Exception("pollFirst lies");
355	if (!(deque.poll() == null))
356	throw new Exception("poll lies");
357	if (!(deque.peekFirst() == null))
358	throw new Exception("peekFirst lies");
359	if (!(deque.peek() == null))
360	throw new Exception("peek lies");
361	if (!(deque.pollLast() == null))
362	throw new Exception("pollLast lies");
363	if (!(deque.peekLast() == null))
364	throw new Exception("peekLast lies");
365
366	if (!checkedThrows) {
367	checkedThrows = true;
368	boolean threw = false;
369	int result = 666;
370	try {
371	result = ((random() & 1) == 0 ?
372	deque.getFirst() : deque.element());
373	} catch (NoSuchElementException e) {
374	threw = true;
375	}
376	if (!threw)
377	throw new Exception("getFirst-no exception: "+result);
378	threw = false;
379	try {
380	result = deque.getLast();
381	} catch (NoSuchElementException e) {
382	threw = true;
383	}
384	if (!threw)
385	throw new Exception("getLast-no exception: "+result);
386	}
387
388	}
389	}