import java.util.*;

/**
 * Unit test for DuckStation duckstation-0001:
 * Cheats::GetCodeListUniquePrefixes uses std::find on a growing std::vector
 * inside a loop over all cheat codes, giving O(N^2) behaviour.
 *
 * PS1 cheat databases (GameShark, CodeBreaker) contain 100s to 1000s of codes
 * per game. This function is called every time our cheat settings UI tab opens.
 *
 * Defect file: src/core/cheats.cpp  line 614
 * Pattern: for each code, std::find(ret.begin(), ret.end(), prefix)
 * Fix: insert into unordered_set for O(1) membership test per code.
 */
public class CheatsUniquePrefixesTest {

    // --- Defective: O(N^2) linear scan dedup ---
    static List<String> getUniquePrefixesDefective(List<String> codes) {
        List<String> ret = new ArrayList<>();
        for (String code : codes) {
            // Simulate GetNameParentPart: prefix is everything before '/'
            int slash = code.lastIndexOf('/');
            String prefix = (slash >= 0) ? code.substring(0, slash) : "";
            if (prefix.isEmpty()) continue;
            if (!ret.contains(prefix)) {  // O(N) scan per code
                ret.add(prefix);
            }
        }
        return ret;
    }

    // --- Fixed: O(N) with hash set ---
    static List<String> getUniquePrefixesFixed(List<String> codes) {
        List<String> ret = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        for (String code : codes) {
            int slash = code.lastIndexOf('/');
            String prefix = (slash >= 0) ? code.substring(0, slash) : "";
            if (prefix.isEmpty()) continue;
            if (seen.add(prefix)) {
                ret.add(prefix);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int NUM_GROUPS = 200;
        int CODES_PER_GROUP = 5;
        int N = NUM_GROUPS * CODES_PER_GROUP;

        // Build test data: codes named "Group_N/Code_M"
        List<String> codes = new ArrayList<>(N);
        for (int g = 0; g < NUM_GROUPS; g++) {
            for (int c = 0; c < CODES_PER_GROUP; c++) {
                codes.add("Group_" + g + "/Code_" + c);
            }
        }

        // Correctness check
        List<String> defResult = getUniquePrefixesDefective(codes);
        List<String> fixResult = getUniquePrefixesFixed(codes);
        Collections.sort(defResult);
        Collections.sort(fixResult);
        assert defResult.equals(fixResult)
            : "Prefix list mismatch: defective=" + defResult.size() + " fixed=" + fixResult.size();
        assert fixResult.size() == NUM_GROUPS : "Expected " + NUM_GROUPS + " unique prefixes";

        // Warm up
        for (int i = 0; i < 100; i++) {
            getUniquePrefixesDefective(codes);
            getUniquePrefixesFixed(codes);
        }

        // Benchmark
        int ITER = 1000;
        long t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) getUniquePrefixesDefective(codes);
        long defectNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) getUniquePrefixesFixed(codes);
        long fixedNs = System.nanoTime() - t0;

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

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