ntree_rs/traversal/traverse_owned/
mod.rs

1//! Traversal algorithms for an owned instance 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::{Asynchronous, Node, Synchronous};
12use std::{marker::PhantomData, ops::Not};
13
14/// Implements the traverse algorithms for an owned instance of [`Node`].
15pub struct TraverseOwned<T, S> {
16    node: Node<T>,
17    strategy: PhantomData<S>,
18}
19
20impl<T, S> From<Node<T>> for TraverseOwned<T, S> {
21    fn from(node: Node<T>) -> Self {
22        Self {
23            node,
24            strategy: PhantomData,
25        }
26    }
27}
28
29impl<T> From<TraverseOwned<T, Asynchronous>> for TraverseOwned<T, Synchronous> {
30    fn from(value: TraverseOwned<T, Asynchronous>) -> Self {
31        TraverseOwned::new(value.node)
32    }
33}
34
35impl<T> From<TraverseOwned<T, Synchronous>> for TraverseOwned<T, Asynchronous>
36where
37    T: Sync + Send,
38{
39    fn from(value: TraverseOwned<T, Synchronous>) -> Self {
40        TraverseOwned::new_async(value.node)
41    }
42}
43
44impl<T, S> TraverseOwned<T, S> {
45    pub fn node(&self) -> &Node<T> {
46        &self.node
47    }
48
49    pub fn node_mut(&mut self) -> &mut Node<T> {
50        &mut self.node
51    }
52
53    pub fn take(self) -> Node<T> {
54        self.node
55    }
56
57    /// Returns the `pre-order` traversal entity for the tree.
58    pub fn pre(self) -> InPreOwned<T, S> {
59        InPreOwned {
60            next: vec![self.node],
61            strategy: PhantomData,
62        }
63    }
64
65    /// Returns the `post-order` traversal entity for the tree.
66    pub fn post(self) -> InPostOwned<T, S> {
67        InPostOwned {
68            next: vec![self.node],
69            strategy: PhantomData,
70        }
71    }
72}
73
74/// Represents the `pre-order` traversal.
75pub struct InPreOwned<T, S> {
76    next: Vec<Node<T>>,
77    strategy: PhantomData<S>,
78}
79
80impl<T, S> Iterator for InPreOwned<T, S> {
81    type Item = T;
82
83    fn next(&mut self) -> Option<Self::Item> {
84        let current = self.next.pop()?;
85        self.next.extend(current.children.into_iter().rev());
86        Some(current.value)
87    }
88}
89
90/// Represents the `post-order` traversal.
91pub struct InPostOwned<T, S> {
92    next: Vec<Node<T>>,
93    strategy: PhantomData<S>,
94}
95
96impl<T, S> Iterator for InPostOwned<T, S> {
97    type Item = Node<T>;
98
99    fn next(&mut self) -> Option<Self::Item> {
100        let mut parent = self.next.pop()?;
101
102        if let Some(next_child) = parent
103            .children
104            .is_empty()
105            .not()
106            .then(|| parent.children.drain(0..1))
107            .and_then(|mut drain| drain.next())
108        {
109            self.next.push(parent);
110            self.next.push(next_child);
111            return self.next();
112        }
113
114        Some(parent)
115    }
116}
117
118/// Implements both traversals at once.
119pub struct PrePostOwned<T, R, F, S> {
120    node: Node<T>,
121    pre: F,
122    r: PhantomData<R>,
123    strategy: PhantomData<S>,
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129    use crate::node;
130
131    #[test]
132    fn test_pre_order_traversal() {
133        let root = node!(
134            10,
135            node!(20, node!(40), node!(50), node!(60)),
136            node!(30, node!(70), node!(80))
137        );
138
139        let mut result = Vec::new();
140        root.into_traverse().pre().for_each(|n| result.push(n));
141
142        assert_eq!(result, vec![10, 20, 40, 50, 60, 30, 70, 80]);
143    }
144
145    #[test]
146    fn test_post_order_traversal() {
147        let root = node!(
148            10,
149            node!(20, node!(40), node!(50), node!(60)),
150            node!(30, node!(70), node!(80))
151        );
152
153        let mut result = Vec::new();
154        root.into_traverse()
155            .post()
156            .for_each(|n| result.push(n.value));
157
158        assert_eq!(result, vec![40, 50, 60, 20, 70, 80, 30, 10]);
159    }
160}
ntree_rs/traversal/traverse_owned/mod.rs

ntree_rs/traversal/traverse_owned/
mod.rs
