import java.util.*;

/**
 * Unit test for PCSX2 pcsx2-0003:
 * Achievements::DrawAchievement uses std::find_if on a std::vector of
 * (pointer, path) pairs to look up our cached badge path per achievement.
 * Called once per achievement per ImGui frame while our achievements window
 * is open. A game with A achievements gives O(A^2) total scan work per frame.
 *
 * Modern PS2 titles routinely ship 50-200 RetroAchievements entries.
 *
 * Defect file: pcsx2/Achievements.cpp  line 2777
 * Pattern: std::find_if(s_achievement_badge_paths.begin(), ..., ptr == cheevo)
 * Fix: change s_achievement_badge_paths to std::unordered_map<const void*, string>
 *      and use .find(cheevo) for O(1) lookup.
 */
public class AchievementBadgePathsTest {

    // --- Defective: vector-as-map, O(A) lookup per draw call ---
    static String drawAchievementDefective(
            List<long[]> badgePaths,  // pair<ptr_id, path_index>
            Map<Long, String> pathStore,
            long cheevoId,
            int[] pathCounter) {

        for (long[] entry : badgePaths) {
            if (entry[0] == cheevoId) {
                return pathStore.get(entry[1]);
            }
        }
        // Not found: add new entry
        long idx = pathCounter[0]++;
        pathStore.put(idx, "badge_" + cheevoId + ".png");
        badgePaths.add(new long[]{cheevoId, idx});
        return pathStore.get(idx);
    }

    // --- Fixed: unordered_map, O(1) lookup per draw call ---
    static String drawAchievementFixed(
            Map<Long, String> badgeMap,
            long cheevoId) {

        return badgeMap.computeIfAbsent(cheevoId,
            id -> "badge_" + id + ".png");
    }

    // Simulate one frame: draw all achievements
    static long frameDefective(int numAchievements) {
        List<long[]> badgePaths = new ArrayList<>(numAchievements);
        Map<Long, String> pathStore = new HashMap<>();
        int[] counter = {0};

        long ops = 0;
        for (int i = 0; i < numAchievements; i++) {
            drawAchievementDefective(badgePaths, pathStore, (long) i, counter);
            ops += badgePaths.size();  // track scan length
        }
        return ops;
    }

    static void frameFixed(int numAchievements) {
        Map<Long, String> badgeMap = new HashMap<>(numAchievements);
        for (int i = 0; i < numAchievements; i++) {
            drawAchievementFixed(badgeMap, (long) i);
        }
    }

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

        // Correctness: both paths must return same badge path
        List<long[]> vecPaths = new ArrayList<>();
        Map<Long, String> pathStore = new HashMap<>();
        int[] counter = {0};
        Map<Long, String> mapPaths = new HashMap<>();

        for (int i = 0; i < N; i++) {
            String defPath = drawAchievementDefective(vecPaths, pathStore, (long) i, counter);
            String fixPath = drawAchievementFixed(mapPaths, (long) i);
            assert defPath.equals(fixPath)
                : "Path mismatch at i=" + i + ": " + defPath + " != " + fixPath;
        }

        // Second pass: lookup must return same path (not duplicate)
        for (int i = 0; i < N; i++) {
            String defPath = drawAchievementDefective(vecPaths, pathStore, (long) i, counter);
            String fixPath = drawAchievementFixed(mapPaths, (long) i);
            assert defPath.equals(fixPath) : "Cache miss mismatch at i=" + i;
        }

        // Warm up
        for (int i = 0; i < 50; i++) {
            frameDefective(N);
            frameFixed(N);
        }

        // Benchmark: simulate 500 frames
        int FRAMES = 500;
        long t0 = System.nanoTime();
        for (int f = 0; f < FRAMES; f++) frameDefective(N);
        long defectNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int f = 0; f < FRAMES; f++) frameFixed(N);
        long fixedNs = System.nanoTime() - t0;

        double ratio = (double) defectNs / fixedNs;
        System.out.printf("DrawAchievement badge lookup  A=%d achievements  %d frames  defect=%.1fms  fixed=%.1fms  ratio=%.1fx%n",
                N, FRAMES, defectNs / 1e6, fixedNs / 1e6, ratio);

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