tree_traversal 0.5.0

Find best leaf node in a tree
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

use std::iter::FusedIterator;

use crate::node::TreeNode;

use super::functional::dfs_reach;

/// Depth-First traversal implementation.
pub struct DepthFirstTraversal<N> {
    state: Box<dyn FusedIterator<Item = N>>,
}

impl<C, N> DepthFirstTraversal<N>
where
    C: Copy + Ord + 'static,
    N: TreeNode<Cost = C> + 'static,
{
    /// Creates a new `DepthFirstTraversal` instance that performs a depth-first search starting from the given root node.
    ///
    /// Depth-first search explores as far as possible along each branch before backtracking.
    ///
    /// # Parameters
    /// - `root_node`: The starting node for the traversal.
    ///
    /// # Returns
    /// A new `DepthFirstTraversal` iterator.
    pub fn new(root_node: N) -> Self {
        let state = dfs_reach(root_node, |n: &N| n.generate_child_nodes());
        Self {
            state: Box::new(state),
        }
    }
}

impl<N> Iterator for DepthFirstTraversal<N> {
    type Item = N;

    fn next(&mut self) -> Option<Self::Item> {
        self.state.next()
    }
}

impl<N> FusedIterator for DepthFirstTraversal<N> {}