java-topology/defects/jicofo-0001/test/JicofoReinviteParticipantsTest.java

import java.util.*;

/**
 * Unit test for jicofo-0001: reInviteParticipantsById List.contains O(P x R).
 *
 * Simulates finding participants to reinvite using List vs HashSet lookup.
 * Measures op-count ratio to prove O(P x R) vs O(P) overhead.
 */
public class JicofoReinviteParticipantsTest {

    // Stub participant — holds only the endpoint ID we need for the test
    static class StubParticipant {
        private final String endpointId;
        StubParticipant(String id) { this.endpointId = id; }
        String getEndpointId() { return endpointId; }
    }

    // Defective implementation: List.contains() O(R) per participant
    static long reinviteWithList(List<StubParticipant> participants,
                                  List<String> idsToReinvite) {
        long ops = 0;
        int n = idsToReinvite.size();
        List<StubParticipant> result = new ArrayList<>();
        for (StubParticipant p : participants) {
            if (result.size() == n) break;
            for (String id : idsToReinvite) {  // simulates List.contains() scan
                ops++;
                if (id.equals(p.getEndpointId())) {
                    result.add(p);
                    break;
                }
            }
        }
        return ops;
    }

    // Fixed implementation: HashSet.contains() O(1) per participant
    static long reinviteWithSet(List<StubParticipant> participants,
                                 List<String> idsToReinvite) {
        long ops = 0;
        int n = idsToReinvite.size();
        Set<String> idSet = new HashSet<>(idsToReinvite);  // O(R) once
        List<StubParticipant> result = new ArrayList<>();
        for (StubParticipant p : participants) {
            if (result.size() == n) break;
            ops++;
            if (idSet.contains(p.getEndpointId())) {
                result.add(p);
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        // Simulate: 1000-person conference, bridge holding 500 participants fails
        int P = 1000;   // total participants in conference
        int R = 500;    // participants to reinvite (bridge capacity)

        List<StubParticipant> allParticipants = new ArrayList<>();
        for (int i = 0; i < P; i++) {
            allParticipants.add(new StubParticipant("endpoint-" + i));
        }

        // Reinvite first R participants (participants 0..R-1)
        List<String> idsToReinvite = new ArrayList<>();
        for (int i = 0; i < R; i++) {
            idsToReinvite.add("endpoint-" + i);
        }

        long listOps = reinviteWithList(allParticipants, idsToReinvite);
        long setOps  = reinviteWithSet(allParticipants, idsToReinvite);

        System.out.println("=== jicofo-0001 benchmark ===");
        System.out.println("P=" + P + " participants, R=" + R + " to reinvite");
        System.out.println("List ops:    " + listOps);
        System.out.println("HashSet ops: " + setOps);
        System.out.printf("Ratio: %.1fx%n", (double) listOps / setOps);

        // Verify correctness: both methods find the same participants
        Set<String> listResult = new HashSet<>();
        Set<String> setResult  = new HashSet<>();
        int nl = 0, ns = 0;
        for (StubParticipant p : allParticipants) {
            if (idsToReinvite.contains(p.getEndpointId())) { listResult.add(p.getEndpointId()); nl++; }
            if (new HashSet<>(idsToReinvite).contains(p.getEndpointId())) { setResult.add(p.getEndpointId()); ns++; }
        }
        if (!listResult.equals(setResult)) {
            System.err.println("FAIL: result mismatch");
            System.exit(1);
        }

        // Assert: ratio must exceed 50x for this defect to be confirmed
        double ratio = (double) listOps / setOps;
        if (ratio < 50.0) {
            System.err.println("FAIL: expected >50x ratio, got " + ratio);
            System.exit(1);
        }

        System.out.println("PASS: " + ratio + "x overhead confirmed");
    }
}