Complexity Plot

"use client";

import { useState } from "react";
import { Info, TriangleAlert } from "lucide-react";
import { Alert, AlertDescription } from "@/components/ui/alert";
import { formatNs } from "@/registry/hextor/lib/format";
import {
  resolveLabels,
  type ComplexityPlotLabels,
} from "@/registry/hextor/components/hextor/complexity-plot/labels";
import type {
  BigOResult,
  ComplexityClass,
} from "@/registry/hextor/components/hextor/complexity-plot/types";

/**
 * Empirical complexity, plotted log-log.
 *
 * Log-log is not a stylistic choice — it is the same space the fit is performed
 * in. Fitting `t = a·f(n) + b` on absolute times lets the largest n dominate the
 * residuals, which is exactly how a linear algorithm gets mis-called O(n³).
 * In log-log every decade of n contributes equally, and the exponent is just the
 * slope, so what the reader sees is what the model actually did.
 *
 * Form is EMPHASIS, not categorical: the measurement is the subject, the fit and
 * the optimal reference are context. One accent hue plus greys — no palette.
 */

/** Growth functions for drawing a reference curve. Deliberately only the six
 *  classes that are distinguishable over n = 100…100k. */
const GROWTH: Record<ComplexityClass, (n: number) => number> = {
  "O(1)": () => 1,
  "O(log n)": (n) => Math.log2(n),
  "O(n)": (n) => n,
  "O(n log n)": (n) => n * Math.log2(n),
  "O(n^2)": (n) => n * n,
  "O(n^3)": (n) => n * n * n,
};

/**
 * Least-squares fit of `t = a·f(n) + b` over the usable points.
 *
 * The `b` term is not optional. Every measurement carries a fixed cost — call
 * overhead, allocation, the harness itself — and at the small-n end that
 * constant can dominate the signal. Two things go wrong if you ignore it:
 *
 *  - A reference curve anchored through a single small-n point inherits that
 *    point's constant as if it were growth, and lands a decade high.
 *  - A plain log-log regression reads the flattening at small n as a smaller
 *    exponent, so a clean O(n) can measure as slope ≈ 0.6.
 *
 * Fitting both the measured class and the optimal class the same way makes the
 * two curves genuinely comparable: same model family, same freedom, same data.
 */
function fitCurve(
  f: (n: number) => number,
  pts: { n: number; medianNs: number }[],
): { a: number; b: number; at: (n: number) => number } {
  const k = pts.length;
  const xs = pts.map((p) => f(p.n));
  const ys = pts.map((p) => p.medianNs);
  const sx = xs.reduce((s, v) => s + v, 0);
  const sy = ys.reduce((s, v) => s + v, 0);
  const sxx = xs.reduce((s, v) => s + v * v, 0);
  const sxy = xs.reduce((s, v, i) => s + v * ys[i], 0);
  const den = k * sxx - sx * sx;

  // O(1) has zero variance in f(n), so slope is undefined — fall back to the mean.
  if (k < 2 || den === 0) {
    const mean = sy / Math.max(1, k);
    return { a: 0, b: mean, at: () => mean };
  }
  const a = (k * sxy - sx * sy) / den;
  const b = (sy - a * sx) / k;
  return { a, b, at: (n) => Math.max(1, a * f(n) + b) };
}

/**
 * The optimal-class reference curve.
 *
 * Deliberately NOT an independent least-squares fit. Fitting `a·f(n) + b` for a
 * model the data doesn't follow produces a large negative intercept — fit
 * O(n log n) to quadratic data and it goes negative below the measured range,
 * which on a log axis clamps into a vertical wall.
 *
 * Instead the reference inherits the measured fit's constant term `b` and only
 * its growth coefficient is re-solved, pinned to agree at the smallest usable n.
 * That encodes the comparison the reader actually wants: *same fixed overhead,
 * this is how the curve should have bent.* Monotonic by construction.
 */
function referenceCurve(
  fRef: (n: number) => number,
  measured: { a: number; b: number; at: (n: number) => number },
  n0: number,
): (n: number) => number {
  const growthAtN0 = Math.max(1e-9, fRef(n0));
  const aRef = (measured.at(n0) - measured.b) / growthAtN0;
  return (n) => Math.max(1, measured.b + aRef * fRef(n));
}

/** Decade ticks want "1 ms", not "1.00 ms" — the precision is pure noise here. */
function tickLabel(ns: number): string {
  if (ns < 1_000) return `${Math.round(ns)} ns`;
  if (ns < 1_000_000) return `${Math.round(ns / 1_000)} µs`;
  if (ns < 1_000_000_000) return `${Math.round(ns / 1_000_000)} ms`;
  return `${Math.round(ns / 1_000_000_000)} s`;
}

