bitstring_trees/tree/
path.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
use bitstring::BitString as _;

use super::{
	goto::{
		LookupStepWith,
		NodeRef as _,
	},
	IterMutPath,
	Node,
	TreeProperties,
};

/// Iterate over all nodes that are a prefix of target key
pub struct MutPath<'r, TP: TreeProperties> {
	start: bool,
	current: Option<&'r mut Node<TP>>,
	target: TP::Key,
	target_len: usize,
}

impl<'r, TP: TreeProperties> MutPath<'r, TP> {
	pub(in crate::tree) fn new(root: Option<&'r mut Node<TP>>, key: TP::Key) -> Self {
		Self {
			start: true,
			current: root,
			target_len: key.len(),
			target: key,
		}
	}

	/// Next step towards target node
	#[allow(clippy::should_implement_trait)] // iterator doesn't allow using lifetime of itself in item
	pub fn next(&mut self) -> Option<&mut Node<TP>> {
		let lookup_step = if self.start {
			self.start = false;
			self.current
				.take()?
				.lookup_initial_step(&self.target, self.target_len)
		} else {
			self.current
				.take()?
				.lookup_step(&self.target, self.target_len)
		};

		match lookup_step {
			LookupStepWith::Found(node, _) => Some(node),
			LookupStepWith::Path(node, _) => {
				self.current = Some(node);
				Some(self.current.as_mut()?)
			},
			LookupStepWith::Miss => None,
		}
	}
}

impl<'r, TP: TreeProperties> IntoIterator for MutPath<'r, TP> {
	type IntoIter = IterMutPath<'r, TP>;
	type Item = (
		&'r TP::Key,
		&'r mut TP::Value,
		Option<&'r mut TP::LeafValue>,
	);

	fn into_iter(self) -> Self::IntoIter {
		IterMutPath::new(self)
	}
}

/// Iterate over all nodes that are a prefix of target key
pub struct IterPath<'r, TP: TreeProperties> {
	start: bool,
	current: Option<&'r Node<TP>>,
	target: TP::Key,
	target_len: usize,
}

impl<'r, TP: TreeProperties> IterPath<'r, TP> {
	pub(in crate::tree) fn new(node: Option<&'r Node<TP>>, key: TP::Key) -> Self {
		Self {
			start: true,
			current: node,
			target_len: key.len(),
			target: key,
		}
	}
}

impl<'r, TP: TreeProperties> Iterator for IterPath<'r, TP> {
	type Item = &'r Node<TP>;

	fn next(&mut self) -> Option<&'r Node<TP>> {
		let current = self.current.take()?;
		let lookup_step = if self.start {
			self.start = false;
			current.lookup_initial_step(&self.target, self.target_len)
		} else {
			current.lookup_step(&self.target, self.target_len)
		};

		match lookup_step {
			LookupStepWith::Found(node, _) => Some(node),
			LookupStepWith::Path(node, _) => {
				self.current = Some(node);
				Some(node)
			},
			LookupStepWith::Miss => None,
		}
	}
}