trailtree/implement/update.rs
1use crate::{TrailTree, Node, Cell};
2
3use core::cmp::Ordering;
4use alloc::{vec::Vec, vec};
5
6impl<K,T> TrailTree<K,T>
7where K: Clone + Ord
8{
9 /// Inserts an index path into the tree, returning the ID of the last node in the path.
10 ///
11 /// # Examples
12 ///
13 /// ```
14 /// use trailtree::TrailTree;
15 ///
16 /// let mut con = TrailTree::<u32,()>::new();
17 ///
18 /// let a = con.insert(&[5, 10]);
19 ///
20 /// assert_eq!(con.search(&[5, 10]), Some(a));
21 /// ```
22 ///
23 /// See also [`TrailTree::extend`].
24 pub fn insert(&mut self, path:&[K]) -> usize
25 {
26 self.modify(self.root, path)
27 }
28
29 /// Extends an existing path in the tree with a new path, returning the ID of the last node in the extended path.
30 ///
31 /// # Examples
32 ///
33 /// ```
34 /// use trailtree::TrailTree;
35 ///
36 /// let mut con = TrailTree::<u32,()>::new();
37 ///
38 /// let a = con.insert(&[5]);
39 /// let b = con.extend(a, &[10]);
40 ///
41 /// assert_eq!(con.search(&[5, 10]), Some(b));
42 /// assert_eq!(con.parent(b), Some(a));
43 /// ```
44 ///
45 /// See also [`TrailTree::insert`].
46 pub fn extend(&mut self, mut id:usize, path:&[K]) -> usize
47 {
48 let root = self.rel(id).child[1];
49 if root == usize::MAX {
50 let mut first = None;
51 self.fill_path(&mut first, &mut id, path);
52 first.unwrap_or(id)
53 } else {
54 self.modify(root, path)
55 }
56 }
57
58 fn modify(&mut self, id:usize, path:&[K]) -> usize
59 {
60 let mut current = id;
61
62 // Create root node if empty.
63 if self.root == usize::MAX {
64 let mut first = None;
65 self.fill_path(&mut first, &mut current, path);
66 self.root = first.unwrap_or(usize::MAX);
67 } else {
68 let mut path_index = 0;
69 while path_index < path.len() {
70 let mut traverse = true;
71
72 while traverse {
73 let node = self.node(current).unwrap();
74 let rel = node.rel;
75
76 let compare = path[path_index].cmp(&node.key);
77 match compare {
78 Ordering::Less | Ordering::Greater => {
79 let index = (compare as i8 + 1) as usize;
80 if node.rel.child[index] == usize::MAX {
81 let (next_id, next) = self.acquire(path[path_index].clone());
82
83 next.rel.parent = current;
84 next.rel.root = rel.root;
85
86 self.rel_mut(current).child[index] = next_id;
87 current = next_id;
88
89 self.balance_tree(current);
90
91 self.fill_path(&mut None, &mut current, &path[path_index+1..]);
92
93 traverse = false;
94 path_index = path.len();
95 } else {
96 current = node.rel.child[index];
97 }
98 }
99
100 Ordering::Equal => if node.rel.child[1] == usize::MAX {
101 self.fill_path(&mut None, &mut current, &path[path_index+1..]);
102
103 traverse = false;
104 path_index = path.len();
105 } else {
106 current = if path_index + 1 < path.len() { node.rel.child[1] } else { current };
107 traverse = false;
108 }
109 }
110 }
111
112 path_index += 1;
113 }
114 }
115
116 current
117 }
118
119 fn fill_path(&mut self, first:&mut Option<usize>, current:&mut usize, path:&[K])
120 {
121 for key in path {
122 let next = {
123 let (next_id, next_node) = self.acquire(key.clone());
124 next_node.rel.root = *current;
125 next_id
126 };
127
128 first.get_or_insert(next);
129
130 if *current != usize::MAX {
131 self.rel_mut(*current).child[1] = next;
132 }
133
134 *current = next;
135 }
136 }
137
138 /// Moves an element and its subtree to the prefix of a destination element.
139 /// The operation fails if the key already exists in the destination.
140 pub fn relocate(&mut self, id:usize, dst:usize) -> bool
141 {
142 if let Some(node) = self.node(id) {
143 self.relocate_with(id, dst, node.key.clone())
144 } else {
145 return false;
146 }
147 }
148
149 pub fn relocate_with(&mut self, id:usize, dst:usize, key:K) -> bool
150 {
151 if id != dst {
152 if let Some(dnode) = self.node(dst) {
153 let drel = dnode.rel;
154
155 // Check that id is not ancestor of parent.
156 let mut current = drel.root;
157 while current != usize::MAX && current != id {
158 current = self.rel(current).root;
159 }
160 if current == id { return false }
161
162 // Insert node into destination subtree.
163 let mut traverse = true;
164 current = drel.child[1];
165
166 // Insert moved into destination subtree.
167 if current != usize::MAX {
168 while traverse {
169 let node = self.node(current).unwrap();
170
171 let compare = key.cmp(&node.key);
172 match compare {
173 Ordering::Less | Ordering::Greater => {
174 let index = (compare as i8 + 1) as usize;
175 if node.rel.child[index] == usize::MAX {
176
177 // Detach node from current subtree.
178 self.detach(id);
179
180 // Update moved node parents.
181 if let Some(node) = self.node_mut(id) {
182 node.rel.parent = current;
183 node.rel.root = dst;
184 }
185
186 self.rel_mut(current).child[index] = id;
187
188 self.balance_tree(current);
189
190 traverse = false;
191 } else {
192 current = node.rel.child[index];
193 }
194 }
195
196 // Key conflicts with existing element.
197 Ordering::Equal => return false,
198 }
199 }
200 }
201
202 // Moved is first node under destination.
203 else {
204 self.rel_mut(dst).child[1] = id;
205 self.rel_mut(id).root = dst;
206 }
207
208 // Update key of moved node.
209 if let Some(node) = self.node_mut(id) {
210 node.key = key;
211 }
212
213 return true;
214 }
215 }
216
217 false
218 }
219
220 /// Removes the subtree starting at the specified element.
221 ///
222 /// # Examples
223 ///
224 /// ```
225 /// use trailtree::TrailTree;
226 ///
227 /// let mut con = TrailTree::<u32,()>::new();
228 ///
229 /// let a = con.insert(&[10]);
230 /// con.extend(a, &[20, 30]);
231 /// let b = con.insert(&[5, 2]);
232 /// con.insert(&[20]);
233 /// con.insert(&[15]);
234 ///
235 /// con.remove(a);
236 ///
237 /// assert_eq!(con.search(&[10]), None);
238 /// assert_eq!(con.search(&[5, 2]), Some(b));
239 /// ```
240 pub fn remove(&mut self, id:usize)
241 {
242 if self.node(id).is_some() {
243 let rel = self.rel(id);
244
245 // Remove child subtree.
246 self.remove_subtree(rel.child[1]);
247 self.detach(id);
248
249 // Replace cell with next pointer.
250 self.cells[id] = Cell::pointer(self.next);
251 self.next = id;
252 }
253 }
254
255 fn detach(&mut self, id:usize)
256 {
257 let rel = self.rel(id);
258
259 let lrel = self.rel(rel.child[0]);
260 let rrel = self.rel(rel.child[2]);
261
262 // Clear node children.
263 {
264 let rel = self.rel_mut(id);
265 rel.root = usize::MAX;
266 rel.parent = usize::MAX;
267 rel.child[0] = usize::MAX;
268 rel.child[2] = usize::MAX;
269 rel.height = 0;
270 }
271
272 // Determine method of filling tree gap.
273 let mut replacement = usize::MAX;
274 let mut balance = rel.parent;
275
276 let mask = ((rel.child[0] != usize::MAX) as u32)
277 | (((rel.child[2] != usize::MAX) as u32) << 1);
278 match mask {
279 // Only lesser child.
280 1 => {
281 self.rel_mut(rel.child[0]).parent = rel.parent;
282
283 replacement = rel.child[0];
284 balance = rel.parent;
285 }
286
287 // Only greater child.
288 2 => {
289 self.rel_mut(rel.child[2]).parent = rel.parent;
290
291 replacement = rel.child[2];
292 balance = rel.parent;
293 }
294
295 // Node has both children.
296 3 => {
297 let sel = if rrel.height > lrel.height { 2 } else { 0 };
298 let isel = if sel == 0 { 2 } else { 0 };
299
300 // Move nearest descendant to top.
301 let mut current = rel.child[sel];
302
303 while let Some(node) = self.node(current) && node.rel.child[isel] != usize::MAX {
304 current = node.rel.child[isel];
305 }
306
307 // Update parent and child nodes.
308 let mut srel = self.rel(current);
309 self.rel_mut(srel.parent).child[isel] = srel.child[sel];
310
311 if srel.child[sel] != usize::MAX {
312 self.rel_mut(srel.child[sel]).parent = srel.parent;
313 }
314
315 // Update moved node.
316 srel = {
317 let srel = self.rel_mut(current);
318 srel.parent = rel.parent;
319 if rel.child[0] != current { srel.child[0] = rel.child[0]; }
320 if rel.child[2] != current { srel.child[2] = rel.child[2]; }
321 replacement = current;
322 *srel
323 };
324
325 self.rel_mut(srel.child[0]).parent = current;
326 self.rel_mut(srel.child[2]).parent = current;
327
328 balance = srel.parent;
329 }
330 _ => { }
331 }
332
333 // Update node references.
334 if rel.parent != usize::MAX {
335 let prel = self.rel_mut(rel.parent);
336 if prel.child[0] == id {
337 prel.child[0] = replacement;
338 } else {
339 prel.child[2] = replacement;
340 }
341 } else if rel.root != usize::MAX {
342 self.rel_mut(rel.root).child[1] = replacement;
343 } else {
344 self.root = replacement;
345 }
346
347 if balance != usize::MAX {
348 self.balance_tree(balance);
349 }
350 }
351
352 fn remove_subtree(&mut self, id:usize)
353 {
354 if id != usize::MAX {
355 let mut stack = vec![(id, 0)];
356
357 while let Some((top, index)) = stack.last_mut() {
358 let rel = self.rel(*top);
359
360 if *index < 3 {
361 // Push next child to stack.
362 let i = *index;
363 *index += 1;
364
365 if rel.child[i] != usize::MAX {
366 stack.push((rel.child[i], 0));
367 }
368 } else {
369 // Update node references.
370 if rel.parent != usize::MAX {
371 let prel = self.rel_mut(rel.parent);
372 if prel.child[0] == *top {
373 prel.child[0] = usize::MAX;
374 } else {
375 prel.child[2] = usize::MAX;
376 }
377 } else if rel.root != usize::MAX {
378 self.rel_mut(rel.root).child[1] = usize::MAX;
379 } else {
380 self.root = usize::MAX;
381 }
382
383 // Replace cell with next pointer.
384 self.cells[*top] = Cell::pointer(self.next);
385 self.next = *top;
386
387 stack.pop();
388 }
389 }
390 }
391 }
392
393 /// Removes all items from the tree, but does not release memory.
394 ///
395 /// # Examples
396 ///
397 /// ```
398 /// use trailtree::TrailTree;
399 ///
400 /// let mut con = TrailTree::<u32,()>::new();
401 ///
402 /// con.insert(&[5, 10, 15]);
403 /// con.clear();
404 ///
405 /// assert_eq!(con.first(None), None);
406 /// ```
407 pub fn clear(&mut self)
408 {
409 self.cells.clear();
410 self.root = usize::MAX;
411 self.next = 0;
412 }
413
414 /// Releases all memory used by the tree.
415 pub fn release(&mut self)
416 {
417 self.cells = Vec::new();
418 self.root = usize::MAX;
419 self.next = 0;
420 }
421
422 /// Replaces data associated with the specified element and returns the old value.
423 ///
424 /// # Examples
425 ///
426 /// ```
427 /// use trailtree::TrailTree;
428 ///
429 /// let mut con = TrailTree::<u32,u32>::new();
430 ///
431 /// let a = con.insert(&[5, 10]);
432 ///
433 /// assert_eq!(con.set(a, 42), None);
434 /// assert_eq!(con.set(a, 43), Some(42));
435 /// ```
436 pub fn set(&mut self, id:usize, data:T) -> Option<T>
437 {
438 if id < self.cells.len() && let Cell::Node(node) = &mut self.cells[id] {
439 let old = node.data.take();
440 node.data = Some(data);
441 old
442 } else {
443 None
444 }
445 }
446
447 /// Removes data associated with the specified element and returns the old value.
448 ///
449 /// # Examples
450 ///
451 /// ```
452 /// use trailtree::TrailTree;
453 ///
454 /// let mut con = TrailTree::<u32,u32>::new();
455 ///
456 /// let a = con.insert(&[5, 10]);
457 ///
458 /// con.set(a, 24);
459 ///
460 /// assert_eq!(con.unset(a), Some(24));
461 /// assert_eq!(con.unset(a), None);
462 /// ```
463 pub fn unset(&mut self, id:usize) -> Option<T>
464 {
465 if id < self.cells.len() && let Cell::Node(node) = &mut self.cells[id] {
466 node.data.take()
467 } else {
468 None
469 }
470 }
471
472 fn acquire(&mut self, key:K) -> (usize, &mut Node<K,T>)
473 {
474 let id = self.next;
475
476 // Acquire block if next exceeds current allocation.
477 if id >= self.cells.len() {
478 let next = self.cells.len() + 1;
479 self.cells.push(Cell::pointer(next));
480 }
481
482 if let Cell::Pointer(addr) = self.cells[id] {
483 self.next = addr.root;
484 }
485 self.cells[id] = Cell::Node(Node::new(key));
486
487 if let Cell::Node(node) = &mut self.cells[id] {
488 (id, node)
489 } else {
490 unreachable!()
491 }
492 }
493}