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);

            // 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 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.1
Committed:	Mon May 2 19:19:38 2005 UTC (19 years ago) by dl
Branch:	MAIN
Log Message:	Put misc performance tests into CVS
#	User	Rev	Content
1	dl	1.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
70			// Test serialization and copying
71			if ((i & 4095) == 0) {
72			testEqual(deque, deepCopy(deque));
73			testEqual(deque, (Deque<Integer>) deque.getClass().
74			getConstructor(Collection.class).newInstance(deque));
75			}
76
77			// Test fancy removal stuff once in a blue moon
78			if ((i & 8191) == 0)
79			testRemove(deque);
80
81			}
82
83			// Stupid tests for clear, toString
84			deque.clear();
85			testEmpty(deque);
86			Collection<Integer> c = Arrays.asList(1, 2, 3);
87			deque.addAll(c);
88			if (!deque.toString().equals("[1, 2, 3]"))
89			throw new Exception("Deque.toString(): " + deque.toString());
90			}
91
92			static void testIter(Deque<Integer> deque) throws Exception {
93			int next = nextHead + 1;
94			int count = 0;
95			for (int j : deque) {
96			if (j != next++)
97			throw new Exception("Element "+ j + " != " + (next-1));
98			count++;
99			}
100			if (count != size())
101			throw new Exception("Count " + count + " != " + size());
102			}
103
104			static void sizeTests(Deque<Integer> deque) throws Exception {
105			if (deque.size() != size())
106			throw new Exception("Size: " + deque.size() +
107			", expecting " + size());
108			if (deque.isEmpty() != (size() == 0))
109			throw new Exception(
110			"IsEmpty " + deque.isEmpty() + ", size " + size());
111			// Check head and tail
112			if (size() == 0)
113			testEmpty(deque);
114			else
115			nonEmptyTest(deque);
116
117			}
118
119			static void nonEmptyTest(Deque<Integer> deque) throws Exception {
120			if (deque.getFirst() != nextHead + 1)
121			throw new Exception("getFirst got: " +
122			deque.getFirst() + " expecting " + (nextHead + 1));
123			if (deque.element() != nextHead + 1)
124			throw new Exception("element got: " + deque.element() +
125			" expecting " + (nextHead + 1));
126			if (deque.peekFirst() != nextHead + 1)
127			throw new Exception("peekFirst got: "+deque.peekFirst() +
128			" expecting " + (nextHead + 1));
129			if (deque.peek() != nextHead + 1)
130			throw new Exception("peek got: " + deque.peek() +
131			" expecting " + (nextHead + 1));
132
133			if (deque.peekLast() != nextTail - 1)
134			throw new Exception("peekLast got: " + deque.peekLast() +
135			" expecting " + (nextTail - 1));
136			if (deque.getLast() != nextTail - 1)
137			throw new Exception("getLast got: " +
138			deque.getLast() + " expecting " + (nextTail - 1));
139			}
140
141
142			static void randomOp(Deque<Integer> deque) throws Exception {
143
144			// Perform a random operation
145			switch(random() & 3) {
146			case 0:
147			switch(random() & 3) {
148			case 0: deque.addLast(nextTail++); break;
149			case 1: deque.offerLast(nextTail++); break;
150			case 2: deque.offer(nextTail++); break;
151			case 3: deque.add(nextTail++); break;
152			default: throw new Exception("How'd we get here");
153			}
154			break;
155			case 1:
156			if (size() == 0) {
157			int result = 666;
158			boolean threw = false;
159			try {
160			switch(random(3)) {
161			case 0: result = deque.removeFirst(); break;
162			case 1: result = deque.remove(); break;
163			case 2: result = deque.pop(); break;
164			default: throw new Exception("How'd we get here");
165			}
166			} catch(NoSuchElementException e) {
167			threw = true;
168			}
169			if (!threw)
170			throw new Exception("Remove-no exception: " + result);
171			} else { // deque nonempty
172			int result = -1;
173			switch(random(5)) {
174			case 0: result = deque.removeFirst(); break;
175			case 1: result = deque.remove(); break;
176			case 2: result = deque.pop(); break;
177			case 3: result = deque.pollFirst(); break;
178			case 4: result = deque.poll(); break;
179			default: throw new Exception("How'd we get here");
180			}
181			if (result != ++nextHead)
182			throw new Exception(
183			"Removed "+ result + " expecting "+(nextHead - 1));
184			}
185			break;
186			case 2:
187			switch(random(3)) {
188			case 0: deque.addFirst(nextHead--); break;
189			case 1: deque.offerFirst(nextHead--); break;
190			case 2: deque.push(nextHead--); break;
191			default: throw new Exception("How'd we get here");
192			}
193			break;
194			case 3:
195			if (size() == 0) {
196			int result = -1;
197			boolean threw = false;
198			try {
199			result = deque.removeLast();
200			} catch(NoSuchElementException e) {
201			threw = true;
202			}
203			if (!threw)
204			throw new Exception("Remove-no exception: " + result);
205			} else { // deque nonempty
206			int result = ((random() & 1) == 0?
207			deque.removeLast() : deque.pollLast());
208			if (result != --nextTail)
209			throw new Exception(
210			"Removed "+ result + " expecting "+(nextTail + 1));
211			}
212			break;
213			default:
214			throw new Exception("How'd we get here");
215			}
216			}
217
218
219			private static void testEqual(Deque<Integer> d1, Deque<Integer> d2)
220			throws Exception
221			{
222			if (d1.size() != d2.size())
223			throw new Exception("Size " + d1.size() + " != " + d2.size());
224			Iterator<Integer> it = d2.iterator();
225			for(int i : d1) {
226			int j = it.next();
227			if (j != i)
228			throw new Exception("Element " + j + " != " + i);
229			}
230
231			for(int i : d1)
232			if (!d2.contains(i))
233			throw new Exception("d2 doesn't contain " + i);
234			for(int i : d2)
235			if (!d1.contains(i))
236			throw new Exception("d2 doesn't contain " + i);
237
238			if (d1.contains(Integer.MIN_VALUE))
239			throw new Exception("d2 contains Integer.MIN_VALUE");
240			if (d2.contains(Integer.MIN_VALUE))
241			throw new Exception("d2 contains Integer.MIN_VALUE");
242			if (d1.contains(null))
243			throw new Exception("d1 contains null");
244			if (d2.contains(null))
245			throw new Exception("d2 contains null");
246
247			if (!d1.containsAll(d2))
248			throw new Exception("d1 doesn't contain all of d2");
249			if (!d2.containsAll(d1))
250			throw new Exception("d2 doesn't contain all of d1");
251			Collection<Integer> c = Collections.singleton(Integer.MIN_VALUE);
252			if (d1.containsAll(c))
253			throw new Exception("d1 contains all of {Integer.MIN_VALUE }");
254			if (d2.containsAll(c))
255			throw new Exception("d2 contains all of {Integer.MIN_VALUE }");
256			}
257
258			private static <T> T deepCopy(T o) {
259			try {
260			ByteArrayOutputStream bos = new ByteArrayOutputStream();
261			ObjectOutputStream oos = new ObjectOutputStream(bos);
262			oos.writeObject(o);
263			oos.flush();
264			ByteArrayInputStream bin = new ByteArrayInputStream(
265			bos.toByteArray());
266			ObjectInputStream ois = new ObjectInputStream(bin);
267			return (T) ois.readObject();
268			} catch(Exception e) {
269			throw new IllegalArgumentException(e);
270			}
271			}
272
273			private static void testRemove(Deque<Integer> deque) throws Exception {
274			Deque<Integer> copy = null;
275			switch(random() & 1) {
276			case 0:
277			copy = (Deque<Integer>) deque.getClass().
278			getConstructor(Collection.class).newInstance(deque);
279			break;
280			case 1:
281			copy = deepCopy(deque);
282			break;
283			default:
284			throw new Exception("How'd we get here");
285			}
286
287			int numRemoved = 0;
288			for (Iterator<Integer> it = copy.iterator(); it.hasNext(); ) {
289			if ((it.next() & 1) == 0) {
290			it.remove();
291			numRemoved++;
292			}
293			}
294
295			if (copy.size() + numRemoved != size())
296			throw new Exception((copy.size() + numRemoved) + " != " + size());
297			for (int i : copy)
298			if ((i & 1) == 0)
299			throw new Exception("Even number still present: " + i);
300
301			List<Integer> elements = Arrays.asList(copy.toArray(new Integer[0]));
302			Collections.shuffle(elements);
303			for (int e : elements) {
304			if (!copy.contains(e))
305			throw new Exception(e + " missing.");
306
307			boolean removed = false;
308			switch(random(3)) {
309			case 0: removed = copy.remove(e); break;
310			case 1: removed = copy.removeFirstOccurrence(e); break;
311			case 2: removed = copy.removeLastOccurrence(e); break;
312			default: throw new Exception("How'd we get here");
313			}
314			if (!removed)
315			throw new Exception(e + " not removed.");
316
317			if (copy.contains(e))
318			throw new Exception(e + " present after removal.");
319			}
320
321			testEmpty(copy);
322
323			copy = (Deque<Integer>) deque.getClass().
324			getConstructor(Collection.class).newInstance(deque);
325			copy.retainAll(deque);
326			testEqual(deque, copy);
327			copy.removeAll(deque);
328			testEmpty(copy);
329			}
330
331			static boolean checkedThrows;
332
333			private static void testEmpty(Deque<Integer> deque) throws Exception {
334			if (!deque.isEmpty())
335			throw new Exception("Deque isn't empty");
336			if (deque.size() != 0)
337			throw new Exception("Deque size isn't zero");
338			if (!(deque.pollFirst() == null))
339			throw new Exception("pollFirst lies");
340			if (!(deque.poll() == null))
341			throw new Exception("poll lies");
342			if (!(deque.peekFirst() == null))
343			throw new Exception("peekFirst lies");
344			if (!(deque.peek() == null))
345			throw new Exception("peek lies");
346			if (!(deque.pollLast() == null))
347			throw new Exception("pollLast lies");
348			if (!(deque.peekLast() == null))
349			throw new Exception("peekLast lies");
350
351			if (!checkedThrows) {
352			checkedThrows = true;
353			boolean threw = false;
354			int result = 666;
355			try {
356			result = ((random() & 1) == 0?
357			deque.getFirst() : deque.element());
358			} catch(NoSuchElementException e) {
359			threw = true;
360			}
361			if (!threw)
362			throw new Exception("getFirst-no exception: "+result);
363			threw = false;
364			try {
365			result = deque.getLast();
366			} catch(NoSuchElementException e) {
367			threw = true;
368			}
369			if (!threw)
370			throw new Exception("getLast-no exception: "+result);
371			}
372
373			}
374			}