///|
/// Compact graph together with a mapping from each original state to its new
/// identifier. `None` means that the original state was removed.
pub struct TrimResult[W] {
  graph : Transducer[W]
  priv old_to_new : Array[Int32?]
}

///|
/// Return whether each state can be reached from the start by graph arcs.
/// Arc weights and labels (including epsilon) do not affect structural reachability.
pub fn[W] reachable_states(transducer : Transducer[W]) -> Array[Bool] {
  let count = transducer.outgoing.length()
  let reached : Array[Bool] = []
  for _ in 0.. ()
    Some(start) => {
      reached[start] = true
      let queue : Array[Int32] = [start]
      let mut cursor = 0
      while cursor < queue.length() {
        let state = queue[cursor]
        for arc in transducer.outgoing[state] {
          if !reached[arc.destination] {
            reached[arc.destination] = true
            queue.push(arc.destination)
          }
        }
        cursor = cursor + 1
      }
    }
  }
  reached
}

///|
/// Return whether each state can reach a structurally final state.
/// A state is final whenever it has an explicitly stored final weight, even if
/// that value is the semiring zero. Epsilon and zero-valued arcs are traversed.
pub fn[W] coaccessible_states(transducer : Transducer[W]) -> Array[Bool] {
  let count = transducer.outgoing.length()
  let predecessors : Array[Array[Int32]] = []
  let accessible : Array[Bool] = []
  let queue : Array[Int32] = []
  for state in 0.. Transducer[W] {
  result.graph
}

///|
/// Return a copy of the original-to-compacted state mapping.
pub fn[W] trim_result_state_mapping(result : TrimResult[W]) -> Array[Int32?] {
  let copy : Array[Int32?] = []
  for state in result.old_to_new {
    copy.push(state)
  }
  copy
}

///|
/// Remove states that are not both reachable from the start and able to reach
/// a structurally final state. Retained states are re-numbered in original
/// state order. An absent start or an empty accepting core yields an empty
/// graph with no start state. The operation is structural: it does not inspect
/// label matches or compare generic weights against semiring zero.
pub fn[W] trim(transducer : Transducer[W]) -> TrimResult[W] {
  let core = accepting_core_states(transducer)
  let keep : Array[Bool] = []
  let mapping : Array[Int32?] = []
  let mut retained_count = 0
  for state in 0..
      match mapping[start] {
        Some(new_start) => ignore(set_start(builder, new_start))
        None => ()
      }
    None => ()
  }
  for old_state in 0.. ignore(set_final(builder, new_state, weight))
        None => ()
      }
      for arc in transducer.outgoing[old_state] {
        if keep[arc.destination] {
          ignore(
            add_arc(
              builder,
              new_state,
              arc.input,
              arc.output,
              mapping[arc.destination].unwrap(),
              arc.weight,
            ),
          )
        }
      }
    }
  }
  { graph: build_transducer(builder), old_to_new: mapping, }
}

///|
/// Return a deterministic topological order of every state in a DAG.
/// All disconnected components are included. Initially ready states are queued
/// in ascending state-id order; newly ready states follow outgoing-arc insertion
/// order and are appended to the queue. A cycle returns `GraphHasCycle`.
pub fn[W] topological_order(
  transducer : Transducer[W],
) -> Result[Array[Int32], WfstError] {
  let count = transducer.outgoing.length()
  let indegree : Array[Int32] = []
  for _ in 0.. Result[Array[Bool], WfstError] {
  let count = transducer.outgoing.length()
  if root < 0 || root >= count {
    return Err(WfstError::InvalidStateId(root))
  }
  let reached : Array[Bool] = []
  for _ in 0.. Array[Bool] {
  let reached = reachable_states(transducer)
  let accessible = coaccessible_states(transducer)
  let core : Array[Bool] = []
  for state in 0.. Bool {
  let core = accepting_core_states(transducer)
  for state in core {
    if !state {
      return false
    }
  }
  true
}