import java.net.URI;
import java.net.URISyntaxException;
import java.util.Locale;

public class RootPathQuadraticProof {

    // Original function (kept for optional timing comparison)
    static String getRootPath(String npath, String opath) {
        int index = 0;
        int toindex;

        try {
            npath = new URI(npath).normalize().getPath();
            opath = new URI(opath).normalize().getPath();
        } catch (URISyntaxException e) {
            // ignore
        }

        while (index < opath.length()) {
            toindex = opath.indexOf('/', index + 1);
            if (toindex != -1 && opath.regionMatches(0, npath, 0, toindex + 1)) {
                index = toindex;
            } else {
                return opath.substring(0, index + 1);
            }
        }
        return npath;
    }

    static final class Counter {
        long charComparisons = 0;
    }

    // Character-by-character region match that counts comparisons
    static boolean regionMatchesCount(String a, int aOff, String b, int bOff, int len, Counter c) {
        if (aOff < 0 || bOff < 0) return false;
        if (aOff + len > a.length() || bOff + len > b.length()) return false;

        for (int i = 0; i < len; i++) {
            c.charComparisons++;
            if (a.charAt(aOff + i) != b.charAt(bOff + i)) return false;
        }
        return true;
    }

    // Same logic as getRootPath, but replaces regionMatches with regionMatchesCount
    static String getRootPathCount(String npath, String opath, Counter c) {
        int index = 0;
        int toindex;

        try {
            npath = new URI(npath).normalize().getPath();
            opath = new URI(opath).normalize().getPath();
        } catch (URISyntaxException e) {
            // ignore
        }

        while (index < opath.length()) {
            toindex = opath.indexOf('/', index + 1);
            if (toindex != -1 && regionMatchesCount(opath, 0, npath, 0, toindex + 1, c)) {
                index = toindex;
            } else {
                return opath.substring(0, index + 1);
            }
        }
        return npath;
    }

    // Worst-case style input: many short segments with lots of '/' and identical prefixes
    // Example: "/a/a/a/.../a/"
    static String makeWorstPath(int segments) {
        StringBuilder sb = new StringBuilder(segments * 3);
        for (int i = 0; i < segments; i++) sb.append("/a/");
        return sb.toString();
    }

    // Timing helper (less reliable than counting comparisons, but useful as a secondary signal)
    static long timeNanosPerCall(int iters, String npath, String opath) {
        long t0 = System.nanoTime();
        int sink = 0;
        for (int i = 0; i < iters; i++) {
            sink ^= getRootPath(npath, opath).length();
        }
        long t1 = System.nanoTime();
        if (sink == 42) System.out.println("sink"); // prevent dead-code elimination
        return (t1 - t0) / iters;
    }

    public static void main(String[] args) {
        Locale.setDefault(Locale.ROOT);

        int[] sizes = {200, 400, 800, 1600, 3200, 6400,12800,25600};

        System.out.println("== Quadratic evidence via counted character comparisons ==");
        String h1 = "%10s %10s %18s %14s %14s%n";
        String r1 = "%10d %10d %18d %14.3f %14.9f%n";
        System.out.printf(h1, "segments", "len(n)", "comparisons", "comp/n", "comp/n^2");

        for (int seg : sizes) {
            String opath = makeWorstPath(seg);
            String npath = new String(opath);

            Counter c = new Counter();
            getRootPathCount(npath, opath, c);

            double n = opath.length();
            double comp = c.charComparisons;
            System.out.printf(r1, seg, opath.length(), c.charComparisons, comp / n, comp / (n * n));
        }

        System.out.println();
        System.out.println("== Optional timing (subject to JIT/GC/CPU variability) ==");
        String h2 = "%10s %10s %14s %14s %14s%n";
        String r2 = "%10d %10d %14d %14.3f %14.9f%n";
        System.out.printf(h2, "segments", "len(n)", "avg_ns", "ns/n", "ns/n^2");

        // Warm up for JIT
        for (int i = 0; i < 4000; i++) {
            String p = makeWorstPath(200);
            getRootPath(new String(p), p);
        }

        int iters = 50;
        for (int seg : sizes) {
            String opath = makeWorstPath(seg);
            String npath = new String(opath);

            long avgNs = timeNanosPerCall(iters, npath, opath);
            double n = opath.length();
            System.out.printf(r2, seg, opath.length(), avgNs, avgNs / n, avgNs / (n * n));
        }
    }
}