//! This module implements a function to produce the depth-first order
//! for a graph.

use super::*;

use error::Error;

/// Return a list of indices that are ordered according to a depth-first search.
///
/// A node is only recorded at most once.  And the search starts from
/// the `root`, so this in fact only includes the connected component
/// of the `root`.
pub fn dfs(g: &impl Graph, root: usize) -> Result<Vec<usize>, Error> {
    // let g = g.borrow();

    let nodes_len = g.nodes_len();

    let mut result: Vec<usize> = Vec::with_capacity(nodes_len);

    let mut stack: Vec<usize> = Vec::with_capacity(nodes_len);

    stack.push(root);

    let mut seen_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();

    while let Some(top) = stack.pop() {
        match seen_nodes.get_mut(top) {
            Some(reference) if !*reference => {
                *reference = true;

                result.push(top);

                // REVIEW: Maybe I shall add a method
                // `children_of_rev`.

                stack.extend(g.children_of(top)?.collect::<Vec<_>>().into_iter().rev());
            }
            None => {
                return Err(Error::IndexOutOfBounds(top, nodes_len));
            }
            _ => {}
        }
    }

    Ok(result)
}

#[cfg(test)]
mod tests {
    use super::*;

    use crate::labelled::simple::SLGBuilder;

    #[test]
    fn test_dfs() -> Result<(), Box<dyn std::error::Error>> {
        let mut builder = SLGBuilder::<usize, usize>::default();

        // Add five nodes
        builder.add_vertex(0);
        builder.add_vertex(1);
        builder.add_vertex(2);
        builder.add_vertex(3);
        builder.add_vertex(4);

        let dummy_label = 0usize;

        builder.add_edge(0, 1, dummy_label)?;
        builder.add_edge(0, 4, dummy_label)?;
        builder.add_edge(1, 4, dummy_label)?;
        builder.add_edge(1, 2, dummy_label)?;
        builder.add_edge(2, 3, dummy_label)?;
        builder.add_edge(3, 4, dummy_label)?;

        // build a graph

        let graph = builder.build();

        let dfs = dfs(&graph, 0)?;

        println!("dfs = {dfs:?}");

        let answer = vec![0, 1, 4, 2, 3];

        assert_eq!(answer, dfs);

        Ok(())
    }
}