import java.util.*;

/**
 * Unit test for hibernate-orm-0001: InFlightMetadataCollectorImpl
 * .buildRecursiveOrderedFkSecondPasses List.contains() O(N²)
 * → companion HashSet O(N).
 */
public class HibernateOrm0001Test {

    // Simulate FkSecondPass as a simple wrapper
    static class FkSecondPass {
        final String table;
        final String dependentTable;
        FkSecondPass(String table, String dependentTable) {
            this.table = table;
            this.dependentTable = dependentTable;
        }
        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof FkSecondPass)) return false;
            FkSecondPass that = (FkSecondPass) o;
            return table.equals(that.table) && dependentTable.equals(that.dependentTable);
        }
        @Override public int hashCode() {
            return Objects.hash(table, dependentTable);
        }
    }

    // --- BEFORE: O(N²) with List.contains() ---
    static void buildRecursiveBefore(
            List<FkSecondPass> ordered,
            Map<String, Set<FkSecondPass>> deps,
            String startTable, String currentTable) {
        Set<FkSecondPass> dependencies = deps.get(currentTable);
        if (dependencies != null) {
            for (FkSecondPass fk : dependencies) {
                if (!fk.dependentTable.equals(startTable)) {
                    buildRecursiveBefore(ordered, deps, startTable, fk.dependentTable);
                }
                if (!ordered.contains(fk)) {  // O(N) linear scan
                    ordered.add(0, fk);
                }
            }
        }
    }

    // --- AFTER: O(N) with companion HashSet ---
    static void buildRecursiveAfter(
            List<FkSecondPass> ordered,
            Set<FkSecondPass> orderedSet,
            Map<String, Set<FkSecondPass>> deps,
            String startTable, String currentTable) {
        Set<FkSecondPass> dependencies = deps.get(currentTable);
        if (dependencies != null) {
            for (FkSecondPass fk : dependencies) {
                if (!fk.dependentTable.equals(startTable)) {
                    buildRecursiveAfter(ordered, orderedSet, deps, startTable, fk.dependentTable);
                }
                if (!orderedSet.contains(fk)) {  // O(1) lookup
                    orderedSet.add(fk);
                    ordered.add(0, fk);
                }
            }
        }
    }

    public static void main(String[] args) {
        // Build a chain of N tables: t0 → t1 → t2 → ... → tN
        int N = 500;
        Map<String, Set<FkSecondPass>> deps = new HashMap<>();
        for (int i = 0; i < N - 1; i++) {
            String table = "t" + i;
            String depTable = "t" + (i + 1);
            deps.computeIfAbsent(table, k -> new LinkedHashSet<>())
                .add(new FkSecondPass(table, depTable));
        }

        // Correctness
        List<FkSecondPass> beforeList = new ArrayList<>();
        buildRecursiveBefore(beforeList, deps, "t0", "t0");

        List<FkSecondPass> afterList = new ArrayList<>();
        Set<FkSecondPass> afterSet = new HashSet<>();
        buildRecursiveAfter(afterList, afterSet, deps, "t0", "t0");

        assert beforeList.size() == afterList.size() :
            "Size mismatch: " + beforeList.size() + " vs " + afterList.size();
        for (int i = 0; i < beforeList.size(); i++) {
            assert beforeList.get(i).equals(afterList.get(i)) :
                "Mismatch at index " + i;
        }
        System.out.println("PASS correctness: " + beforeList.size() + " FK passes ordered identically");

        // Performance
        int iterations = 200;

        // Warmup
        for (int w = 0; w < 20; w++) {
            List<FkSecondPass> tmp = new ArrayList<>();
            buildRecursiveBefore(tmp, deps, "t0", "t0");
            tmp = new ArrayList<>();
            Set<FkSecondPass> ts = new HashSet<>();
            buildRecursiveAfter(tmp, ts, deps, "t0", "t0");
        }

        long t0 = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            List<FkSecondPass> tmp = new ArrayList<>();
            buildRecursiveBefore(tmp, deps, "t0", "t0");
        }
        long beforeNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            List<FkSecondPass> tmp = new ArrayList<>();
            Set<FkSecondPass> ts = new HashSet<>();
            buildRecursiveAfter(tmp, ts, deps, "t0", "t0");
        }
        long afterNs = System.nanoTime() - t0;

        double ratio = (double) beforeNs / afterNs;
        System.out.printf("PASS performance: before=%dms after=%dms ratio=%.1fx (N=%d)%n",
                beforeNs / 1_000_000, afterNs / 1_000_000, ratio, N);
        assert ratio > 2.0 : "Expected at least 2x speedup, got " + ratio;
        System.out.println("PASS all tests for hibernate-orm-0001");
    }
}