bitstring_trees/tree/
goto.rs1use 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 Final(InsertPositionWith<N>),
14 Continue(N, WalkedDirection),
18}
19
20#[derive(Clone, Copy, PartialEq, Eq, Debug)]
24pub enum InsertPosition {
25 BelowLeaf,
29 AlreadyExists,
31 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#[derive(Debug)]
52pub enum InsertPositionWith<N> {
53 BelowLeaf(N),
57 AlreadyExists(N),
59 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
101pub(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 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 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 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}