import java.util.*;

/**
 * Unit test for dosbox-x-0004: bdlist std::list<uint16_t> O(N^2) membership
 * in String_DBCS_TO_HOST_UTF16/UTF8 per-character conversion loop.
 *
 * Models DOSBox-X's DBCS filename conversion where std::find(bdlist) is called
 * for every character in the input string. bdlist tracks byte positions of
 * box-draw characters; with CROSS_LEN=512, worst case is 512*512=262,144
 * comparisons per filename conversion.
 *
 * The fix replaces std::list<uint16_t> with std::unordered_set<uint16_t>,
 * making each membership test O(1).
 */
public class DosboxXBdlistTest {

    static final int CROSS_LEN = 512;

    // --- Defect: std::list<uint16_t> with std::find per character ---
    static boolean listContains(List<Integer> bdlist, int pos) {
        for (int v : bdlist) {
            if (v == pos) return true;
        }
        return false;
    }

    static int convertWithList(int[] stringBytes, List<Integer> bdlist) {
        int converted = 0;
        for (int i = 0; i < stringBytes.length; i++) {
            if (listContains(bdlist, i)) {
                converted++;  // box-draw path
            } else {
                converted++;  // normal DBCS path
            }
        }
        return converted;
    }

    // --- Fix: std::unordered_set<uint16_t> with O(1) count ---
    static int convertWithSet(int[] stringBytes, Set<Integer> bdset) {
        int converted = 0;
        for (int i = 0; i < stringBytes.length; i++) {
            if (bdset.contains(i)) {
                converted++;  // box-draw path
            } else {
                converted++;  // normal DBCS path
            }
        }
        return converted;
    }

    public static void main(String[] args) {
        // Build a worst-case string: CROSS_LEN chars, half are box-draw positions
        int[] str = new int[CROSS_LEN];
        Arrays.fill(str, 0xA1);  // Kanji-range bytes

        List<Integer> bdlist = new ArrayList<>();
        Set<Integer> bdset = new HashSet<>();
        for (int i = 0; i < CROSS_LEN; i += 2) {
            bdlist.add(i);
            bdset.add(i);
        }

        // Correctness check
        int listResult = convertWithList(str, bdlist);
        int setResult = convertWithSet(str, bdset);
        assert listResult == setResult : "Correctness failed: list=" + listResult + " set=" + setResult;
        System.out.println("Correctness OK: both produce " + listResult + " converted chars");

        // Performance benchmark
        int reps = 5000;

        // Warmup
        for (int i = 0; i < 10; i++) {
            convertWithList(str, bdlist);
            convertWithSet(str, bdset);
        }

        long t0 = System.nanoTime();
        long totalList = 0;
        for (int i = 0; i < reps; i++) totalList += convertWithList(str, bdlist);
        long listNs = System.nanoTime() - t0;

        long t1 = System.nanoTime();
        long totalSet = 0;
        for (int i = 0; i < reps; i++) totalSet += convertWithSet(str, bdset);
        long setNs = System.nanoTime() - t1;

        assert totalList == totalSet : "Result mismatch";

        double ratio = (double) listNs / setNs;
        System.out.printf("DBCS filename conversion CROSS_LEN=%d, bdlist=%d entries (%d reps):%n",
                CROSS_LEN, bdlist.size(), reps);
        System.out.printf("  std::list<uint16_t> linear find: %,d ns%n", listNs);
        System.out.printf("  unordered_set<uint16_t> O(1):    %,d ns%n", setNs);
        System.out.printf("  speedup: %.1fx%n", ratio);

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