import java.util.*;

/**
 * CWE-407 unit test for Zabbix zabbix-0002:
 * discoverer_queue_lock() in discoverer_queue.c — O(N²) job ID dedup via
 * zbx_vector_uint64_search linear scan.
 *
 * Defect: While iterating discovery jobs in the queue, the code builds a
 * visited-IDs vector using zbx_vector_uint64_search (linear scan) to detect
 * when we've looped back to a previously-seen job. N jobs × O(N) search = O(N²).
 *
 * Fix: Use a HashSet (zbx_hashset_t in C) for O(1) ID membership check.
 */
public class ZabbixDiscovererQueueDedupTest {

    public static void main(String[] args) {
        int N = 3000; // number of discovery jobs in queue

        // Simulate unique job IDs
        long[] jobIds = new long[N];
        for (int i = 0; i < N; i++) {
            jobIds[i] = i + 1;
        }

        // --- Defective: linear scan of ids vector ---
        List<Long> idsDefective = new ArrayList<>();
        long opsDefective = 0;
        long startDef = System.nanoTime();
        for (long id : jobIds) {
            boolean found = false;
            for (Long existing : idsDefective) {
                opsDefective++;
                if (existing == id) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                idsDefective.add(id);
            }
        }
        long defectiveNs = System.nanoTime() - startDef;

        // --- Fixed: HashSet for O(1) lookup ---
        HashSet<Long> idsFixed = new HashSet<>();
        long opsFixed = 0;
        long startFix = System.nanoTime();
        for (long id : jobIds) {
            opsFixed++;
            if (!idsFixed.contains(id)) {
                idsFixed.add(id);
            }
        }
        long fixedNs = System.nanoTime() - startFix;

        double ratio = (double) opsDefective / Math.max(opsFixed, 1);
        double speedup = (double) defectiveNs / Math.max(fixedNs, 1);

        System.out.println("=== Zabbix zabbix-0002: discoverer queue ID dedup CWE-407 ===");
        System.out.println("Jobs:           " + N);
        System.out.println("Defective ops:  " + opsDefective);
        System.out.println("Fixed ops:      " + opsFixed);
        System.out.println("Op ratio:       " + String.format("%.1fx", ratio));
        System.out.println("Defective time: " + (defectiveNs / 1_000_000) + " ms");
        System.out.println("Fixed time:     " + (fixedNs / 1_000_000) + " ms");
        System.out.println("Speedup:        " + String.format("%.1fx", speedup));

        assert idsFixed.size() == N : "Fixed should have all IDs";
        assert idsDefective.size() == N : "Defective should have all IDs";

        boolean pass = ratio > 5.0;
        System.out.println("RESULT: " + (pass ? "PASS" : "FAIL") +
            " (ratio " + String.format("%.1f", ratio) + "x, threshold 5x)");
        if (!pass) System.exit(1);
    }
}