import java.util.*;

/**
 * Java model of FreeCAD freecad-0003: CrossSection::removeDuplicates O(W^2 * E)
 * vs O(W * E log E) with a hash-keyed seen-set.
 *
 * Each "wire" is modelled as a sorted list of long edge-IDs (stand-ins for
 * TopoDS_TShape pointers).  Two wires with the same edge-ID set are duplicates.
 */
public class FreeCadCrossSectionTest {

    // --- Defect: O(W^2 * E) list-based dedup --------------------------------

    static List<List<Long>> removeDuplicatesDefect(List<List<Long>> wires) {
        List<List<Long>> result = new ArrayList<>();
        for (List<Long> wire : wires) {
            boolean dup = false;
            for (List<Long> kept : result) {      // O(W) scan
                if (kept.size() == wire.size()) {
                    boolean same = true;
                    for (int i = 0; i < kept.size(); i++) {  // O(E)
                        if (!kept.get(i).equals(wire.get(i))) { same = false; break; }
                    }
                    if (same) { dup = true; break; }
                }
            }
            if (!dup) result.add(wire);
        }
        return result;
    }

    // --- Fix: O(W * E) hash-keyed seen-set -----------------------------------

    static List<List<Long>> removeDuplicatesFixed(List<List<Long>> wires) {
        Set<List<Long>> seen = new HashSet<>();
        List<List<Long>> result = new ArrayList<>();
        for (List<Long> wire : wires) {
            List<Long> key = new ArrayList<>(wire);
            Collections.sort(key);          // O(E log E) canonical key
            if (seen.add(key))              // O(1) set membership
                result.add(wire);
        }
        return result;
    }

    // --- Benchmark -----------------------------------------------------------

    public static void main(String[] args) {
        Random rng = new Random(42);
        for (int W : new int[]{50, 100, 200, 400}) {
            int E = 8; // edges per wire
            // Build W/2 unique wires, each duplicated once
            List<List<Long>> wires = new ArrayList<>();
            for (int w = 0; w < W / 2; w++) {
                List<Long> wire = new ArrayList<>();
                for (int e = 0; e < E; e++) wire.add((long)(w * 100 + e));
                Collections.sort(wire);
                wires.add(wire);
                wires.add(new ArrayList<>(wire)); // duplicate
            }
            Collections.shuffle(wires, rng);

            long t0 = System.nanoTime();
            List<List<Long>> resD = removeDuplicatesDefect(wires);
            long defectNs = System.nanoTime() - t0;

            long t1 = System.nanoTime();
            List<List<Long>> resF = removeDuplicatesFixed(wires);
            long fixedNs = System.nanoTime() - t1;

            assert resD.size() == resF.size()
                    : "Unique count mismatch: " + resD.size() + " vs " + resF.size();

            double ratio = (double) defectNs / Math.max(fixedNs, 1);
            System.out.printf("W=%4d E=%d  defect=%8dns  fixed=%8dns  ratio=%.1fx%n",
                    W, E, defectNs, fixedNs, ratio);
        }
        System.out.println("PASS");
    }
}