///|
fn minimum_three(first : Int, second : Int, third : Int) -> Int {
  let pair = if first < second { first } else { second }
  if pair < third {
    pair
  } else {
    third
  }
}

///|
/// Computes edit distance using two rows and MoonBit string index units.
pub fn levenshtein_distance(left : String, right : String) -> Int {
  if left == right {
    return 0
  }
  if left.length() == 0 {
    return right.length()
  }
  if right.length() == 0 {
    return left.length()
  }
  if right.length() > left.length() {
    return levenshtein_distance(right, left)
  }
  let mut previous = Array::make(right.length() + 1, 0)
  let mut current = Array::make(right.length() + 1, 0)
  for j = 0; j <= right.length(); j = j + 1 {
    previous[j] = j
  }
  for i = 1; i <= left.length(); i = i + 1 {
    current[0] = i
    for j = 1; j <= right.length(); j = j + 1 {
      let substitution = if left[i - 1] == right[j - 1] { 0 } else { 1 }
      current[j] = minimum_three(
        current[j - 1] + 1,
        previous[j] + 1,
        previous[j - 1] + substitution,
      )
    }
    let swap = previous
    previous = current
    current = swap
  }
  previous[right.length()]
}

///|
/// Returns `1 - distance / max_length` in the closed interval `[0, 1]`.
pub fn levenshtein_similarity(left : String, right : String) -> Double {
  let maximum = if left.length() > right.length() {
    left.length()
  } else {
    right.length()
  }
  if maximum == 0 {
    return 1.0
  }
  1.0 - levenshtein_distance(left, right).to_double() / maximum.to_double()
}