java-topology/defects/jitsi-meet-0004/unit/VisitorsDeltaTest.java

import java.util.*;

/**
 * Unit test for jitsi-meet-0004: Visitors delta-update list membership O(U*V).
 *
 * Models the TypeScript middleware logic in Java to verify O(1) Map-based
 * delta application vs O(V) Array.findIndex() per update.
 *
 * Defect location:
 *   react/features/visitors/middleware.ts  lines 397-413 (delta updates callback)
 *
 * Compile and run:
 *   javac defects/jitsi-meet-0004/unit/VisitorsDeltaTest.java
 *   java -cp defects/jitsi-meet-0004/unit VisitorsDeltaTest
 */
public class VisitorsDeltaTest {

    static class Visitor {
        String id, name;
        Visitor(String id, String name) { this.id = id; this.name = name; }
    }

    // --- Defective implementation: Array.findIndex() per update ---

    static List<Visitor> applyJoinsArray(List<Visitor> visitors, List<String[]> joins) {
        List<Visitor> result = new ArrayList<>(visitors);
        for (String[] j : joins) {
            String id = j[0], name = j[1];
            int index = -1;
            for (int i = 0; i < result.size(); i++) {  // O(V) per join
                if (result.get(i).id.equals(id)) { index = i; break; }
            }
            if (index == -1) result.add(new Visitor(id, name));
            else result.set(index, new Visitor(id, name));
        }
        return result;
    }

    static List<Visitor> applyLeavesArray(List<Visitor> visitors, List<String> leaves) {
        List<Visitor> result = new ArrayList<>(visitors);
        for (String id : leaves) {
            result.removeIf(v -> v.id.equals(id));  // O(V) per leave
        }
        return result;
    }

    // --- Fixed implementation: Map-based O(1) per update ---

    static List<Visitor> applyJoinsMap(List<Visitor> visitors, List<String[]> joins) {
        Map<String, Visitor> map = new LinkedHashMap<>();
        for (Visitor v : visitors) map.put(v.id, v);
        for (String[] j : joins) map.put(j[0], new Visitor(j[0], j[1]));  // O(1)
        return new ArrayList<>(map.values());
    }

    static List<Visitor> applyLeavesMap(List<Visitor> visitors, List<String> leaves) {
        Map<String, Visitor> map = new LinkedHashMap<>();
        for (Visitor v : visitors) map.put(v.id, v);
        for (String id : leaves) map.remove(id);  // O(1)
        return new ArrayList<>(map.values());
    }

    static void check(boolean cond, String msg) {
        if (!cond) throw new AssertionError("FAIL: " + msg);
    }

    public static void main(String[] args) {
        System.out.println("jitsi-meet-0004: VisitorsDeltaTest");

        // Test 1: Join correctness
        {
            List<Visitor> initial = new ArrayList<>();
            initial.add(new Visitor("v1", "V1"));
            initial.add(new Visitor("v2", "V2"));

            List<String[]> joins = List.of(new String[]{"v3", "V3"}, new String[]{"v1", "V1-updated"});

            List<Visitor> arrayResult = applyJoinsArray(initial, joins);
            List<Visitor> mapResult = applyJoinsMap(initial, joins);

            check(arrayResult.size() == 3, "Array join: expected 3, got " + arrayResult.size());
            check(mapResult.size() == 3, "Map join: expected 3, got " + mapResult.size());
            check(arrayResult.stream().anyMatch(v -> v.id.equals("v3")), "Array: v3 must be present");
            check(mapResult.stream().anyMatch(v -> v.id.equals("v3")), "Map: v3 must be present");
            System.out.println("  PASS test-1: join correctness");
        }

        // Test 2: Leave correctness
        {
            List<Visitor> initial = new ArrayList<>();
            for (int i = 1; i <= 5; i++) initial.add(new Visitor("v" + i, "V" + i));

            List<String> leaves = List.of("v2", "v4");

            List<Visitor> arrayResult = applyLeavesArray(initial, leaves);
            List<Visitor> mapResult = applyLeavesMap(initial, leaves);

            check(arrayResult.size() == 3, "Array leave: expected 3, got " + arrayResult.size());
            check(mapResult.size() == 3, "Map leave: expected 3, got " + mapResult.size());
            check(arrayResult.stream().noneMatch(v -> v.id.equals("v2")), "Array: v2 must be gone");
            check(mapResult.stream().noneMatch(v -> v.id.equals("v2")), "Map: v2 must be gone");
            System.out.println("  PASS test-2: leave correctness");
        }

        // Test 3: Join performance — O(U*V) vs O(U)
        {
            int V = 5_000;
            int U = 1_000;

            List<Visitor> initial = new ArrayList<>();
            for (int i = 0; i < V; i++) initial.add(new Visitor("v" + i, "V" + i));

            List<String[]> joins = new ArrayList<>();
            for (int i = V; i < V + U; i++) joins.add(new String[]{"v" + i, "V" + i});

            long arrayStart = System.nanoTime();
            List<Visitor> arrayResult = applyJoinsArray(initial, joins);
            long arrayTime = System.nanoTime() - arrayStart;

            long mapStart = System.nanoTime();
            List<Visitor> mapResult = applyJoinsMap(initial, joins);
            long mapTime = System.nanoTime() - mapStart;

            check(arrayResult.size() == mapResult.size(),
                "Both must produce same size: " + arrayResult.size() + " vs " + mapResult.size());

            double ratio = (double) arrayTime / mapTime;
            System.out.printf("  PASS test-3: join perf V=%d U=%d | array %,d ns | map %,d ns | %.1fx%n",
                V, U, arrayTime, mapTime, ratio);
            check(mapTime < arrayTime, "Map join must be faster for V=" + V + " U=" + U);
        }

        // Test 4: Leave performance
        {
            int V = 2_000;
            int L = V / 2;

            List<Visitor> initial = new ArrayList<>();
            for (int i = 0; i < V; i++) initial.add(new Visitor("v" + i, "V" + i));

            List<String> leaves = new ArrayList<>();
            for (int i = 0; i < L; i++) leaves.add("v" + i);

            long arrayStart = System.nanoTime();
            List<Visitor> arrayResult = applyLeavesArray(initial, leaves);
            long arrayTime = System.nanoTime() - arrayStart;

            long mapStart = System.nanoTime();
            List<Visitor> mapResult = applyLeavesMap(initial, leaves);
            long mapTime = System.nanoTime() - mapStart;

            check(arrayResult.size() == L, "Array leave: expected " + L + ", got " + arrayResult.size());
            check(mapResult.size() == L, "Map leave: expected " + L + ", got " + mapResult.size());

            double ratio = (double) arrayTime / mapTime;
            System.out.printf("  PASS test-4: leave perf V=%d L=%d | array %,d ns | map %,d ns | %.1fx%n",
                V, L, arrayTime, mapTime, ratio);
            check(mapTime < arrayTime, "Map leave must be faster for V=" + V + " L=" + L);
        }

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