export interface DiffLine {
  sign: " " | "+" | "-";
  text: string;
}

export interface Hunk {
  aStart: number;
  aLines: number;
  bStart: number;
  bLines: number;
  lines: DiffLine[];
}

/** myers O(ND) shortest edit script over lines, grouped into context hunks */
export function diffLines(aText: string, bText: string, context = 3): Hunk[] {
  const a = splitLines(aText);
  const b = splitLines(bText);
  const trace = myers(a, b);
  return groupHunks(a, b, trace, context);
}

function splitLines(text: string): string[] {
  if (text === "") return [];
  const lines = text.split("\n");
  if (lines.at(-1) === "") lines.pop();
  return lines;
}

type Edit = { sign: " " | "+" | "-"; aLine: number; bLine: number };

function myers(a: string[], b: string[]): Edit[] {
  const max = a.length + b.length;
  if (max === 0) return [];
  const offset = max;
  let v = new Array<number>(2 * max + 1).fill(0);
  const traces: number[][] = [];

  outer: for (let d = 0; d <= max; d++) {
    traces.push(v.slice());
    for (let k = -d; k <= d; k += 2) {
      let x = k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1])
        ? v[offset + k + 1]
        : v[offset + k - 1] + 1;
      let y = x - k;
      while (x < a.length && y < b.length && a[x] === b[y]) {
        x++;
        y++;
      }
      v[offset + k] = x;
      if (x >= a.length && y >= b.length) break outer;
    }
    v = v.slice();
  }

  // backtrack the recorded frontiers into an edit script
  const edits: Edit[] = [];
  let x = a.length;
  let y = b.length;
  for (let d = traces.length - 1; x > 0 || y > 0; d--) {
    const vd = traces[d];
    const k = x - y;
    const prevK = k === -d || (k !== d && vd[offset + k - 1] < vd[offset + k + 1]) ? k + 1 : k - 1;
    const prevX = vd[offset + prevK];
    const prevY = prevX - prevK;
    while (x > prevX && y > prevY) {
      edits.push({ sign: " ", aLine: --x, bLine: --y });
    }
    if (d === 0) break;
    if (x === prevX) edits.push({ sign: "+", aLine: x, bLine: --y });
    else edits.push({ sign: "-", aLine: --x, bLine: y });
  }
  return edits.reverse();
}

function groupHunks(a: string[], b: string[], edits: Edit[], context: number): Hunk[] {
  const hunks: Hunk[] = [];
  let current: Hunk | null = null;
  let trailingContext = 0;

  for (let i = 0; i < edits.length; i++) {
    const edit = edits[i];
    if (edit.sign === " ") {
      if (current) {
        if (trailingContext < context) {
          current.lines.push({ sign: " ", text: a[edit.aLine] });
          current.aLines++;
          current.bLines++;
          trailingContext++;
        } else {
          // check whether another change follows within 2*context
          const nextChange = edits.slice(i, i + context + 1).findIndex(e => e.sign !== " ");
          if (nextChange === -1) {
            current = null;
          } else {
            current.lines.push({ sign: " ", text: a[edit.aLine] });
            current.aLines++;
            current.bLines++;
          }
        }
      }
      continue;
    }

    if (!current) {
      const lead: DiffLine[] = [];
      let aStart = edit.aLine;
      let bStart = edit.bLine;
      for (let c = 1; c <= context; c++) {
        const prev = edits[i - c];
        if (!prev || prev.sign !== " ") break;
        lead.unshift({ sign: " ", text: a[prev.aLine] });
        aStart = prev.aLine;
        bStart = prev.bLine;
      }
      current = {
        aStart: aStart + 1,
        bStart: bStart + 1,
        aLines: lead.length,
        bLines: lead.length,
        lines: lead,
      };
      hunks.push(current);
    }
    trailingContext = 0;
    if (edit.sign === "-") {
      current.lines.push({ sign: "-", text: a[edit.aLine] });
      current.aLines++;
    } else {
      current.lines.push({ sign: "+", text: b[edit.bLine] });
      current.bLines++;
    }
  }

  return hunks;
}