import java.util.*;

/**
 * CWE-407 unit test for syncthing-0001: deviceFolderFileDownloadState.blockIndexes
 * linear scan O(B) inside per-device per-block availability check.
 *
 * Defect: blockIndexes stored as ArrayList<Integer> (simulating Go []int) with
 *         contains() O(B) lookup called from blockAvailabilityFromTemporary
 *         per device per block. Total: O(D * B^2).
 * Fix:    Replace with HashSet<Integer> for O(1) membership test.
 *
 * File: lib/model/devicedownloadstate.go
 */
public class Syncthing0001Test {

    // --- DEFECTIVE: []int with slices.Contains (linear scan) ---
    static class DefectiveDownloadState {
        private final List<Integer> blockIndexes = new ArrayList<>();

        void addBlocks(List<Integer> indexes) {
            blockIndexes.addAll(indexes);
        }

        boolean has(int index) {
            return blockIndexes.contains(index); // O(B) linear scan
        }
    }

    // --- FIXED: map[int]struct{} (hash set) ---
    static class FixedDownloadState {
        private final Set<Integer> blockIndexes = new HashSet<>();

        void addBlocks(List<Integer> indexes) {
            blockIndexes.addAll(indexes);
        }

        boolean has(int index) {
            return blockIndexes.contains(index); // O(1) hash lookup
        }
    }

    /**
     * Simulate blockAvailabilityFromTemporaryRLocked: for each device,
     * check if a block index exists in the download state.
     * With B blocks and D devices, defective = O(D * B^2), fixed = O(D * B).
     */
    static long benchmarkAvailability(int numBlocks, int numDevices, boolean useFixed) {
        // Build block indexes (simulating progressive download)
        List<Integer> indexes = new ArrayList<>(numBlocks);
        for (int i = 0; i < numBlocks; i++) {
            indexes.add(i);
        }

        // Create per-device download states
        Object[] states;
        if (useFixed) {
            FixedDownloadState[] fs = new FixedDownloadState[numDevices];
            for (int d = 0; d < numDevices; d++) {
                fs[d] = new FixedDownloadState();
                fs[d].addBlocks(indexes);
            }
            states = fs;
        } else {
            DefectiveDownloadState[] ds = new DefectiveDownloadState[numDevices];
            for (int d = 0; d < numDevices; d++) {
                ds[d] = new DefectiveDownloadState();
                ds[d].addBlocks(indexes);
            }
            states = ds;
        }

        // Simulate: for each block we want to pull, check availability across all devices
        long ops = 0;
        long start = System.nanoTime();
        for (int blockIdx = 0; blockIdx < numBlocks; blockIdx++) {
            for (int d = 0; d < numDevices; d++) {
                boolean found;
                if (useFixed) {
                    found = ((FixedDownloadState) states[d]).has(blockIdx);
                } else {
                    found = ((DefectiveDownloadState) states[d]).has(blockIdx);
                }
                if (found) ops++;
            }
        }
        long elapsed = System.nanoTime() - start;

        return elapsed;
    }

    public static void main(String[] args) {
        int B = 1000;  // blocks (realistic: 128MB file / 128KB block size)
        int D = 5;     // devices sharing the folder

        // Warmup
        for (int i = 0; i < 3; i++) {
            benchmarkAvailability(B, D, false);
            benchmarkAvailability(B, D, true);
        }

        // Measure
        long defectiveNs = benchmarkAvailability(B, D, false);
        long fixedNs     = benchmarkAvailability(B, D, true);

        double ratio = (double) defectiveNs / fixedNs;

        System.out.printf("syncthing-0001: deviceDownloadState blockIndexes linear scan%n");
        System.out.printf("  B=%d blocks, D=%d devices%n", B, D);
        System.out.printf("  Defective (ArrayList.contains): %,d ns%n", defectiveNs);
        System.out.printf("  Fixed     (HashSet.contains):   %,d ns%n", fixedNs);
        System.out.printf("  Ratio: %.1fx%n", ratio);

        // Correctness check
        DefectiveDownloadState ds = new DefectiveDownloadState();
        FixedDownloadState fs = new FixedDownloadState();
        List<Integer> testIndexes = Arrays.asList(0, 5, 10, 15, 20);
        ds.addBlocks(testIndexes);
        fs.addBlocks(testIndexes);

        boolean pass = true;
        for (int idx : new int[]{0, 5, 10, 15, 20}) {
            if (!ds.has(idx) || !fs.has(idx)) { pass = false; break; }
        }
        for (int idx : new int[]{1, 6, 11, 16, 21}) {
            if (ds.has(idx) || fs.has(idx)) { pass = false; break; }
        }

        if (!pass) {
            System.out.println("FAIL: correctness check failed");
            System.exit(1);
        }

        if (ratio < 2.0) {
            System.out.println("FAIL: expected ratio >= 2.0, got " + ratio);
            System.exit(1);
        }

        System.out.println("PASS");
    }
}