Function try_nonrecursive_dft_mut

src/ore/src/graph.rs:85–113

Same as [`try_nonrecursive_dft`], but allows changes to be made to the graph.

(
    graph: &mut Graph,
    root: NodeId,
    at_enter: &mut AtEnter,
    at_exit: &mut AtExit,
)

/// Same as [`try_nonrecursive_dft`], but allows changes to be made to the graph.
pub fn try_nonrecursive_dft_mut<Graph, NodeId, AtEnter, AtExit, E>(
    graph: &mut Graph,
    root: NodeId,
    at_enter: &mut AtEnter,
    at_exit: &mut AtExit,
) -> Result<(), E>
where
    NodeId: std::cmp::Ord + Clone,
    AtEnter: FnMut(&mut Graph, &NodeId) -> Result<Vec<NodeId>, E>,
    AtExit: FnMut(&mut Graph, &NodeId) -> Result<(), E>,
{
    // Code in this method is identical to the code in `nonrecursive_dft`.
    let mut entered = Vec::new();
    let mut exited = BTreeSet::new();

    let children = at_enter(graph, &root)?;
    entered_node(&mut entered, root, children);
    while !entered.is_empty() {
        if let Some(to_enter) = find_next_child_to_enter(&mut entered, &exited) {
            let children = at_enter(graph, &to_enter)?;
            entered_node(&mut entered, to_enter, children);
        } else {
            let (to_exit, _) = entered.pop().unwrap();
            at_exit(graph, &to_exit)?;
            exited.insert(to_exit);
        }
    }
    Ok(())
}

/// A non-recursive implementation of an infallible depth-first traversal
/// starting from `root`.