import java.util.*;

/**
 * root-cern-0001: TTreeCache::FillBuffer potentialVetoes O(N²) vs O(1)
 *
 * Models the defect in TTreeCache::FillBuffer where, for each basket j in
 * the inner loop, a std::find() scan through potentialVetoes (a vector) is
 * performed. potentialVetoes holds unused basket indices and can grow to N.
 * With B branches each having N baskets this costs O(B * N²).
 *
 * Fix: replace std::vector with std::unordered_set, making membership O(1).
 */
public class RootCern0001Test {

    // DEFECT: simulate TTreeCache::FillBuffer with List.contains — O(N) per lookup
    static long simulateDefect(int nBranches, int nBaskets) {
        long count = 0;
        for (int i = 0; i < nBranches; i++) {
            // simulate GetUnused() filling potentialVetoes
            List<Integer> potentialVetoes = new ArrayList<>();
            for (int k = 0; k < nBaskets / 2; k++) {
                potentialVetoes.add(k * 2); // every other basket is "unused"
            }
            // inner basket loop
            for (int j = 0; j < nBaskets; j++) {
                count++;
                // O(V) scan — the defect
                if (potentialVetoes.contains(j)) {
                    // veto this basket
                }
            }
        }
        return count;
    }

    // FIX: simulate with HashSet.contains — O(1) per lookup
    static long simulateFix(int nBranches, int nBaskets) {
        long count = 0;
        for (int i = 0; i < nBranches; i++) {
            Set<Integer> potentialVetoes = new HashSet<>();
            for (int k = 0; k < nBaskets / 2; k++) {
                potentialVetoes.add(k * 2);
            }
            for (int j = 0; j < nBaskets; j++) {
                count++;
                // O(1) lookup — the fix
                if (potentialVetoes.contains(j)) {
                    // veto this basket
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // Verify functional equivalence first
        int nBranches = 5;
        int nBaskets = 20;

        // Both should iterate same number of baskets
        long defectCount = simulateDefect(nBranches, nBaskets);
        long fixCount = simulateFix(nBranches, nBaskets);
        assert defectCount == fixCount : "Iteration counts must match";
        assert defectCount == (long) nBranches * nBaskets : "Expected " + (nBranches * nBaskets);

        // Measure performance difference
        int bigBranches = 10;
        int bigBaskets = 5000;

        long t0 = System.nanoTime();
        simulateDefect(bigBranches, bigBaskets);
        long defectNs = System.nanoTime() - t0;

        long t1 = System.nanoTime();
        simulateFix(bigBranches, bigBaskets);
        long fixNs = System.nanoTime() - t1;

        double ratio = (double) defectNs / fixNs;
        System.out.printf("root-cern-0001 potentialVetoes: defect=%dms fix=%dms ratio=%.1fx%n",
                defectNs / 1_000_000, fixNs / 1_000_000, ratio);

        assert ratio > 5.0 : "Expected at least 5x speedup, got " + ratio;
        System.out.println("PASS");
    }
}