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![
107 Node {
108 value: 6,
109 children: vec![],
110 },
111 ],
112 },
113 ],
114 };
115
116 let values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
117 assert_eq!(values, vec![1, 2, 4, 5, 3, 6]);
118 }
119
120 #[test]
121 fn test_breadth_first_traversal() {
122 let tree = Node {
123 value: 1,
124 children: vec![
125 Node {
126 value: 2,
127 children: vec![
128 Node {
129 value: 4,
130 children: vec![],
131 },
132 Node {
133 value: 5,
134 children: vec![],
135 },
136 ],
137 },
138 Node {
139 value: 3,
140 children: vec![
141 Node {
142 value: 6,
143 children: vec![],
144 },
145 ],
146 },
147 ],
148 };
149
150 let values: Vec<i32> = tree.iter::<BreadthFirst>().map(|n| n.value).collect();
151 assert_eq!(values, vec![1, 2, 3, 4, 5, 6]);
152 }
153
154 #[test]
155 fn test_mutable_depth_first_traversal() {
156 let mut tree = Node {
157 value: 1,
158 children: vec![
159 Node {
160 value: 2,
161 children: vec![],
162 },
163 Node {
164 value: 3,
165 children: vec![],
166 },
167 ],
168 };
169
170 // Double each value in the tree
171 let mut iter = tree.iter_mut::<DepthFirst>();
172 while let Some(mut node) = iter.next() {
173 node.value *= 2;
174 }
175
176 // Verify values were changed
177 let values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
178 assert_eq!(values, vec![2, 4, 6]);
179 }
180
181 #[test]
182 fn test_mutable_breadth_first_traversal() {
183 let mut tree = Node {
184 value: 1,
185 children: vec![
186 Node {
187 value: 2,
188 children: vec![
189 Node {
190 value: 4,
191 children: vec![],
192 },
193 ],
194 },
195 Node {
196 value: 3,
197 children: vec![],
198 },
199 ],
200 };
201
202 // Add 10 to each value in the tree
203 let mut iter = tree.iter_mut::<BreadthFirst>();
204 while let Some(mut node) = iter.next() {
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]);
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 tree = Node {
254 value: 1,
255 children: vec![
256 Node {
257 value: 2,
258 children: vec![
259 Node {
260 value: 4,
261 children: vec![
262 Node {
263 value: 7,
264 children: vec![],
265 },
266 ],
267 },
268 Node {
269 value: 5,
270 children: vec![],
271 },
272 ],
273 },
274 Node {
275 value: 3,
276 children: vec![
277 Node {
278 value: 6,
279 children: vec![
280 Node {
281 value: 8,
282 children: vec![],
283 },
284 Node {
285 value: 9,
286 children: vec![],
287 },
288 ],
289 },
290 ],
291 },
292 ],
293 };
294
295 // Test depth-first traversal
296 let df_values: Vec<i32> = tree.iter::<DepthFirst>().map(|n| n.value).collect();
297 assert_eq!(df_values, vec![1, 2, 4, 7, 5, 3, 6, 8, 9]);
298
299 // Test breadth-first traversal
300 let bf_values: Vec<i32> = tree.iter::<BreadthFirst>().map(|n| n.value).collect();
301 assert_eq!(bf_values, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
302 }
303}