import java.io.IOException;
import java.nio.file.Path;
import java.util.*;

// Class 12, 9:40: the same three collections asked the same questions,
// counting the questions each one asks back instead of timing them. A Counted
// number adds one to a counter every time its equals, hashCode or compareTo
// runs, and a lookup is nothing but those calls: the list calls equals on
// element after element until it finds one, the hash set calls hashCode once
// and equals once or twice in one bucket, the tree set calls compareTo once
// per level on its way down. Timing the sets is noise on a laptop (see
// Growth.java); counting is exact, and the same on every run.
//
//     java Steps.java          (JDK 22 or newer; it compiles Chart.java too)
//
// It also draws its three columns, one chart each, as steps-list.svg,
// steps-hash.svg and steps-tree.svg beside it, by way of Chart.java.
//
// JDK 21, 2026-10-04, identical on two runs, 1.1 seconds:
//     size         list      x   hash set      x   tree set      x
//    25000      18738.0      -        1.5      -       21.0      -
//    50000      37475.5   2.00        1.5   1.00       22.5   1.07
//   100000      74950.5   2.00        1.5   1.00       24.0   1.07
//   200000     149900.5   2.00        1.5   1.00       25.5   1.06
//   400000     299800.5   2.00        1.5   1.00       27.0   1.06
//   800000     599600.5   2.00        1.5   1.00       28.5   1.06
// Doubling the size doubles the list's questions, leaves the hash set's at one
// and a half, and adds one and a half to the tree set's. The list's 18,738 at
// 25,000 is three quarters of the size: a hit stops partway, a miss walks to
// the end, and half the questions are misses.
public class Steps {
    static final int QUESTIONS = 1_000;                                       // lookups per row
    static final int[] SIZES = {25_000, 50_000, 100_000, 200_000, 400_000, 800_000};

    // A number that counts the questions asked of it. equals, hashCode and
    // compareTo each add one to a counter, and the counters are static, so they
    // count across every Counted there is.
    static final class Counted implements Comparable<Counted> {
        static long equalsCalls, hashCodeCalls, compareToCalls;
        final int value;

        Counted(int value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object other) {
            equalsCalls++;
            return other instanceof Counted that && value == that.value;
        }

        @Override
        public int hashCode() {
            hashCodeCalls++;
            return Integer.hashCode(value);
        }

        @Override
        public int compareTo(Counted that) {
            compareToCalls++;
            return Integer.compare(value, that.value);
        }

        static void reset() {
            equalsCalls = hashCodeCalls = compareToCalls = 0;
        }
    }

    // puts 0 to size - 1 into c
    static void fill(Collection<Counted> c, int size) {
        for (int i = 0; i < size; i++) {
            c.add(new Counted(i));
        }
    }

    // asks c QUESTIONS lookups, half of them past the end, and returns how many
    // questions each lookup asked on average: equals, hashCode, compareTo
    static double[] perLookup(Collection<Counted> c, int size) {
        int step = 2 * size / QUESTIONS;
        Counted.reset();
        int found = 0;
        for (int i = 0; i < QUESTIONS; i++) {
            if (c.contains(new Counted(i * step))) found++;
        }
        if (found != QUESTIONS / 2) throw new AssertionError("found " + found);
        return new double[] {(double) Counted.equalsCalls / QUESTIONS,
                             (double) Counted.hashCodeCalls / QUESTIONS,
                             (double) Counted.compareToCalls / QUESTIONS};
    }

    public static void main(String[] args) throws IOException {
        double[][] columns = new double[3][SIZES.length];   // list, hash set, tree set
        System.out.printf("%8s %12s %6s %10s %6s %10s %6s%n",
                          "size", "list", "x", "hash set", "x", "tree set", "x");
        double[] last = null;
        for (int r = 0; r < SIZES.length; r++) {
            int size = SIZES[r];
            Collection<Counted> list = new ArrayList<>();
            Collection<Counted> hashed = new HashSet<>();
            Collection<Counted> sorted = new TreeSet<>();
            fill(list, size);
            fill(hashed, size);
            fill(sorted, size);
            double[] l = perLookup(list, size), h = perLookup(hashed, size), t = perLookup(sorted, size);
            double[] now = {l[0], h[1] + h[0], t[2]};   // what each one asks: equals; hashCode and equals; compareTo
            StringBuilder line = new StringBuilder(String.format("%8d", size));
            for (int k = 0; k < 3; k++) {
                String x = last == null ? "-" : String.format("%.2f", now[k] / last[k]);
                line.append(String.format(k == 0 ? " %12.1f %6s" : " %10.1f %6s", now[k], x));
            }
            System.out.println(line);
            last = now;
            for (int k = 0; k < 3; k++) {
                columns[k][r] = now[k];
            }
        }
        System.out.println("questions asked per lookup: equals for the list, hashCode and equals for the"
                           + " hash set, compareTo for the tree set; x is the factor against the row above");

        // the three columns as three charts, one shape each, written beside this file
        String[] names = {"list", "hash set", "tree set"};
        String[] files = {"steps-list.svg", "steps-hash.svg", "steps-tree.svg"};
        for (int k = 0; k < 3; k++) {
            Chart.write(Path.of(files[k]), names[k] + ": questions per lookup", SIZES,
                        new double[][] {columns[k]}, new String[] {names[k]});
        }
        System.out.println("drawn: steps-list.svg, steps-hash.svg, steps-tree.svg");
    }
}
