package unit;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;

/**
 * TerraformDagTest
 *
 * Models three CWE-407 defects across two repos:
 *
 *   TF-001 (HIGH) — internal/dag/tarjan.go inStack()
 *     Defective: inStack iterates s.Stack []Vertex — O(stack-depth) per call.
 *                Called once per edge in stronglyConnected → O(V×E) total.
 *     Fixed:     onStack map[Vertex]bool — O(1) per call.
 *
 *   TF-002 (MEDIUM) — internal/dag/graph.go EdgesTo()
 *     Defective: EdgesTo iterates g.Edges() (all edges) filtering by target
 *                — O(E) per call.  Called inside for-range Vertices() → O(V×E).
 *     Fixed:     upEdges index gives sources for a target directly — O(in-degree).
 *
 *   SALT-001 (MEDIUM) — salt/cloud/__init__.py _has_loop()
 *     Defective: seen is a list; `dep not in seen` is O(depth); list(seen) copy
 *                O(depth) per recursive call → O(V²) total.
 *     Fixed:     seen is a set; `dep not in seen` is O(1); set(seen) copy still
 *                O(depth) but no per-element scan.
 *
 * Operation counts are instrumented explicitly — not wall-clock timing.
 */
public class TerraformDagTest {

    // -----------------------------------------------------------------------
    // TF-001: inStack modelled as ArrayList linear scan vs HashMap O(1) lookup
    // -----------------------------------------------------------------------

    /** Defective Tarjan inStack: iterate ArrayList<String> for membership. */
    static long defectiveInStack(ArrayList<String> stack, String needle) {
        long comparisons = 0;
        for (String n : stack) {
            comparisons++;
            if (n.equals(needle)) {
                return comparisons;   // found — return cost of this call
            }
        }
        return comparisons;           // not found
    }

