package unit;

import java.util.*;

/**
 * OnosTarjanTest — CWE-407 unit test for ONOS-001.
 *
 * Models the defective and fixed variants of TarjanGraphSearch.SccResult:
 *   - Defective: visited membership via ArrayList.contains()  → O(n) per check
 *   - Fixed:     visited membership via companion HashSet      → O(1) per check
 *
 * An instrumented comparison counter replaces wall-clock timing so results
 * are deterministic and environment-independent.
 *
 * Compile & run:
 *   cd /home/fox/git/java-topology/tests
 *   javac -d . ../defects/onos/unit/OnosTarjanTest.java
 *   java -ea unit.OnosTarjanTest
 */
public class OnosTarjanTest {

    // -----------------------------------------------------------------------
    // Minimal graph model
    // -----------------------------------------------------------------------

    static class Node {
        final int id;
        Node(int id) { this.id = id; }
        @Override public boolean equals(Object o) { return o instanceof Node && ((Node) o).id == id; }
        @Override public int hashCode() { return id; }
        @Override public String toString() { return "N" + id; }
    }

    /** Build a random directed graph with V vertices and approx E edges. */
    static List<int[]> buildGraph(int V, int E, long seed) {
        Random rng = new Random(seed);
        Set<Long> seen = new HashSet<>();
        List<int[]> edges = new ArrayList<>();
        // Ensure the graph is connected enough to exercise the visited-stack path:
        // first add a single directed cycle through all vertices, then random edges.
        for (int i = 0; i < V; i++) {
            int src = i;
            int dst = (i + 1) % V;
            edges.add(new int[]{src, dst});
            seen.add((long) src * V + dst);
        }
        int attempts = 0;
        while (edges.size() < E && attempts < E * 10) {
            attempts++;
            int src = rng.nextInt(V);
            int dst = rng.nextInt(V);
            if (src == dst) continue;
            long key = (long) src * V + dst;
            if (seen.add(key)) {
                edges.add(new int[]{src, dst});
            }
        }
        return edges;
    }

    // -----------------------------------------------------------------------
    // Defective Tarjan — ArrayList.contains() for visited membership
    // -----------------------------------------------------------------------

    static long runDefective(int V, List<int[]> edges) {
        // adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);

        // Tarjan state
        int[] index    = new int[V];
        int[] lowlink  = new int[V];
        boolean[] onStack = new boolean[V];   // separate O(1) flag for SCC pop loop
        boolean[] defined = new boolean[V];
        int[] indexCounter = {0};
        long[] comparisons = {0};

        // visited list = LIFO stack (insertions at head, removals at head)
        List<Integer> visited = new ArrayList<>();

        // iterative Tarjan using an explicit call stack to avoid Java stack overflow
        Deque<int[]> callStack = new ArrayDeque<>(); // [vertex, edgeIndex]
        List<List<Integer>> sccResult = new ArrayList<>();

        for (int start = 0; start < V; start++) {
            if (defined[start]) continue;
            callStack.push(new int[]{start, 0});
            index[start]   = indexCounter[0];
            lowlink[start] = indexCounter[0];
            indexCounter[0]++;
            defined[start] = true;
            visited.add(0, start);
            onStack[start] = true;

            while (!callStack.isEmpty()) {
                int[] frame = callStack.peek();
                int v = frame[0];
                int ei = frame[1];
                List<Integer> neighbors = adj.get(v);

                if (ei < neighbors.size()) {
                    frame[1]++;
                    int w = neighbors.get(ei);

                    if (!defined[w]) {
                        // tree edge — recurse
                        index[w]   = indexCounter[0];
                        lowlink[w] = indexCounter[0];
                        indexCounter[0]++;
                        defined[w] = true;
                        visited.add(0, w);
                        onStack[w] = true;
                        callStack.push(new int[]{w, 0});
                    } else {
                        // cross/back edge — O(n) membership test (the defect)
                        boolean isVisited = false;
                        for (int i = 0; i < visited.size(); i++) {
                            comparisons[0]++;
                            if (visited.get(i).equals(w)) {
                                isVisited = true;
                                break;
                            }
                        }
                        if (isVisited) {
                            lowlink[v] = Math.min(lowlink[v], index[w]);
                        }
                    }
                } else {
                    // done with v's edges — pop
                    callStack.pop();
                    if (!callStack.isEmpty()) {
                        int parent = callStack.peek()[0];
                        lowlink[parent] = Math.min(lowlink[parent], lowlink[v]);
                    }
                    // SCC root check
                    if (lowlink[v] == index[v]) {
                        List<Integer> scc = new ArrayList<>();
                        int w;
                        do {
                            w = visited.remove(0);
                            onStack[w] = false;
                            scc.add(w);
                        } while (w != v);
                        sccResult.add(scc);
                    }
                }
            }
        }

        return comparisons[0];
    }

