import java.util.*;

/**
 * Unit tests for RPCS3 CWE-407 defects.
 *
 * rpcs3-0001: SPU recompiler m_preds vector dedup O(E*P)
 * rpcs3-0002: SPU recompiler func.calls vector dedup O(B*T*C)
 * rpcs3-0003: cellSaveData blist sort comparator O(N*logN*B)
 */
public class Rpcs3SpuRecompilerTest {

    // --- rpcs3-0001/0002: predecessor/call vector dedup ---

    /** DEFECTIVE: linear scan before push_back */
    static void addPred_defective(List<Integer> preds, int pos) {
        if (!preds.contains(pos)) {
            preds.add(pos);
        }
    }

    /** FIXED: hash set for O(1) dedup */
    static void addPred_fixed(List<Integer> preds, Set<Integer> predSet, int pos) {
        if (predSet.add(pos)) {
            preds.add(pos);
        }
    }

    // --- rpcs3-0003: blist sort comparator ---

    /** DEFECTIVE: linear find in comparator */
    static void sortFiles_defective(List<String> files, List<String> blist) {
        files.sort((a, b) -> {
            int ai = blist.indexOf(a);
            int bi = blist.indexOf(b);
            if (ai == -1 && bi == -1) return a.compareTo(b);
            if (ai == -1) return 1;
            if (bi == -1) return -1;
            return Integer.compare(ai, bi);
        });
    }

    /** FIXED: pre-built index map */
    static void sortFiles_fixed(List<String> files, List<String> blist) {
        Map<String, Integer> index = new HashMap<>();
        for (int i = 0; i < blist.size(); i++) {
            if (!blist.get(i).isEmpty()) index.put(blist.get(i), i);
        }
        files.sort((a, b) -> {
            Integer ai = index.get(a);
            Integer bi = index.get(b);
            if (ai == null && bi == null) return a.compareTo(b);
            if (ai == null) return 1;
            if (bi == null) return -1;
            return Integer.compare(ai, bi);
        });
    }

    public static void main(String[] args) {
        int passed = 0;
        int failed = 0;

        // --- Test 1: rpcs3-0001 correctness ---
        {
            List<Integer> defect = new ArrayList<>();
            List<Integer> fixed = new ArrayList<>();
            Set<Integer> fixedSet = new HashSet<>();
            for (int i = 0; i < 100; i++) {
                addPred_defective(defect, i);
                addPred_defective(defect, i); // duplicate
                addPred_fixed(fixed, fixedSet, i);
                addPred_fixed(fixed, fixedSet, i); // duplicate
            }
            boolean ok = defect.size() == 100 && fixed.size() == 100 && defect.equals(fixed);
            System.out.println((ok ? "PASS" : "FAIL") + " rpcs3-0001 correctness: predecessor dedup");
            if (ok) passed++; else failed++;
        }

        // --- Test 2: rpcs3-0001 performance ---
        {
            int N = 5000;
            List<Integer> defect = new ArrayList<>();
            long t0 = System.nanoTime();
            for (int i = 0; i < N; i++) addPred_defective(defect, i);
            long defectNs = System.nanoTime() - t0;

            List<Integer> fixed = new ArrayList<>();
            Set<Integer> fixedSet = new HashSet<>();
            t0 = System.nanoTime();
            for (int i = 0; i < N; i++) addPred_fixed(fixed, fixedSet, i);
            long fixedNs = System.nanoTime() - t0;

            double ratio = (double) defectNs / Math.max(fixedNs, 1);
            boolean ok = ratio > 5.0;
            System.out.printf("%s rpcs3-0001 performance: N=%d defect=%.1fms fixed=%.1fms ratio=%.1fx%n",
                    ok ? "PASS" : "FAIL", N, defectNs / 1e6, fixedNs / 1e6, ratio);
            if (ok) passed++; else failed++;
        }

        // --- Test 3: rpcs3-0002 correctness (same pattern, different context) ---
        {
            List<Integer> defect = new ArrayList<>();
            List<Integer> fixed = new ArrayList<>();
            Set<Integer> fixedSet = new HashSet<>();
            int[] targets = {100, 200, 300, 100, 200, 400};
            for (int t : targets) {
                addPred_defective(defect, t);
                addPred_fixed(fixed, fixedSet, t);
            }
            boolean ok = defect.size() == 4 && fixed.size() == 4;
            System.out.println((ok ? "PASS" : "FAIL") + " rpcs3-0002 correctness: call target dedup");
            if (ok) passed++; else failed++;
        }

        // --- Test 4: rpcs3-0003 correctness ---
        {
            List<String> blist = new ArrayList<>(Arrays.asList("icon0.png", "param.sfo", "data.bin"));
            List<String> files1 = new ArrayList<>(Arrays.asList("data.bin", "extra.txt", "icon0.png", "param.sfo", "readme.txt"));
            List<String> files2 = new ArrayList<>(files1);
            sortFiles_defective(files1, blist);
            sortFiles_fixed(files2, blist);
            boolean ok = files1.equals(files2);
            System.out.println((ok ? "PASS" : "FAIL") + " rpcs3-0003 correctness: blist sort order " + files1 + " == " + files2);
            if (ok) passed++; else failed++;
        }

        // --- Test 5: rpcs3-0003 performance ---
        {
            int N = 3000;
            List<String> blist = new ArrayList<>();
            for (int i = 0; i < N; i++) blist.add("file_" + String.format("%05d", i));

            List<String> files1 = new ArrayList<>(blist);
            Collections.shuffle(files1, new Random(42));
            List<String> files2 = new ArrayList<>(files1);

            long t0 = System.nanoTime();
            sortFiles_defective(files1, blist);
            long defectNs = System.nanoTime() - t0;

            t0 = System.nanoTime();
            sortFiles_fixed(files2, blist);
            long fixedNs = System.nanoTime() - t0;

            double ratio = (double) defectNs / Math.max(fixedNs, 1);
            boolean ok = ratio > 3.0;
            System.out.printf("%s rpcs3-0003 performance: N=%d defect=%.1fms fixed=%.1fms ratio=%.1fx%n",
                    ok ? "PASS" : "FAIL", N, defectNs / 1e6, fixedNs / 1e6, ratio);
            if (ok) passed++; else failed++;
        }

        // --- Test 6: rpcs3-0002 performance ---
        {
            int N = 5000;
            List<Integer> defect = new ArrayList<>();
            long t0 = System.nanoTime();
            // Simulate: for each BB target, dedup into calls list
            for (int bb = 0; bb < 50; bb++) {
                for (int t = 0; t < N / 50; t++) {
                    addPred_defective(defect, t * 4); // same targets from different BBs
                }
            }
            long defectNs = System.nanoTime() - t0;

            List<Integer> fixed = new ArrayList<>();
            Set<Integer> fixedSet = new HashSet<>();
            t0 = System.nanoTime();
            for (int bb = 0; bb < 50; bb++) {
                for (int t = 0; t < N / 50; t++) {
                    addPred_fixed(fixed, fixedSet, t * 4);
                }
            }
            long fixedNs = System.nanoTime() - t0;

            double ratio = (double) defectNs / Math.max(fixedNs, 1);
            boolean ok = ratio > 3.0;
            System.out.printf("%s rpcs3-0002 performance: N=%d defect=%.1fms fixed=%.1fms ratio=%.1fx%n",
                    ok ? "PASS" : "FAIL", N, defectNs / 1e6, fixedNs / 1e6, ratio);
            if (ok) passed++; else failed++;
        }

        System.out.printf("%n%d/%d tests passed%n", passed, passed + failed);
        if (failed > 0) System.exit(1);
    }
}