///|
fn make_ngrams(input : String, size : Int) -> Array[String] {
  let grams : Array[String] = []
  if size > input.length() {
    return grams
  }
  for i = 0; i + size <= input.length(); i = i + 1 {
    grams.push(ascii_slice(input, i, i + size))
  }
  grams
}

///|
fn ngram_multiset_intersection(
  left : Array[String],
  right : Array[String],
) -> Int {
  let matched = Array::make(right.length(), false)
  let mut intersection = 0
  for left_gram in left {
    let mut found = false
    let mut index = 0
    while index < right.length() && !found {
      if !matched[index] && left_gram == right[index] {
        matched[index] = true
        intersection = intersection + 1
        found = true
      }
      index = index + 1
    }
  }
  intersection
}

///|
/// Computes multiset Dice similarity for character n-grams.
pub fn dice_similarity(
  left : String,
  right : String,
  size : Int,
) -> Result[Double, SimilarityError] {
  if size < 1 || size > 64 {
    return Err(InvalidNGramSize(size))
  }
  if left == right {
    return Ok(1.0)
  }
  let left_grams = make_ngrams(left, size)
  let right_grams = make_ngrams(right, size)
  let total = left_grams.length() + right_grams.length()
  if total == 0 {
    return Ok(0.0)
  }
  let intersection = ngram_multiset_intersection(left_grams, right_grams)
  Ok(2.0 * intersection.to_double() / total.to_double())
}