/**
 * CWE-407 simulation tests for LibreOffice defects.
 *
 * Each test simulates the defective O(N^2) pattern and the fixed O(N) pattern,
 * measuring operation counts to confirm the quadratic vs linear behavior.
 */
import java.util.*;

public class LibreOfficeTest {

    static int ops;

    // ========================================================================
    // libreoffice-0001: SwWW8WrGrf::Write() graphic dedup O(N^2)
    // ========================================================================

    /** Defective: for each graphic, linear scan backward to find duplicate */
    static Map<Integer, Long> graphicWriteDefective(List<Integer> details) {
        ops = 0;
        Map<Integer, Long> positions = new HashMap<>();
        long streamPos = 0;
        for (int i = 0; i < details.size(); i++) {
            // Linear scan from 0..i-1 looking for match
            int foundIdx = -1;
            for (int j = 0; j < i; j++) {
                ops++;
                if (details.get(j).equals(details.get(i))) {
                    foundIdx = j;
                    break;
                }
            }
            if (foundIdx >= 0) {
                positions.put(i, positions.get(foundIdx));
            } else {
                positions.put(i, streamPos);
                streamPos += 100; // simulate writing graphic data
            }
        }
        return positions;
    }

    /** Fixed: use HashMap for O(1) dedup */
    static Map<Integer, Long> graphicWriteFixed(List<Integer> details) {
        ops = 0;
        Map<Integer, Long> positions = new HashMap<>();
        Map<Integer, Integer> seenMap = new HashMap<>(); // value -> first index
        long streamPos = 0;
        for (int i = 0; i < details.size(); i++) {
            ops++;
            Integer firstIdx = seenMap.get(details.get(i));
            if (firstIdx != null) {
                positions.put(i, positions.get(firstIdx));
            } else {
                seenMap.put(details.get(i), i);
                positions.put(i, streamPos);
                streamPos += 100;
            }
        }
        return positions;
    }

    static void testGraphicWriteDedup() {
        int N = 500;
        List<Integer> details = new ArrayList<>();
        // All unique graphics — worst case for backward scan
        for (int i = 0; i < N; i++) details.add(i);

        graphicWriteDefective(details);
        int defectOps = ops;

        graphicWriteFixed(details);
        int fixedOps = ops;

        double ratio = (double) defectOps / fixedOps;
        System.out.printf("libreoffice-0001 wrtww8gr Write()  N=%d  defect=%d  fixed=%d  ratio=%.1fx%n",
                N, defectOps, fixedOps, ratio);
        assert defectOps > fixedOps * 10 : "Expected >10x ratio, got " + ratio;
        assert ratio > 20 : "Expected >20x ratio for O(N^2) vs O(N)";
    }

    // ========================================================================
    // libreoffice-0002: GroupFilter::match() O(R*I) pivot table filter
    // ========================================================================

    /** Defective: linear scan of items per row */
    static int pivotFilterDefective(int[][] rows, Set<Integer> filterItems) {
        ops = 0;
        List<Integer> itemList = new ArrayList<>(filterItems);
        int matched = 0;
        for (int[] row : rows) {
            // Per-row: check if row value is in filter items via linear scan
            int cellValue = row[0];
            boolean found = false;
            for (int item : itemList) {
                ops++;
                if (item == cellValue) {
                    found = true;
                    break;
                }
            }
            if (found) matched++;
        }
        return matched;
    }

    /** Fixed: HashSet for O(1) membership */
    static int pivotFilterFixed(int[][] rows, Set<Integer> filterItems) {
        ops = 0;
        HashSet<Integer> itemSet = new HashSet<>(filterItems);
        int matched = 0;
        for (int[] row : rows) {
            ops++;
            if (itemSet.contains(row[0])) matched++;
        }
        return matched;
    }

    static void testPivotFilter() {
        int R = 5000, I = 100;
        int[][] rows = new int[R][1];
        Set<Integer> filterItems = new LinkedHashSet<>();
        for (int i = 0; i < I; i++) filterItems.add(i);
        // Rows with values that won't match (worst case for linear scan)
        for (int r = 0; r < R; r++) rows[r][0] = I + r;

        int m1 = pivotFilterDefective(rows, filterItems);
        int defectOps = ops;

        int m2 = pivotFilterFixed(rows, filterItems);
        int fixedOps = ops;

        assert m1 == m2 : "Results must match";
        double ratio = (double) defectOps / fixedOps;
        System.out.printf("libreoffice-0002 GroupFilter::match  R=%d I=%d  defect=%d  fixed=%d  ratio=%.1fx%n",
                R, I, defectOps, fixedOps, ratio);
        assert ratio > 10 : "Expected >10x ratio, got " + ratio;
    }

    // ========================================================================
    // libreoffice-0003: SfxSlotPool group dedup O(F*G)
    // ========================================================================

    /** Defective: for each slot, linear scan of groups vector */
    static List<Integer> slotPoolGroupsDefective(int[] slotGroupIds) {
        ops = 0;
        List<Integer> groups = new ArrayList<>();
        for (int groupId : slotGroupIds) {
            if (groupId == 0) continue; // NONE
            boolean found = false;
            for (int g : groups) {
                ops++;
                if (g == groupId) {
                    found = true;
                    break;
                }
            }
            if (!found) groups.add(groupId);
        }
        return groups;
    }

