package unit;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * SPIRV-CROSS-0002: O(n²) access-chain expression tracking — add_implied_read_expression.
 *
 * Models spirv_cross.cpp add_implied_read_expression():
 *   Slow: linear scan of implied_read_expressions vector (std::find).
 *   Fast: unordered_set insert (O(1) dedup).
 *
 * Simulates an access chain of depth D (each level adds one unique read expression).
 */
public class SpirvcrossImpliedReadAlgorithm {

    // ---------------------------------------------------------------
    // SLOW: linear dedup into a list (original code)
    // ---------------------------------------------------------------
    static long addImpliedReadSlow(List<Integer> readExprs, int source) {
        long comparisons = 0;
        boolean found = false;
        for (Integer id : readExprs) {
            comparisons++;
            if (id == source) {
                found = true;
                break;
            }
        }
        if (!found) {
            readExprs.add(source);
        }
        return comparisons;
    }

    /** Simulate an access chain of depth D (all unique IDs — worst case). */
    static long simulateSlow(int depth) {
        List<Integer> readExprs = new ArrayList<>();
        long total = 0;
        for (int i = 0; i < depth; i++) {
            total += addImpliedReadSlow(readExprs, i);
        }
        return total;
    }

    // ---------------------------------------------------------------
    // FAST: unordered_set (patched code)
    // ---------------------------------------------------------------
    static long addImpliedReadFast(Set<Integer> readExprs, int source) {
        readExprs.add(source); // one O(1) op
        return 1;
    }

    static long simulateFast(int depth) {
        Set<Integer> readExprs = new HashSet<>();
        long total = 0;
        for (int i = 0; i < depth; i++) {
            total += addImpliedReadFast(readExprs, i);
        }
        return total;
    }

    // ---------------------------------------------------------------
    // Tests
    // ---------------------------------------------------------------
    static void test(String name, int depth) {
        long slow = simulateSlow(depth);
        long fast = simulateFast(depth);

        // Slow must be O(D²): sum 0+1+...+(D-1) = D*(D-1)/2
        long expectedSlow = (long) depth * (depth - 1) / 2;
        assert slow == expectedSlow :
            name + " slow ops=" + slow + " expected=" + expectedSlow;
        // Fast must be exactly D
        assert fast == depth :
            name + " fast ops=" + fast + " expected=" + depth;

        System.out.printf("  %-30s D=%-4d slow=%5d fast=%4d speedup=%.1fx%n",
                          name, depth, slow, fast, (double) slow / Math.max(fast, 1));
    }

    public static void main(String[] args) {
        int passed = 0;
        int total = 0;

        int[] depths = {4, 8, 16, 32, 64, 128};
        for (int d : depths) {
            total++;
            test("addImpliedRead D=" + d, d);
            passed++;
        }

        // Verify dedup semantics (duplicate IDs should not inflate the set)
        total++;
        {
            List<Integer> slowList = new ArrayList<>();
            Set<Integer> fastSet = new HashSet<>();
            long slowOps = 0;
            long fastOps = 0;
            int[] sequence = {10, 20, 10, 30, 20, 40}; // 3 unique out of 6
            for (int id : sequence) {
                slowOps += addImpliedReadSlow(slowList, id);
                fastOps += addImpliedReadFast(fastSet, id);
            }
            assert slowList.size() == 4 : "slow dedup wrong: " + slowList.size();
            assert fastSet.size() == 4  : "fast dedup wrong: " + fastSet.size();
            assert new HashSet<>(slowList).equals(fastSet) : "sets differ";
            System.out.printf("  %-30s dedup correct: slowList=%s%n", "semantics check", slowList);
            passed++;
        }

        System.out.printf("%n%d/%d PASS%n", passed, total);
    }
}