package unit;
import java.util.*;

/**
 * CWE-407 benchmark for jitsi-videobridge defects:
 *  jitsi-videobridge-0001: Prioritize.kt List.contains() + List.indexOf() O(n²)
 *  jitsi-videobridge-0002: BandwidthAllocator.kt selectedSources getter List.contains() O(n²)
 *  jitsi-videobridge-0003: ConferenceSpeechActivity.java ArrayList.contains() in endpointsChanged O(n²)
 */
public class JitsiVideobridgeTest {

    static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
        // warm up
        slow.run(); fast.run();
        long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
        long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
        double r = fOps > 0 ? (double) sOps / fOps : 0;
        System.out.printf("  %-60s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.0fx%n",
                label, sMs, sOps, fMs, fOps, r);
    }

    // ─────────────────────────────────────────────────────────────────────────
    // jitsi-videobridge-0001: Prioritize.kt contains() + indexOf()
    // ─────────────────────────────────────────────────────────────────────────

    /** Slow: List.contains() inside forEach (O(n²)) */
    static long slowPrioritizeContains(List<String> sources, List<String> selectedNames) {
        long ops = 0;
        List<String> selected = new ArrayList<>();
        List<String> notSelected = new ArrayList<>();
        for (String source : sources) {
            ops++;
            for (String s : selectedNames) { // O(n) scan
                ops++;
                if (s.equals(source)) {
                    selected.add(source);
                    break;
                }
            }
            if (!selectedNames.contains(source)) {
                notSelected.add(source);
            }
        }
        return ops;
    }

    /** Slow: List.indexOf() in sort comparator (called O(n log n) times, each O(n)) */
    static long slowPrioritizeIndexOf(List<String> sources, List<String> selectedNames) {
        long ops = 0;
        List<String> copy = new ArrayList<>(sources);
        // simulate sortBy { selectedNames.indexOf(it) } — O(n log n) comparisons, each O(n)
        copy.sort((a, b) -> {
            // Each indexOf is O(|selectedNames|)
            int ia = selectedNames.indexOf(a);  // O(n)
            int ib = selectedNames.indexOf(b);  // O(n)
            return Integer.compare(ia == -1 ? Integer.MAX_VALUE : ia,
                    ib == -1 ? Integer.MAX_VALUE : ib);
        });
        // count operations: O(n log n * n) comparisons total — approximate by n² for timing
        ops = (long) sources.size() * selectedNames.size();
        return ops;
    }

    /** Fast: HashSet.contains() + pre-built index map (O(n)) */
    static long fastPrioritize(List<String> sources, List<String> selectedNames) {
        long ops = 0;
        Set<String> selectedSet = new HashSet<>(selectedNames);
        Map<String, Integer> selectedIndex = new HashMap<>();
        for (int i = 0; i < selectedNames.size(); i++) {
            selectedIndex.put(selectedNames.get(i), i);
            ops++;
        }
        List<String> selected = new ArrayList<>();
        List<String> notSelected = new ArrayList<>();
        for (String source : sources) {
            ops++;
            if (selectedSet.contains(source)) {
                selected.add(source);
            } else {
                notSelected.add(source);
            }
        }
        selected.sort(Comparator.comparingInt(s -> selectedIndex.getOrDefault(s, Integer.MAX_VALUE)));
        ops += selected.size();
        return ops;
    }

    // ─────────────────────────────────────────────────────────────────────────
    // jitsi-videobridge-0002: BandwidthAllocator selectedSources getter
    // ─────────────────────────────────────────────────────────────────────────

    /** Slow: MutableList.contains() per element — O(n²) dedup */
    static long slowSelectedSourcesGetter(List<String> onStage, List<String> selected) {
        long ops = 0;
        List<String> merged = new ArrayList<>(onStage);
        for (String s : selected) {
            ops++;
            boolean found = false;
            for (String m : merged) { // O(n) scan
                ops++;
                if (m.equals(s)) { found = true; break; }
            }
            if (!found) merged.add(s);
        }
        return ops;
    }

    /** Fast: LinkedHashSet — O(n) dedup preserving order */
    static long fastSelectedSourcesGetter(List<String> onStage, List<String> selected) {
        long ops = 0;
        LinkedHashSet<String> merged = new LinkedHashSet<>(onStage);
        ops += onStage.size();
        for (String s : selected) {
            merged.add(s); // O(1)
            ops++;
        }
        return ops;
    }

    // ─────────────────────────────────────────────────────────────────────────
    // jitsi-videobridge-0003: ConferenceSpeechActivity endpointsChanged
    // ─────────────────────────────────────────────────────────────────────────

    /** Slow: ArrayList.contains() inside for-each loop — O(n²) */
    static long slowEndpointsChanged(List<String> activityList, List<String> conferenceEndpoints) {
        long ops = 0;
        List<String> byActivity = new ArrayList<>(activityList);
        // removeIf with contains on conferenceEndpoints (ArrayList) — O(n) per element
        byActivity.removeIf(ep -> {
            boolean found = false;
            for (String c : conferenceEndpoints) { // O(n) scan
                if (c.equals(ep)) { found = true; break; }
            }
            return !found;
        });
        // for loop with contains on byActivity (ArrayList) — O(n) per element
        for (String ep : conferenceEndpoints) {
            ops++;
            boolean found = false;
            for (String a : byActivity) { // O(n) scan
                ops++;
                if (a.equals(ep)) { found = true; break; }
            }
            if (!found) {
                byActivity.add(ep);
            }
        }
        return ops;
    }

    /** Fast: HashSet for O(1) membership tests */
    static long fastEndpointsChanged(List<String> activityList, List<String> conferenceEndpoints) {
        long ops = 0;
        List<String> byActivity = new ArrayList<>(activityList);
        Set<String> confSet = new HashSet<>(conferenceEndpoints);
        ops += conferenceEndpoints.size();
        // O(n) removeIf with O(1) set lookup
        byActivity.removeIf(ep -> { ops_counter[0]++; return !confSet.contains(ep); });
        // O(1) contains check using Set
        Set<String> activitySet = new LinkedHashSet<>(byActivity);
        ops += byActivity.size();
        for (String ep : conferenceEndpoints) {
            ops++;
            if (!activitySet.contains(ep)) { // O(1)
                byActivity.add(ep);
                activitySet.add(ep);
            }
        }
        return ops;
    }

    // hack for lambda counter
    static long[] ops_counter = new long[1];

    // ─────────────────────────────────────────────────────────────────────────

    public static void main(String[] args) {
        int N = 200; // simulate large conference sources
        int SELECTED = 50;

        // Build source names
        List<String> sources = new ArrayList<>();
        for (int i = 0; i < N; i++) sources.add("source-" + i);

        List<String> selectedNames = new ArrayList<>();
        for (int i = 0; i < SELECTED; i++) selectedNames.add("source-" + i);

        // Mix some selected into onStage to create overlap
        List<String> onStage = new ArrayList<>();
        for (int i = 0; i < SELECTED / 2; i++) onStage.add("source-" + i);
        List<String> selectedSources = new ArrayList<>();
        for (int i = SELECTED / 4; i < SELECTED; i++) selectedSources.add("source-" + i);

        // Activity list: all sources already tracked
        List<String> activityList = new ArrayList<>(sources);
        // Conference: 90% overlap, 10% new
        List<String> conferenceEndpoints = new ArrayList<>();
        for (int i = 0; i < (int)(N * 0.9); i++) conferenceEndpoints.add("source-" + i);
        for (int i = N; i < N + 20; i++) conferenceEndpoints.add("source-" + i);

        System.out.println("=== jitsi-videobridge CWE-407 benchmark ===");
        System.out.printf("  N=%d sources, %d selected%n%n", N, SELECTED);

        // --- 0001 contains ---
        long sOps1a = slowPrioritizeContains(sources, selectedNames);
        long fOps1a = fastPrioritize(sources, selectedNames);
        bench("jvb-0001 Prioritize.contains() [N=" + N + ",sel=" + SELECTED + "]",
                () -> slowPrioritizeContains(sources, selectedNames),
                () -> fastPrioritize(sources, selectedNames),
                sOps1a, fOps1a);

        // --- 0001 indexOf in sort ---
        long sOps1b = slowPrioritizeIndexOf(sources, selectedNames);
        long fOps1b = fastPrioritize(sources, selectedNames);
        bench("jvb-0001 Prioritize.indexOf() in sortBy [N=" + N + ",sel=" + SELECTED + "]",
                () -> slowPrioritizeIndexOf(sources, selectedNames),
                () -> fastPrioritize(sources, selectedNames),
                sOps1b, fOps1b);

        // --- 0002 selectedSources getter ---
        long sOps2 = slowSelectedSourcesGetter(onStage, selectedSources);
        long fOps2 = fastSelectedSourcesGetter(onStage, selectedSources);
        bench("jvb-0002 BandwidthAllocator.selectedSources getter [N=" + SELECTED + "]",
                () -> slowSelectedSourcesGetter(onStage, selectedSources),
                () -> fastSelectedSourcesGetter(onStage, selectedSources),
                sOps2, fOps2);

        // --- 0003 endpointsChanged ---
        ops_counter[0] = 0;
        long sOps3 = slowEndpointsChanged(activityList, conferenceEndpoints);
        ops_counter[0] = 0;
        long fOps3 = fastEndpointsChanged(activityList, conferenceEndpoints);
        bench("jvb-0003 ConferenceSpeechActivity.endpointsChanged [N=" + N + "]",
                () -> slowEndpointsChanged(activityList, conferenceEndpoints),
                () -> fastEndpointsChanged(activityList, conferenceEndpoints),
                sOps3, fOps3);

        System.out.println();

        // Assertions
        int pass = 0, total = 0;

        // 0001-contains: slow scans list for each source → O(N*SELECTED) in worst case (misses),
        // early-exit on hits means actual ops ~= N + SELECTED*(SELECTED/2) for selected hits + N*SELECTED for misses.
        // Simplest check: slow >> fast by at least 10x.
        total++;
        if (sOps1a > fOps1a * 10) {
            System.out.println("  jvb-0001-contains: PASS (slow=" + sOps1a + " > 10x fast=" + fOps1a + ")");
            pass++;
        } else {
            System.out.println("  jvb-0001-contains: FAIL (slow=" + sOps1a + " fast=" + fOps1a + ")");
        }

        // 0001-indexOf: slow >> fast
        total++;
        if (sOps1b > fOps1b * 5) {
            System.out.println("  jvb-0001-indexOf:  PASS (slow=" + sOps1b + " > 5x fast=" + fOps1b + ")");
            pass++;
        } else {
            System.out.println("  jvb-0001-indexOf:  FAIL (slow=" + sOps1b + " fast=" + fOps1b + ")");
        }

        // 0002: slow >= onStage.size * selected.size, fast <= onStage+selected
        total++;
        if (sOps2 > fOps2 * 3) {
            System.out.println("  jvb-0002-getter:   PASS (slow=" + sOps2 + " > 3x fast=" + fOps2 + ")");
            pass++;
        } else {
            System.out.println("  jvb-0002-getter:   FAIL (slow=" + sOps2 + " fast=" + fOps2 + ")");
        }

        // 0003: slow >= N*conf, fast < N + conf
        total++;
        if (sOps3 > fOps3 * 5) {
            System.out.println("  jvb-0003-changed:  PASS (slow=" + sOps3 + " > 5x fast=" + fOps3 + ")");
            pass++;
        } else {
            System.out.println("  jvb-0003-changed:  FAIL (slow=" + sOps3 + " fast=" + fOps3 + ")");
        }

        System.out.println();
        System.out.println(pass + "/" + total + (pass == total ? " PASS" : " FAIL"));
        if (pass != total) System.exit(1);
    }
}