    /** Fixed: HashSet shadow for O(1) dedup */
    static List<Integer> slotPoolGroupsFixed(int[] slotGroupIds) {
        ops = 0;
        List<Integer> groups = new ArrayList<>();
        Set<Integer> groupSet = new HashSet<>();
        for (int groupId : slotGroupIds) {
            if (groupId == 0) continue;
            ops++;
            if (groupSet.add(groupId)) {
                groups.add(groupId);
            }
        }
        return groups;
    }

    static void testSlotPoolGroups() {
        int F = 500, G = 50;
        // 500 slots spread across 50 groups — each group appears 10 times
        int[] slotGroupIds = new int[F];
        for (int i = 0; i < F; i++) slotGroupIds[i] = (i % G) + 1;

        List<Integer> r1 = slotPoolGroupsDefective(slotGroupIds);
        int defectOps = ops;

        List<Integer> r2 = slotPoolGroupsFixed(slotGroupIds);
        int fixedOps = ops;

        assert r1.size() == r2.size() : "Same number of groups";
        double ratio = (double) defectOps / fixedOps;
        System.out.printf("libreoffice-0003 SfxSlotPool groups  F=%d G=%d  defect=%d  fixed=%d  ratio=%.1fx%n",
                F, G, defectOps, fixedOps, ratio);
        assert ratio > 5 : "Expected >5x ratio, got " + ratio;
    }

    // ========================================================================
    // libreoffice-0004: InsertLine() table line dedup O(L^2)
    // ========================================================================

    /** Defective: std::find in vector per insert */
    static List<Integer> insertLineDefective(int[] lineIds) {
        ops = 0;
        List<Integer> lineArr = new ArrayList<>();
        for (int lineId : lineIds) {
            boolean found = false;
            for (int existing : lineArr) {
                ops++;
                if (existing == lineId) {
                    found = true;
                    break;
                }
            }
            if (!found) lineArr.add(lineId);
        }
        return lineArr;
    }

    /** Fixed: HashSet shadow for O(1) dedup */
    static List<Integer> insertLineFixed(int[] lineIds) {
        ops = 0;
        List<Integer> lineArr = new ArrayList<>();
        Set<Integer> lineSet = new HashSet<>();
        for (int lineId : lineIds) {
            ops++;
            if (lineSet.add(lineId)) {
                lineArr.add(lineId);
            }
        }
        return lineArr;
    }

    // Helper to avoid compilation issues — ArrayList doesn't have push_back
    static { }

    static void testInsertLine() {
        int L = 500;
        // All unique lines — worst case
        int[] lineIds = new int[L];
        for (int i = 0; i < L; i++) lineIds[i] = i;

        // Inline the defective version to avoid the push_back issue
        ops = 0;
        List<Integer> lineArr = new ArrayList<>();
        for (int lineId : lineIds) {
            boolean found = false;
            for (int existing : lineArr) {
                ops++;
                if (existing == lineId) {
                    found = true;
                    break;
                }
            }
            if (!found) lineArr.add(lineId);
        }
        int defectOps = ops;

        insertLineFixed(lineIds);
        int fixedOps = ops;

        double ratio = (double) defectOps / fixedOps;
        System.out.printf("libreoffice-0004 InsertLine  L=%d  defect=%d  fixed=%d  ratio=%.1fx%n",
                L, defectOps, fixedOps, ratio);
        assert ratio > 20 : "Expected >20x ratio, got " + ratio;
    }

    // ========================================================================
    // libreoffice-0005: OutlineView selected paragraphs O(P*S) linear scan
    // ========================================================================

    /** Defective: linear scan of selected list per paragraph */
    static int[] outlineViewDefective(int[] allParas, List<Integer> selectedParas) {
        ops = 0;
        int[] selected = new int[allParas.length];
        for (int i = 0; i < allParas.length; i++) {
            boolean found = false;
            for (int sel : selectedParas) {
                ops++;
                if (sel == allParas[i]) {
                    found = true;
                    break;
                }
            }
            selected[i] = found ? 1 : 0;
        }
        return selected;
    }

    /** Fixed: HashSet for O(1) lookup */
    static int[] outlineViewFixed(int[] allParas, List<Integer> selectedParas) {
        ops = 0;
        Set<Integer> selectedSet = new HashSet<>(selectedParas);
        int[] selected = new int[allParas.length];
        for (int i = 0; i < allParas.length; i++) {
            ops++;
            selected[i] = selectedSet.contains(allParas[i]) ? 1 : 0;
        }
        return selected;
    }

    static void testOutlineView() {
        int P = 500, S = 200;
        int[] allParas = new int[P];
        List<Integer> selectedParas = new ArrayList<>();
        for (int i = 0; i < P; i++) allParas[i] = i;
        // Select every other paragraph — none match in worst-case scan position
        for (int i = P - 1; i >= P - S; i--) selectedParas.add(i);

        outlineViewDefective(allParas, selectedParas);
        int defectOps = ops;

        outlineViewFixed(allParas, selectedParas);
        int fixedOps = ops;

        double ratio = (double) defectOps / fixedOps;
        System.out.printf("libreoffice-0005 OutlineView  P=%d S=%d  defect=%d  fixed=%d  ratio=%.1fx%n",
                P, S, defectOps, fixedOps, ratio);
        assert ratio > 20 : "Expected >20x ratio, got " + ratio;
    }

    // ========================================================================
    // Main
    // ========================================================================

    public static void main(String[] args) {
        testGraphicWriteDedup();
        testPivotFilter();
        testSlotPoolGroups();
        testInsertLine();
        testOutlineView();
        System.out.println("ALL 5 TESTS PASSED");
    }
}