/**
 * @factory/editor — TASK-0123: deterministic word-level diff.
 *
 * `wordDiff(oldText, newText)` splits both texts into words (whitespace-
 * separated, preserving the whitespace runs as `same` segments between them)
 * and returns the minimal edit script via LCS (longest common subsequence) on
 * the word lists:
 *
 *   [{ type: "same", text: "Hello " }, { type: "del", text: "old" },
 *    { type: "add", text: "new" }, { type: "same", text: " world." }]
 *
 * Pure + deterministic — the UI renders the script as spans (`add` =
 * highlighted insertion, `del` = struck-through deletion) and the unit
 * tests pin byte-stable output. For very large texts (> 2000 words each)
 * LCS is quadratic, so it degrades to `del(old) + add(new)` — still
 * deterministic, still correct as a diff.
 */

export type DiffSegment = {
  type: "same" | "add" | "del";
  text: string;
};

/** Split text into words + the whitespace between them.
 *  `split("a  b\n")` → `[{w:"a"},{s:"  "},{w:"b"},{s:"\n"}]`. */
function tokenize(text: string): Array<{ kind: "w" | "s"; value: string }> {
  const out: Array<{ kind: "w" | "s"; value: string }> = [];
  if (!text) return out;
  const re = /(\s+)/g;
  let last = 0;
  let m: RegExpExecArray | null;
  while ((m = re.exec(text)) !== null) {
    if (m.index > last) out.push({ kind: "w", value: text.slice(last, m.index) });
    out.push({ kind: "s", value: m[0] });
    last = m.index + m[0].length;
  }
  if (last < text.length) out.push({ kind: "w", value: text.slice(last) });
  return out;
}

/** LCS edit script over two word arrays → segments.
 *  Standard DP with a back-pointer walk; O(n·m) memory/bounded by the
 *  2000-word guard in {@link wordDiff}. */
function lcsSegments(oldWords: string[], newWords: string[]): Array<{ type: "same" | "add" | "del"; word: string }> {
  const n = oldWords.length;
  const m = newWords.length;
  // dp[i][j] = LCS length of oldWords[i:] vs newWords[j:]
  const dp: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(m + 1).fill(0));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = m - 1; j >= 0; j--) {
      dp[i]![j] = oldWords[i] === newWords[j] ? dp[i + 1]![j + 1]! + 1 : Math.max(dp[i + 1]![j]!, dp[i]![j + 1]!);
    }
  }
  const out: Array<{ type: "same" | "add" | "del"; word: string }> = [];
  let i = 0;
  let j = 0;
  while (i < n && j < m) {
    if (oldWords[i] === newWords[j]) {
      out.push({ type: "same", word: oldWords[i]! });
      i++;
      j++;
    } else if (dp[i + 1]![j]! >= dp[i]![j + 1]!) {
      out.push({ type: "del", word: oldWords[i]! });
      i++;
    } else {
      out.push({ type: "add", word: newWords[j]! });
      j++;
    }
  }
  while (i < n) out.push({ type: "del", word: oldWords[i++]! });
  while (j < m) out.push({ type: "add", word: newWords[j++]! });
  return out;
}

/** Merge per-word segments back into runs, re-attaching whitespace so both
 *  reconstruction invariants hold EXACTLY:
 *    same+del (their whitespace) == oldText
 *    same+add (their whitespace) == newText
 *  Rule: a word carries the whitespace that FOLLOWS it in its own source
 *  string (old words → old whitespace, new words → new whitespace). `same`
 *  words are old-side for the old text and new-side for the new text, so
 *  they are emitted with BOTH whitespace runs: `word + oldWS` (del/same
 *  side) followed by `newWS` (add/same side) when they differ — the UI
 *  renders whitespace as plain text either way. */
function mergeToSegments(
  oldText: string,
  newText: string,
  wordScript: Array<{ type: "same" | "add" | "del"; word: string }>,
): DiffSegment[] {
  const oldTok = tokenize(oldText);
  const newTok = tokenize(newText);
  const oldWords = oldTok.filter((t) => t.kind === "w").map((t) => t.value);
  const newWords = newTok.filter((t) => t.kind === "w").map((t) => t.value);
  const afterOf = (tok: Array<{ kind: "w" | "s"; value: string }>): string[] => {
    const out: string[] = [];
    tok.forEach((t, idx) => {
      if (t.kind === "w") out.push(tok[idx + 1]?.kind === "s" ? tok[idx + 1]!.value : "");
    });
    return out;
  };
  const oldAfter = afterOf(oldTok);
  const newAfter = afterOf(newTok);

  const out: DiffSegment[] = [];
  const push = (type: DiffSegment["type"], text: string) => {
    if (!text) return;
    const lastSeg = out[out.length - 1];
    if (lastSeg && lastSeg.type === type) lastSeg.text += text;
    else out.push({ type, text });
  };

  let oi = 0;
  let ni = 0;
  for (const step of wordScript) {
    if (step.type === "same") {
      const oldWS = oldAfter[oi]!;
      const newWS = newAfter[ni]!;
      push("same", oldWords[oi]!);
      if (oldWS === newWS) {
        push("same", oldWS);
      } else {
        // spacing differs around an unchanged word: the old spacing is a
        // deletion, the new spacing an insertion — both invariants hold.
        push("del", oldWS);
        push("add", newWS);
      }
      oi++;
      ni++;
    } else if (step.type === "del") {
      push("del", oldWords[oi]! + oldAfter[oi]!);
      oi++;
    } else {
      push("add", newWords[ni]! + newAfter[ni]!);
      ni++;
    }
  }
  return out;
}

/** Quadratic guard: LCS over > 2000 words per side would be > 4M cells —
 *  above that we degrade to full-replace (still deterministic + correct). */
const MAX_LCS_WORDS = 2000;

/** Diff `oldText` → `newText` as a minimal word-level edit script.
 *  Pure/deterministic; empty inputs yield `[]` (empty old → all add). */
export function wordDiff(oldText: string, newText: string): DiffSegment[] {
  if (oldText === newText) return oldText ? [{ type: "same", text: oldText }] : [];
  const oldTok = tokenize(oldText);
  const newTok = tokenize(newText);
  const oldWords = oldTok.filter((t) => t.kind === "w").map((t) => t.value);
  const newWords = newTok.filter((t) => t.kind === "w").map((t) => t.value);
  if (oldWords.length === 0) return newText ? [{ type: "add", text: newText }] : [];
  if (newWords.length === 0) return oldText ? [{ type: "del", text: oldText }] : [];
  if (oldWords.length > MAX_LCS_WORDS || newWords.length > MAX_LCS_WORDS) {
    return [
      { type: "del", text: oldText },
      { type: "add", text: newText },
    ];
  }
  return mergeToSegments(oldText, newText, lcsSegments(oldWords, newWords));
}

/** Reconstruct the source/new text from a diff script — invariant helpers
 *  for the unit tests (same+del = old, same+add = new). */
export function reconstructOld(segments: DiffSegment[]): string {
  return segments.filter((s) => s.type !== "add").map((s) => s.text).join("");
}

export function reconstructNew(segments: DiffSegment[]): string {
  return segments.filter((s) => s.type !== "del").map((s) => s.text).join("");
}