///|
/// One validated DAG edge relative to a Han run.
priv struct FrequencyDagEdge {
  length : Int
  frequency : Int
}

///|
/// Collects dictionary candidates without allowing provider order, duplicates,
/// or malformed values to affect routing.
fn frequency_dag_edges_at(
  dictionary : &ChineseDictionary,
  characters : ReadOnlyArray[Char],
  start : Int,
  end : Int,
) -> Array[FrequencyDagEdge] {
  let edges : Array[FrequencyDagEdge] = []
  for candidate in dictionary.matches_at(characters, start, end) {
    if candidate.length <= 0 ||
      start + candidate.length > end ||
      candidate.frequency <= 0 {
      continue
    }
    match edges.search_by(edge => edge.length == candidate.length) {
      Some(index) =>
        if candidate.frequency > edges[index].frequency {
          edges[index] = {
            length: candidate.length,
            frequency: candidate.frequency,
          }
        }
      None =>
        edges.push({ length: candidate.length, frequency: candidate.frequency })
    }
  }
  if edges.length() == 0 {
    edges.push({ length: 1, frequency: 1 })
  }
  edges
}

///|
/// Returns one chosen token length per character in `[start, end)`.
///
/// Only entries at positions reached by the route are consumed by the caller.
/// Scores follow Jieba's dictionary-only model:
/// `ln(frequency) - ln(total_frequency) + score[next]`.
fn frequency_dag_route(
  dictionary : &ChineseDictionary,
  characters : ReadOnlyArray[Char],
  start : Int,
  end : Int,
) -> Array[Int] {
  let character_count = end - start
  if character_count <= 0 {
    return []
  }
  let graph : Array[Array[FrequencyDagEdge]] = []
  let mut maximum_frequency = 1
  for offset in 0.. maximum_frequency {
        maximum_frequency = edge.frequency
      }
    }
    graph.push(edges)
  }
  let mut total_frequency = dictionary.total_frequency()
  if total_frequency < maximum_frequency {
    total_frequency = maximum_frequency
  }
  if total_frequency < 1 {
    total_frequency = 1
  }
  let log_total = @math.ln(total_frequency.to_double())
  let best_scores = Array::make(character_count + 1, 0.0)
  let best_lengths = Array::make(character_count, 1)
  let mut offset = character_count - 1
  while offset >= 0 {
    let mut found = false
    let mut best_score = 0.0
    let mut best_length = 1
    for edge in graph[offset] {
      let next = offset + edge.length
      let score = @math.ln(edge.frequency.to_double()) -
        log_total +
        best_scores[next]
      if !found ||
        score > best_score ||
        (score == best_score && edge.length > best_length) {
        found = true
        best_score = score
        best_length = edge.length
      }
    }
    best_scores[offset] = best_score
    best_lengths[offset] = best_length
    offset -= 1
  }
  best_lengths
}