import java.util.*;

/**
 * Unit test for Tryton CWE-407 defect: _changed_values and _save_values
 * use list.remove(target.id) inside loop over targets, giving O(T*P)
 * where T = number of targets in a one2many/many2many field and
 * P = number of previous targets.
 *
 * Defect locations:
 *   trytond/model/modelview.py   _changed_values()  line ~925-937
 *   trytond/model/modelstorage.py _save_values()     line ~2118-2140
 *
 * Fix: replace list with set for O(1) lookup and discard.
 */
public class TrytonChangedValuesTest {

    // --- DEFECTIVE: previous as List, O(T*P) ---
    static long defectChangedValues(List<Integer> previousIds, List<Integer> targetIds) {
        long ops = 0;
        List<Integer> previous = new ArrayList<>(previousIds);
        for (int targetId : targetIds) {
            // Simulate list.__contains__ scan
            for (int j = 0; j < previous.size(); j++) {
                ops++;
                if (previous.get(j).equals(targetId)) break;
            }
            if (previous.contains(targetId)) {
                previous.remove(Integer.valueOf(targetId));
            }
        }
        return ops;
    }

    // --- FIXED: previous as Set, O(T) amortised ---
    static long fixedChangedValues(List<Integer> previousIds, List<Integer> targetIds) {
        long ops = 0;
        Set<Integer> previous = new HashSet<>(previousIds);
        for (int targetId : targetIds) {
            ops++;  // O(1) hash lookup
            if (previous.contains(targetId)) {
                previous.remove(targetId);
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        int[] sizes = {100, 500, 1000};
        System.out.println("Tryton CWE-407: _changed_values / _save_values previous-list membership");
        System.out.println("T=targets  P=previous  defect_ops  fixed_ops  ratio");

        boolean allPass = true;
        for (int n : sizes) {
            List<Integer> previousIds = new ArrayList<>();
            List<Integer> targetIds = new ArrayList<>();
            // Targets iterate in reverse order so each lookup must scan
            // to the end of the shrinking previous list
            for (int i = 0; i < n; i++) {
                previousIds.add(i);
            }
            for (int i = n - 1; i >= 0; i--) {
                targetIds.add(i);
            }

            long defectOps = defectChangedValues(previousIds, targetIds);
            long fixedOps = fixedChangedValues(previousIds, targetIds);
            double ratio = (double) defectOps / fixedOps;

            System.out.printf("T=%-5d P=%-5d %10d %10d %8.1fx%n",
                    n, n, defectOps, fixedOps, ratio);

            if (ratio < 2.0) {
                System.out.println("FAIL: ratio too low at N=" + n);
                allPass = false;
            }
        }

        // Verify correctness: both produce same remaining set
        List<Integer> prev = Arrays.asList(1, 2, 3, 4, 5);
        List<Integer> tgts = Arrays.asList(2, 4);

        List<Integer> prevList = new ArrayList<>(prev);
        for (int t : tgts) {
            if (prevList.contains(t)) prevList.remove(Integer.valueOf(t));
        }

        Set<Integer> prevSet = new HashSet<>(prev);
        for (int t : tgts) {
            prevSet.remove(t);
        }

        if (!new HashSet<>(prevList).equals(prevSet)) {
            System.out.println("FAIL: correctness mismatch");
            allPass = false;
        }

        System.out.println(allPass ? "PASS" : "FAIL");
        System.exit(allPass ? 0 : 1);
    }
}