// Port of the pi-fabric word-diff alignment (src/ui/word-diff/alignment.ts).
// suffixAlignedPairs finds the highest-weight set of non-crossing pairs over
// two sequences; the change-block pipeline uses it as exact-match LCS.

const ALIGNMENT_SCORE_EPSILON = 1e-9;

type PairScoreAt = (beforeIndex: number, afterIndex: number) => number;

function sameAlignmentScore(a: number, b: number): boolean {
  return Math.abs(a - b) < ALIGNMENT_SCORE_EPSILON;
}

export function suffixAlignedPairs(
  beforeLength: number,
  afterLength: number,
  scoreAt: PairScoreAt
): [number, number][] {
  const columns = afterLength + 1;
  const dp = new Float64Array((beforeLength + 1) * columns);

  for (let i = beforeLength - 1; i >= 0; i -= 1) {
    const rowOffset = i * columns;
    const nextRowOffset = rowOffset + columns;
    for (let j = afterLength - 1; j >= 0; j -= 1) {
      const pairScore = scoreAt(i, j);
      const align = Number.isFinite(pairScore)
        ? dp[nextRowOffset + j + 1] + pairScore
        : pairScore;
      dp[rowOffset + j] = Math.max(
        align,
        dp[nextRowOffset + j],
        dp[rowOffset + j + 1]
      );
    }
  }

  const pairs: [number, number][] = [];
  let i = 0;
  let j = 0;
  while (i < beforeLength && j < afterLength) {
    const rowOffset = i * columns;
    const nextRowOffset = rowOffset + columns;
    const pairScore = scoreAt(i, j);
    const align = Number.isFinite(pairScore)
      ? dp[nextRowOffset + j + 1] + pairScore
      : pairScore;
    if (
      Number.isFinite(pairScore) &&
      sameAlignmentScore(dp[rowOffset + j], align)
    ) {
      pairs.push([i, j]);
      i += 1;
      j += 1;
    } else if (dp[nextRowOffset + j] >= dp[rowOffset + j + 1]) {
      i += 1;
    } else {
      j += 1;
    }
  }
  return pairs;
}