import java.util.*;

/**
 * CWE-407 unit test for Nagios Core nagioscore-0001:
 * find_notification() linked-list linear scan for contact dedup in
 * add_notification() — O(C²) where C = number of notification contacts.
 *
 * Defect: base/notifications.c add_notification() calls find_notification()
 * which walks the entire notification linked list to check for duplicates.
 * Each add is O(N), called N times = O(N²).
 *
 * Fix: Use a HashSet (dkhash_table in C) for O(1) membership check.
 */
public class NagiosCoreNotificationDedupTest {

    // --- DEFECTIVE: linked-list linear scan for dedup ---
    static LinkedList<String> notificationListDefective = new LinkedList<>();

    static boolean findNotificationDefective(String contact) {
        for (String c : notificationListDefective) {
            if (c.equals(contact)) return true;
        }
        return false;
    }

    static int addNotificationDefective(String contact) {
        if (findNotificationDefective(contact)) return 0; // already present
        notificationListDefective.addFirst(contact);
        return 1;
    }

    // --- FIXED: HashSet for O(1) dedup ---
    static LinkedList<String> notificationListFixed = new LinkedList<>();
    static HashSet<String> notificationHashFixed = new HashSet<>();

    static int addNotificationFixed(String contact) {
        if (notificationHashFixed.contains(contact)) return 0;
        notificationListFixed.addFirst(contact);
        notificationHashFixed.add(contact);
        return 1;
    }

    static void reset() {
        notificationListDefective.clear();
        notificationListFixed.clear();
        notificationHashFixed.clear();
    }

    public static void main(String[] args) {
        int C = 2000; // number of contacts

        // Generate unique contact names
        String[] contacts = new String[C];
        for (int i = 0; i < C; i++) {
            contacts[i] = "contact_" + i;
        }

        // --- Defective path ---
        reset();
        long opsDefective = 0;
        long startDef = System.nanoTime();
        for (String contact : contacts) {
            // Linear scan: O(current_size) per add
            for (String c : notificationListDefective) {
                opsDefective++;
                if (c.equals(contact)) break;
            }
            notificationListDefective.addFirst(contact);
        }
        long defectiveNs = System.nanoTime() - startDef;

        // --- Fixed path ---
        reset();
        long opsFixed = 0;
        long startFix = System.nanoTime();
        for (String contact : contacts) {
            opsFixed++; // HashSet.contains is O(1)
            if (!notificationHashFixed.contains(contact)) {
                notificationListFixed.addFirst(contact);
                notificationHashFixed.add(contact);
            }
        }
        long fixedNs = System.nanoTime() - startFix;

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

        System.out.println("=== Nagios Core nagioscore-0001: notification dedup CWE-407 ===");
        System.out.println("Contacts:       " + C);
        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));

        // Verify correctness
        assert notificationListFixed.size() == C : "Fixed list should have all contacts";

        // Verify O(N²) vs O(N)
        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);
    }
}