import java.util.*;

/**
 * Unit test for Squid CWE-407: NotePairs::appendNewOnly O(S*D) linear hasPair scan.
 *
 * Defect: NotePairs::appendNewOnly iterates source entries and calls hasPair()
 * for each one, which does a linear scan of destination entries.
 * Complexity: O(S * D) where S = source entries, D = destination entries.
 * Called per HTTP request in ClientHttpRequest::initRequest() to merge
 * connection annotations into request annotations.
 *
 * Fix: Build a HashSet of existing (name, value) pairs before the loop,
 * reducing hasPair() from O(D) to O(1). Total: O(S + D) instead of O(S * D).
 */
public class SquidNotePairsTest {

    // --- Defective: linear scan per entry ---
    static int hasPairOps = 0;

    static boolean hasPairDefective(List<String[]> entries, String name, String value) {
        for (String[] e : entries) {
            hasPairOps++;
            if (e[0].equals(name) && e[1].equals(value))
                return true;
        }
        return false;
    }

    static void appendNewOnlyDefective(List<String[]> dest, List<String[]> src) {
        for (String[] e : src) {
            if (!hasPairDefective(dest, e[0], e[1]))
                dest.add(new String[]{e[0], e[1]});
        }
    }

    // --- Fixed: set-based lookup ---
    static int fixedOps = 0;

    static void appendNewOnlyFixed(List<String[]> dest, List<String[]> src) {
        Set<String> existing = new HashSet<>();
        for (String[] e : dest) {
            fixedOps++;
            existing.add(e[0] + "\0" + e[1]);
        }
        for (String[] e : src) {
            fixedOps++;
            String key = e[0] + "\0" + e[1];
            if (!existing.contains(key)) {
                dest.add(new String[]{e[0], e[1]});
                existing.add(key);
            }
        }
    }

    public static void main(String[] args) {
        int N = 500; // annotations in destination
        int S = 500; // annotations from source (connection)

        // Build destination entries (existing annotations)
        List<String[]> destDefective = new ArrayList<>();
        for (int i = 0; i < N; i++)
            destDefective.add(new String[]{"key-" + i, "val-" + i});

        // Build source entries (all new, worst case)
        List<String[]> src = new ArrayList<>();
        for (int i = N; i < N + S; i++)
            src.add(new String[]{"key-" + i, "val-" + i});

        List<String[]> destFixed = new ArrayList<>(destDefective);

        // Run defective version
        hasPairOps = 0;
        appendNewOnlyDefective(destDefective, src);
        int defectiveOps = hasPairOps;

        // Run fixed version
        fixedOps = 0;
        appendNewOnlyFixed(destFixed, src);
        int fixedOpsCount = fixedOps;

        double ratio = (double) defectiveOps / fixedOpsCount;

        System.out.println("=== Squid squid-0001: NotePairs::appendNewOnly O(S*D) ===");
        System.out.println("N (dest entries): " + N);
        System.out.println("S (src entries):  " + S);
        System.out.println("Defective ops:    " + defectiveOps);
        System.out.println("Fixed ops:        " + fixedOpsCount);
        System.out.printf("Ratio:            %.1fx%n", ratio);

        // Verify correctness
        assert destDefective.size() == N + S : "Defective: wrong size";
        assert destFixed.size() == N + S : "Fixed: wrong size";

        // Verify ratio shows quadratic vs linear
        assert ratio > 10.0 : "Expected >10x ratio, got " + ratio;

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