import java.util.*;

/**
 * Java model of KiCad kicad-0003: BOARD_NETLIST_UPDATER::testConnectivity
 * FindPadByNumber O(N*P) list scan vs O(N) hash map lookup.
 *
 * Models: for each component, for each of N pins, call FindPadByNumber which
 * does a linear scan over P pads.
 */
public class KicadNetlistUpdaterTest {

    // --- Defect: O(N * P) linear scan ----------------------------------------

    static int testConnectivityDefect(List<String> pinNames, List<String> padNumbers) {
        int errors = 0;
        for (String pin : pinNames) {
            // FindPadByNumber: O(P) linear scan
            boolean found = false;
            for (String pad : padNumbers) {
                if (pad.equals(pin)) {
                    found = true;
                    break;
                }
            }
            if (!found) errors++;
        }
        return errors;
    }

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

    static int testConnectivityFixed(List<String> pinNames, List<String> padNumbers) {
        // Build pad map once: O(P)
        Set<String> padSet = new HashSet<>(padNumbers);
        int errors = 0;
        for (String pin : pinNames) {
            // O(1) lookup
            if (!padSet.contains(pin)) errors++;
        }
        return errors;
    }

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

    public static void main(String[] args) {
        for (int p : new int[]{64, 128, 256, 512}) {
            List<String> padNumbers = new ArrayList<>();
            List<String> pinNames = new ArrayList<>();
            for (int i = 0; i < p; i++) {
                padNumbers.add(String.valueOf(i + 1));
                pinNames.add(String.valueOf(i + 1));
            }
            // Add a few unknown pins to trigger the error path
            pinNames.add("MISSING_1");
            pinNames.add("MISSING_2");

            int N = pinNames.size();

            long t0 = System.nanoTime();
            int errD = testConnectivityDefect(pinNames, padNumbers);
            long defectNs = System.nanoTime() - t0;

            long t1 = System.nanoTime();
            int errF = testConnectivityFixed(pinNames, padNumbers);
            long fixedNs = System.nanoTime() - t1;

            assert errD == errF : "Error count mismatch";

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