import java.util.*;

/**
 * CWE-407 unit test for calibre-0001: _get_next_series_num_for_list
 * series_indices list membership O(10000 * S) → set membership O(10000 + S)
 *
 * Simulates Calibre's series index "first_free" / "next_free" / "last_free"
 * logic that scans up to 10,000 candidates checking `if i not in series_indices`.
 */
public class CalibreSeriesIndexTest {

    // --- DEFECTIVE: list membership in scan loop ---
    static int firstFreeDefective(List<Integer> seriesIndices) {
        for (int i = 1; i < 10000; i++) {
            if (!seriesIndices.contains(i)) {  // O(S) per iteration
                return i;
            }
        }
        return 10000;
    }

    // --- PATCHED: set membership in scan loop ---
    static int firstFreePatched(List<Integer> seriesIndices) {
        Set<Integer> indexSet = new HashSet<>(seriesIndices);
        for (int i = 1; i < 10000; i++) {
            if (!indexSet.contains(i)) {  // O(1) per iteration
                return i;
            }
        }
        return 10000;
    }

    public static void main(String[] args) {
        // Build a series with S=2000 books using indices 1..S
        int S = 2000;
        List<Integer> seriesIndices = new ArrayList<>();
        for (int i = 1; i <= S; i++) {
            seriesIndices.add(i);
        }

        // Warm up
        for (int w = 0; w < 5; w++) {
            firstFreeDefective(seriesIndices);
            firstFreePatched(seriesIndices);
        }

        // Benchmark defective
        int iterations = 50;
        long startDef = System.nanoTime();
        int resultDef = 0;
        for (int i = 0; i < iterations; i++) {
            resultDef = firstFreeDefective(seriesIndices);
        }
        long defectiveNs = System.nanoTime() - startDef;

        // Benchmark patched
        long startPat = System.nanoTime();
        int resultPat = 0;
        for (int i = 0; i < iterations; i++) {
            resultPat = firstFreePatched(seriesIndices);
        }
        long patchedNs = System.nanoTime() - startPat;

        double ratio = (double) defectiveNs / patchedNs;

        System.out.println("calibre-0001: _get_next_series_num_for_list series index scan");
        System.out.println("S=" + S + " books in series, scanning for first_free");
        System.out.println("Defective result: " + resultDef + "  Patched result: " + resultPat);
        System.out.printf("Defective: %.3f ms%n", defectiveNs / 1e6);
        System.out.printf("Patched:   %.3f ms%n", patchedNs / 1e6);
        System.out.printf("Ratio:     %.1fx%n", ratio);

        // Correctness check
        assert resultDef == resultPat : "Results must match!";
        assert resultDef == S + 1 : "First free should be S+1=" + (S + 1);

        // Performance check
        boolean pass = ratio > 2.0;
        System.out.println(pass ? "PASS" : "FAIL");
        if (!pass) {
            System.exit(1);
        }
    }
}