package unit;

import java.util.*;

/**
 * Standalone unit test for envoy-0004: CWE-407.
 *
 * envoy-0004: sendSettingsHelper — O(S²) linear dedup using std::find_if
 *   during HTTP/2 connection establishment.
 *
 *   slow() simulates the current code: for each setting, scan all already-inserted
 *         settings with std::find_if to check for id collision: O(S²) total.
 *   fast() simulates the fix: use a HashMap<id, value> for O(1) per-insertion
 *         dedup: O(S) total.
 *   Assert: slowOps > fastOps * 10x for S=100 settings.
 *
 * The developer even left a comment in the source:
 *   "Consider using a set as an intermediate data structure, rather than this
 *    ad-hoc deduplication."
 */
public class Envoy0004Test {

    /**
     * Simulates insertParameter with std::find_if (O(S) scan per insertion).
     * Called once per custom_settings_parameters entry.
     */
    static long slowSettingsDedup(int numSettings) {
        long ops = 0;
        List<Integer> settings = new ArrayList<>(numSettings);
        // Simulate custom_settings_parameters with unique IDs 0..numSettings-1
        for (int i = 0; i < numSettings; i++) {
            int id = i; // unique setting ID
            // std::find_if: linear scan over current settings
            boolean found = false;
            for (int existing : settings) {
                ops++;
                if (existing == id) { found = true; break; }
            }
            if (!found) {
                settings.add(id);
            }
        }
        return ops;
    }

    /**
     * Simulates the fix: flat_hash_map<id, value>.emplace() for O(1) dedup.
     */
    static long fastSettingsDedup(int numSettings) {
        long ops = 0;
        Map<Integer, Integer> settingsMap = new HashMap<>(numSettings);
        for (int i = 0; i < numSettings; i++) {
            int id = i;
            ops++; // hash map lookup + insert
            settingsMap.putIfAbsent(id, i);
        }
        return ops;
    }

    public static void main(String[] args) {
        // Test 1: S=100 unique settings
        int S = 100;
        long slow1 = slowSettingsDedup(S);
        long fast1 = fastSettingsDedup(S);
        System.out.printf("Settings dedup S=%d: slow=%d ops, fast=%d ops, ratio=%.1fx%n",
                S, slow1, fast1, (double) slow1 / fast1);
        assert slow1 > fast1 * 10 :
                "Expected slow>fast*10x, got slow=" + slow1 + " fast=" + fast1;

        // Test 2: S=500 unique settings — ratio should scale with S
        int S2 = 500;
        long slow2 = slowSettingsDedup(S2);
        long fast2 = fastSettingsDedup(S2);
        double ratio2 = (double) slow2 / fast2;
        System.out.printf("Settings dedup S=%d: slow=%d ops, fast=%d ops, ratio=%.1fx%n",
                S2, slow2, fast2, ratio2);
        assert ratio2 > 100 : "Expected ratio>100x at S=500, got " + ratio2;

        // Test 3: Complexity — slow should be O(S^2) relative growth vs O(S) fast
        long slow10 = slowSettingsDedup(10);
        long slow100 = slowSettingsDedup(100);
        long fast10 = fastSettingsDedup(10);
        long fast100 = fastSettingsDedup(100);
        // O(S^2): ratio of slow ops should be ~100x when S grows 10x
        double slowComplexityRatio = (double) slow100 / slow10;
        // O(S): ratio of fast ops should be ~10x when S grows 10x
        double fastComplexityRatio = (double) fast100 / fast10;
        System.out.printf("Slow complexity ratio (100 vs 10): %.1fx (expect ~100x for O(S^2))%n",
                slowComplexityRatio);
        System.out.printf("Fast complexity ratio (100 vs 10): %.1fx (expect ~10x for O(S))%n",
                fastComplexityRatio);
        assert slowComplexityRatio > 50 : "Expected O(S^2) scaling, got " + slowComplexityRatio;
        assert fastComplexityRatio < 20 : "Expected O(S) scaling, got " + fastComplexityRatio;

        // Test 4: Verify correctness — both produce the same set of unique settings
        int S4 = 50;
        List<Integer> slowResult = new ArrayList<>();
        for (int i = 0; i < S4; i++) {
            int id = i;
            if (!slowResult.contains(id)) slowResult.add(id);
        }
        Set<Integer> fastResult = new java.util.LinkedHashSet<>();
        for (int i = 0; i < S4; i++) {
            fastResult.add(i);
        }
        assert slowResult.size() == fastResult.size() :
                "Mismatch: slow=" + slowResult.size() + " fast=" + fastResult.size();
        System.out.printf("Correctness: both produce %d unique settings PASS%n", S4);

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