import java.util.*;

/**
 * MOAD-0001 (CWE-407) -- gearsystem-0001
 *
 * Source: src/Processor.cpp, src/Processor.h (GearSystem SMS/GG emulator)
 *
 * Defect: O(B) linear scan over m_breakpoints vector on every memory access
 *         and every opcode dispatch, where B = number of breakpoints set.
 *
 *   // Memory_inline.h:28 -- called on EVERY memory Read()
 *   m_pProcessor->CheckMemoryBreakpoints(GS_BREAKPOINT_TYPE_ROMRAM, address, true);
 *
 *   // Processor.cpp:437 -- called on EVERY opcode dispatch
 *   CheckBreakpoints();  // -> scans full m_breakpoints O(B)
 *
 *   // Video.cpp:532,575,582,608,648 -- called on EVERY VDP memory access
 *   m_pProcessor->CheckMemoryBreakpoints(GS_BREAKPOINT_TYPE_VRAM, ...);
 *
 *   The Z80 CPU in the Sega Master System runs at ~3.58 MHz.  With VRAM/CRAM
 *   accesses added during rendering, total CheckMemoryBreakpoints() calls
 *   exceed 5,000,000 per second.  At B=64 breakpoints: 320,000,000 comparisons/s.
 *
 *   GearSystem is a pure developer tool (no retail GUI), so ALL users are
 *   developers who regularly set breakpoints.  This defect directly degrades
 *   the primary use case.
 *
 * Fix: maintain std::unordered_set<u16> for point breakpoints (range==false).
 *      CheckBreakpoints() and CheckMemoryBreakpoints() probe hash sets in O(1).
 *      Range breakpoints remain in the vector slow-path (rare case).
 *
 * Speedup: ~B x in debug inner loop (64x at B=64 breakpoints).
 */
public class GearsystemBreakpointTest {

    // --- defect simulation ---

    /**
     * Defective: O(B) scan over all breakpoints on every memory/VDP access.
     * Models Processor::CheckMemoryBreakpoints().
     * brk[] = {address1, address2, range, enabled, isRead, isWrite, type}
     */
    static boolean checkBpDefective(List<int[]> breakpoints, int type, int address, boolean read) {
        for (int[] brk : breakpoints) {
            if (brk[3] == 0) continue;  // !enabled
            if (brk[6] != type) continue; // type mismatch
            if (read  && brk[4] == 0) continue;
            if (!read && brk[5] == 0) continue;
            if (brk[2] == 0) {
                if (address == brk[0]) return true;
            } else {
                if (address >= brk[0] && address <= brk[1]) return true;
            }
        }
        return false;
    }

    /**
     * Fixed: O(1) hash probe for point breakpoints per type.
     * Models Processor::CheckMemoryBreakpoints() after patch.
     */
    static boolean checkBpFixed(
            Map<Integer, Set<Integer>> readIdx,
            Map<Integer, Set<Integer>> writeIdx,
            List<int[]> rangeBps,
            int type, int address, boolean read) {

        if (read) {
            Set<Integer> s = readIdx.get(type);
            if (s != null && s.contains(address)) return true;
        } else {
            Set<Integer> s = writeIdx.get(type);
            if (s != null && s.contains(address)) return true;
        }
        // range slow-path
        for (int[] brk : rangeBps) {
            if (brk[3] == 0 || brk[6] != type) continue;
            if (read && brk[4] == 0) continue;
            if (!read && brk[5] == 0) continue;
            if (address >= brk[0] && address <= brk[1]) return true;
        }
        return false;
    }

    static final int TYPE_ROMRAM = 0;
    static final int TYPE_VRAM   = 1;
    static final int TYPE_CRAM   = 2;

    /** Build the hash set index from a list of breakpoints (RebuildBreakpointIndex). */
    static void buildIndex(List<int[]> bps,
            Map<Integer, Set<Integer>> readIdx, Map<Integer, Set<Integer>> writeIdx) {
        readIdx.clear();
        writeIdx.clear();
        for (int[] brk : bps) {
            if (brk[3] == 0 || brk[2] != 0) continue;
            int t = brk[6];
            if (brk[4] != 0) readIdx .computeIfAbsent(t, k -> new HashSet<>()).add(brk[0]);
            if (brk[5] != 0) writeIdx.computeIfAbsent(t, k -> new HashSet<>()).add(brk[0]);
        }
    }

