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

// Class 12, section 2 taken further: SearchCost's timing over doubling sizes,
// so the shape of the growth shows rather than one ratio. One kind at a time,
// a fresh collection filled at each size and asked its questions. Two plain
// things make the numbers repeatable, and nothing else is needed: each kind
// runs once untimed first, because Java compiles a method only after it has
// run for a while; and the sets are asked 50,000 questions rather than 10,000,
// because 10,000 take a tenth of a millisecond, too short to time, with every
// cell scaled to 10,000 so the columns compare.
//
//     java Growth.java          (JDK 22 or newer; it compiles Chart.java too)
//
// It also draws its table, as time-all.svg and time-sets.svg beside it, by
// way of Chart.java; the two beside this file are from the run below.
//
// JDK 21, 2026-10-04, 5.5 seconds, the run that drew the two charts beside
// this file, the median of three by the tree set's last cell:
//     size       list     x   hash set     x   tree set     x
//      25000      74515     -         88     -        481     -
//      50000     149550  2.01         96  1.09        452  0.94
//     100000     290471  1.94         99  1.03        562  1.24
//     200000     576263  1.98        100  1.01        732  1.30
//     400000    1170347  2.03        124  1.24       1159  1.58
// Three earlier runs: list 74203, 150025, 293604, 605338, 1212813; 74960,
// 148302, 292739, 583368, 1182471; 74865, 149920, 293457, 591711, 1204053.
// Hash set 90, 107, 118, 111, 124; 75, 72, 82, 99, 109; 126, 96, 103, 89,
// 106. Tree set 401, 476, 572, 706, 1158; 427, 502, 702, 805, 1220; 399, 480,
// 615, 764, 1441. The list doubles with the size. The hash set does not grow. The tree
// set grows, and faster than its question count (Steps.java: one and a half
// more compareTo calls per doubling), because a bigger tree misses the
// processor's cache more; what the clock measures for a set is memory, and
// Steps counts the questions.
public class Growth {
    static final int[] SIZES = {25_000, 50_000, 100_000, 200_000, 400_000};
    static final int LIST_QUESTIONS = 10_000;   // a list takes long enough to time
    static final int SET_QUESTIONS = 50_000;    // a set answers 10,000 in a tenth of a millisecond,
                                                // too short to time, so it is asked more

    // an empty collection of the kind named
    static Collection<Integer> make(String kind) {
        if (kind.equals("list")) {
            return new ArrayList<>();
        }
        if (kind.equals("hash set")) {
            return new HashSet<>();
        }
        return new TreeSet<>();
    }

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

    // asks c that many contains questions, half of them past the end, and
    // returns the microseconds they took, scaled to 10,000 questions
    static long timeLookups(Collection<Integer> c, int size, int questions) {
        int step = 2 * size / questions;
        long start = System.nanoTime();
        int found = 0;
        for (int i = 0; i < questions; i++) {
            if (c.contains(i * step)) found++;
        }
        if (found != questions / 2) throw new AssertionError("found " + found);
        return (System.nanoTime() - start) / 1_000 * 10_000 / questions;
    }

    // one kind at every size: a fresh collection each time, filled, then timed
    static long[] ladder(String kind, int questions) {
        long[] times = new long[SIZES.length];
        for (int k = 0; k < SIZES.length; k++) {
            Collection<Integer> c = make(kind);
            fill(c, SIZES[k]);
            times[k] = timeLookups(c, SIZES[k], questions);
        }
        return times;
    }

    public static void main(String[] args) throws IOException {
        String[] kinds = {"list", "hash set", "tree set"};
        long[][] times = new long[kinds.length][];
        for (int j = 0; j < kinds.length; j++) {
            int questions = kinds[j].equals("list") ? LIST_QUESTIONS : SET_QUESTIONS;
            // Java compiles a method only after it has run for a while, so the
            // first pass through anything is slower. Run each kind once untimed.
            ladder(kinds[j], questions);
            times[j] = ladder(kinds[j], questions);
        }
        System.out.printf("%8s %10s %5s %10s %5s %10s %5s%n",
                          "size", "list", "x", "hash set", "x", "tree set", "x");
        for (int k = 0; k < SIZES.length; k++) {
            StringBuilder line = new StringBuilder(String.format("%8d", SIZES[k]));
            for (int j = 0; j < kinds.length; j++) {
                String x = k == 0 ? "-" : String.format("%.2f", (double) times[j][k] / times[j][k - 1]);
                line.append(String.format(" %10d %5s", times[j][k], x));
            }
            System.out.println(line);
        }
        System.out.println("microseconds per 10,000 lookups; x is the factor against the row above");

        // the same table as two charts, written beside this file: all three
        // together, then the two sets alone, which the first chart flattens
        double[][] ms = new double[kinds.length][SIZES.length];
        for (int j = 0; j < kinds.length; j++) {
            for (int k = 0; k < SIZES.length; k++) {
                ms[j][k] = times[j][k] / 1000.0;
            }
        }
        Chart.write(Path.of("time-all.svg"), "milliseconds for 10,000 lookups", SIZES, ms, kinds);
        Chart.write(Path.of("time-sets.svg"), "the two sets alone, milliseconds", SIZES,
                    new double[][] {ms[1], ms[2]}, new String[] {kinds[1], kinds[2]});
        System.out.println("drawn: time-all.svg, time-sets.svg");
    }
}
