import java.util.*;

/**
 * Unit test for tomcat-0001: DefaultServerEndpointConfigurator.getNegotiatedSubprotocol
 * List.contains() O(R×S) → HashSet O(R+S) for WebSocket subprotocol negotiation.
 */
public class Tomcat0001Test {

    // --- BEFORE: O(R×S) linear scan ---
    static String negotiateSubprotocolBefore(List<String> supported, List<String> requested) {
        for (String request : requested) {
            if (supported.contains(request)) {  // O(S) per iteration
                return request;
            }
        }
        return "";
    }

    // --- AFTER: O(R+S) with HashSet ---
    static String negotiateSubprotocolAfter(List<String> supported, List<String> requested) {
        Set<String> supportedSet = new HashSet<>(supported);
        for (String request : requested) {
            if (supportedSet.contains(request)) {  // O(1) per iteration
                return request;
            }
        }
        return "";
    }

    public static void main(String[] args) {
        // Correctness tests
        List<String> supported = Arrays.asList("chat", "superchat", "megachat");
        List<String> requested = Arrays.asList("video", "megachat", "chat");

        String beforeResult = negotiateSubprotocolBefore(supported, requested);
        String afterResult = negotiateSubprotocolAfter(supported, requested);
        assert beforeResult.equals(afterResult) : "Results must match";
        assert "megachat".equals(beforeResult) : "Should find megachat";
        System.out.println("PASS correctness: both return '" + beforeResult + "'");

        // No match
        List<String> noMatch = Arrays.asList("video", "audio");
        assert "".equals(negotiateSubprotocolBefore(supported, noMatch));
        assert "".equals(negotiateSubprotocolAfter(supported, noMatch));
        System.out.println("PASS no-match: both return empty");

        // Performance test: S=500 supported, R=500 requested, worst-case no match
        int S = 500, R = 500;
        List<String> bigSupported = new ArrayList<>();
        for (int i = 0; i < S; i++) bigSupported.add("proto-s-" + i);
        List<String> bigRequested = new ArrayList<>();
        for (int i = 0; i < R; i++) bigRequested.add("proto-r-" + i);  // no overlap

        // Warmup
        for (int i = 0; i < 1000; i++) {
            negotiateSubprotocolBefore(bigSupported, bigRequested);
            negotiateSubprotocolAfter(bigSupported, bigRequested);
        }

        int iterations = 5000;
        long t0 = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            negotiateSubprotocolBefore(bigSupported, bigRequested);
        }
        long beforeNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            negotiateSubprotocolAfter(bigSupported, bigRequested);
        }
        long afterNs = System.nanoTime() - t0;

        double ratio = (double) beforeNs / afterNs;
        System.out.printf("PASS performance: before=%dms after=%dms ratio=%.1fx (S=%d R=%d)%n",
                beforeNs / 1_000_000, afterNs / 1_000_000, ratio, S, R);
        assert ratio > 2.0 : "Expected at least 2x speedup, got " + ratio;
        System.out.println("PASS all tests for tomcat-0001");
    }
}