interface MmlNodeLike {
  kind: string;
  childNodes?: MmlNodeLike[];
  getText?: () => string;
}

export interface CellBox {
  lines: string[];
  baseline: number;
}

const SPACED_OPERATORS = new Set([
  "+", "−", "-", "±", "×", "·", "=", "≠", "<", ">", "≤", "≥", "≈", "→", "←", "↔",
]);

const SUPERSCRIPTS: Record<string, string> = {
  "0": "⁰", "1": "¹", "2": "²", "3": "³", "4": "⁴", "5": "⁵", "6": "⁶", "7": "⁷", "8": "⁸", "9": "⁹",
  "+": "⁺", "-": "⁻", "−": "⁻", "=": "⁼", "(": "⁽", ")": "⁾", n: "ⁿ", i: "ⁱ",
};

const SUBSCRIPTS: Record<string, string> = {
  "0": "₀", "1": "₁", "2": "₂", "3": "₃", "4": "₄", "5": "₅", "6": "₆", "7": "₇", "8": "₈", "9": "₉",
  "+": "₊", "-": "₋", "−": "₋", "=": "₌", "(": "₍", ")": "₎",
  a: "ₐ", e: "ₑ", h: "ₕ", i: "ᵢ", j: "ⱼ", k: "ₖ", l: "ₗ", m: "ₘ", n: "ₙ", o: "ₒ", p: "ₚ", r: "ᵣ", s: "ₛ", t: "ₜ", u: "ᵤ", v: "ᵥ", x: "ₓ",
};

export function layoutMathTree(root: unknown): string[] {
  return layoutMathTreeBox(root).lines;
}

export function layoutMathTreeBox(root: unknown): CellBox {
  return trimBox(layoutNode(root as MmlNodeLike));
}

export function wrapTextCells(text: string, maxWidth: number): string[] {
  const width = Math.max(1, Math.floor(maxWidth));
  const words = text.trim().split(/\s+/).filter(Boolean);
  if (words.length === 0) return [];

  const lines: string[] = [];
  let line = "";
  for (const word of words) {
    if (word.length > width) {
      if (line) lines.push(line);
      for (let offset = 0; offset < word.length; offset += width) lines.push(word.slice(offset, offset + width));
      line = "";
      continue;
    }
    const candidate = line ? `${line} ${word}` : word;
    if (candidate.length <= width) {
      line = candidate;
    } else {
      lines.push(line);
      line = word;
    }
  }
  if (line) lines.push(line);
  return lines;
}

function layoutNode(node: MmlNodeLike | undefined): CellBox {
  if (!node) return textBox("");
  const children = node.childNodes ?? [];

  switch (node.kind) {
    case "math":
    case "mrow":
    case "inferredMrow":
    case "TeXAtom":
    case "mstyle":
    case "mpadded":
    case "semantics":
      return horizontal(children.map(layoutNode));
    case "mi":
    case "mn":
    case "mtext":
    case "ms":
      return textBox(tokenText(node));
    case "mo": {
      const operator = tokenText(node).replace("&#x2212;", "−");
      return textBox(SPACED_OPERATORS.has(operator) ? ` ${operator} ` : operator);
    }
    case "mfrac":
      return fraction(layoutNode(children[0]), layoutNode(children[1]));
    case "msqrt":
      return radical(horizontal(children.map(layoutNode)));
    case "mroot":
      return radical(layoutNode(children[0]), layoutNode(children[1]));
    case "msup":
      return scripted(layoutNode(children[0]), undefined, layoutNode(children[1]), plainText(children[1]));
    case "msub":
      return scripted(layoutNode(children[0]), layoutNode(children[1]), undefined, undefined, plainText(children[1]));
    case "msubsup":
      return scripted(
        layoutNode(children[0]),
        layoutNode(children[1]),
        layoutNode(children[2]),
        plainText(children[2]),
        plainText(children[1]),
      );
    case "munder":
      return limits(layoutNode(children[0]), layoutNode(children[1]), undefined);
    case "mover":
      return limits(layoutNode(children[0]), undefined, layoutNode(children[1]));
    case "munderover":
      return limits(layoutNode(children[0]), layoutNode(children[1]), layoutNode(children[2]));
    case "mfenced":
      return horizontal([textBox("("), horizontal(children.map(layoutNode)), textBox(")")]);
    case "mspace":
      return textBox(" ");
    case "merror":
      throw new Error(`MathJax parse error: ${plainText(node) || "invalid expression"}`);
    default:
      if (children.length > 0) return horizontal(children.map(layoutNode));
      throw new Error(`Unsupported MathML node: ${node.kind}`);
  }
}

function tokenText(node: MmlNodeLike): string {
  if (typeof node.getText === "function") return decodeEntities(node.getText());
  return (node.childNodes ?? []).map(tokenText).join("");
}

