bitstring_trees/tree/
goto.rs

1use core::ops::Deref;
2
3use bitstring::BitString as _;
4
5use super::{
6	Node,
7	TreeProperties,
8	WalkedDirection,
9};
10
11pub(in crate::tree) enum GotoStepResult<N> {
12	/// Search done; returns passed node
13	Final(InsertPositionWith<N>),
14	/// Move to next node (that might be the final node)
15	///
16	/// One of next node key and target key is a prefix of the other; in other words: they are not in different subtrees.
17	Continue(N, WalkedDirection),
18}
19
20/// Result of key lookup in tree
21///
22/// Found node is passed somewhere else (probably remembered in a "walk" stack).
23#[derive(Clone, Copy, PartialEq, Eq, Debug)]
24pub enum InsertPosition {
25	/// Found node that is a leaf; its key is a prefix of the target key (but not equal to it)
26	///
27	/// Inserting the target key must convert the found node into an inner node and insert the target key as leaf.
28	BelowLeaf,
29	/// Found node with target key
30	AlreadyExists,
31	/// Found node to replace with target key
32	///
33	/// Parent node is a prefix of target key, but this node is not.
34	///
35	/// To insert a new node needs to replace the current one, using the shared prefix of this node and the target key as node key.
36	/// (This node key could still be the target key.)
37	ReplaceNode,
38}
39
40impl<N> From<InsertPositionWith<N>> for InsertPosition {
41	fn from(value: InsertPositionWith<N>) -> Self {
42		match value {
43			InsertPositionWith::BelowLeaf(_) => Self::BelowLeaf,
44			InsertPositionWith::AlreadyExists(_) => Self::AlreadyExists,
45			InsertPositionWith::ReplaceNode(_) => Self::ReplaceNode,
46		}
47	}
48}
49
50/// Result of finding position to insert a target key
51#[derive(Debug)]
52pub enum InsertPositionWith<N> {
53	/// Found node that is a leaf; its key is a prefix of the target key (but not equal to it)
54	///
55	/// Inserting the target key must convert the found node into an inner node and insert the target key as leaf.
56	BelowLeaf(N),
57	/// Found node with target key
58	AlreadyExists(N),
59	/// Found node to replace with target key
60	///
61	/// Parent node is a prefix of target key, but this node is not.
62	///
63	/// To insert a new node needs to replace the current one, using the shared prefix of this node and the target key as node key.
64	/// (This node key could still be the target key.)
65	ReplaceNode(N),
66}
67
68pub(in crate::tree) enum LookupStep {
69	Path,
70	Found,
71	Miss,
72}
73
74impl<N> From<&LookupStepWith<N>> for LookupStep {
75	fn from(value: &LookupStepWith<N>) -> Self {
76		match value {
77			LookupStepWith::Path(_, _) => Self::Path,
78			LookupStepWith::Found(_, _) => Self::Found,
79			LookupStepWith::Miss => Self::Miss,
80		}
81	}
82}
83
84impl<N> From<LookupStepWith<N>> for LookupStep {
85	fn from(value: LookupStepWith<N>) -> Self {
86		match value {
87			LookupStepWith::Path(_, _) => Self::Path,
88			LookupStepWith::Found(_, _) => Self::Found,
89			LookupStepWith::Miss => Self::Miss,
90		}
91	}
92}
93
94#[derive(Debug)]
95pub(in crate::tree) enum LookupStepWith<N> {
96	Path(N, WalkedDirection),
97	Found(N, WalkedDirection),
98	Miss,
99}
100
101// is `a` a prefix of `b` ?
102// i.e. shared_prefix(a, b) == a ?
103pub(in crate::tree) fn is_prefix<K>(a: &K, a_len: usize, b: &K, b_len: usize) -> bool
104where
105	K: bitstring::BitString + Clone,
106{
107	if a_len > b_len {
108		return false;
109	}
110	let mut b_test = b.clone();
111	b_test.clip(a_len);
112	*a == b_test
113}
114
115pub(in crate::tree) trait NodeRef<'a, TP: TreeProperties>:
116	Sized + Deref<Target = Node<TP>>
117{
118	fn _get_child(self, side: bool) -> Option<Self>;
119
120	// first lookup step with tree root (doesn't walk down, only evaluates root node)
121	fn _lookup_check_node(
122		self,
123		key: &TP::Key,
124		key_len: usize,
125		dir: WalkedDirection,
126	) -> LookupStepWith<Self> {
127		let self_key_len = self.key.len();
128		if !is_prefix(&self.key, self_key_len, key, key_len) {
129			LookupStepWith::Miss
130		} else if self_key_len == key_len {
131			LookupStepWith::Found(self, dir)
132		} else {
133			LookupStepWith::Path(self, dir)
134		}
135	}
136
137	// first lookup step with tree root (doesn't walk down, only evaluates root node)
138	fn lookup_initial_step(self, key: &TP::Key, key_len: usize) -> LookupStepWith<Self> {
139		self._lookup_check_node(key, key_len, WalkedDirection::Down)
140	}
141
142	// only use if previous/initial step returned `LookupStep::Path`
143	// i.e. self must be a (real) prefix of the key
144	fn lookup_step(self, key: &TP::Key, key_len: usize) -> LookupStepWith<Self> {
145		let self_key_len: usize = self.key.len();
146		debug_assert!(is_prefix(&self.key, self_key_len, key, key_len));
147		debug_assert!(self_key_len < key_len);
148		let side = key.get(self_key_len);
149		match self._get_child(side) {
150			None => LookupStepWith::Miss,
151			Some(c) => c._lookup_check_node(key, key_len, WalkedDirection::from_side(side)),
152		}
153	}
154
155	fn goto_insert_step(self, key: &TP::Key, key_len: usize) -> GotoStepResult<Self> {
156		let self_key_len: usize = self.key.len();
157		if !is_prefix(&self.key, self_key_len, key, key_len) {
158			return GotoStepResult::Final(InsertPositionWith::ReplaceNode(self));
159		}
160		if self_key_len < key_len {
161			let side = key.get(self_key_len);
162			if matches!(self.state, super::NodeState::InnerNode { .. }) {
163				GotoStepResult::Continue(
164					self._get_child(side).expect("inner node"),
165					WalkedDirection::from_side(side),
166				)
167			} else {
168				GotoStepResult::Final(InsertPositionWith::BelowLeaf(self))
169			}
170		} else {
171			debug_assert_eq!(self_key_len, key_len);
172			GotoStepResult::Final(InsertPositionWith::AlreadyExists(self))
173		}
174	}
175
176	fn goto_insert(self, key: &TP::Key) -> InsertPositionWith<Self> {
177		let key_len = key.len();
178		let mut cursor = self;
179		loop {
180			cursor = match cursor.goto_insert_step(key, key_len) {
181				GotoStepResult::Continue(c, _) => c,
182				GotoStepResult::Final(f) => return f,
183			};
184		}
185	}
186}
187
188impl<'a, TP: TreeProperties> NodeRef<'a, TP> for &'a Node<TP> {
189	fn _get_child(self, side: bool) -> Option<Self> {
190		self.get_child(side)
191	}
192}
193
194impl<'a, TP: TreeProperties> NodeRef<'a, TP> for &'a mut Node<TP> {
195	fn _get_child(self, side: bool) -> Option<Self> {
196		self.get_child_mut(side)
197	}
198}