import java.util.*;

/**
 * Unit test for DuckStation duckstation-0002:
 * Cheats::EnablePatches loops over all patch codes and calls std::find on
 * enable_list (std::vector<std::string>) for each patch, giving O(P*E)
 * behaviour where P = patch count and E = enabled names list length.
 *
 * PS1 GameShark/CodeBreaker patch databases can contain 100s of codes per game.
 * Called once at game load for both patches and cheats subsections.
 *
 * Defect file: src/core/cheats.cpp  line 909
 * Pattern: for each patch, std::find(enable_list.begin(), enable_list.end(), name)
 * Fix: build unordered_set from enable_list once, use count() for O(1) lookup.
 */
public class CheatsEnablePatchesTest {

    // --- Defective: O(P*E) linear scan per patch ---
    static int enablePatchesDefective(List<String> patches, List<String> enableList) {
        int count = 0;
        for (String name : patches) {
            if (!name.isEmpty() && !enableList.contains(name)) {  // O(E) scan per patch
                continue;
            }
            count++;
        }
        return count;
    }

    // --- Fixed: O(P+E) with hash set ---
    static int enablePatchesFixed(List<String> patches, List<String> enableList) {
        Set<String> enableSet = new HashSet<>(enableList);
        int count = 0;
        for (String name : patches) {
            if (!name.isEmpty() && !enableSet.contains(name)) {  // O(1) per patch
                continue;
            }
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int N = 500;

        List<String> patches = new ArrayList<>(N);
        List<String> enableList = new ArrayList<>(N);

        for (int i = 0; i < N; i++) {
            patches.add("Patch_" + i);
            enableList.add("Patch_" + i);
        }

        // Correctness check
        int defCount = enablePatchesDefective(patches, enableList);
        int fixCount = enablePatchesFixed(patches, enableList);
        assert defCount == fixCount
            : "Count mismatch: defective=" + defCount + " fixed=" + fixCount;
        assert fixCount == N : "Expected all " + N + " patches enabled";

        // Partial enable list
        List<String> partialEnable = enableList.subList(0, N / 2);
        int defPartial = enablePatchesDefective(patches, partialEnable);
        int fixPartial = enablePatchesFixed(patches, partialEnable);
        assert defPartial == fixPartial
            : "Partial count mismatch: defective=" + defPartial + " fixed=" + fixPartial;

        // Warm up
        for (int i = 0; i < 200; i++) {
            enablePatchesDefective(patches, enableList);
            enablePatchesFixed(patches, enableList);
        }

        // Benchmark
        int ITER = 2000;
        long t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) enablePatchesDefective(patches, enableList);
        long defectNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) enablePatchesFixed(patches, enableList);
        long fixedNs = System.nanoTime() - t0;

        double ratio = (double) defectNs / fixedNs;
        System.out.printf("EnablePatches  N=%d  defect=%.1fms  fixed=%.1fms  ratio=%.1fx%n",
                N, defectNs / 1e6, fixedNs / 1e6, ratio);

        assert ratio > 2.0 : "Expected >2x speedup, got " + ratio;
        System.out.println("PASS");
    }
}