function decodeEntities(text: string): string {
  return text
    .replace(/&#x([0-9a-f]+);/giu, (_match, hex: string) => String.fromCodePoint(Number.parseInt(hex, 16)))
    .replace(/&#([0-9]+);/gu, (_match, decimal: string) => String.fromCodePoint(Number.parseInt(decimal, 10)))
    .replaceAll("&lt;", "<")
    .replaceAll("&gt;", ">")
    .replaceAll("&amp;", "&");
}

function plainText(node: MmlNodeLike | undefined): string | undefined {
  if (!node) return undefined;
  if (["mi", "mn", "mo", "mtext", "ms"].includes(node.kind)) return tokenText(node);
  const text = (node.childNodes ?? []).map(plainText).join("");
  return text || undefined;
}

function textBox(text: string): CellBox {
  return { lines: [text], baseline: 0 };
}

function horizontal(boxes: CellBox[]): CellBox {
  if (boxes.length === 0) return textBox("");
  const baseline = Math.max(...boxes.map((box) => box.baseline));
  const below = Math.max(...boxes.map((box) => box.lines.length - box.baseline - 1));
  const height = baseline + below + 1;
  const lines = Array.from({ length: height }, () => "");

  for (const box of boxes) {
    const width = boxWidth(box);
    const top = baseline - box.baseline;
    for (let row = 0; row < height; row += 1) {
      const source = box.lines[row - top] ?? "";
      lines[row] += source.padEnd(width);
    }
  }
  return { lines: lines.map((line) => line.replace(/\s+$/u, "")), baseline };
}

function fraction(numerator: CellBox, denominator: CellBox): CellBox {
  const width = Math.max(1, boxWidth(numerator), boxWidth(denominator));
  return {
    lines: [...center(numerator, width), "─".repeat(width), ...center(denominator, width)],
    baseline: numerator.lines.length,
  };
}

function radical(body: CellBox, index?: CellBox): CellBox {
  const width = boxWidth(body);
  const prefix = index ? `${plainLine(index)}√` : "√";
  const bodyLines = padBox(body, width);
  return {
    lines: [` ${"─".repeat(width)}`, ...bodyLines.map((line, row) => `${row === body.baseline ? prefix : " ".repeat(prefix.length)}${line}`)],
    baseline: body.baseline + 1,
  };
}

function scripted(
  base: CellBox,
  sub?: CellBox,
  sup?: CellBox,
  supText?: string,
  subText?: string,
): CellBox {
  const unicodeSup = supText?.length === 1 ? convertScript(supText, SUPERSCRIPTS) : undefined;
  const unicodeSub = subText?.length === 1 ? convertScript(subText, SUBSCRIPTS) : undefined;
  if ((!sup || unicodeSup) && (!sub || unicodeSub)) {
    return horizontal([base, textBox(`${unicodeSub ?? ""}${unicodeSup ?? ""}`)]);
  }

  const scriptWidth = Math.max(sub ? boxWidth(sub) : 0, sup ? boxWidth(sup) : 0);
  const baseWidth = boxWidth(base);
  const above = sup?.lines.length ?? 0;
  const below = sub?.lines.length ?? 0;
  const lines = [
    ...(sup ? sup.lines.map((line) => " ".repeat(baseWidth) + line.padEnd(scriptWidth)) : []),
    ...padBox(base, baseWidth).map((line) => line + " ".repeat(scriptWidth)),
    ...(sub ? sub.lines.map((line) => " ".repeat(baseWidth) + line.padEnd(scriptWidth)) : []),
  ].map((line) => line.replace(/\s+$/u, ""));
  return { lines, baseline: above + base.baseline };
}

function limits(base: CellBox, under?: CellBox, over?: CellBox): CellBox {
  const compactUnder = under ? compactScriptBox(under) : undefined;
  const compactOver = over ? compactScriptBox(over) : undefined;
  const width = Math.max(
    boxWidth(base),
    compactUnder ? boxWidth(compactUnder) : 0,
    compactOver ? boxWidth(compactOver) : 0,
  );
  return {
    lines: [
      ...(compactOver ? center(compactOver, width) : []),
      ...center(base, width),
      ...(compactUnder ? center(compactUnder, width) : []),
    ],
    baseline: (compactOver?.lines.length ?? 0) + base.baseline,
  };
}

function compactScriptBox(box: CellBox): CellBox {
  return {
    lines: box.lines.map((line) => line.trim().replace(/\s*([=<>≤≥])\s*/gu, "$1")),
    baseline: box.baseline,
  };
}

function convertScript(text: string, table: Record<string, string>): string | undefined {
  let result = "";
  for (const character of text) {
    const converted = table[character];
    if (!converted) return undefined;
    result += converted;
  }
  return result;
}

function center(box: CellBox, width: number): string[] {
  return padBox(box, boxWidth(box)).map((line) => {
    const left = Math.floor((width - line.length) / 2);
    return `${" ".repeat(left)}${line}${" ".repeat(width - left - line.length)}`.replace(/\s+$/u, "");
  });
}

function padBox(box: CellBox, width: number): string[] {
  return box.lines.map((line) => line.padEnd(width));
}

function boxWidth(box: CellBox): number {
  return Math.max(0, ...box.lines.map((line) => line.length));
}

function plainLine(box: CellBox): string {
  return box.lines.join("").trim();
}

function trimBox(box: CellBox): CellBox {
  const lines = box.lines.map((line) => line.replace(/\s+$/u, ""));
  while (lines.length > 0 && !lines[0]?.trim()) lines.shift();
  while (lines.length > 0 && !lines.at(-1)?.trim()) lines.pop();
  const minimumIndent = Math.min(...lines.filter((line) => line.trim()).map((line) => line.length - line.trimStart().length));
  return { lines: lines.map((line) => line.slice(Number.isFinite(minimumIndent) ? minimumIndent : 0)), baseline: box.baseline };
}