tree_struct/iter.rs
1use super::*;
2use std::collections::VecDeque;
3
4/// An [`Iterator`] over all the [`Node`]s of a [`Tree`] (or subtree) using a **Breadth-First Search** algorithm.
5///
6/// Obtained by calling [`Tree::iter_bfs()`] or [`Node::iter_bfs()`].
7///
8/// There is also [`IterDFS`], which uses *Depth-First search*, but **BFS** is usually *faster* in most scenarios.
9pub struct IterBFS<'a, T> {
10 /* Apparently a Vec would perform better than a LinkedList in this case.
11 https://stackoverflow.com/questions/40848918/are-there-queue-and-stack-collections-in-rust */
12 queue: VecDeque<&'a Node<T>>,
13}
14impl<'a, T> IterBFS<'a, T> {
15 pub(crate) fn new(node: &'a Node<T>) -> Self {
16 let mut queue = VecDeque::new();
17 // Step 1: Enqueue the root.
18 queue.push_back(node);
19 Self { queue }
20 }
21}
22impl<'a, T> Iterator for IterBFS<'a, T> {
23 type Item = &'a Node<T>;
24
25 fn next(&mut self) -> Option<Self::Item> {
26 // Step 2: Get next from queue.
27 let popped = self.queue.pop_front();
28 if let Some(popped) = popped {
29 // Step 3: Enqueue its children.
30 self.queue.extend(popped.children().iter());
31 }
32 popped
33 }
34}
35
36/// An [`Iterator`] over all the [`Node`]s of a [`Tree`] (or subtree) using a **non-recursive**, **Depth-First Search** algorithm.
37///
38/// Obtained by calling [`Tree::iter_dfs()`] or [`Node::iter_dfs()`].
39///
40/// You should most likely use [`IterBFS`], which uses *Breadth-First search*, becase it is usually *faster* in most scenarios.
41pub struct IterDFS<'a, T> {
42 /* Apparently a Vec would perform better than a LinkedList in this case.
43 https://stackoverflow.com/questions/40848918/are-there-queue-and-stack-collections-in-rust */
44 stack: Vec<&'a Node<T>>,
45}
46impl<'a, T> IterDFS<'a, T> {
47 pub(crate) fn new(node: &'a Node<T>) -> Self {
48 // Step 1: Push the root.
49 Self { stack: vec![node] }
50 }
51}
52impl<'a, T> Iterator for IterDFS<'a, T> {
53 type Item = &'a Node<T>;
54
55 fn next(&mut self) -> Option<Self::Item> {
56 // Step 2: Get next from stack.
57 let popped = self.stack.pop();
58 if let Some(popped) = popped {
59 // Step 3: Push its children.
60 // Reverse because the first child should be popped next from the stack, so it must go last in the stack.
61 self.stack.extend(popped.children().iter().rev());
62 }
63 popped
64 }
65}