///|
/// A partial accepting path retained by the DAG k-best dynamic program.
priv struct PartialPath[W] {
  states : Array[Int32]
  steps : Array[PathStep[W]]
  weight : W
}

///|
/// Keep at most `limit` paths ordered by accumulated weight. Equal weights are
/// appended after earlier candidates to preserve traversal stability.
fn[W] insert_partial_path(
  paths : Array[PartialPath[W]],
  candidate : PartialPath[W],
  limit : Int32,
  compare : (W, W) -> Int32,
) -> Array[PartialPath[W]] {
  let result : Array[PartialPath[W]] = []
  let mut inserted = false
  for path in paths {
    if !inserted && compare(candidate.weight, path.weight) < 0 {
      result.push(candidate)
      inserted = true
    }
    if result.length() < limit {
      result.push(path)
    }
  }
  if !inserted && result.length() < limit {
    result.push(candidate)
  }
  result
}

///|
/// Keep at most `limit` accepting paths ordered by complete path weight.
fn[W] insert_accepting_path(
  paths : Array[AcceptingPath[W]],
  candidate : AcceptingPath[W],
  limit : Int32,
  compare : (W, W) -> Int32,
) -> Array[AcceptingPath[W]] {
  let result : Array[AcceptingPath[W]] = []
  let mut inserted = false
  for path in paths {
    if !inserted && compare(candidate.total, path.total) < 0 {
      result.push(candidate)
      inserted = true
    }
    if result.length() < limit {
      result.push(path)
    }
  }
  if !inserted && result.length() < limit {
    result.push(candidate)
  }
  result
}

///|
/// Find up to `limit` least-weight accepting paths in a finite DAG.
/// Unlike `shortest_path`, this dynamic program does not require nonnegative
/// arc weights because cycles are rejected before traversal. The supplied
/// comparison must still be compatible with semiring path extension. Parallel
/// arcs remain distinct paths; equal-cost paths retain deterministic graph
/// traversal order. A nonpositive limit is rejected.
pub fn[W] shortest_paths_in_dag(
  transducer : Transducer[W],
  order : PathOrder[W],
  limit : Int32,
) -> Result[Array[AcceptingPath[W]], WfstError] {
  if limit <= 0 {
    return Err(WfstError::InvalidPathLimit(limit))
  }
  let start = match transducer.start {
    Some(state) => state
    None => return Err(WfstError::NoStartState)
  }
  let order_of_states = match topological_order(transducer) {
    Ok(order) => order
    Err(error) => return Err(error)
  }
  let paths_to_state : Array[Array[PartialPath[W]]] = []
  for _ in 0..
        for prefix in paths_to_state[state] {
          let total = semiring_times(
            transducer.semiring,
            prefix.weight,
            final_weight,
          )
          if !(order.is_zero)(total) {
            let candidate : AcceptingPath[W] = {
              states: prefix.states,
              steps: prefix.steps,
              final_weight,
              total,
            }
            let next = insert_accepting_path(
              accepting,
              candidate,
              limit,
              order.compare,
            )
            accepting.clear()
            for path in next {
              accepting.push(path)
            }
          }
        }
      _ => ()
    }
  }
  Ok(accepting)
}