package unit;

import java.util.*;

/**
 * ScipyTest — CWE-407 benchmark for scipy-0001
 *
 * scipy-0001: SHGO.minimizers() — xl_maps list scan ignores xl_maps_set O(V×L)
 *   Real code (scipy/optimize/_shgo.py:1155-1174):
 *     for x in self.HC.V.cache:           # V vertices
 *         for xlmi in self.LMC.xl_maps:   # O(L) list scan
 *             if np.all(np.array(x) == np.array(xlmi)):
 *                 in_LMC = True
 *
 *   xl_maps_set = set() is maintained by LMapCache.add_res() but never used here.
 *
 * Fix: replace list scan with xl_maps_set.contains(tuple(x)) — O(1).
 */
public class ScipyTest {

    /**
     * Simulates SHGO.minimizers() with xl_maps list scan.
     * @param V  vertices in HC.V.cache
     * @param L  local minima already in LMC (xl_maps length)
     * @param I  optimizer iterations
     * @return total comparisons
     */
    static long slowShgoMinimizers(int V, int L, int I) {
        // Build xl_maps as list of "tuples" (represented as Strings here)
        List<String> xlMaps = new ArrayList<>();
        for (int i = 0; i < L; i++) xlMaps.add("min_" + i);

        long ops = 0;
        for (int iter = 0; iter < I; iter++) {
            List<Object> minimizerPool = new ArrayList<>();
            for (int v = 0; v < V; v++) {
                String x = "vertex_" + v;
                boolean inLMC = false;
                // DEFECT: O(L) scan
                for (int k = 0; k < xlMaps.size(); k++) {
                    ops++;
                    if (xlMaps.get(k).startsWith("min_" + (v % L))) {
                        inLMC = true;
                        break;
                    }
                }
                if (inLMC) continue;

                // if minimiser(): check not in pool (also a list)
                boolean isMin = (v % 7 == 0);  // ~14% of vertices are local minima
                if (isMin) {
                    boolean inPool = false;
                    for (int k = 0; k < minimizerPool.size(); k++) {
                        ops++;
                        if (minimizerPool.get(k).equals(x)) { inPool = true; break; }
                    }
                    if (!inPool) minimizerPool.add(x);
                }
            }
        }
        return ops;
    }

    /**
     * Simulates fixed SHGO.minimizers() using xl_maps_set.
     * @return total ops
     */
    static long fastShgoMinimizers(int V, int L, int I) {
        Set<String> xlMapsSet = new HashSet<>();
        for (int i = 0; i < L; i++) xlMapsSet.add("min_" + i);

        long ops = 0;
        for (int iter = 0; iter < I; iter++) {
            List<Object> minimizerPool = new ArrayList<>();
            for (int v = 0; v < V; v++) {
                String x = "vertex_" + v;
                ops++;  // O(1) set probe
                if (xlMapsSet.contains("min_" + (v % L))) continue;

                boolean isMin = (v % 7 == 0);
                if (isMin) minimizerPool.add(x);  // no dedup needed (unique keys)
            }
        }
        return ops;
    }

    static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
        slow.run(); fast.run();
        long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
        long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
        double speedup = fMs > 0 ? (double) sMs / fMs : (double) sOps / fOps;
        System.out.printf("  %-60s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.0fx%n",
                label, sMs, sOps, fMs, fOps, speedup);
    }

    public static void main(String[] args) {
        System.out.println("ScipyTest — scipy-0001: SHGO.minimizers() xl_maps list scan vs xl_maps_set");
        System.out.println();

        System.out.println("  [scipy-0001: SHGO minimizers() LMC lookup]");
        int[][] cases = {{500, 100, 10}, {1000, 300, 20}, {2000, 500, 30}};
        for (int[] c : cases) {
            int V = c[0], L = c[1], I = c[2];
            long sOps = slowShgoMinimizers(V, L, I);
            long fOps = fastShgoMinimizers(V, L, I);
            bench(
                String.format("V=%d vertices, L=%d local-minima, I=%d iters", V, L, I),
                () -> slowShgoMinimizers(V, L, I),
                () -> fastShgoMinimizers(V, L, I),
                sOps, fOps
            );
        }

        System.out.println();

        int pass = 0;

        long s = slowShgoMinimizers(1000, 300, 20);
        long f = fastShgoMinimizers(1000, 300, 20);
        assert s > f * 50 : "scipy-0001 expected >50x ratio; slow=" + s + " fast=" + f;
        pass++;

        System.out.printf("%d/1 PASS%n", pass);
        System.out.printf("scipy-0001: _shgo.SHGO.minimizers() xl_maps list → xl_maps_set O(V×L) → O(V)%n");
        System.out.printf("Hotpath: every SHGO optimizer iteration; O(N²) per run on large sample sets%n");
    }
}