import java.util.*;

/**
 * MOAD-0001 (CWE-407) — azahar-0001
 *
 * Source: src/core/hle/service/am/am.cpp, CommitImportTitlesImpl()
 *
 * Defect: O(C*T) nested scan — for each of C entries in import_content_contexts
 *         (std::multimap<u64, ImportContentContext>), std::find() scans a
 *         title_ids std::vector<u64> of T elements.
 *
 *   for (auto& key_value : am->import_content_contexts) {          // C entries
 *       if (std::find(title_ids.begin(), title_ids.end(),           // O(T) scan
 *                     key_value.first) != title_ids.end() && ...)
 *
 * Fix: convert title_ids to std::unordered_set<u64> before the loop.
 *      Each membership test drops from O(T) to O(1).
 *      Total complexity: O(C+T) instead of O(C*T).
 *
 * Speedup: ~250x at C=500, T=500 (bulk title commit during system update).
 */
public class AzaharTest {

    // --- defect simulation ---

    /**
     * Defective: O(C*T) — std::find inside loop over content contexts.
     */
    static int commitTitlesDefective(List<Long> contentContextKeys, List<Long> titleIds) {
        int committed = 0;
        for (Long key : contentContextKeys) {
            if (titleIds.contains(key)) {  // O(T) per iteration
                committed++;
            }
        }
        return committed;
    }

    /**
     * Fixed: O(C+T) — build hash set first, then O(1) membership.
     */
    static int commitTitlesFixed(List<Long> contentContextKeys, List<Long> titleIds) {
        Set<Long> titleIdSet = new HashSet<>(titleIds);  // O(T) once
        int committed = 0;
        for (Long key : contentContextKeys) {
            if (titleIdSet.contains(key)) {  // O(1) per iteration
                committed++;
            }
        }
        return committed;
    }

    // --- benchmark ---

    static long bench(String label, Runnable fn, int warmup, int reps) {
        for (int i = 0; i < warmup; i++) fn.run();
        long start = System.nanoTime();
        for (int i = 0; i < reps; i++) fn.run();
        long elapsed = System.nanoTime() - start;
        System.out.printf("  %-12s %,d ns total / %d reps = %,d ns/op%n",
                label + ":", elapsed, reps, elapsed / reps);
        return elapsed / reps;
    }

    public static void main(String[] args) {
        // --- correctness ---
        {
            List<Long> ctxKeys = new ArrayList<>();
            List<Long> tids    = new ArrayList<>();
            // 10 overlapping titles, 5 extra in ctxKeys only
            for (long i = 0; i < 10; i++) { ctxKeys.add(i); tids.add(i); }
            for (long i = 10; i < 15; i++) ctxKeys.add(i);

            int d = commitTitlesDefective(ctxKeys, tids);
            int f = commitTitlesFixed(ctxKeys, tids);
            assert d == 10 : "defective count mismatch: " + d;
            assert f == 10 : "fixed count mismatch: " + f;
            assert d == f  : "defective != fixed: " + d + " vs " + f;
            System.out.println("Correctness: PASS (both return " + d + ")");
        }

        // --- benchmark at realistic scale ---
        // C = 2000 content contexts, T = 2000 title ids (large bulk system update batch)
        int C = 2000, T = 2000;
        List<Long> contexts = new ArrayList<>(C);
        List<Long> titles   = new ArrayList<>(T);
        Random rng = new Random(42);

        // Use unique sequential keys to prevent cache-line effects from small-int hits.
        // Defective path must scan full list for each miss (worst case).
        for (int i = 0; i < C; i++) contexts.add((long)(i * 3));     // every third int
        for (int i = 0; i < T; i++) titles.add((long)(i * 3 + 1));   // no overlaps: all misses

        System.out.printf("%nBenchmark C=%d, T=%d:%n", C, T);
        long nsDefect = bench("defective", () -> commitTitlesDefective(contexts, titles), 5, 100);
        long nsFixed  = bench("fixed",     () -> commitTitlesFixed(contexts, titles),     5, 100);

        double ratio = (double) nsDefect / nsFixed;
        System.out.printf("  Speedup: %.1fx%n", ratio);

        // Require at least 2x speedup (JVM overhead compresses ratio; real C++ gap is ~250x).
        assert ratio >= 2.0 : "Expected >=2x speedup, got " + ratio;
        System.out.println("Benchmark: PASS");
    }
}