orx_tree/traversal/depth_first/
traverser.rs

1use super::stack::Stack;
2use crate::traversal::{
3    over::{Over, OverData},
4    traverser::Traverser,
5};
6
7/// A (pre-order) depth first search traverser ([Wikipedia](https://en.wikipedia.org/wiki/Depth-first_search)).
8///
9/// A traverser can be created once and used to traverse over trees multiple times without
10/// requiring additional memory allocation.
11///
12/// # Construction
13///
14/// A depth first traverser can be created,
15/// * either by using Default trait and providing its two generic type parameters
16///   * `Dfs::<_, OverData>::default()` or `Dfs::<_, OverDepthSiblingIdxData>::default()`, or
17///   * `Dfs::<Dyn<u64>, OverData>::default()` or `Dfs::<Dary<2, String>, OverDepthSiblingIdxData>::default()`
18///     if we want the complete type signature.
19/// * or by using the [`Traversal`] type.
20///   * `Traversal.dfs()` or `Traversal.dfs().with_depth().with_sibling_idx()`.
21///
22/// [`Traversal`]: crate::Traversal
23pub struct Dfs<O = OverData>
24where
25    O: Over,
26{
27    pub(super) stack: Stack<O::Enumeration>,
28}
29
30impl Default for Dfs {
31    fn default() -> Self {
32        Self::new()
33    }
34}
35
36impl<O> Traverser<O> for Dfs<O>
37where
38    O: Over,
39{
40    type IntoOver<O2>
41        = Dfs<O2>
42    where
43        O2: Over;
44
45    fn new() -> Self {
46        Self {
47            stack: Default::default(),
48        }
49    }
50
51    fn transform_into<O2: Over>(self) -> Self::IntoOver<O2> {
52        Dfs::<O2>::new()
53    }
54}
orx_tree/traversal/depth_first/traverser.rs

orx_tree/traversal/depth_first/
traverser.rs
