// This program tests a Set implementation from the command line.
//
// Usage: java -ea Driver IMPNAME N S
//
// Here IMPNAME names an implementation of Set, N is the number of
// items inserted, and S is the random number generator seed.  You may
// omit the last two parameters to get some reasonable defaults.
//
// After building the table, this driver reports both the average and
// worst-case number of probes (equality operations) required to find
// a particular item x.
//
// If you run with assertions disabled, it prints a warning.

import java.util.Random;
import java.math.BigInteger;
import java.lang.reflect.Constructor;

public class Driver
{
    // We hash Int objects.  These are a like Integer, but with extra
    // counter fields for performance measurement purposes.
    static class Int {
        final int val;          // wrapped int value
        static int ec=0, hc=0;  // operation counters
        Int(int v) { val=v; }
        public int hashCode() { ++hc; return val; }
        public boolean equals(Object o) {
            ++ec; return (o instanceof Int) && ((Int)o).val==val;
        }
        public String toString() { return ""+val; }
    }

    public static void main(String[] a)
    {
        // Check that assertions are enabled.
        boolean assertionsChecked = false;
        assert (assertionsChecked = true);
        if (!assertionsChecked)
            warn("running with assertions disabled!");
        // Parse the command line parameters:
        String impName;         // implementation name
        int N, S;               // integer arguments, as described above
        impName = a[0];
        N = a.length>1 ? Integer.parseInt(a[1]) : 500000;
        S = a.length>2 ? Integer.parseInt(a[2]) : 37;
        System.out.printf("Testing %s with N=%d items, seed S=%d\n",
                          impName, N, S);

        // Try to load the named class, and construct an empty table.
        Set set = null;
        try {
            set =
                (Set)
                Class
                .forName(impName) // class object
                .getConstructor(new Class[] {}) // Constructor object
                .newInstance(new Object[] {}); // Object (we hope a Set)
        } catch (Exception e) {
            System.err.println("Error: " + e);
            System.exit(1);
        }
        System.out.printf("Constructed new %s()\n", impName);

        // Insert pseudo-random Int objects into both a java.util.Set
        // and our set until size reaches N.  Check for same number
        // of tries with each.
        Random gen = new Random(S);
        int checkTries = 0;
        java.util.HashSet<Int> checkSet = new java.util.HashSet<Int>();
        while (checkSet.size() < N) {
            ++checkTries;
            checkSet.add(new Int(gen.nextInt()));
        }
        gen = new Random(S);
        int tries = 0, ec=Int.ec, hc=Int.hc;
        long beg = System.currentTimeMillis();
        while (set.size() < N) {
            set.add(new Int(gen.nextInt()));
            ++tries;
        }
        double secs = (System.currentTimeMillis()-beg)/1000.0;
        assert tries == checkTries;
        ec = Int.ec-ec; hc = Int.hc-hc;
        System.out.printf
            ("Added %d Ints (with %d duplicates on the way):\n" +
             " used %d .equals calls, %d .hashCode calls, %.3f seconds\n",
             N, tries-N, ec, hc, secs);

        reportHitProbes(checkSet, set);

        // Now remove half the items, first in checkSet.
        checkTries = tries = 0;
        gen = new Random(S);  // different RNG
        while (checkSet.size() > N/2) {
            ++checkTries;
            checkSet.remove(new Int(gen.nextInt()));
        }
        // Again, in set, this time measuring time/op resources.
        gen = new Random(S);
        ec=Int.ec; hc=Int.hc; beg = System.currentTimeMillis();
        while (set.size() > N/2) {
            ++tries;
            set.remove(new Int(gen.nextInt()));
        }
        assert checkTries == tries;
        ec = Int.ec-ec; hc = Int.hc-hc;
        secs = (System.currentTimeMillis()-beg)/1000.0;
        System.out.printf
            ("Removed %d Ints (with %d false tries on the way):\n" +
             " used %d .equals calls, %d .hashCode calls, %.3f seconds\n",
             N-N/2, tries-(N-N/2), ec, hc, secs);

        reportHitProbes(checkSet, set);
    }

    static void reportHitProbes(java.util.Set<Int> checkSet, Set set) {
        // Report the average and worst-case #probes over all
        // items in the table (the "hit" statistics).
        int maxProbes=0, sumProbes=0, sumSquares=0, n=0;
        for (Int item: checkSet) {
            int probes = probesToFind(set, item);
            ++n;
            if (probes > maxProbes) maxProbes = probes;
            sumProbes += probes;
            sumSquares += probes*probes;
        }
        double mean = (double)sumProbes/n, mean2 = (double)sumSquares/n;
        double sigma = Math.sqrt(mean2 - mean*mean);
        System.out.printf("Hit probe stats over all %d items: " +
                          "mean=%.4f, sigma=%.4f, max=%d\n",
                          n, mean, sigma, maxProbes);
    }

    static int probesToFind(Set s, Int x)
    {
        int ec = Int.ec, hc = Int.hc;
        s.find(x);
        ec = Int.ec-ec; hc = Int.hc-hc;
        // s.find(x) should used .hashCode() at most twice.
        if (hc>2) warn("find("+x+") used .hashCode() "+hc+" times\n");
        return ec;
    }

    static int warnCount = 0;
    static void warn(String msg) {
        switch (++warnCount) {
        case 1: case 2: case 3: case 4:
            System.err.printf("WARNING: " + msg + "\n");
            break;
        case 5:
            System.err.println("WARNING: further warnings suppressed.");
        default:
            break;
        }
    }
}