    // -----------------------------------------------------------------------
    // Fixed Tarjan — companion HashSet for O(1) visited membership
    // -----------------------------------------------------------------------

    static long runFixed(int V, List<int[]> edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);

        int[] index    = new int[V];
        int[] lowlink  = new int[V];
        boolean[] onStack = new boolean[V];
        boolean[] defined = new boolean[V];
        int[] indexCounter = {0};
        long[] comparisons = {0};

        List<Integer> visited    = new ArrayList<>();          // LIFO ordering preserved
        Set<Integer>  visitedSet = new HashSet<>();            // CWE-407 fix: O(1) lookup

        Deque<int[]> callStack = new ArrayDeque<>();
        List<List<Integer>> sccResult = new ArrayList<>();

        for (int start = 0; start < V; start++) {
            if (defined[start]) continue;
            callStack.push(new int[]{start, 0});
            index[start]   = indexCounter[0];
            lowlink[start] = indexCounter[0];
            indexCounter[0]++;
            defined[start] = true;
            visited.add(0, start);
            visitedSet.add(start);                             // CWE-407 fix
            onStack[start] = true;

            while (!callStack.isEmpty()) {
                int[] frame = callStack.peek();
                int v = frame[0];
                int ei = frame[1];
                List<Integer> neighbors = adj.get(v);

                if (ei < neighbors.size()) {
                    frame[1]++;
                    int w = neighbors.get(ei);

                    if (!defined[w]) {
                        index[w]   = indexCounter[0];
                        lowlink[w] = indexCounter[0];
                        indexCounter[0]++;
                        defined[w] = true;
                        visited.add(0, w);
                        visitedSet.add(w);                     // CWE-407 fix
                        onStack[w] = true;
                        callStack.push(new int[]{w, 0});
                    } else {
                        // O(1) membership test — the fix
                        comparisons[0]++;                      // one hash probe = one comparison
                        if (visitedSet.contains(w)) {          // CWE-407 fix
                            lowlink[v] = Math.min(lowlink[v], index[w]);
                        }
                    }
                } else {
                    callStack.pop();
                    if (!callStack.isEmpty()) {
                        int parent = callStack.peek()[0];
                        lowlink[parent] = Math.min(lowlink[parent], lowlink[v]);
                    }
                    if (lowlink[v] == index[v]) {
                        List<Integer> scc = new ArrayList<>();
                        int w;
                        do {
                            w = visited.remove(0);
                            visitedSet.remove(w);              // CWE-407 fix: keep sets in sync
                            onStack[w] = false;
                            scc.add(w);
                        } while (w != v);
                        sccResult.add(scc);
                    }
                }
            }
        }

