import java.util.*;

/**
 * CWE-407 unit test for dovecot defect.
 *
 * dovecot-0001: mail-storage-hooks.c mail_user_add_plugin_hooks()
 *   array_foreach(&module_hooks, hook) {
 *     array_lsearch(&user->set->mail_plugins, &name, strcmp) // O(P) per hook
 *   }
 *   Fix: pre-sort mail_plugins + array_bsearch → O(H log P)
 */
public class DovecotTest {

    // Simulate linear scan (defect)
    static List<String> addPluginHooksLinear(List<String> moduleHooks,
                                              List<String> mailPlugins) {
        List<String> result = new ArrayList<>();
        for (String hook : moduleHooks) {
            if (mailPlugins.contains(hook)) {   // O(P) linear scan
                result.add(hook);
            }
        }
        return result;
    }

    // Simulate sorted + binary search (fix)
    static List<String> addPluginHooksBinary(List<String> moduleHooks,
                                              List<String> mailPlugins) {
        List<String> sorted = new ArrayList<>(mailPlugins);
        Collections.sort(sorted);                       // sort once O(P log P)

        List<String> result = new ArrayList<>();
        for (String hook : moduleHooks) {
            int idx = Collections.binarySearch(sorted, hook);  // O(log P) per hook
            if (idx >= 0) {
                result.add(hook);
            }
        }
        return result;
    }

    static void testDovecot0001() throws Exception {
        int H = 500;   // module hooks
        int P = 500;   // mail_plugins

        List<String> moduleHooks = new ArrayList<>();
        List<String> mailPlugins = new ArrayList<>();
        for (int i = 0; i < H; i++) moduleHooks.add("hook-" + i);
        // half the hooks are in mail_plugins
        for (int i = 0; i < P / 2; i++) mailPlugins.add("hook-" + i);
        for (int i = P / 2; i < P; i++) mailPlugins.add("plugin-" + i);

        // correctness: both paths must return same hooks
        List<String> rLinear = addPluginHooksLinear(moduleHooks, mailPlugins);
        List<String> rBinary = addPluginHooksBinary(moduleHooks, mailPlugins);
        Collections.sort(rLinear);
        Collections.sort(rBinary);
        assert rLinear.equals(rBinary) : "linear and binary must agree";

        // performance
        long t0 = System.nanoTime();
        for (int r = 0; r < 500; r++) addPluginHooksLinear(moduleHooks, mailPlugins);
        long tLinear = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int r = 0; r < 500; r++) addPluginHooksBinary(moduleHooks, mailPlugins);
        long tBinary = System.nanoTime() - t0;

        double ratio = (double) tLinear / tBinary;
        System.out.printf("dovecot-0001: linear=%.3fs binary=%.3fs ratio=%.1f×%n",
                tLinear / 1e9, tBinary / 1e9, ratio);
        assert ratio > 2 : "Expected >2× speedup, got " + ratio;
        System.out.println("PASS dovecot-0001");
    }

    public static void main(String[] args) throws Exception {
        testDovecot0001();
        System.out.println("ALL PASS");
    }
}