ntree_rs/traversal/traverse/
mod.rs

1//! Traversal algorithms for an immutable reference of [Node].
2
3#[cfg(feature = "async")]
4mod r#async;
5#[cfg(feature = "async")]
6pub use r#async::*;
7
8mod sync;
9pub use sync::*;
10
11use crate::Node;
12use std::marker::PhantomData;
13
14/// Implements the traverse algorithms for an immutable reference of a [`Node`].
15pub struct Traverse<'a, T, S> {
16    node: &'a Node<T>,
17    strategy: PhantomData<S>,
18}
19
20impl<'a, T, S> From<&'a Node<T>> for Traverse<'a, T, S> {
21    fn from(node: &'a Node<T>) -> Self {
22        Self {
23            node,
24            strategy: PhantomData,
25        }
26    }
27}
28
29impl<'a, T, S> Traverse<'a, T, S> {
30    pub fn node(&self) -> &Node<T> {
31        self.node
32    }
33
34    /// Returns the `pre-order` traversal entity for the tree.
35    pub fn pre(self) -> InPre<'a, T, S> {
36        InPre {
37            node: self.node,
38            next: vec![self.node],
39            strategy: PhantomData,
40        }
41    }
42
43    /// Returns the `post-order` traversal entity for the tree.
44    pub fn post(self) -> InPost<'a, T, S> {
45        InPost {
46            node: self.node,
47            next: vec![(self.node, 0)],
48            strategy: PhantomData,
49        }
50    }
51}
52
53/// Represents the `pre-order` traversal.
54pub struct InPre<'a, T, S> {
55    node: &'a Node<T>,
56    next: Vec<&'a Node<T>>,
57    strategy: PhantomData<S>,
58}
59
60impl<'a, T, S> Iterator for InPre<'a, T, S> {
61    type Item = &'a Node<T>;
62
63    fn next(&mut self) -> Option<Self::Item> {
64        let current = self.next.pop()?;
65        self.next.extend(current.children.iter().rev());
66        Some(current)
67    }
68}
69
70impl<'a, T, S> InPre<'a, T, S> {
71    pub fn iter(self) -> impl Iterator<Item = &'a Node<T>> {
72        self
73    }
74}
75
76/// Represents the `post-order` traversal.
77pub struct InPost<'a, T, S> {
78    node: &'a Node<T>,
79    next: Vec<(&'a Node<T>, usize)>,
80    strategy: PhantomData<S>,
81}
82
83impl<'a, T, S> Iterator for InPost<'a, T, S> {
84    type Item = &'a Node<T>;
85
86    fn next(&mut self) -> Option<Self::Item> {
87        let (parent, next_child) = *self.next.last()?;
88        if let Some(next_child) = parent.children.get(next_child) {
89            self.next.last_mut()?.1 += 1;
90            self.next.push((next_child, 0));
91            return self.next();
92        }
93
94        self.next.pop().map(|(parent, _)| parent)
95    }
96}
97
98impl<'a, T, S> InPost<'a, T, S> {
99    pub fn iter(self) -> impl Iterator<Item = &'a Node<T>> {
100        self
101    }
102}
103
104/// Implements both traversals at once.
105pub struct PrePost<'a, T, R, F, S> {
106    node: &'a Node<T>,
107    pre: F,
108    r: PhantomData<R>,
109    strategy: PhantomData<S>,
110}
111
112#[cfg(test)]
113mod tests {
114    use super::*;
115    use crate::node;
116
117    #[test]
118    fn test_pre_order_traversal() {
119        let root = node!(
120            10,
121            node!(20, node!(40), node!(50), node!(60)),
122            node!(30, node!(70), node!(80))
123        );
124
125        let mut result = Vec::new();
126        root.traverse()
127            .pre()
128            .iter()
129            .for_each(|n| result.push(n.value));
130
131        assert_eq!(result, vec![10, 20, 40, 50, 60, 30, 70, 80]);
132    }
133
134    #[test]
135    fn test_post_order_traversal() {
136        let root = node!(
137            10,
138            node!(20, node!(40), node!(50), node!(60)),
139            node!(30, node!(70), node!(80))
140        );
141
142        let mut result = Vec::new();
143        root.traverse()
144            .post()
145            .iter()
146            .for_each(|n| result.push(n.value));
147
148        assert_eq!(result, vec![40, 50, 60, 20, 70, 80, 30, 10]);
149    }
150}
ntree_rs/traversal/traverse/mod.rs

ntree_rs/traversal/traverse/
mod.rs
