tree_traversal 0.5.0

use std::iter::FusedIterator;

use crate::node::{Priority, TreeNode};

use super::functional::gds_reach;

/// Greedy traversal implementation.
pub struct GreedyTraversal<N> {
    state: Box<dyn FusedIterator<Item = N>>,
}

impl<C, N> GreedyTraversal<N>
where
    C: Copy + Ord + 'static,
    N: TreeNode<Cost = C> + Priority + 'static,
{
    /// Creates a new `GreedyTraversal` instance that performs a greedy search starting from the given root node.
    ///
    /// Greedy search always chooses the locally optimal choice at each step, aiming for an approximate solution.
    ///
    /// # Parameters
    /// - `root_node`: The starting node for the traversal.
    ///
    /// # Returns
    /// A new `GreedyTraversal` iterator.
    pub fn new(root_node: N) -> Self {
        let state = gds_reach(
            root_node,
            |n: &N| n.generate_child_nodes(),
            |n: &N| n.priority(),
        );
        Self {
            state: Box::new(state),
        }
    }
}

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

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

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