/**
 * Line-level diff for the lesson source panes (the deep-dive learning section).
 *
 * A lesson walks a spec from an 80%-naive version to a polished one as a chain of
 * small edits; each step shows the new spec with *the lines this step changed*
 * highlighted, so a reader sees exactly what the edit did. Given the previous
 * step's formatted text and the current step's, {@link changedLines} reports which
 * line indices of the *current* text are new or changed.
 *
 * Pure: operates on already-formatted text (see {@link formatSpec}), no Vega, no
 * DOM. Standard longest-common-subsequence over lines — every current line not
 * part of the LCS with the previous text is "changed". This is why it beats a
 * naive "line not present in the previous text" test: Vega specs repeat lines
 * (`"type": "quantitative"` many times over), and only the LCS classifies a
 * genuinely-new occurrence as changed while leaving the unchanged duplicates be.
 */

/**
 * Indices (0-based, into `nextText`'s lines) that are new or changed relative to
 * `prevText`. Identical inputs yield an empty set; an empty `prevText` (a first
 * step with nothing before it) marks every line — callers that render a baseline
 * step simply skip the highlight.
 */
export function changedLines(prevText: string, nextText: string): Set<number> {
  const a = prevText.length ? prevText.split('\n') : [];
  const b = nextText.length ? nextText.split('\n') : [];
  const m = a.length;
  const n = b.length;

  // dp[i][j] = length of the LCS of a[i..] and b[j..]. Filled bottom-up so the
  // forward walk below can pick the branch that preserves the longer subsequence.
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      dp[i][j] = a[i] === b[j] ? dp[i + 1][j + 1] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);
    }
  }

  const changed = new Set<number>();
  let i = 0;
  let j = 0;
  while (j < n) {
    if (i < m && a[i] === b[j]) {
      i++; // line common to both — unchanged
      j++;
    } else if (i < m && dp[i + 1][j] >= dp[i][j + 1]) {
      i++; // previous line dropped — not a change in `next`
    } else {
      changed.add(j); // new/changed line in `next`
      j++;
    }
  }
  return changed;
}
