///|
/// A global alignment with an explicit traceback, not only a distance score.
pub struct GlobalAlignment {
  left : String
  right : String
  score : Int
  matches : Int
  mismatches : Int
  gaps : Int
  identity : Double
} derive(Debug, Eq)

///|
/// Align two sequences with a deterministic Needleman-Wunsch implementation.
pub fn global_align(
  left : String,
  right : String,
  match_score : Int,
  mismatch_score : Int,
  gap_score : Int,
) -> GlobalAlignment {
  let a = normalize_sequence(left)
  let b = normalize_sequence(right)
  let width = b.length() + 1
  let height = a.length() + 1
  let scores = Array::make(width * height, 0)
  for i in 1.. 0 || j > 0 {
    let current = scores[i * width + j]
    let diagonal = if i > 0 && j > 0 {
      Some(
        scores[(i - 1) * width + j - 1] +
        (if a.get_char(i - 1).unwrap() == b.get_char(j - 1).unwrap() {
          match_score
        } else {
          mismatch_score
        }),
      )
    } else {
      None
    }
    let up = if i > 0 {
      Some(scores[(i - 1) * width + j] + gap_score)
    } else {
      None
    }
    if diagonal is Some(value) && value == current {
      let left_char = a.get_char(i - 1).unwrap()
      let right_char = b.get_char(j - 1).unwrap()
      aligned_left = left_char.to_string() + aligned_left
      aligned_right = right_char.to_string() + aligned_right
      if left_char == right_char {
        matches += 1
      } else {
        mismatches += 1
      }
      i -= 1
      j -= 1
    } else if up is Some(value) && value == current {
      aligned_left = a.get_char(i - 1).unwrap().to_string() + aligned_left
      aligned_right = "-" + aligned_right
      gaps += 1
      i -= 1
    } else {
      aligned_left = "-" + aligned_left
      aligned_right = b.get_char(j - 1).unwrap().to_string() + aligned_right
      gaps += 1
      j -= 1
    }
  }
  let aligned_length = aligned_left.length()
  {
    left: aligned_left,
    right: aligned_right,
    score: scores[a.length() * width + b.length()],
    matches,
    mismatches,
    gaps,
    identity: if aligned_length == 0 {
      100.0
    } else {
      matches.to_double() * 100.0 / aligned_length.to_double()
    },
  }
}

///|
/// Use conventional scoring for quick pairwise comparisons.
pub fn align_sequences(left : String, right : String) -> GlobalAlignment {
  global_align(left, right, 2, -1, -2)
}

///|
/// Return a CIGAR-like operation string (`M`, `X`, and `-`).
pub fn alignment_operations(alignment : GlobalAlignment) -> String {
  let output = StringBuilder()
  for index in 0.. String {
  let markers = StringBuilder()
  for index in 0.. String {
  "{\"left\":" +
  json_string(self.left) +
  ",\"right\":" +
  json_string(self.right) +
  ",\"score\":" +
  self.score.to_string() +
  ",\"matches\":" +
  self.matches.to_string() +
  ",\"mismatches\":" +
  self.mismatches.to_string() +
  ",\"gaps\":" +
  self.gaps.to_string() +
  ",\"identity\":" +
  self.identity.to_string() +
  "}"
}

///|
/// Compare a sequence against many candidates and retain their best scores.
pub fn best_alignments(
  query : String,
  candidates : Array[String],
) -> Array[GlobalAlignment] {
  let result : Array[GlobalAlignment] = []
  for candidate in candidates {
    result.push(align_sequences(query, candidate))
  }
  result.sort_by(fn(left, right) { right.score - left.score })
  result
}