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::bfs_reach;

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

impl<C, N> BreadthFirstTraversal<N>
where
    C: Copy + Ord + 'static,
    N: TreeNode<Cost = C> + 'static,
{
    /// Creates a new `BreadthFirstTraversal` instance that performs a breadth-first search starting from the given root node.
    ///
    /// Breadth-first search explores nodes level by level, visiting all nodes at the current depth before moving to the next.
    ///
    /// # Parameters
    /// - `root_node`: The starting node for the traversal.
    ///
    /// # Returns
    /// A new `BreadthFirstTraversal` iterator.
    pub fn new(root_node: N) -> Self {
        let state = bfs_reach(root_node, |n: &N| n.generate_child_nodes());
        Self {
            state: Box::new(state),
        }
    }
}

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

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

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