/** "O(n^2)" is how the class is stored on the wire; nobody wants to read that. */
export function prettyComplexity(c: ComplexityClass): string {
  return c.replace("^2", "²").replace("^3", "³");
}

export function ComplexityPlot({
  result,
  labels,
}: {
  result: BigOResult;
  /** Overrides `defaultLabels` (Thai) per-section; pass nothing to keep them. */
  labels?: Partial<ComplexityPlotLabels>;
}) {
  const [hover, setHover] = useState<number | null>(null);
  const copy = resolveLabels(labels);

  if (result.estimated === null) {
    return (
      <Alert>
        <TriangleAlert />
        <AlertDescription>
          <span className="font-medium text-foreground">{copy.inconclusive.heading}</span>
          {" — "}
          {result.inconclusiveReason === "too_few_points"
            ? copy.inconclusive.tooFewPoints
            : copy.inconclusive.lowRSquared(result.rSquared)}
          <br />
          <span className="text-xs">{copy.inconclusive.footnote}</span>
        </AlertDescription>
      </Alert>
    );
  }

  const W = 560;
  const H = 300;
  const M = { top: 16, right: 78, bottom: 34, left: 52 };
  const iw = W - M.left - M.right;
  const ih = H - M.top - M.bottom;

  const used = result.points.filter((p) => p.usedInFit);
  const all = result.points;

  const lx = (n: number) => Math.log10(n);
  const ly = (ns: number) => Math.log10(ns);

  const xMin = lx(Math.min(...all.map((p) => p.n)));
  const xMax = lx(Math.max(...all.map((p) => p.n)));
  const yVals = all.map((p) => ly(p.medianNs));
  const yMin = Math.min(...yVals) - 0.18;
  const yMax = Math.max(...yVals) + 0.18;

  const px = (n: number) => M.left + ((lx(n) - xMin) / (xMax - xMin)) * iw;
  const py = (ns: number) => M.top + ih - ((ly(ns) - yMin) / (yMax - yMin)) * ih;

  const fitPts = used.length >= 2 ? used : all;
  const measured = fitCurve(GROWTH[result.estimated], fitPts);
  const fitAt = measured.at;
  const refAt = referenceCurve(GROWTH[result.optimal], measured, fitPts[0].n);

  const curve = (f: (n: number) => number) => {
    const steps = 48;
    return Array.from({ length: steps + 1 }, (_, i) => {
      const l = xMin + ((xMax - xMin) * i) / steps;
      const n = 10 ** l;
      return `${i === 0 ? "M" : "L"}${px(n)},${py(f(n))}`;
    }).join(" ");
  };

  const isOptimal = result.estimated === result.optimal;
  const hovered = hover !== null ? all[hover] : null;

  return (
    <div className="space-y-2">
      <div className="flex flex-wrap items-baseline gap-x-3 gap-y-1">
        <span className="font-mono text-lg font-semibold">
          {prettyComplexity(result.estimated)}
        </span>
        <span className="tnum text-xs text-muted-foreground">
          R² {result.rSquared.toFixed(3)} · {fitPts.length} {copy.pointsSuffix}
        </span>
        <span
          className="ml-auto rounded-full px-2 py-0.5 text-[11px] font-medium"
          style={{
            background: isOptimal ? "color-mix(in oklab, var(--verdict-pass) 16%, transparent)" : "color-mix(in oklab, var(--verdict-warn) 16%, transparent)",
            color: isOptimal ? "var(--verdict-pass)" : "var(--verdict-warn)",
          }}
        >
          {isOptimal ? `✓ optimal` : copy.referenceAchieves(prettyComplexity(result.optimal))}
        </span>
      </div>

      <div className="relative">
        <svg
          viewBox={`0 0 ${W} ${H}`}
          className="w-full overflow-visible"
          role="img"
          aria-label={`Log-log plot of runtime against input size. Measured complexity ${prettyComplexity(result.estimated)}, optimal ${prettyComplexity(result.optimal)}.`}
        >
          {/* grid + x ticks at the measured n values */}
          {all.map((p) => (
            <g key={`gx-${p.n}`}>
              <line
                x1={px(p.n)}
                y1={M.top}
                x2={px(p.n)}
                y2={M.top + ih}
                stroke="var(--viz-grid)"
                strokeWidth={1}
              />
              <text
                x={px(p.n)}
                y={M.top + ih + 16}
                textAnchor="middle"
                className="fill-muted-foreground text-[10px]"
              >
                {p.n >= 1000 ? `${p.n / 1000}k` : p.n}
              </text>
            </g>
          ))}

          {/* y ticks at decade boundaries */}
          {Array.from(
            { length: Math.floor(yMax) - Math.ceil(yMin) + 1 },
            (_, i) => Math.ceil(yMin) + i,
          ).map((decade) => (
            <g key={`gy-${decade}`}>
              <line
                x1={M.left}
                y1={py(10 ** decade)}
                x2={M.left + iw}
                y2={py(10 ** decade)}
                stroke="var(--viz-grid)"
                strokeWidth={1}
              />
              <text
                x={M.left - 8}
                y={py(10 ** decade) + 3}
                textAnchor="end"
                className="fill-muted-foreground text-[10px]"
              >
                {tickLabel(10 ** decade)}
              </text>
            </g>
          ))}

          <text
            x={M.left + iw / 2}
            y={H - 2}
            textAnchor="middle"
            className="fill-muted-foreground text-[10px]"
          >
            input size n (log)
          </text>

          {/* Context: optimal reference, greyed and dashed. Omitted when the
              measured class IS the optimal class — the two fits coincide, and a
              dashed line hidden underneath the solid one just looks like a bug. */}
          {!isOptimal && (
            <>
              <path
                d={curve(refAt)}
                fill="none"
                stroke="var(--viz-ink-muted)"
                strokeWidth={1.5}
                strokeDasharray="5 4"
                opacity={0.65}
              />
              <text
                x={M.left + iw + 6}
                y={py(refAt(10 ** xMax)) + 3}
                className="fill-muted-foreground text-[10px]"
              >
                optimal
              </text>
            </>
          )}

          {/* the subject: fitted model */}
          <path
            d={curve(fitAt)}
            fill="none"
            stroke="var(--axis-complexity)"
            strokeWidth={2}
            strokeLinecap="round"
          />
          <text
            x={M.left + iw + 6}
            y={py(fitAt(10 ** xMax)) + 3}
            className="text-[10px] font-medium"
            fill="var(--axis-complexity)"
          >
            {isOptimal ? "fit = optimal" : "fit"}
          </text>

          {/* measurements — ≥8px markers, 2px surface ring so overlaps stay readable */}
          {all.map((p, i) => (
            <g key={`p-${p.n}`}>
              <circle
                cx={px(p.n)}
                cy={py(p.medianNs)}
                r={hover === i ? 6 : 4.5}
                fill={p.usedInFit ? "var(--axis-complexity)" : "var(--background)"}
                stroke={p.usedInFit ? "var(--background)" : "var(--viz-ink-muted)"}
                strokeWidth={2}
                className="transition-all"
              />
              <circle
                cx={px(p.n)}
                cy={py(p.medianNs)}
                r={16}
                fill="transparent"
                onMouseEnter={() => setHover(i)}
                onMouseLeave={() => setHover(null)}
              />
            </g>
          ))}

          {hovered && (
            <g pointerEvents="none">
              <line
                x1={px(hovered.n)}
                y1={M.top}
                x2={px(hovered.n)}
                y2={M.top + ih}
                stroke="var(--foreground)"
                strokeWidth={1}
                opacity={0.25}
              />
            </g>
          )}
        </svg>

        {hovered && (
          <div className="pointer-events-none absolute left-1/2 top-0 -translate-x-1/2 rounded-md border bg-popover px-2.5 py-1.5 text-popover-foreground shadow-md">
            <div className="tnum flex items-center gap-2 text-xs">
              <span className="text-muted-foreground">n =</span>
              <span className="font-medium">{hovered.n.toLocaleString()}</span>
              <span className="text-muted-foreground">→</span>
              <span className="font-medium">{formatNs(hovered.medianNs)}</span>
            </div>
            {!hovered.usedInFit && (
              <p className="mt-0.5 text-[10px] text-muted-foreground">
                {copy.belowNoiseFloor}
              </p>
            )}
          </div>
        )}
      </div>

      {result.ambiguousWith && (
        <Alert>
          <Info />
          <AlertDescription className="text-xs">
            {copy.ambiguous(
              prettyComplexity(result.estimated),
              prettyComplexity(result.ambiguousWith),
            )}
          </AlertDescription>
        </Alert>
      )}

      <p className="text-[11px] leading-snug text-muted-foreground">
        <span className="font-medium text-foreground">{copy.footer.lead}</span>{" "}
        — {copy.footer.body(used.length)} {copy.footer.caveat}
      </p>
    </div>
  );
}