import java.util.*;

/**
 * CWE-407 simulation for RawTherapee defects.
 * rawtherapee-0001: BatchQueue cancelItems O(I*Q) linear scan
 *
 * Pattern: for each item in selection (I items), std::find scans entire fd vector (Q entries).
 * After each erase, fd shrinks by 1 — but in the worst case (items at end of fd),
 * each std::find traverses nearly the full vector. Average case: O(I * Q/2).
 *
 * To isolate the membership-test cost from structural erase, we simulate
 * the scan phase only (std::find walk), mirroring the C++ implementation.
 * Fix: build unordered_set from items, then a single remove_if pass over fd.
 */
public class RawTherapeeTest {

    // --- rawtherapee-0001: cancelItems O(I*Q) ---

    /**
     * Defect: for each item to cancel, std::find walks fd until it finds the entry.
     * Items are placed at the END of fd so each scan traverses the full vector.
     * Total ops ~ I * Q (worst case).
     */
    static long cancelItemsDefect(int queueSize, int cancelCount) {
        // fd: indices 0..queueSize-1
        // items to cancel: the LAST cancelCount items (worst case: must scan full vector)
        int[] fd = new int[queueSize];
        for (int i = 0; i < queueSize; i++) fd[i] = i;
        boolean[] removed = new boolean[queueSize];

        // Items to cancel are at positions [queueSize-cancelCount .. queueSize-1]
        int[] toCancel = new int[cancelCount];
        for (int i = 0; i < cancelCount; i++) {
            toCancel[i] = queueSize - cancelCount + i;
        }

        long ops = 0;
        int fdSize = queueSize;
        for (int item : toCancel) {
            // std::find: scan fd from begin until we find 'item'
            for (int j = 0; j < fdSize; j++) {
                if (removed[fd[j]]) continue; // skip already-removed (simulate compacted view)
                ops++;
                if (fd[j] == item) {
                    removed[fd[j]] = true;
                    fdSize--;
                    break;
                }
            }
        }
        return ops;
    }

    /**
     * Fixed: build unordered_set from items O(I), then single remove_if pass O(Q).
     * Total: O(I + Q) operations.
     */
    static long cancelItemsFixed(int queueSize, int cancelCount) {
        Set<Integer> toCancel = new HashSet<>();
        int[] fd = new int[queueSize];
        for (int i = 0; i < queueSize; i++) fd[i] = i;
        for (int i = 0; i < cancelCount; i++) {
            toCancel.add(queueSize - cancelCount + i);
        }

        long ops = 0;
        // Build set: O(I)
        ops += cancelCount;
        // Single pass over fd: O(Q)
        for (int j = 0; j < queueSize; j++) {
            ops++;
            toCancel.contains(fd[j]); // O(1) hash lookup
        }
        return ops;
    }

    public static void main(String[] args) {
        int pass = 0, fail = 0;

        // Test rawtherapee-0001: batch queue Q=1000, cancel I=500 items (worst case: items at end)
        {
            int Q = 1000, I = 500;
            long defectOps = cancelItemsDefect(Q, I);
            long fixedOps = cancelItemsFixed(Q, I);
            double ratio = (double) defectOps / fixedOps;
            boolean ok = ratio > 10.0;
            System.out.printf(
                "rawtherapee-0001 cancelItems Q=%d I=%d: defect=%d fixed=%d ratio=%.1fx %s%n",
                Q, I, defectOps, fixedOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) pass++; else fail++;
        }

        // Test at larger scale: Q=2000, cancel I=1000
        {
            int Q = 2000, I = 1000;
            long defectOps = cancelItemsDefect(Q, I);
            long fixedOps = cancelItemsFixed(Q, I);
            double ratio = (double) defectOps / fixedOps;
            boolean ok = ratio > 50.0;
            System.out.printf(
                "rawtherapee-0001 cancelItems Q=%d I=%d: defect=%d fixed=%d ratio=%.1fx %s%n",
                Q, I, defectOps, fixedOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) pass++; else fail++;
        }

        System.out.printf("%nSummary: %d/%d PASS%n", pass, pass + fail);
        if (fail > 0) System.exit(1);
    }
}