bitstring_trees/tree/
path.rs

1use bitstring::BitString as _;
2
3use super::{
4	goto::{
5		LookupStepWith,
6		NodeRef as _,
7	},
8	IterMutPath,
9	Node,
10	TreeProperties,
11};
12
13/// Iterate over all nodes that are a prefix of target key
14pub struct MutPath<'r, TP: TreeProperties> {
15	start: bool,
16	current: Option<&'r mut Node<TP>>,
17	target: TP::Key,
18	target_len: usize,
19}
20
21impl<'r, TP: TreeProperties> MutPath<'r, TP> {
22	pub(in crate::tree) fn new(root: Option<&'r mut Node<TP>>, key: TP::Key) -> Self {
23		Self {
24			start: true,
25			current: root,
26			target_len: key.len(),
27			target: key,
28		}
29	}
30
31	/// Next step towards target node
32	#[allow(clippy::should_implement_trait)] // iterator doesn't allow using lifetime of itself in item
33	pub fn next(&mut self) -> Option<&mut Node<TP>> {
34		let lookup_step = if self.start {
35			self.start = false;
36			self.current
37				.take()?
38				.lookup_initial_step(&self.target, self.target_len)
39		} else {
40			self.current
41				.take()?
42				.lookup_step(&self.target, self.target_len)
43		};
44
45		match lookup_step {
46			LookupStepWith::Found(node, _) => Some(node),
47			LookupStepWith::Path(node, _) => {
48				self.current = Some(node);
49				Some(self.current.as_mut()?)
50			},
51			LookupStepWith::Miss => None,
52		}
53	}
54}
55
56impl<'r, TP: TreeProperties> IntoIterator for MutPath<'r, TP> {
57	type IntoIter = IterMutPath<'r, TP>;
58	type Item = (
59		&'r TP::Key,
60		&'r mut TP::Value,
61		Option<&'r mut TP::LeafValue>,
62	);
63
64	fn into_iter(self) -> Self::IntoIter {
65		IterMutPath::new(self)
66	}
67}
68
69/// Iterate over all nodes that are a prefix of target key
70pub struct IterPath<'r, TP: TreeProperties> {
71	start: bool,
72	current: Option<&'r Node<TP>>,
73	target: TP::Key,
74	target_len: usize,
75}
76
77impl<'r, TP: TreeProperties> IterPath<'r, TP> {
78	pub(in crate::tree) fn new(node: Option<&'r Node<TP>>, key: TP::Key) -> Self {
79		Self {
80			start: true,
81			current: node,
82			target_len: key.len(),
83			target: key,
84		}
85	}
86}
87
88impl<'r, TP: TreeProperties> Iterator for IterPath<'r, TP> {
89	type Item = &'r Node<TP>;
90
91	fn next(&mut self) -> Option<&'r Node<TP>> {
92		let current = self.current.take()?;
93		let lookup_step = if self.start {
94			self.start = false;
95			current.lookup_initial_step(&self.target, self.target_len)
96		} else {
97			current.lookup_step(&self.target, self.target_len)
98		};
99
100		match lookup_step {
101			LookupStepWith::Found(node, _) => Some(node),
102			LookupStepWith::Path(node, _) => {
103				self.current = Some(node);
104				Some(node)
105			},
106			LookupStepWith::Miss => None,
107		}
108	}
109}
bitstring_trees/tree/path.rs

bitstring_trees/tree/
path.rs
