///|
fn jaro_window(left_length : Int, right_length : Int) -> Int {
  let maximum = if left_length > right_length {
    left_length
  } else {
    right_length
  }
  let distance = maximum / 2 - 1
  if distance < 0 {
    0
  } else {
    distance
  }
}

///|
/// Computes Jaro similarity in the closed interval `[0, 1]`.
pub fn jaro_similarity(left : String, right : String) -> Double {
  if left == right {
    return 1.0
  }
  if left.length() == 0 || right.length() == 0 {
    return 0.0
  }
  let window = jaro_window(left.length(), right.length())
  let left_matches = Array::make(left.length(), false)
  let right_matches = Array::make(right.length(), false)
  let mut matches = 0
  for i = 0; i < left.length(); i = i + 1 {
    let start = if i > window { i - window } else { 0 }
    let requested_end = i + window + 1
    let end = if requested_end < right.length() {
      requested_end
    } else {
      right.length()
    }
    let mut found = false
    let mut j = start
    while j < end && !found {
      if !right_matches[j] && left[i] == right[j] {
        left_matches[i] = true
        right_matches[j] = true
        matches = matches + 1
        found = true
      }
      j = j + 1
    }
  }
  if matches == 0 {
    return 0.0
  }
  let mut right_index = 0
  let mut transpositions = 0
  for i = 0; i < left.length(); i = i + 1 {
    if left_matches[i] {
      while right_index < right.length() && !right_matches[right_index] {
        right_index = right_index + 1
      }
      if right_index < right.length() && left[i] != right[right_index] {
        transpositions = transpositions + 1
      }
      right_index = right_index + 1
    }
  }
  let matched = matches.to_double()
  let half_transpositions = transpositions.to_double() / 2.0
  (
    matched / left.length().to_double() +
    matched / right.length().to_double() +
    (matched - half_transpositions) / matched
  ) /
  3.0
}