// 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();

}