java-topology/defects/freecad-0004/unit/FreeCadSketchAnalysisTest.java

import java.util.*;

/**
 * Java model of FreeCAD freecad-0004:
 * SketchAnalysis::detectMissingEqualityConstraints O(C * E_eq) list scan
 * vs O(C) hash-map lookup.
 *
 * equalCandidates = list of (geoId_a, geoId_b) pairs for geometries that
 *   could be constrained Equal but are not yet.
 * existingConstraints = list of (geoId_a, geoId_b) Equal constraints already
 *   present in the sketch.
 *
 * Goal: remove from equalCandidates every pair already covered by a constraint.
 * What remains = missing constraints the user should add.
 */
public class FreeCadSketchAnalysisTest {

    record GeoPair(int first, int second) {
        GeoPair canonical() {
            return first <= second ? this : new GeoPair(second, first);
        }
    }

    // --- Defect: O(C * E_eq) std::find_if over list -------------------------

    static List<GeoPair> detectMissingDefect(
            List<GeoPair> candidates, List<GeoPair> existing) {
        List<GeoPair> remaining = new ArrayList<>(candidates);
        for (GeoPair ex : existing) {
            GeoPair key = ex.canonical();
            // find_if: O(remaining.size())
            Iterator<GeoPair> it = remaining.iterator();
            while (it.hasNext()) {
                if (it.next().canonical().equals(key)) {
                    it.remove();
                    break;
                }
            }
        }
        return remaining;
    }

    // --- Fix: O(C) hash-map lookup ------------------------------------------

    static List<GeoPair> detectMissingFixed(
            List<GeoPair> candidates, List<GeoPair> existing) {
        // Build multimap keyed on canonical pair: O(E_eq)
        Map<GeoPair, Deque<GeoPair>> map = new LinkedHashMap<>();
        for (GeoPair c : candidates) {
            map.computeIfAbsent(c.canonical(), k -> new ArrayDeque<>()).add(c);
        }
        // Remove entries covered by existing constraints: O(C)
        for (GeoPair ex : existing) {
            Deque<GeoPair> bucket = map.get(ex.canonical());
            if (bucket != null && !bucket.isEmpty()) bucket.poll();
        }
        // Collect remaining
        List<GeoPair> result = new ArrayList<>();
        for (Deque<GeoPair> bucket : map.values()) result.addAll(bucket);
        return result;
    }

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

    public static void main(String[] args) {
        Random rng = new Random(0);
        for (int M : new int[]{50, 100, 200, 400}) {
            // M identical-length lines → O(M^2) candidates
            List<GeoPair> candidates = new ArrayList<>();
            for (int i = 0; i < M; i++)
                for (int j = i + 1; j < M; j++)
                    candidates.add(new GeoPair(i, j));

            // C = M/2 existing Equal constraints covering random pairs
            int C = M;
            List<GeoPair> existing = new ArrayList<>();
            List<GeoPair> shuffled = new ArrayList<>(candidates);
            Collections.shuffle(shuffled, rng);
            for (int k = 0; k < C && k < shuffled.size(); k++)
                existing.add(shuffled.get(k));

            // warmup
            for (int w = 0; w < 3; w++) {
                detectMissingDefect(candidates, existing);
                detectMissingFixed(candidates, existing);
            }

            int REPS = 10;
            long defectNs = 0, fixedNs = 0;
            for (int r = 0; r < REPS; r++) {
                long t0 = System.nanoTime();
                detectMissingDefect(candidates, existing);
                defectNs += System.nanoTime() - t0;
            }
            for (int r = 0; r < REPS; r++) {
                long t1 = System.nanoTime();
                detectMissingFixed(candidates, existing);
                fixedNs += System.nanoTime() - t1;
            }
            defectNs /= REPS;
            fixedNs  /= REPS;

            List<GeoPair> resD = detectMissingDefect(candidates, existing);
            List<GeoPair> resF = detectMissingFixed(candidates, existing);

            assert resD.size() == resF.size()
                    : "Mismatch: defect=" + resD.size() + " fixed=" + resF.size();

            double ratio = (double) defectNs / Math.max(fixedNs, 1);
            int Eeq = candidates.size();
            System.out.printf(
                "M=%4d  E_eq=%6d  C=%4d  defect=%8dns  fixed=%8dns  ratio=%.1fx%n",
                M, Eeq, C, defectNs, fixedNs, ratio);
        }
        System.out.println("PASS");
    }
}