import java.util.*;

/**
 * Unit test for Wekan CWE-407 defect wekan-0001:
 * boards.js setNewLabelOrder uses indexOf() inside sort comparator,
 * resulting in O(L^2 * log L) label reorder.
 * Fix: build a Map for O(1) index lookup, making sort O(L log L).
 *
 * Defect location: models/boards.js setNewLabelOrder()
 * Pattern: newLabelOrderOnlyIds.indexOf(a._id) in sort comparator + every() check
 */
public class WekanBoardLabelSortTest {

    // --- DEFECTIVE: O(L^2 * log L) indexOf in sort comparator ---
    static List<String> sortLabelsDefective(List<String> labels, List<String> newOrder) {
        // Check all labels present in order (O(L^2))
        for (String label : labels) {
            if (newOrder.indexOf(label) < 0) return labels;
        }
        // Sort using indexOf in comparator (O(L^2 * log L))
        List<String> sorted = new ArrayList<>(labels);
        sorted.sort((a, b) -> newOrder.indexOf(a) - newOrder.indexOf(b));
        return sorted;
    }

    // --- FIXED: O(L log L) with Map ---
    static List<String> sortLabelsFixed(List<String> labels, List<String> newOrder) {
        Map<String, Integer> orderMap = new HashMap<>();
        for (int i = 0; i < newOrder.size(); i++) {
            orderMap.put(newOrder.get(i), i);
        }
        // Check all labels present in order (O(L))
        for (String label : labels) {
            if (!orderMap.containsKey(label)) return labels;
        }
        // Sort using Map lookup in comparator (O(L log L))
        List<String> sorted = new ArrayList<>(labels);
        sorted.sort((a, b) -> orderMap.get(a) - orderMap.get(b));
        return sorted;
    }

    public static void main(String[] args) {
        // Correctness test
        List<String> labels = Arrays.asList("LjRBxH", "FvtD34", "PAEgDP", "YJ8sZz");
        List<String> order = Arrays.asList("FvtD34", "PAEgDP", "LjRBxH", "YJ8sZz");
        List<String> rDef = sortLabelsDefective(labels, order);
        List<String> rFix = sortLabelsFixed(labels, order);
        assert rDef.equals(rFix) : "Results must match: " + rDef + " vs " + rFix;
        assert rDef.equals(order) : "Should match new order";
        System.out.println("PASS correctness: " + rFix);

        // Performance test
        int N = 20_000;
        List<String> largeLabels = new ArrayList<>();
        List<String> largeOrder = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            largeLabels.add("label-" + i);
            largeOrder.add("label-" + (N - 1 - i)); // reverse order
        }

        // Warmup
        for (int i = 0; i < 3; i++) {
            sortLabelsDefective(new ArrayList<>(largeLabels), largeOrder);
            sortLabelsFixed(new ArrayList<>(largeLabels), largeOrder);
        }

        long t0 = System.nanoTime();
        List<String> rDefLarge = sortLabelsDefective(new ArrayList<>(largeLabels), largeOrder);
        long t1 = System.nanoTime();
        List<String> rFixLarge = sortLabelsFixed(new ArrayList<>(largeLabels), largeOrder);
        long t2 = System.nanoTime();

        double defMs = (t1 - t0) / 1e6;
        double fixMs = (t2 - t1) / 1e6;
        double ratio = defMs / fixMs;

        assert rDefLarge.equals(rFixLarge) : "Large results must match";
        System.out.printf("PASS defective: %.1f ms, fixed: %.1f ms, ratio: %.1fx%n", defMs, fixMs, ratio);
        assert ratio > 2.0 : "Fixed should be at least 2x faster, got " + ratio + "x";
        System.out.println("PASS performance: ratio " + String.format("%.1f", ratio) + "x");
        System.out.println("ALL TESTS PASSED");
    }
}