    // --- benchmark harness ---

    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("  %-14s %,d ns total / %d reps = %,d ns/op%n",
                label + ":", elapsed, reps, elapsed / reps);
        return elapsed / reps;
    }

    public static void main(String[] args) {
        // --- correctness ---
        System.out.println("=== Correctness ===");
        {
            List<int[]> bps = new ArrayList<>();
            // ROMRAM read+write breakpoints
            int[] romAddrs = {0x0100, 0x0200, 0xC000, 0x8000, 0x4000};
            for (int a : romAddrs) bps.add(new int[]{a, 0, 0, 1, 1, 1, TYPE_ROMRAM});
            // VRAM read breakpoints
            int[] vramAddrs = {0x0000, 0x1000, 0x1800};
            for (int a : vramAddrs) bps.add(new int[]{a, 0, 0, 1, 1, 0, TYPE_VRAM});
            // CRAM write breakpoints
            bps.add(new int[]{0x0010, 0, 0, 1, 0, 1, TYPE_CRAM});
            // one ROMRAM range breakpoint
            bps.add(new int[]{0xD000, 0xDFFF, 1, 1, 1, 1, TYPE_ROMRAM});

            Map<Integer, Set<Integer>> readIdx  = new HashMap<>();
            Map<Integer, Set<Integer>> writeIdx = new HashMap<>();
            buildIndex(bps, readIdx, writeIdx);
            List<int[]> rangeBps = new ArrayList<>();
            for (int[] b : bps) { if (b[2] != 0) rangeBps.add(b); }

            // hit in ROMRAM
            assert checkBpDefective(bps, TYPE_ROMRAM, 0x0100, true);
            assert checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_ROMRAM, 0x0100, true);
            // hit in VRAM
            assert checkBpDefective(bps, TYPE_VRAM, 0x1000, true);
            assert checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_VRAM, 0x1000, true);
            // hit in CRAM write
            assert checkBpDefective(bps, TYPE_CRAM, 0x0010, false);
            assert checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_CRAM, 0x0010, false);
            // hit in range
            assert checkBpDefective(bps, TYPE_ROMRAM, 0xD500, true);
            assert checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_ROMRAM, 0xD500, true);
            // miss
            assert !checkBpDefective(bps, TYPE_ROMRAM, 0x1234, true);
            assert !checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_ROMRAM, 0x1234, true);
            // wrong type
            assert !checkBpDefective(bps, TYPE_CRAM, 0x0100, true);
            assert !checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_CRAM, 0x0100, true);
            // wrong access (VRAM breakpoint is read-only)
            assert !checkBpDefective(bps, TYPE_VRAM, 0x1000, false);
            assert !checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_VRAM, 0x1000, false);

            System.out.println("  All correctness checks: PASS");
        }

        // --- benchmark ---
        // B = 64 breakpoints (ROMRAM + VRAM + CRAM)
        // 5000 memory accesses per rep (CPU + VDP combined per frame segment)
        int B = 64;
        int ACCESSES = 5000;
        int REPS = 500;

        List<int[]> bps = new ArrayList<>();
        for (int i = 0; i < B / 2; i++) {
            int addr = (i * 0x0200) & 0xFFFF;
            bps.add(new int[]{addr, 0, 0, 1, 1, 1, TYPE_ROMRAM});
        }
        for (int i = 0; i < B / 4; i++) {
            bps.add(new int[]{i * 0x0100, 0, 0, 1, 1, 0, TYPE_VRAM});
        }
        for (int i = 0; i < B / 4; i++) {
            bps.add(new int[]{i * 4, 0, 0, 1, 0, 1, TYPE_CRAM});
        }

        Map<Integer, Set<Integer>> readIdx  = new HashMap<>();
        Map<Integer, Set<Integer>> writeIdx = new HashMap<>();
        buildIndex(bps, readIdx, writeIdx);
        List<int[]> rangeBps = new ArrayList<>();

        Random rng = new Random(42);
        int[] accesses = new int[ACCESSES];
        for (int i = 0; i < ACCESSES; i++) accesses[i] = (rng.nextInt(0x10000) | 1);

        System.out.printf("%n=== Benchmark B=%d breakpoints, %d accesses/rep, %d reps ===%n", B, ACCESSES, REPS);

        long nsDefect = bench("defective",
            () -> { for (int a : accesses) checkBpDefective(bps, TYPE_ROMRAM, a, true); },
            10, REPS);

        long nsFixed = bench("fixed",
            () -> { for (int a : accesses) checkBpFixed(readIdx, writeIdx, rangeBps, TYPE_ROMRAM, a, true); },
            10, REPS);

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

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

        System.out.println("\nAll tests PASSED");
    }
}