/**
 * CWE-407 simulation: VLC randomizer_Remove O(N×C) linear scan.
 *
 * Simulates the defect in src/playlist/randomizer.c where
 * randomizer_Remove() calls randomizer_RemoveOne() for each item,
 * which calls randomizer_IndexOf() → vlc_vector_index_of() — a
 * linear scan of the vector. Total: O(N×C), where N = playlist size
 * and C = items to remove. When C ≈ N this is O(N²).
 *
 * Fix: use a HashSet for O(1) lookup → O(N+C) total.
 */
import java.util.*;

public class VlcTest {

    /* --- Defective path: linear scan per removal --- */
    static long removeDefective(ArrayList<Object> playlist, Object[] toRemove) {
        long ops = 0;
        for (Object item : toRemove) {
            // randomizer_IndexOf → vlc_vector_index_of: linear scan
            int idx = -1;
            for (int i = 0; i < playlist.size(); i++) {
                ops++;
                if (playlist.get(i) == item) {
                    idx = i;
                    break;
                }
            }
            if (idx >= 0) {
                playlist.remove(idx);
            }
        }
        return ops;
    }

    /* --- Fixed path: hash set for O(1) membership, single pass --- */
    static long removeFixed(ArrayList<Object> playlist, Object[] toRemove) {
        long ops = 0;
        Set<Object> removeSet = new HashSet<>();
        for (Object item : toRemove) {
            removeSet.add(item);
            ops++; // building the set
        }
        Iterator<Object> it = playlist.iterator();
        while (it.hasNext()) {
            ops++;
            if (removeSet.contains(it.next())) {
                it.remove();
            }
        }
        return ops;
    }

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

        System.out.println("=== VLC randomizer_Remove CWE-407 Test ===");
        System.out.printf("%-8s %-12s %-12s %-8s %-6s%n",
                "N", "Defective", "Fixed", "Ratio", "Pass");

        for (int N : sizes) {
            // Build playlist of N items, remove N/2 items scattered randomly
            Object[] items = new Object[N];
            for (int i = 0; i < N; i++) items[i] = new Object();

            // Remove the last N/2 items (worst case: they are at end of list)
            int removeCount = N / 2;
            Object[] toRemove = new Object[removeCount];
            // Remove items from the second half — they sit at the end,
            // so each indexOf scan traverses ~N items
            System.arraycopy(items, N - removeCount, toRemove, 0, removeCount);

            ArrayList<Object> playlist1 = new ArrayList<>(Arrays.asList(items));
            ArrayList<Object> playlist2 = new ArrayList<>(Arrays.asList(items));

            long opsDefective = removeDefective(playlist1, toRemove);
            long opsFixed = removeFixed(playlist2, toRemove);

            double ratio = (double) opsDefective / opsFixed;
            boolean pass = ratio > 2.0;
            if (!pass) allPass = false;

            System.out.printf("%-8d %-12d %-12d %-8.1fx %-6s%n",
                    N, opsDefective, opsFixed, ratio, pass ? "PASS" : "FAIL");
        }

        System.out.println();
        if (allPass) {
            System.out.println("ALL PASS — defective path is quadratic, fixed path is linear");
        } else {
            System.out.println("FAIL — ratio not demonstrated");
            System.exit(1);
        }
    }
}