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}
tree_struct/iter.rs

tree_struct/
iter.rs
