tree_iter/tree.rs
1use crate::{iter::TreeNode, prelude::TreeNodeMut};
2
3/// A generic tree node implementation.
4///
5/// This struct provides a simple implementation of a tree node with a value and a vector of children.
6/// It implements both `TreeNode` and `TreeNodeMut` traits, allowing it to be used with both
7/// immutable and mutable iterators.
8///
9/// # Type Parameters
10///
11/// * `T` - The type of value stored in each node.
12///
13/// # Examples
14///
15/// ```rust
16/// use tree_iter::tree::Node;
17/// use tree_iter::prelude::*;
18///
19/// // Create a simple tree
20/// let tree = Node {
21/// value: 1,
22/// children: vec![
23/// Node {
24/// value: 2,
25/// children: vec![],
26/// },
27/// Node {
28/// value: 3,
29/// children: vec![],
30/// },
31/// ],
32/// };
33///
34/// // Traverse in depth-first order
35/// let values: Vec<i32> = tree.iter::<DepthFirst>()
36/// .map(|node| node.value)
37/// .collect();
38/// assert_eq!(values, vec![1, 2, 3]);
39/// ```
40pub struct Node<T> {
41 /// The value stored in this node.
42 pub value: T,
43 /// The children of this node.
44 pub children: Vec<Node<T>>,
45}
46
47/// Implementation of `TreeNode` for `Node<T>`.
48///
49/// This allows immutable iteration over the tree.
50impl<T> TreeNode for Node<T> {
51 /// Returns an iterator over the children of this node.
52 fn children(&self) -> impl DoubleEndedIterator<Item = &Self> + '_ {
53 self.children.iter()
54 }
55}
56
57/// Implementation of `TreeNodeMut` for `Node<T>`.
58///
59/// This allows mutable iteration over the tree.
60impl<T> TreeNodeMut for Node<T> {
61 /// Returns a mutable iterator over the children of this node.
62 fn children_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut Self> + '_ {
63 self.children.iter_mut()
64 }
65}
66
67#[cfg(test)]
68mod tests {
69 use super::*;
70 use crate::prelude::*;
71
72 #[test]
73 fn test_empty_tree() {
74 let tree: Node<i32> = Node {
75 value: 42,
76 children: vec![],
77 };
78
79 let values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
80 assert_eq!(values, vec![42]);
81
82 let values: Vec<i32> = tree.iter::<BreadthFirst>().map(|n| n.value).collect();
83 assert_eq!(values, vec![42]);
84 }
85
86 #[test]
87 fn test_depth_first_traversal() {
88 let tree = Node {
89 value: 1,
90 children: vec![
91 Node {
92 value: 2,
93 children: vec![
94 Node {
95 value: 4,
96 children: vec![],
97 },
98 Node {
99 value: 5,
100 children: vec![],
101 },
102 ],
103 },
104 Node {
105 value: 3,
106 children: vec![Node {
107 value: 6,
108 children: vec![],
109 }],
110 },
111 ],
112 };
113
114 let values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
115 assert_eq!(values, vec![1, 2, 4, 5, 3, 6]);
116 }
117
118 #[test]
119 fn test_breadth_first_traversal() {
120 let tree = Node {
121 value: 1,
122 children: vec![
123 Node {
124 value: 2,
125 children: vec![
126 Node {
127 value: 4,
128 children: vec![],
129 },
130 Node {
131 value: 5,
132 children: vec![],
133 },
134 ],
135 },
136 Node {
137 value: 3,
138 children: vec![Node {
139 value: 6,
140 children: vec![],
141 }],
142 },
143 ],
144 };
145
146 let values: Vec<i32> = tree.iter::<BreadthFirst>().map(|n| n.value).collect();
147 assert_eq!(values, vec![1, 2, 3, 4, 5, 6]);
148 }
149
150 #[test]
151 fn test_mutable_depth_first_traversal() {
152 let mut tree = Node {
153 value: 1,
154 children: vec![
155 Node {
156 value: 2,
157 children: vec![],
158 },
159 Node {
160 value: 3,
161 children: vec![],
162 },
163 ],
164 };
165
166 // Double each value in the tree
167 let mut iter = tree.iter_mut::<DepthFirst>();
168 while let Some(mut node) = iter.next() {
169 node.value *= 2;
170 }
171
172 // Verify values were changed
173 let values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
174 assert_eq!(values, vec![2, 4, 6]);
175 }
176
177 #[test]
178 fn test_mutable_breadth_first_traversal() {
179 let mut tree = Node {
180 value: 1,
181 children: vec![
182 Node {
183 value: 2,
184 children: vec![Node {
185 value: 4,
186 children: vec![],
187 }],
188 },
189 Node {
190 value: 3,
191 children: vec![],
192 },
193 ],
194 };
195
196 // Add 10 to each value in the tree, and add a child to node with value 2
197 let mut iter = tree.iter_mut::<BreadthFirst>();
198 while let Some(mut node) = iter.next() {
199 if node.value == 2 {
200 node.children.push(Node {
201 value: 10,
202 children: vec![],
203 });
204 }
205 node.value += 10;
206 }
207
208 // Verify values were changed in breadth-first order
209 let values: Vec<i32> = tree.iter::<BreadthFirst>().map(|n| n.value).collect();
210 assert_eq!(values, vec![11, 12, 13, 14, 20]);
211 }
212
213 #[test]
214 fn test_tree_modification() {
215 // Create a tree manually with specific structure
216 let mut tree = Node {
217 value: 1,
218 children: vec![
219 Node {
220 value: 2,
221 children: vec![],
222 },
223 Node {
224 value: 3,
225 children: vec![],
226 },
227 ],
228 };
229
230 // Verify initial structure
231 let initial_values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
232 assert_eq!(initial_values, vec![1, 2, 3]);
233
234 // Modify the tree directly, avoiding iterator with borrow issues
235 tree.children[0].children.push(Node {
236 value: 20,
237 children: vec![],
238 });
239
240 tree.children[1].children.push(Node {
241 value: 30,
242 children: vec![],
243 });
244
245 // Verify the modified structure
246 let final_values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
247 assert_eq!(final_values, vec![1, 2, 20, 3, 30]);
248 }
249
250 #[test]
251 fn test_complex_tree_traversal() {
252 // Create a more complex tree
253 let mut tree = Node {
254 value: 1,
255 children: vec![
256 Node {
257 value: 2,
258 children: vec![
259 Node {
260 value: 4,
261 children: vec![Node {
262 value: 7,
263 children: vec![],
264 }],
265 },
266 Node {
267 value: 5,
268 children: vec![],
269 },
270 ],
271 },
272 Node {
273 value: 3,
274 children: vec![Node {
275 value: 6,
276 children: vec![
277 Node {
278 value: 8,
279 children: vec![],
280 },
281 Node {
282 value: 9,
283 children: vec![],
284 },
285 ],
286 }],
287 },
288 ],
289 };
290
291 // Test depth-first traversal
292 let df_values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
293 assert_eq!(df_values, vec![1, 2, 4, 7, 5, 3, 6, 8, 9]);
294
295 // Test mutable depth-first traversal
296 let mut df_values_mut = vec![];
297 let mut iter = tree.iter_mut::<DepthFirst>();
298 while let Some(node) = iter.next() {
299 df_values_mut.push(node.value);
300 }
301 assert_eq!(df_values_mut, vec![1, 2, 4, 7, 5, 3, 6, 8, 9]);
302
303 // Test breadth-first traversal
304 let bf_values: Vec<i32> = tree.iter::<BreadthFirst>().map(|n| n.value).collect();
305 assert_eq!(bf_values, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
306
307 // Test mutable breadth-first traversal
308 let mut bf_values_mut = vec![];
309 let mut iter = tree.iter_mut::<BreadthFirst>();
310 while let Some(node) = iter.next() {
311 bf_values_mut.push(node.value);
312 }
313 assert_eq!(bf_values_mut, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
314 }
315}