///|
priv struct MatchingStringScore {
  score : Double
  notices : Array[String]
}

///|
fn token_candidate_precedes(
  score : Double,
  left_index : Int,
  right_index : Int,
  best_score : Double,
  best_left : Int,
  best_right : Int,
) -> Bool {
  score > best_score ||
  (
    score == best_score &&
    (
      best_left < 0 ||
      left_index < best_left ||
      (left_index == best_left && right_index < best_right)
    )
  )
}

///|
fn best_token_pair_score(
  left_tokens : Array[String],
  right_tokens : Array[String],
  metric : SimilarityMetric,
  unmatched_token_penalty : Double,
) -> Result[MatchingStringScore, SimilarityError] {
  let left_used = Array::make(left_tokens.length(), false)
  let right_used = Array::make(right_tokens.length(), false)
  let pair_limit = if left_tokens.length() < right_tokens.length() {
    left_tokens.length()
  } else {
    right_tokens.length()
  }
  let notices : Array[String] = []
  let mut score_sum = 0.0
  let mut selected = 0
  while selected < pair_limit {
    let mut best_left = -1
    let mut best_right = -1
    let mut best_score = -1.0
    for left_index = 0
        left_index < left_tokens.length()
        left_index = left_index + 1 {
      if left_used[left_index] {
        continue
      }
      for right_index = 0
          right_index < right_tokens.length()
          right_index = right_index + 1 {
        if right_used[right_index] {
          continue
        }
        let score = match
          string_similarity(
            left_tokens[left_index],
            right_tokens[right_index],
            metric,
          ) {
          Err(error) => return Err(error)
          Ok(value) => value
        }
        if token_candidate_precedes(
            score, left_index, right_index, best_score, best_left, best_right,
          ) {
          best_left = left_index
          best_right = right_index
          best_score = score
        }
      }
    }
    left_used[best_left] = true
    right_used[best_right] = true
    score_sum = score_sum + best_score
    notices.push(
      "token pair left=" + "\{best_left}" + " right=" + "\{best_right}",
    )
    selected = selected + 1
  }
  let unmatched_left = left_tokens.length() - selected
  let unmatched_right = right_tokens.length() - selected
  let unmatched = unmatched_left + unmatched_right
  if unmatched > 0 {
    notices.push(
      "unmatched tokens left=" +
      "\{unmatched_left}" +
      " right=" +
      "\{unmatched_right}",
    )
  }
  let denominator = selected.to_double() +
    unmatched.to_double() * unmatched_token_penalty
  Ok({ score: score_sum / denominator, notices })
}

///|
fn matching_string_score(
  left : NormalizationResult,
  right : NormalizationResult,
  config : MatchConfig,
) -> Result[MatchingStringScore, SimilarityError] {
  match config.token_policy {
    WholeInput =>
      match
        string_similarity(left.normalized, right.normalized, config.metric) {
        Err(error) => Err(error)
        Ok(score) => Ok({ score, notices: [] })
      }
    BestTokenPairs =>
      best_token_pair_score(
        left.tokens,
        right.tokens,
        config.metric,
        config.unmatched_token_penalty,
      )
  }
}