// A line diff (Myers, O(ND)) used to align blame computed on the base
// version of a file with the lines of the editor's current text.

/** For each line of `after`, the index of the matching line in `before`, or -1 when new. */
export function alignLines(before: string[], after: string[]): number[] {
  const n = before.length;
  const m = after.length;
  const result = new Array<number>(m).fill(-1);
  if (n === 0 || m === 0) {
    return result;
  }
  // Trim common prefix and suffix first; they dominate real edits.
  let start = 0;
  while (start < n && start < m && before[start] === after[start]) {
    result[start] = start;
    start++;
  }
  let endB = n;
  let endA = m;
  while (endB > start && endA > start && before[endB - 1] === after[endA - 1]) {
    endB--;
    endA--;
    result[endA] = endB;
  }
  const a = before.slice(start, endB);
  const b = after.slice(start, endA);
  if (a.length === 0 || b.length === 0) {
    return result;
  }
  // Bail out to positional matching on huge middles to bound memory.
  if (a.length * b.length > 25_000_000) {
    for (let i = 0; i < Math.min(a.length, b.length); i++) {
      if (a[i] === b[i]) {
        result[start + i] = start + i;
      }
    }
    return result;
  }
  for (const [i, j] of myers(a, b)) {
    result[start + j] = start + i;
  }
  return result;
}

/** Pairs (i, j) of equal lines a[i] === b[j] along a shortest edit script. */
function myers(a: string[], b: string[]): [number, number][] {
  const n = a.length;
  const m = b.length;
  const max = n + m;
  const offset = max;
  const trace: Int32Array[] = [];
  let v = new Int32Array(2 * max + 2);
  v[offset + 1] = 0;
  outer: for (let d = 0; d <= max; d++) {
    const snapshot = v.slice();
    trace.push(snapshot);
    for (let k = -d; k <= d; k += 2) {
      let x: number;
      if (k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1])) {
        x = v[offset + k + 1];
      } else {
        x = v[offset + k - 1] + 1;
      }
      let y = x - k;
      while (x < n && y < m && a[x] === b[y]) {
        x++;
        y++;
      }
      v[offset + k] = x;
      if (x >= n && y >= m) {
        break outer;
      }
    }
  }
  // Backtrack.
  const pairs: [number, number][] = [];
  let x = n;
  let y = m;
  for (let d = trace.length - 1; d >= 0; d--) {
    const vd = trace[d];
    const k = x - y;
    let prevK: number;
    if (k === -d || (k !== d && vd[offset + k - 1] < vd[offset + k + 1])) {
      prevK = k + 1;
    } else {
      prevK = k - 1;
    }
    const prevX = vd[offset + prevK];
    const prevY = prevX - prevK;
    while (x > prevX && y > prevY) {
      x--;
      y--;
      pairs.push([x, y]);
    }
    if (d > 0) {
      x = prevX;
      y = prevY;
    }
  }
  return pairs.reverse();
}