import java.util.*;

/**
 * CWE-407 unit test for terraform-0001: Tarjan SCC inStack linear scan.
 *
 * Defect: sccAcct.inStack() scans the Stack slice linearly O(V) per call.
 * Called from stronglyConnected() for every edge to an already-visited vertex.
 * Total complexity: O(E*V) instead of O(V+E).
 *
 * Fix: maintain a HashSet (map[Vertex]bool in Go) for O(1) membership.
 */
public class TerraformTest {

    static long defectOps;
    static long fixedOps;

    // --- Graph representation ---
    static class Graph {
        int V;
        List<List<Integer>> adj;

        Graph(int V) {
            this.V = V;
            this.adj = new ArrayList<>(V);
            for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        }

        void addEdge(int u, int v) {
            adj.get(u).add(v);
        }
    }

    // --- DEFECTIVE: Tarjan with linear inStack scan ---
    static List<List<Integer>> tarjanDefective(Graph g) {
        int[] index = new int[g.V];
        int[] lowlink = new int[g.V];
        List<Integer> stack = new ArrayList<>();
        List<List<Integer>> sccs = new ArrayList<>();
        int[] nextIndex = {1};
        defectOps = 0;

        for (int v = 0; v < g.V; v++) {
            if (index[v] == 0) {
                strongConnectDefective(g, v, index, lowlink, stack, sccs, nextIndex);
            }
        }
        return sccs;
    }

    static void strongConnectDefective(Graph g, int v, int[] index, int[] lowlink,
                                        List<Integer> stack, List<List<Integer>> sccs,
                                        int[] nextIndex) {
        index[v] = nextIndex[0];
        lowlink[v] = nextIndex[0];
        nextIndex[0]++;
        stack.add(v);

        for (int w : g.adj.get(v)) {
            if (index[w] == 0) {
                strongConnectDefective(g, w, index, lowlink, stack, sccs, nextIndex);
                lowlink[v] = Math.min(lowlink[v], lowlink[w]);
            } else if (inStackLinear(stack, w)) {  // DEFECT: O(|stack|) per edge
                lowlink[v] = Math.min(lowlink[v], index[w]);
            }
        }

        if (lowlink[v] == index[v]) {
            List<Integer> scc = new ArrayList<>();
            int w;
            do {
                w = stack.remove(stack.size() - 1);
                scc.add(w);
            } while (w != v);
            sccs.add(scc);
        }
    }

    /** DEFECT: linear scan of stack -- O(|stack|) per call */
    static boolean inStackLinear(List<Integer> stack, int needle) {
        for (int n : stack) {
            defectOps++;   // count comparisons
            if (n == needle) return true;
        }
        return false;
    }

    // --- FIXED: Tarjan with HashSet for inStack ---
    static List<List<Integer>> tarjanFixed(Graph g) {
        int[] index = new int[g.V];
        int[] lowlink = new int[g.V];
        Set<Integer> inStack = new HashSet<>();
        List<Integer> stack = new ArrayList<>();
        List<List<Integer>> sccs = new ArrayList<>();
        int[] nextIndex = {1};
        fixedOps = 0;

        for (int v = 0; v < g.V; v++) {
            if (index[v] == 0) {
                strongConnectFixed(g, v, index, lowlink, stack, inStack, sccs, nextIndex);
            }
        }
        return sccs;
    }

    static void strongConnectFixed(Graph g, int v, int[] index, int[] lowlink,
                                    List<Integer> stack, Set<Integer> inStack,
                                    List<List<Integer>> sccs, int[] nextIndex) {
        index[v] = nextIndex[0];
        lowlink[v] = nextIndex[0];
        nextIndex[0]++;
        stack.add(v);
        inStack.add(v);

        for (int w : g.adj.get(v)) {
            if (index[w] == 0) {
                strongConnectFixed(g, w, index, lowlink, stack, inStack, sccs, nextIndex);
                lowlink[v] = Math.min(lowlink[v], lowlink[w]);
            } else {
                fixedOps++;   // count HashSet.contains call (O(1))
                if (inStack.contains(w)) {
                    lowlink[v] = Math.min(lowlink[v], index[w]);
                }
            }
        }

        if (lowlink[v] == index[v]) {
            List<Integer> scc = new ArrayList<>();
            int w;
            do {
                w = stack.remove(stack.size() - 1);
                inStack.remove(w);
                scc.add(w);
            } while (w != v);
            sccs.add(scc);
        }
    }

    // --- Build worst-case graph: single large SCC (cycle of V vertices) ---
    static Graph buildLargeSCC(int V) {
        Graph g = new Graph(V);
        for (int i = 0; i < V - 1; i++) {
            g.addEdge(i, i + 1);
        }
        g.addEdge(V - 1, 0); // close the cycle
        // Add cross-edges to increase edge count and inStack pressure
        Random rng = new Random(42);
        for (int i = 0; i < V * 3; i++) {
            int src = rng.nextInt(V);
            int target = rng.nextInt(V);
            if (target != src) g.addEdge(src, target);
        }
        return g;
    }

    public static void main(String[] args) {
        int[] sizes = {500, 1000, 2000};

        System.out.println("terraform-0001: Tarjan SCC inStack linear scan");
        System.out.println("==============================================");
        System.out.printf("%-8s %14s %14s %10s %s%n",
                "V", "Defect(ops)", "Fixed(ops)", "Ratio", "Status");

        boolean allPass = true;

        for (int V : sizes) {
            Graph g = buildLargeSCC(V);

            // Correctness: both must find same number of SCCs
            List<List<Integer>> sccDef = tarjanDefective(g);
            long dOps = defectOps;
            List<List<Integer>> sccFix = tarjanFixed(g);
            long fOps = fixedOps;

            boolean correct = (sccDef.size() == sccFix.size());

            double ratio = (double) dOps / Math.max(fOps, 1);
            // At V=500 with ~2000 edges, defective should do ~250x more ops
            String status = (ratio >= 5.0 && correct) ? "PASS" : "FAIL";
            if (!status.equals("PASS")) allPass = false;

            System.out.printf("%-8d %14d %14d %10.1fx %s%n",
                    V, dOps, fOps, ratio, status);
        }

        System.out.println();
        System.out.println(allPass ? "ALL PASS" : "SOME FAIL");
        System.exit(allPass ? 0 : 1);
    }
}