        return comparisons[0];
    }

    // -----------------------------------------------------------------------
    // Correctness helpers — collect SCC vertex sets for comparison
    // -----------------------------------------------------------------------

    static List<Set<Integer>> sccDefective(int V, List<int[]> edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);

        int[] index    = new int[V];
        int[] lowlink  = new int[V];
        boolean[] defined = new boolean[V];
        int[] counter = {0};

        List<Integer> visited = new ArrayList<>();
        Deque<int[]> callStack = new ArrayDeque<>();
        List<Set<Integer>> result = new ArrayList<>();

        for (int start = 0; start < V; start++) {
            if (defined[start]) continue;
            callStack.push(new int[]{start, 0});
            index[start] = lowlink[start] = counter[0]++;
            defined[start] = true;
            visited.add(0, start);

            while (!callStack.isEmpty()) {
                int[] frame = callStack.peek();
                int v = frame[0];
                List<Integer> neighbors = adj.get(v);
                if (frame[1] < neighbors.size()) {
                    int w = neighbors.get(frame[1]++);
                    if (!defined[w]) {
                        index[w] = lowlink[w] = counter[0]++;
                        defined[w] = true;
                        visited.add(0, w);
                        callStack.push(new int[]{w, 0});
                    } else if (visited.contains(w)) {
                        lowlink[v] = Math.min(lowlink[v], index[w]);
                    }
                } else {
                    callStack.pop();
                    if (!callStack.isEmpty()) {
                        int p = callStack.peek()[0];
                        lowlink[p] = Math.min(lowlink[p], lowlink[v]);
                    }
                    if (lowlink[v] == index[v]) {
                        Set<Integer> scc = new HashSet<>();
                        int w;
                        do { w = visited.remove(0); scc.add(w); } while (w != v);
                        result.add(Collections.unmodifiableSet(scc));
                    }
                }
            }
        }
        return result;
    }

    static List<Set<Integer>> sccFixed(int V, List<int[]> edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);

        int[] index    = new int[V];
        int[] lowlink  = new int[V];
        boolean[] defined = new boolean[V];
        int[] counter = {0};

        List<Integer> visited  = new ArrayList<>();
        Set<Integer> visitedSet = new HashSet<>();
        Deque<int[]> callStack = new ArrayDeque<>();
        List<Set<Integer>> result = new ArrayList<>();

        for (int start = 0; start < V; start++) {
            if (defined[start]) continue;
            callStack.push(new int[]{start, 0});
            index[start] = lowlink[start] = counter[0]++;
            defined[start] = true;
            visited.add(0, start);
            visitedSet.add(start);

            while (!callStack.isEmpty()) {
                int[] frame = callStack.peek();
                int v = frame[0];
                List<Integer> neighbors = adj.get(v);
                if (frame[1] < neighbors.size()) {
                    int w = neighbors.get(frame[1]++);
                    if (!defined[w]) {
                        index[w] = lowlink[w] = counter[0]++;
                        defined[w] = true;
                        visited.add(0, w);
                        visitedSet.add(w);
                        callStack.push(new int[]{w, 0});
                    } else if (visitedSet.contains(w)) {
                        lowlink[v] = Math.min(lowlink[v], index[w]);
                    }
                } else {
                    callStack.pop();
                    if (!callStack.isEmpty()) {
                        int p = callStack.peek()[0];
                        lowlink[p] = Math.min(lowlink[p], lowlink[v]);
                    }
                    if (lowlink[v] == index[v]) {
                        Set<Integer> scc = new HashSet<>();
                        int w;
                        do {
                            w = visited.remove(0);
                            visitedSet.remove(w);
                            scc.add(w);
                        } while (w != v);
                        result.add(Collections.unmodifiableSet(scc));
                    }
                }
            }
        }
        return result;
    }

    // -----------------------------------------------------------------------
    // Test methods
    // -----------------------------------------------------------------------

    static void testDefectiveIsQuadratic() {
        // At scale the defective variant must accumulate substantially more
        // comparisons than edges, demonstrating super-linear growth.
        int V = 200, E = 800;
        List<int[]> edges = buildGraph(V, E, 42L);
        long cmp = runDefective(V, edges);
        // With V=200, E=800 and a dense visited list, comparisons >> E.
        // A purely linear algorithm would score ~E comparisons; quadratic >> that.
        assert cmp > E : "Defective comparisons (" + cmp + ") should exceed edge count (" + E + ")";
        System.out.printf("  testDefectiveIsQuadratic: PASS  (comparisons=%d, edges=%d)%n", cmp, E);
    }

    static void testFixedIsLinear() {
        // Fixed variant: one hash probe per cross/back edge → comparisons ≈ cross-edge count ≤ E.
        int V = 200, E = 800;
        List<int[]> edges = buildGraph(V, E, 42L);
        long cmp = runFixed(V, edges);
        assert cmp <= E : "Fixed comparisons (" + cmp + ") should be <= edge count (" + E + ")";
        System.out.printf("  testFixedIsLinear:        PASS  (comparisons=%d, edges=%d)%n", cmp, E);
    }

    static void testRatioAtScale() {
        // The ratio defective/fixed must be at least 10x at this scale.
        int V = 200, E = 800;
        List<int[]> edges = buildGraph(V, E, 99L);
        long defCmp   = runDefective(V, edges);
        long fixedCmp = runFixed(V, edges);
        double ratio = (double) defCmp / fixedCmp;
        assert ratio >= 10.0 : "Expected ratio >= 10, got " + ratio;
        System.out.printf("  testRatioAtScale:         PASS  (defective=%d, fixed=%d, ratio=%.1fx)%n",
                defCmp, fixedCmp, ratio);
    }

    static void testCorrectnessDefective() {
        // Small deterministic graph: cycle 0→1→2→0, plus cross edge 1→0.
        // Expected SCCs: one SCC containing {0,1,2}.
        int V = 3;
        List<int[]> edges = Arrays.asList(
                new int[]{0, 1}, new int[]{1, 2}, new int[]{2, 0}, new int[]{1, 0});
        List<Set<Integer>> sccs = sccDefective(V, edges);
        assert sccs.size() == 1 : "Expected 1 SCC, got " + sccs.size();
        Set<Integer> scc = sccs.get(0);
        assert scc.contains(0) && scc.contains(1) && scc.contains(2)
                : "SCC should contain {0,1,2}, got " + scc;
        System.out.printf("  testCorrectnessDefective: PASS  (sccs=%d, members=%s)%n", sccs.size(), scc);
    }

    static void testCorrectnessFixed() {
        // Same graph, fixed variant must produce identical result.
        int V = 3;
        List<int[]> edges = Arrays.asList(
                new int[]{0, 1}, new int[]{1, 2}, new int[]{2, 0}, new int[]{1, 0});
        List<Set<Integer>> defSccs   = sccDefective(V, edges);
        List<Set<Integer>> fixedSccs = sccFixed(V, edges);
        assert defSccs.size() == fixedSccs.size()
                : "SCC count mismatch: defective=" + defSccs.size() + " fixed=" + fixedSccs.size();
        // Verify every SCC in defective appears in fixed (order may differ).
        for (Set<Integer> ds : defSccs) {
            assert fixedSccs.contains(ds) : "Missing SCC in fixed result: " + ds;
        }

        // Also verify a larger random graph produces the same SCC partition.
        int V2 = 50, E2 = 150;
        List<int[]> edges2 = buildGraph(V2, E2, 7L);
        List<Set<Integer>> d2 = sccDefective(V2, edges2);
        List<Set<Integer>> f2 = sccFixed(V2, edges2);
        assert d2.size() == f2.size()
                : "Large graph SCC count mismatch: defective=" + d2.size() + " fixed=" + f2.size();
        for (Set<Integer> ds : d2) {
            assert f2.contains(ds) : "Missing SCC in fixed result: " + ds;
        }
        System.out.printf("  testCorrectnessFixed:     PASS  (small sccs=%d, large sccs=%d)%n",
                fixedSccs.size(), f2.size());
    }

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

    public static void main(String[] args) {
        System.out.println("OnosTarjanTest — ONOS-001 CWE-407 unit tests");
        System.out.println("  Graph: V=200, E=800 (dense, seeded random)");
        System.out.println();

        int passed = 0, failed = 0;
        String[] names = {
            "testDefectiveIsQuadratic",
            "testFixedIsLinear",
            "testRatioAtScale",
            "testCorrectnessDefective",
            "testCorrectnessFixed"
        };
        Runnable[] tests = {
            OnosTarjanTest::testDefectiveIsQuadratic,
            OnosTarjanTest::testFixedIsLinear,
            OnosTarjanTest::testRatioAtScale,
            OnosTarjanTest::testCorrectnessDefective,
            OnosTarjanTest::testCorrectnessFixed
        };

        for (int i = 0; i < tests.length; i++) {
            try {
                tests[i].run();
                passed++;
            } catch (AssertionError | RuntimeException e) {
                System.out.printf("  %s: FAIL  (%s)%n", names[i], e.getMessage());
                failed++;
            }
        }

        System.out.println();
        System.out.printf("Results: %d passed, %d failed%n", passed, failed);

        // Print summary ratio using the canonical seed
        int V = 200, E = 800;
        List<int[]> edges = buildGraph(V, E, 42L);
        long defCmp   = runDefective(V, edges);
        long fixedCmp = runFixed(V, edges);
        System.out.printf("Speedup ratio (seed=42): defective=%d comparisons, fixed=%d comparisons, ratio=%.1fx%n",
                defCmp, fixedCmp, (double) defCmp / fixedCmp);

        if (failed > 0) System.exit(1);
    }
}