import java.util.*;

/**
 * CWE-407 simulation test for RetroArch defect.
 *
 * retroarch-0001: playlist_entry_exists O(P) linear scan called per scan result
 *                 in content scanner loop → O(R*P) total.
 */
public class RetroArchCwe407Test {

    /**
     * DEFECTIVE: For each scan result, linear scan through playlist entries.
     * Simulates playlist_entry_exists called from task_database.c scan loop.
     */
    static int playlistEntryExists_defective(int R, int P) {
        // Build initial playlist with P entries
        List<String> playlist = new ArrayList<>();
        for (int i = 0; i < P; i++) {
            playlist.add("/roms/game" + i + ".rom");
        }

        int ops = 0;
        // Scan R new results, each checks playlist_entry_exists
        for (int r = 0; r < R; r++) {
            String path = "/roms/game" + (P + r) + ".rom"; // new content not in playlist
            // Linear scan through all P entries
            boolean found = false;
            for (int j = 0; j < playlist.size(); j++) {
                ops++;
                if (playlist.get(j).equals(path)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                playlist.add(path); // push to playlist
            }
        }
        return ops;
    }

    /**
     * PATCHED: Use hash set for O(1) existence check.
     */
    static int playlistEntryExists_patched(int R, int P) {
        Set<String> pathSet = new HashSet<>();
        for (int i = 0; i < P; i++) {
            pathSet.add("/roms/game" + i + ".rom");
        }

        int ops = 0;
        for (int r = 0; r < R; r++) {
            String path = "/roms/game" + (P + r) + ".rom";
            ops++; // O(1) hash lookup
            if (!pathSet.contains(path)) {
                pathSet.add(path);
            }
        }
        return ops;
    }

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

        {
            int R = 500; // scan results
            int P = 500; // existing playlist entries
            int defOps = playlistEntryExists_defective(R, P);
            int patOps = playlistEntryExists_patched(R, P);
            double ratio = (double) defOps / patOps;

            System.out.printf("retroarch-0001 playlist_entry_exists (R=%d, P=%d):%n", R, P);
            System.out.printf("  defective ops: %d%n", defOps);
            System.out.printf("  patched ops:   %d%n", patOps);
            System.out.printf("  ratio:         %.1fx%n", ratio);

            // Defective: each of R=500 new entries scans growing list (~500..999)
            // ~500*500 + 500*499/2 ≈ 374,750 ops
            // Patched: R = 500 ops
            if (ratio > 100) {
                System.out.println("  PASS: ratio > 100x confirms O(R*P) vs O(R)");
                passed++;
            } else {
                System.out.println("  FAIL: expected ratio > 100x, got " + ratio);
                failed++;
            }
        }

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