orx_tree/traversal/breadth_first/
traverser.rs

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

orx_tree/traversal/breadth_first/
traverser.rs
