dequebash.java

来自「SRI international 发布的OAA框架软件」· Java 代码 · 共 388 行 · 第 1/2 页

/*
 * 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.*;
import edu.emory.mathcs.backport.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) {
            Deque deque = (Deque) 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 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, (Deque)deepCopy(deque));
                testEqual(deque, (Deque) deque.getClass().
                          getConstructor(new Class[] { Collection.class }).
                              newInstance(new Object[] { 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 c = Arrays.asList(new Integer[] {new Integer(1), new Integer(2), new Integer(3)});
        deque.addAll(c);
        if (!deque.toString().equals("[1, 2, 3]"))
            throw new Exception("Deque.toString():  " + deque.toString());
    }

    static void testIter(Deque deque) throws Exception {
        int next = nextHead + 1;
        int count = 0;
        for (Iterator jitr = deque.iterator(); jitr.hasNext();) {
            int j = ((Integer)jitr.next()).intValue();
            if (j != next++)
                throw new Exception("Element "+ j + " != " + (next-1));
            count++;
        }
        if (count != size())
            throw new Exception("Count " + count + " != " + size());
    }

    static void sizeTests(Deque 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 deque) throws Exception {
        if (((Integer)deque.getFirst()).intValue() != nextHead + 1)
            throw new Exception("getFirst got: " +
                                deque.getFirst() + " expecting " + (nextHead + 1));
        if (((Integer)deque.element()).intValue() != nextHead + 1)
            throw new Exception("element got: " + deque.element() +
                                " expecting " + (nextHead + 1));
        if (((Integer)deque.peekFirst()).intValue() != nextHead + 1)
            throw new Exception("peekFirst got: "+deque.peekFirst() +
                                " expecting " + (nextHead + 1));
        if (((Integer)deque.peek()).intValue() != nextHead + 1)
            throw new Exception("peek got: " +  deque.peek() +
                                " expecting " + (nextHead + 1));

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


    static void randomOp(Deque deque) throws Exception {

        // Perform a random operation
        switch(random() & 3) {
        case 0:
            switch(random() & 3) {
            case 0: deque.addLast(new Integer(nextTail++));   break;
            case 1: deque.offerLast(new Integer(nextTail++)); break;
            case 2: deque.offer(new Integer(nextTail++));     break;
            case 3: deque.add(new Integer(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 = ((Integer)deque.removeFirst()).intValue(); break;
                    case 1: result = ((Integer)deque.remove()).intValue();      break;
                    case 2: result = ((Integer)deque.pop()).intValue();         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 = ((Integer)deque.removeFirst()).intValue(); break;
                case 1: result = ((Integer)deque.remove()).intValue();      break;
                case 2: result = ((Integer)deque.pop()).intValue();         break;
                case 3: result = ((Integer)deque.pollFirst()).intValue();   break;
                case 4: result = ((Integer)deque.poll()).intValue();        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(new Integer(nextHead--));   break;
            case 1: deque.offerFirst(new Integer(nextHead--)); break;
            case 2: deque.push(new Integer(nextHead--));       break;
            default: throw new Exception("How'd we get here");