bitstring_trees/tree/
iter.rs

1use super::{
2	Node,
3	Tree,
4	TreeProperties,
5	Walk,
6	WalkedDirection,
7};
8use crate::iter::{
9	iter_between,
10	IterBetween,
11};
12
13/// Iterate over node of tree depth-first pre-order
14pub struct IterPreOrder<'r, TP: TreeProperties> {
15	walk: Walk<'r, TP, WalkedDirection>,
16}
17
18impl<'r, TP: TreeProperties> IterPreOrder<'r, TP> {
19	pub(in crate::tree) fn new(tree: &'r Tree<TP>) -> Self {
20		Self { walk: tree.walk() }
21	}
22}
23
24impl<'r, TP: TreeProperties> Iterator for IterPreOrder<'r, TP> {
25	type Item = &'r Node<TP>;
26
27	fn next(&mut self) -> Option<Self::Item> {
28		self.walk.next_pre_order()
29	}
30}
31
32/// Iterate over node of tree depth-first in-order
33pub struct IterInOrder<'r, TP: TreeProperties> {
34	walk: Walk<'r, TP, WalkedDirection>,
35}
36
37impl<'r, TP: TreeProperties> IterInOrder<'r, TP> {
38	pub(in crate::tree) fn new(tree: &'r Tree<TP>) -> Self {
39		Self { walk: tree.walk() }
40	}
41}
42
43impl<'r, TP: TreeProperties> Iterator for IterInOrder<'r, TP> {
44	type Item = &'r Node<TP>;
45
46	fn next(&mut self) -> Option<Self::Item> {
47		self.walk.next_in_order()
48	}
49}
50
51/// Iterate over node of tree depth-first post-order
52pub struct IterPostOrder<'r, TP: TreeProperties> {
53	walk: Walk<'r, TP, WalkedDirection>,
54}
55
56impl<'r, TP: TreeProperties> IterPostOrder<'r, TP> {
57	pub(in crate::tree) fn new(tree: &'r Tree<TP>) -> Self {
58		Self { walk: tree.walk() }
59	}
60}
61
62impl<'r, TP: TreeProperties> Iterator for IterPostOrder<'r, TP> {
63	type Item = &'r Node<TP>;
64
65	fn next(&mut self) -> Option<Self::Item> {
66		self.walk.next_post_order()
67	}
68}
69
70/// Iterate over nodes and leaf values of tree in-order
71pub struct IterLeaf<'r, TP: TreeProperties> {
72	walk: Walk<'r, TP, WalkedDirection>,
73}
74
75impl<'r, TP: TreeProperties> IterLeaf<'r, TP> {
76	pub(in crate::tree) fn new(tree: &'r Tree<TP>) -> Self {
77		Self { walk: tree.walk() }
78	}
79}
80
81impl<'r, TP: TreeProperties> Iterator for IterLeaf<'r, TP> {
82	type Item = (&'r Node<TP>, &'r TP::LeafValue);
83
84	fn next(&mut self) -> Option<Self::Item> {
85		let node = self.walk.next_leaf()?;
86		Some((node, node.get_leaf_value().expect("leaf node")))
87	}
88}
89
90/// Iterate over keys and mutable leaf values and uncovered keys of tree in-order
91pub struct IterLeafFull<'r, TP: TreeProperties> {
92	walk: Option<Walk<'r, TP, WalkedDirection>>,
93	previous_key: Option<TP::Key>,
94	uncovered: IterBetween<TP::Key>,
95	next: Option<(TP::Key, &'r TP::LeafValue)>,
96}
97
98impl<'r, TP: TreeProperties> IterLeafFull<'r, TP> {
99	pub(in crate::tree) fn new(tree: &'r Tree<TP>) -> Self {
100		Self {
101			walk: Some(tree.walk()),
102			previous_key: None,
103			uncovered: Default::default(),
104			next: None,
105		}
106	}
107}
108
109impl<'r, TP: TreeProperties> Iterator for IterLeafFull<'r, TP> {
110	type Item = (TP::Key, Option<&'r TP::LeafValue>);
111
112	fn next(&mut self) -> Option<Self::Item> {
113		loop {
114			if let Some(k) = self.uncovered.next() {
115				return Some((k, None));
116			}
117			if let Some((key, value)) = self.next.take() {
118				return Some((key, Some(value)));
119			}
120			match self.walk.as_mut()?.next_leaf() {
121				None => {
122					self.walk = None;
123					// return final uncovered prefixes
124					self.uncovered = iter_between(self.previous_key.clone(), None);
125				},
126				Some(node) => {
127					// safety: only once per node per iteration
128					let key = node.get_key().clone();
129					let leaf_value = node.get_leaf_value().expect("leaf node");
130					// return uncovered prefixes before
131					let start = core::mem::replace(&mut self.previous_key, Some(key.clone()));
132					self.uncovered = iter_between(start, Some(key.clone()));
133					self.next = Some((key, leaf_value));
134				},
135			}
136		}
137	}
138}
bitstring_trees/tree/iter.rs

bitstring_trees/tree/
iter.rs
