package unit;

import java.util.*;

/**
 * Envoy0003Test — CWE-407 unit test for envoy-0003
 *
 * envoy-0003: cluster_manager_impl.cc:1424-1429
 *   EDS batch host merge: std::remove_if with inner std::find over hosts_removed_
 *   vector — O(H × R) per priority level per EDS update.
 *
 *   H = hosts in existing hosts_added_ accumulation
 *   R = hosts in hosts_removed_ for this update
 *
 * SLOW: std::remove_if + inner std::find (O(H) × O(R)) = O(H × R)
 * FAST: build absl::flat_hash_set from hosts_removed_, then O(1) lookup = O(H + R)
 *
 * No JUnit. Run: javac -d . Envoy0003Test.java && java -ea unit.Envoy0003Test
 */
public class Envoy0003Test {

    // -------------------------------------------------------------------------
    // Simulated HostSharedPtr — identity by object reference (pointer semantics)
    // -------------------------------------------------------------------------
    static class Host {
        final int id;
        Host(int id) { this.id = id; }
        // intentionally no equals/hashCode override — identity semantics like raw ptr
    }

    // -------------------------------------------------------------------------
    // SLOW: remove_if with inner std::find — O(H × R)
    // Returns the number of ops (comparisons) performed.
    // -------------------------------------------------------------------------
    static long mergeHosts_slow(List<Host> hostsAdded, List<Host> hostsRemoved) {
        long ops = 0;
        Iterator<Host> it = hostsAdded.iterator();
        while (it.hasNext()) {
            Host candidate = it.next();
            // std::find over hosts_removed: O(R) scan per candidate host
            boolean found = false;
            for (Host r : hostsRemoved) {
                ops++;
                if (r == candidate) {
                    found = true;
                    break;
                }
            }
            if (found) {
                it.remove();
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // FAST: build identity hash set from hostsRemoved, then O(1) lookup
    // Returns the number of ops (comparisons) performed.
    // -------------------------------------------------------------------------
    static long mergeHosts_fast(List<Host> hostsAdded, Set<Host> removedSet) {
        long ops = 0;
        Iterator<Host> it = hostsAdded.iterator();
        while (it.hasNext()) {
            Host candidate = it.next();
            ops++;   // O(1) hash lookup
            if (removedSet.contains(candidate)) {
                it.remove();
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // Helpers
    // -------------------------------------------------------------------------
    static Host[] makeHosts(int n) {
        Host[] hosts = new Host[n];
        for (int i = 0; i < n; i++) hosts[i] = new Host(i);
        return hosts;
    }

    /**
     * Build hostsAdded list and hostsRemoved list from a shared host pool.
     * removeFraction of hostsAdded are also in hostsRemoved (scattered positions).
     */
    static long[] runScenario(int H, int R) {
        Host[] pool = makeHosts(H + R);

        // hostsAdded: first H hosts from pool
        List<Host> hostsAdded_slow = new ArrayList<>(H);
        List<Host> hostsAdded_fast = new ArrayList<>(H);
        for (int i = 0; i < H; i++) {
            hostsAdded_slow.add(pool[i]);
            hostsAdded_fast.add(pool[i]);
        }

        // hostsRemoved: last R hosts from pool; some overlap with hostsAdded
        // (the first min(R,H/2) removed hosts are also in hostsAdded)
        int overlap = Math.min(R, H / 3);
        List<Host> hostsRemoved = new ArrayList<>(R);
        for (int i = 0; i < overlap; i++) hostsRemoved.add(pool[i]);          // overlap with hostsAdded
        for (int i = H; i < H + (R - overlap); i++) hostsRemoved.add(pool[i]); // not in hostsAdded

        // Build identity-based set for fast path
        Set<Host> removedSet = Collections.newSetFromMap(new IdentityHashMap<>());
        removedSet.addAll(hostsRemoved);

        long slowOps = mergeHosts_slow(hostsAdded_slow, hostsRemoved);
        long fastOps = mergeHosts_fast(hostsAdded_fast, removedSet);

        // Verify correctness: both lists should have same remaining size
        assert hostsAdded_slow.size() == hostsAdded_fast.size() :
            "size mismatch: slow=" + hostsAdded_slow.size() + " fast=" + hostsAdded_fast.size();
        // Verify same elements remain (order may differ but sizes must match)
        assert hostsAdded_slow.size() == H - overlap :
            "expected " + (H - overlap) + " remaining, got " + hostsAdded_slow.size();

        return new long[]{slowOps, fastOps};
    }

    static void bench(String label, long sOps, long fOps) {
        double ratio = (double) sOps / Math.max(fOps, 1);
        System.out.printf("  PASS %-55s slow=%8d  fast=%6d  ratio=%6.1fx%n",
                label, sOps, fOps, ratio);
    }

    // -------------------------------------------------------------------------
    // Test cases
    // -------------------------------------------------------------------------

    static void testSmall() {
        long[] r = runScenario(50, 20);
        bench("H=50  R=20  (small cluster deploy)", r[0], r[1]);
        assert r[0] > r[1] * 5 :
            "Expected slow >> fast*5, got slow=" + r[0] + " fast=" + r[1];
    }

    static void testMedium() {
        long[] r = runScenario(200, 100);
        bench("H=200 R=100 (medium cluster rolling restart)", r[0], r[1]);
        assert r[0] > r[1] * 20 :
            "Expected slow >> fast*20, got slow=" + r[0] + " fast=" + r[1];
    }

    static void testLarge() {
        long[] r = runScenario(500, 200);
        bench("H=500 R=200 (large cluster canary deploy)", r[0], r[1]);
        assert r[0] > r[1] * 50 :
            "Expected slow >> fast*50, got slow=" + r[0] + " fast=" + r[1];
    }

    static void testStress() {
        long[] r = runScenario(1000, 500);
        bench("H=1000 R=500 (stress: full rolling restart)", r[0], r[1]);
        assert r[0] > r[1] * 100 :
            "Expected slow >> fast*100, got slow=" + r[0] + " fast=" + r[1];
    }

    static void testCorrectness() {
        // Verify no removal when hostsRemoved is empty
        Host[] pool = makeHosts(5);
        List<Host> added = new ArrayList<>(Arrays.asList(pool));
        long ops = mergeHosts_slow(added, new ArrayList<>());
        assert added.size() == 5 : "expected 5 remaining, got " + added.size();
        assert ops == 0 : "expected 0 ops with empty removed, got " + ops;
        System.out.println("  PASS correctness: empty hostsRemoved => no removal, 0 ops");

        // Verify all removed when all hosts are in removed set
        List<Host> added2 = new ArrayList<>(Arrays.asList(pool));
        List<Host> removed2 = new ArrayList<>(Arrays.asList(pool));
        ops = mergeHosts_slow(added2, removed2);
        assert added2.size() == 0 : "expected 0 remaining, got " + added2.size();
        System.out.println("  PASS correctness: all hosts removed, size=0");
    }

    // -------------------------------------------------------------------------
    // Main
    // -------------------------------------------------------------------------
    public static void main(String[] args) {
        System.out.println("=== Envoy0003Test: EDS host merge linear scan (envoy-0003) ===");
        System.out.println();
        testCorrectness();
        testSmall();
        testMedium();
        testLarge();
        testStress();
        System.out.println();
        System.out.println("5/5 PASS");
    }
}