import java.util.*;

/**
 * Unit test for litellm-0001: ProxyConfig._delete_deployment combined_id_list
 * linear membership test O(R*C) -> O(R) with set.
 *
 * Defect: litellm/proxy/proxy_server.py _delete_deployment() iterates
 * router_model_ids and for each checks `model_id not in combined_id_list`
 * where combined_id_list is a plain Python list. O(R*C) where R = router
 * model count, C = combined list size.
 *
 * Fix: convert combined_id_list to a set before the loop for O(1) lookups.
 */
public class LitellmTest {

    // --- Defective: list membership in loop O(R*C) ---
    static int deleteDeploymentsDefective(List<String> routerModelIds, List<String> combinedIdList) {
        int deleted = 0;
        long ops = 0;
        for (String modelId : routerModelIds) {
            // Linear scan of combinedIdList — O(C) per iteration
            boolean found = false;
            for (String cid : combinedIdList) {
                ops++;
                if (cid.equals(modelId)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                deleted++;
            }
        }
        System.out.println("  defective ops: " + ops);
        return deleted;
    }

    // --- Fixed: set membership in loop O(R) ---
    static int deleteDeploymentsFixed(List<String> routerModelIds, List<String> combinedIdList) {
        int deleted = 0;
        long ops = 0;
        Set<String> combinedIdSet = new HashSet<>(combinedIdList);
        for (String modelId : routerModelIds) {
            ops++;
            if (!combinedIdSet.contains(modelId)) {
                deleted++;
            }
        }
        System.out.println("  fixed ops:     " + ops);
        return deleted;
    }

    public static void main(String[] args) {
        int[] sizes = {50, 200, 500};
        boolean allPass = true;

        for (int N : sizes) {
            System.out.println("N=" + N + " (router models and combined IDs):");

            // Router has N models; combined list has N models (half overlap)
            List<String> routerModelIds = new ArrayList<>();
            List<String> combinedIdList = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                routerModelIds.add("model-" + i);
                // Half overlap: combined has even-indexed models + some extras
                if (i % 2 == 0) {
                    combinedIdList.add("model-" + i);
                } else {
                    combinedIdList.add("extra-" + i);
                }
            }

            int defectiveResult = deleteDeploymentsDefective(routerModelIds, combinedIdList);
            int fixedResult = deleteDeploymentsFixed(routerModelIds, combinedIdList);

            // Results must match
            boolean match = (defectiveResult == fixedResult);
            System.out.println("  deleted: defective=" + defectiveResult + " fixed=" + fixedResult + " match=" + match);

            if (!match) {
                allPass = false;
                System.out.println("  FAIL: results don't match");
            } else {
                System.out.println("  PASS");
            }
        }

        // Op-count ratio check at N=500
        // Defective: ~500 * 250 (avg) = 125,000 ops
        // Fixed: 500 ops
        // Ratio should be >= 50x
        int N = 500;
        List<String> routerIds = new ArrayList<>();
        List<String> combinedIds = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            routerIds.add("model-" + i);
            combinedIds.add("model-" + (i + N / 2)); // partial overlap
        }

        long startDef = System.nanoTime();
        for (int rep = 0; rep < 1000; rep++) {
            deleteDeploymentsDefective(routerIds, combinedIds);
        }
        long defTime = System.nanoTime() - startDef;

        long startFix = System.nanoTime();
        for (int rep = 0; rep < 1000; rep++) {
            deleteDeploymentsFixed(routerIds, combinedIds);
        }
        long fixTime = System.nanoTime() - startFix;

        double ratio = (double) defTime / fixTime;
        System.out.println("\nTiming at N=" + N + ": defective=" + defTime / 1_000_000 + "ms fixed=" + fixTime / 1_000_000 + "ms ratio=" + String.format("%.1f", ratio) + "x");
        boolean ratioPass = ratio >= 5.0;
        System.out.println("Ratio check (>=5x): " + (ratioPass ? "PASS" : "FAIL"));
        if (!ratioPass) allPass = false;

        System.out.println("\n" + (allPass ? "ALL TESTS PASSED" : "SOME TESTS FAILED"));
        System.exit(allPass ? 0 : 1);
    }
}