///|
/// A matching pair in two sequences, with indices in their original coordinate systems.
priv struct Anchor {
  before : Int32
  after : Int32
}

///|
priv struct AlignmentBudget {
  mut cells : Int32
}

///|
fn AlignmentBudget::reserve(
  self : AlignmentBudget,
  rows : Int32,
  cols : Int32,
) -> Bool {
  if self.cells <= 0 || rows >= self.cells || cols >= self.cells {
    return false
  }
  let width = cols + 1
  if rows + 1 > self.cells / width {
    return false
  }
  self.cells -= (rows + 1) * width
  true
}

///|
fn lcs_middle(
  before_end : Int32,
  after_end : Int32,
  start : Int32,
  matches : (Int32, Int32) -> Bool,
  budget : AlignmentBudget,
) -> Array[Anchor] {
  let rows = before_end - start
  let cols = after_end - start
  if rows == 0 || cols == 0 || !budget.reserve(rows, cols) {
    return []
  }
  let width = cols + 1
  let scores = Array::make((rows + 1) * width, 0)
  for row = rows - 1; row >= 0; row = row - 1 {
    for col = cols - 1; col >= 0; col = col - 1 {
      let slot = row * width + col
      scores[slot] = if matches(start + row, start + col) {
        1 + scores[slot + width + 1]
      } else {
        Int32::max(scores[slot + width], scores[slot + 1])
      }
    }
  }
  let anchors = []
  let mut row = 0
  let mut col = 0
  while row < rows && col < cols {
    let slot = row * width + col
    if matches(start + row, start + col) {
      anchors.push({ before: start + row, after: start + col, })
      row += 1
      col += 1
    } else if scores[slot + width] >= scores[slot + 1] {
      row += 1
    } else {
      col += 1
    }
  }
  anchors
}

///|
/// Keep identical ends even when the shared LCS budget is exhausted.
fn alignment(
  before_count : Int32,
  after_count : Int32,
  matches : (Int32, Int32) -> Bool,
  budget : AlignmentBudget,
) -> Array[Anchor] {
  let shortest = Int32::min(before_count, after_count)
  let mut prefix = 0
  while prefix < shortest && matches(prefix, prefix) {
    prefix += 1
  }
  let mut suffix = 0
  while suffix < shortest - prefix &&
        matches(before_count - suffix - 1, after_count - suffix - 1) {
    suffix += 1
  }
  let before_end = before_count - suffix
  let after_end = after_count - suffix
  let anchors = lcs_middle(before_end, after_end, prefix, matches, budget)
  // These boundary anchors leave the common prefix and suffix out of edit loops.
  anchors.insert(0, { before: prefix - 1, after: prefix - 1, })
  anchors.push({ before: before_end, after: after_end, })
  anchors
}