    /**
     * Simulate running stronglyConnected on a graph with V vertices and E edges.
     * Each edge causes one inStack call; stack size averages V/2 (worst case V).
     * Total comparisons: sum over each edge of (average stack depth).
     */
    static long simulateDefectiveTarjan(int v, int edgesPerVertex) {
        ArrayList<String> stack = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            stack.add("v" + i);   // push all onto stack (worst case)
        }
        long totalComparisons = 0;
        // Each vertex has edgesPerVertex edges; each edge → one inStack call.
        for (int vertex = 0; vertex < v; vertex++) {
            for (int e = 0; e < edgesPerVertex; e++) {
                // needle not in stack in the worst path (scan to end)
                totalComparisons += defectiveInStack(stack, "missing");
            }
        }
        return totalComparisons;
    }

    /** Fixed Tarjan onStack: HashMap<String,Boolean> O(1) lookup. */
    static long simulateFixedTarjan(int v, int edgesPerVertex) {
        HashMap<String, Boolean> onStack = new HashMap<>();
        for (int i = 0; i < v; i++) {
            onStack.put("v" + i, true);
        }
        long lookups = 0;
        for (int vertex = 0; vertex < v; vertex++) {
            for (int e = 0; e < edgesPerVertex; e++) {
                onStack.containsKey("missing");   // O(1)
                lookups++;
            }
        }
        return lookups;
    }

    // -----------------------------------------------------------------------
    // TF-002: EdgesTo modelled as full-edge scan vs upEdges index lookup
    // -----------------------------------------------------------------------

    /** One Edge: source → target (both as integer IDs). */
    static class Edge {
        final int source, target;
        Edge(int source, int target) { this.source = source; this.target = target; }
    }

    /**
     * Defective EdgesTo: iterate all edges and filter by target.
     * Returns comparison count (one per edge inspected).
     */
    static long defectiveEdgesTo(ArrayList<Edge> allEdges, int targetVertex) {
        long comparisons = 0;
        for (Edge e : allEdges) {
            comparisons++;
            // filter logic — result unused, we only count work
            @SuppressWarnings("unused")
            boolean match = (e.target == targetVertex);
        }
        return comparisons;
    }

    /**
     * Fixed EdgesTo: use upEdges index — HashMap<Integer, ArrayList<Integer>>
     * mapping target → list of sources.  Cost: one map lookup + in-degree iterations.
     */
    static long fixedEdgesTo(HashMap<Integer, ArrayList<Integer>> upEdges, int targetVertex) {
        ArrayList<Integer> sources = upEdges.getOrDefault(targetVertex, new ArrayList<>());
        // one lookup + sources.size() edge constructions
        return 1 + sources.size();   // CWE-407 fix cost model: O(1 + in-degree)
    }

    /** Build a graph with v vertices in a chain: 0→1→2→...→(v-1). */
    static ArrayList<Edge> buildAllEdges(int v) {
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < v - 1; i++) {
            edges.add(new Edge(i, i + 1));
        }
        return edges;
    }

    static HashMap<Integer, ArrayList<Integer>> buildUpEdges(int v) {
        HashMap<Integer, ArrayList<Integer>> up = new HashMap<>();
        for (int i = 0; i < v - 1; i++) {
            up.computeIfAbsent(i + 1, k -> new ArrayList<>()).add(i);
        }
        return up;
    }

    // -----------------------------------------------------------------------
    // SALT-001: _has_loop seen modelled as ArrayList vs HashSet membership
    // -----------------------------------------------------------------------

    /**
     * Defective _has_loop: seen is an ArrayList.
     * Counts list-scan comparisons for `val in seen` across depth recursion levels.
     */
    static long defectiveHasLoopMembershipCost(int depth) {
        // Simulate depth recursive calls each doing a linear scan of seen.
        // At call i, seen.size() == i  →  cost i comparisons.
        // Total: 0 + 1 + 2 + ... + (depth-1) = depth*(depth-1)/2
        ArrayList<String> seen = new ArrayList<>();
        long comparisons = 0;
        for (int i = 0; i < depth; i++) {
            String val = "machine" + i;
            // simulate `if val in seen` (miss — val not yet added)
            for (String s : seen) {
                comparisons++;
                if (s.equals(val)) break;
            }
            seen.add(val);
        }
        return comparisons;
    }

    /**
     * Fixed _has_loop: seen is a HashSet.
     * Each membership test is O(1); count one lookup per call.
     */
    static long fixedHasLoopMembershipCost(int depth) {
        HashSet<String> seen = new HashSet<>();
        long lookups = 0;
        for (int i = 0; i < depth; i++) {
            String val = "machine" + i;
            seen.contains(val);   // O(1)
            lookups++;
            seen.add(val);
        }
        return lookups;
    }

    // -----------------------------------------------------------------------
    // Test 1 — TF-001: defective inStack grows O(V×E), fixed is O(E)
    // -----------------------------------------------------------------------

    static void test1_tf001_inStackLinearVsMap() {
        int v1 = 20, v2 = 40;
        int edges = 5;

        long d1 = simulateDefectiveTarjan(v1, edges);
        long d2 = simulateDefectiveTarjan(v2, edges);
        long f1 = simulateFixedTarjan(v1, edges);
        long f2 = simulateFixedTarjan(v2, edges);

        // Defective: comparisons ∝ V² (V vertices × E edges × V stack depth)
        // Doubling V should roughly quadruple defect ops.
        double defectGrowth = (double) d2 / Math.max(1, d1);
        // Fixed: lookups = V × E, linear in V.
        double fixedGrowth  = (double) f2 / Math.max(1, f1);

        System.out.printf("test1 TF-001: v=%d→%d  defect=%d→%d (%.1fx)  fixed=%d→%d (%.1fx)%n",
                v1, v2, d1, d2, defectGrowth, f1, f2, fixedGrowth);

        assert defectGrowth > fixedGrowth
                : "defect growth " + defectGrowth + " should exceed fixed growth " + fixedGrowth;
        assert defectGrowth > 2.0
                : "defect should grow super-linearly on 2x V, got " + defectGrowth;
        assert d1 > f1
                : "defect ops " + d1 + " must exceed fixed ops " + f1 + " at V=" + v1;
    }

    // -----------------------------------------------------------------------
    // Test 2 — TF-001: defect at V=100 is at least 10x more work than fix
    // -----------------------------------------------------------------------

    static void test2_tf001_tenXRatioAtV100() {
        int v = 100, edges = 3;

        long defectOps = simulateDefectiveTarjan(v, edges);
        long fixedOps  = simulateFixedTarjan(v, edges);
        double ratio   = (double) defectOps / Math.max(1, fixedOps);

        System.out.printf("test2 TF-001: v=%d edges=%d  defect=%d  fixed=%d  ratio=%.1fx%n",
                v, edges, defectOps, fixedOps, ratio);

        assert ratio > 10.0
                : "expected defect/fixed ratio > 10x at V=100, got " + ratio;
    }

    // -----------------------------------------------------------------------
    // Test 3 — TF-002: defective EdgesTo O(E) vs fixed O(in-degree)
    // -----------------------------------------------------------------------

    static void test3_tf002_edgesToIndexVsScan() {
        int v = 200;   // chain graph: 199 edges, each vertex has in-degree 1

        ArrayList<Edge> allEdges = buildAllEdges(v);
        HashMap<Integer, ArrayList<Integer>> upEdges = buildUpEdges(v);

        // Query EdgesTo for every vertex — simulates transform_destroy_cbd loop.
        long defectTotal = 0;
        long fixedTotal  = 0;
        for (int vertex = 0; vertex < v; vertex++) {
            defectTotal += defectiveEdgesTo(allEdges, vertex);
            fixedTotal  += fixedEdgesTo(upEdges, vertex);
        }

        double ratio = (double) defectTotal / Math.max(1, fixedTotal);

        System.out.printf("test3 TF-002: V=%d  defect_total=%d  fixed_total=%d  ratio=%.1fx%n",
                v, defectTotal, fixedTotal, ratio);

        // Defect: V calls × E edges scanned = V×(V-1) ≈ V²
        // Fixed:  V calls × (1 + in-degree) ≈ V + E ≈ 2V
        // Ratio ≈ V/2 = 100 for V=200.
        assert defectTotal > fixedTotal
                : "defect total " + defectTotal + " must exceed fixed total " + fixedTotal;
        assert ratio > 10.0
                : "expected ratio > 10x for V=200, got " + ratio;
    }

    // -----------------------------------------------------------------------
    // Test 4 — SALT-001: seen-list O(depth²) vs seen-set O(depth)
    // -----------------------------------------------------------------------

    static void test4_salt001_seenListVsSet() {
        int depth1 = 50;
        int depth2 = 100;  // double the depth

        long d1 = defectiveHasLoopMembershipCost(depth1);
        long d2 = defectiveHasLoopMembershipCost(depth2);
        long f1 = fixedHasLoopMembershipCost(depth1);
        long f2 = fixedHasLoopMembershipCost(depth2);

        double defectGrowth = (double) d2 / Math.max(1, d1);
        double fixedGrowth  = (double) f2 / Math.max(1, f1);

        // Defective: O(depth²) → doubling depth quadruples comparisons
        long expectedDefect50 = (long) depth1 * (depth1 - 1) / 2;

        System.out.printf("test4 SALT-001: depth=%d→%d  defect=%d→%d (%.1fx, expect_d50=%d)  fixed=%d→%d (%.1fx)%n",
                depth1, depth2, d1, d2, defectGrowth, expectedDefect50, f1, f2, fixedGrowth);

        assert d1 == expectedDefect50
                : "defect cost at depth=50 expected " + expectedDefect50 + " got " + d1;
        assert defectGrowth > 2.0
                : "defect should grow super-linearly on 2x depth, got " + defectGrowth;
        assert fixedGrowth <= 2.5
                : "fixed should grow at most linearly on 2x depth, got " + fixedGrowth;
        assert defectGrowth > fixedGrowth
                : "defect growth " + defectGrowth + " should exceed fixed growth " + fixedGrowth;
    }

    // -----------------------------------------------------------------------
    // Test 5 — SALT-001: ratio > 5x at depth=80
    // -----------------------------------------------------------------------

    static void test5_salt001_ratioAtDepth80() {
        int depth = 80;

        long defectOps = defectiveHasLoopMembershipCost(depth);
        long fixedOps  = fixedHasLoopMembershipCost(depth);
        double ratio   = (double) defectOps / Math.max(1, fixedOps);

        // Defect: depth*(depth-1)/2 = 80*79/2 = 3160
        // Fixed:  depth = 80
        // Ratio:  ~39.5x
        long expectedDefect = (long) depth * (depth - 1) / 2;

        System.out.printf("test5 SALT-001: depth=%d  defect=%d (expect=%d)  fixed=%d  ratio=%.1fx%n",
                depth, defectOps, expectedDefect, fixedOps, ratio);

        assert defectOps == expectedDefect
                : "defect comparisons=" + defectOps + " expected=" + expectedDefect;
        assert ratio > 5.0
                : "expected ratio > 5x at depth=80, got " + ratio;
    }

    // -----------------------------------------------------------------------
    // Main
    // -----------------------------------------------------------------------

    public static void main(String[] args) {
        System.out.println("=== TerraformDagTest ===");
        System.out.println("Modelling CWE-407: TF-001 (inStack), TF-002 (EdgesTo), SALT-001 (_has_loop)");
        System.out.println();

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

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

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

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

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

        System.out.println();
        System.out.println("All 5 tests PASSED.");
    }
}