outils/tree/bst/aatree.rs
1//!
2//! `AaTree<K, V>` is an unweighted balanced binary search tree data structure.
3//!
4use slab;
5use std::cmp::Ordering;
6use std::iter::empty;
7use std::mem::swap;
8use std::ops::{Index, IndexMut};
9use crate::tree::bst::{BinarySearchTree, BstDirection, OrderedTree};
10use crate::tree::traversal::{BinaryInOrder, BinaryInOrderIndices, Traversable};
11use crate::types::{Keys, KeyType, NodeIndex, Tgf, Values, ValueType};
12
13#[cfg(test)]
14mod tests;
15
16#[derive(Clone, Debug)]
17struct Node<K, V>
18 where
19 K: KeyType,
20 V: ValueType,
21{
22 key: K,
23 value: V,
24 level: usize,
25 parent: usize,
26 children: [usize; 2],
27}
28
29impl<K, V> Node<K, V>
30 where
31 K: KeyType,
32 V: ValueType,
33{
34 fn new() -> Self {
35 Node {
36 key: K::default(),
37 value: V::default(),
38 level: 0,
39 parent: 0,
40 children: [0, 0],
41 }
42 }
43
44 fn new_leaf(key: K, value: V) -> Self {
45 Node {
46 key,
47 value,
48 level: 1,
49 parent: 0,
50 children: [0, 0],
51 }
52 }
53}
54
55impl<K, V> Index<BstDirection> for Node<K, V>
56 where
57 K: KeyType,
58 V: ValueType,
59{
60 type Output = usize;
61 fn index(&self, index: BstDirection) -> &usize {
62 &self.children[index as usize]
63 }
64}
65
66impl<K, V> IndexMut<BstDirection> for Node<K, V>
67 where
68 K: KeyType,
69 V: ValueType,
70{
71 fn index_mut(&mut self, index: BstDirection) -> &mut usize {
72 &mut self.children[index as usize]
73 }
74}
75
76impl<K, V> Index<usize> for Node<K, V>
77 where
78 K: KeyType,
79 V: ValueType,
80{
81 type Output = usize;
82 fn index(&self, index: usize) -> &usize {
83 &self.children[index as usize]
84 }
85}
86
87impl<K, V> IndexMut<usize> for Node<K, V>
88 where
89 K: KeyType,
90 V: ValueType,
91{
92 fn index_mut(&mut self, index: usize) -> &mut usize {
93 &mut self.children[index as usize]
94 }
95}
96
97/// `AaTree<K, V>` is a balanced binary search tree data structure. Its tree nodes
98/// are held in a [memory arena][1] and are addressed through their associated `NodeIndex`.
99///
100/// The balancing method for maintaining a tree height of log(n) where n is the number nodes
101/// in the tree is described here: [AA tree][2].
102///
103/// `AaTree` is parameterized over:
104///
105/// - Search keys of type `K`, where `K` must implement the trait [`KeyType`][3]
106/// - Associated values of type `V`, where `V` must implement the trait [`ValueType`][4]
107///
108/// The usage of `AaTree` resembles that of [`BTreeMap`][5] from the standard library:
109///
110/// ```
111/// use std::collections::BTreeMap;
112/// use outils::prelude::*;
113///
114/// let mut btreemap = BTreeMap::new();
115/// let mut aatree = AaTree::new(10);
116///
117/// btreemap.insert("DE", "Germany");
118/// btreemap.insert("FR", "France");
119/// btreemap.insert("IT", "Italy");
120///
121/// aatree.insert("DE", "Germany");
122/// aatree.insert("FR", "France");
123/// aatree.insert("IT", "Italy");
124///
125/// assert_eq!(btreemap.get(&"DE"), Some(&"Germany"));
126/// assert_eq!(aatree.get(&"DE"), Some(&"Germany"));
127///
128/// assert_eq!(btreemap.remove(&"FR"), Some("France"));
129/// assert_eq!(aatree.remove(&"FR"), Some("France"));
130///
131/// assert_eq!(btreemap.get(&"FR"), None);
132/// assert_eq!(aatree.get(&"FR"), None);
133/// ```
134///
135/// For most use cases, it is recommended to simply use `BTreeMap`, as it is considerably
136/// faster (appr. 50%). However, if information on parent and child relations between tree nodes,
137/// or custom traversal of the tree as such, are needed, `AaTree` has an advantage over `BTreeMap`.
138///
139/// [1]: https://en.wikipedia.org/wiki/Region-based_memory_management
140/// [2]: https://en.wikipedia.org/wiki/AA_tree
141/// [3]: types/trait.KeyType.html
142/// [4]: ../../../types/trait.ValueType.html
143/// [5]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
144///
145#[derive(Clone, Debug)]
146pub struct AaTree<K, V>
147 where
148 K: KeyType,
149 V: ValueType,
150{
151 arena: slab::Slab<Node<K, V>>,
152 root: usize,
153 nil: usize,
154}
155
156impl<K, V> AaTree<K, V>
157 where
158 K: KeyType,
159 V: ValueType,
160{
161 /// Construct a new empty `AaTree` with an initial capacity of `size`.
162 pub fn new(size: usize) -> Self {
163 let mut a = slab::Slab::with_capacity(size + 1);
164 let n = a.insert(Node::new());
165
166 AaTree {
167 arena: a,
168 root: n,
169 nil: n,
170 }
171 }
172
173 fn compare(&self, key: K, node: usize) -> Option<Ordering> {
174 if node == self.nil {
175 return None;
176 }
177 Some(key.cmp(&self.arena[node].key))
178 }
179
180 fn link(&mut self, parent: usize, child: usize, dir: BstDirection) {
181 if parent == child {
182 return;
183 }
184 if parent != self.nil {
185 self.arena[parent][dir] = child;
186 if child != self.nil {
187 self.arena[child].parent = parent;
188 }
189 } else {
190 self.arena[child].parent = self.nil;
191 self.root = child;
192 }
193 }
194
195 fn unlink(&mut self, parent: usize, child: usize, dir: BstDirection) {
196 if parent == child {
197 return;
198 }
199 if parent != self.nil {
200 self.arena[parent][dir] = self.nil;
201 if child != self.nil {
202 self.arena[child].parent = self.nil;
203 }
204 }
205 }
206
207 fn skew_node(&mut self, node: usize) -> usize {
208 if node == self.nil {
209 return node;
210 }
211
212 let node_level = self.arena[node].level;
213 let left = self.arena[node][BstDirection::Left];
214 let left_level = self.arena[left].level;
215 let mut ret = node;
216
217 if node_level == left_level {
218 let parent = self.arena[node].parent;
219 let dir = if self.arena[parent][BstDirection::Left] == node {
220 BstDirection::Left
221 } else {
222 BstDirection::Right
223 };
224 let left_right = self.arena[left][BstDirection::Right];
225
226 ret = left;
227 self.link(parent, left, dir);
228 self.link(left, node, BstDirection::Right);
229 self.link(node, left_right, BstDirection::Left);
230 }
231 ret
232 }
233
234 fn split_node(&mut self, node: usize) -> usize {
235 if node == self.nil {
236 return node;
237 }
238
239 let node_level = self.arena[node].level;
240 let right = self.arena[node][BstDirection::Right];
241 let right_right = self.arena[right][BstDirection::Right];
242 let right_right_level = self.arena[right_right].level;
243 let mut ret = node;
244
245 if right_right_level == node_level && node_level != 0 {
246 let parent = self.arena[node].parent;
247 let dir = if self.arena[parent][BstDirection::Left] == node {
248 BstDirection::Left
249 } else {
250 BstDirection::Right
251 };
252 let right_left = self.arena[right][BstDirection::Left];
253
254 ret = right;
255 self.link(parent, right, dir);
256 self.link(right, node, BstDirection::Left);
257 self.link(node, right_left, BstDirection::Right);
258 self.arena[right].level += 1;
259 }
260 ret
261 }
262
263 fn find_node(&self, key: K) -> Option<usize> {
264 let mut parent = self.root;
265 let mut child;
266
267 if parent == self.nil {
268 return None;
269 }
270
271 loop {
272 match self.compare(key, parent).unwrap_or(Ordering::Equal) {
273 Ordering::Less => {
274 child = self.arena[parent][BstDirection::Left];
275 }
276 Ordering::Greater => {
277 child = self.arena[parent][BstDirection::Right];
278 }
279 Ordering::Equal => {
280 return Some(parent);
281 }
282 }
283
284 if child == self.nil {
285 return None;
286 }
287 parent = child;
288 }
289 }
290
291 fn next_from_subtree(&self, node: usize, dir: BstDirection) -> usize {
292 let mut parent = self.arena[node][dir];
293 let mut child;
294 let other_dir = dir.other();
295 loop {
296 child = self.arena[parent][other_dir];
297 if child == self.nil {
298 break;
299 }
300 parent = child;
301 }
302 parent
303 }
304
305 fn next(&self, node: usize, dir: BstDirection) -> usize {
306 let mut child = self.next_from_subtree(node, dir);
307 if child != self.nil {
308 return child;
309 }
310
311 child = self.arena[node].parent;
312 if child == self.nil {
313 return self.nil;
314 }
315 let other_dir = dir.other();
316 let mut parent_dir = if self.arena[child][BstDirection::Left] == node {
317 BstDirection::Left
318 } else {
319 BstDirection::Right
320 };
321 if parent_dir == other_dir {
322 return child;
323 }
324
325 let mut parent = self.arena[child].parent;
326 loop {
327 if parent == self.nil {
328 return self.nil;
329 }
330 parent_dir = if self.arena[parent][BstDirection::Left] == child {
331 BstDirection::Left
332 } else {
333 BstDirection::Right
334 };
335 if parent_dir == other_dir {
336 return parent;
337 }
338 child = parent;
339 parent = self.arena[child].parent;
340 }
341 }
342
343 fn extreme(&self, node: usize, dir: BstDirection) -> usize {
344 let mut parent = node;
345 let mut child = self.arena[parent][dir];
346 loop {
347 if child == self.nil {
348 break;
349 }
350 parent = child;
351 child = self.arena[parent][dir];
352 }
353 parent
354 }
355
356 fn apply(
357 &self,
358 f: fn(&AaTree<K, V>, usize, BstDirection) -> usize,
359 node: usize,
360 dir: BstDirection,
361 ) -> Option<usize> {
362 if self.arena.contains(node) {
363 let ret = f(self, node, dir);
364 if ret == self.nil {
365 return None;
366 }
367 return Some(ret);
368 }
369 None
370 }
371}
372
373impl<K, V> BinarySearchTree<K, V> for AaTree<K, V>
374 where
375 K: KeyType,
376 V: ValueType,
377{
378 fn insert_pos(&self, key: K) -> Option<(NodeIndex, Ordering)> {
379 if self.root == self.nil {
380 return None;
381 }
382
383 let mut parent = self.root;
384 let mut child = self.nil;
385
386 loop {
387 let ordering = match self.compare(key, parent).unwrap_or(Ordering::Equal) {
388 Ordering::Less => {
389 child = self.arena[parent][BstDirection::Left];
390 Ordering::Less
391 }
392 Ordering::Greater => {
393 child = self.arena[parent][BstDirection::Right];
394 Ordering::Greater
395 }
396 Ordering::Equal => Ordering::Equal,
397 };
398
399 if ordering == Ordering::Equal || child == self.nil {
400 return Some((NodeIndex(parent), ordering));
401 }
402 parent = child;
403 }
404 }
405
406 /// Inserts a key-value pair into the `AaTree`. If the tree did not have this `key` present, `None`
407 /// is returned. If the tree **did** have this `key` present, the value is updated, and the old
408 /// value is returned. Note that in this situation, the key is left unchanged.
409 ///
410 /// ```
411 /// use outils::prelude::*;
412 ///
413 /// let mut aatree = AaTree::new(10);
414 ///
415 /// assert_eq!(aatree.insert("KEY-1", "VALUE-1"), None);
416 /// assert_eq!(aatree.insert("KEY-2", "VALUE-2"), None);
417 /// assert_eq!(aatree.insert("KEY-1", "VALUE-3"), Some("VALUE-1"));
418 /// assert_eq!(aatree.get(&"KEY-1"), Some(&"VALUE-3"));
419 /// assert_eq!(aatree.get(&"KEY-2"), Some(&"VALUE-2"));
420 /// ```
421 fn insert(&mut self, key: K, value: V) -> Option<V> {
422 match self.insert_pos(key) {
423 None => {
424 self.root = self.arena.insert(Node::new_leaf(key, value));
425 None
426 },
427 Some((node_idx, ord)) => {
428 let parent = node_idx.index();
429 let dir = match ord {
430 Ordering::Equal => {
431 let mut old_value = value;
432 swap(&mut self.arena[parent].value, &mut old_value);
433 return Some(old_value);
434 },
435 Ordering::Less => BstDirection::Left,
436 Ordering::Greater => BstDirection::Right,
437 };
438
439 let mut child = self.arena.insert(Node::new_leaf(key, value));
440 self.link(parent, child, dir);
441
442 loop {
443 child = self.skew_node(child);
444 child = self.split_node(child);
445 child = self.arena[child].parent;
446 if child == self.nil {
447 break;
448 }
449 }
450 None
451 }
452 }
453 }
454
455 /// Removes a `key` from the tree if present, in this case returning the associated value.
456 ///
457 /// ```
458 /// use outils::prelude::*;
459 ///
460 /// let mut aatree = AaTree::new(10);
461 /// aatree.insert("KEY-1", "VALUE-1");
462 /// assert_eq!(aatree.remove(&"KEY-1"), Some("VALUE-1"));
463 /// assert_eq!(aatree.remove(&"KEY-2"), None);
464 /// ```
465 fn remove(&mut self, key: K) -> Option<V> {
466 let node;
467 match self.find_node(key) {
468 Some(n) => {
469 node = n;
470 }
471 None => {
472 return None;
473 }
474 }
475
476 let deleted = node;
477 let deleted_left = self.arena[deleted][BstDirection::Left];
478 let deleted_right = self.arena[deleted][BstDirection::Right];
479 let mut parent = self.arena[node].parent;
480 let dir = if self.arena[parent][BstDirection::Left] == node {
481 BstDirection::Left
482 } else {
483 BstDirection::Right
484 };
485
486 self.unlink(parent, deleted, dir);
487 self.unlink(deleted, deleted_left, BstDirection::Left);
488 self.unlink(deleted, deleted_right, BstDirection::Right);
489
490 let mut child;
491
492 if deleted_left == self.nil {
493 if deleted_right == self.nil {
494 child = parent;
495 } else {
496 child = deleted_right;
497 self.link(parent, child, dir);
498 self.arena[child].level = self.arena[deleted].level;
499 }
500 } else if deleted_right == self.nil {
501 child = deleted_left;
502 self.link(parent, child, dir);
503 self.arena[child].level = self.arena[deleted].level;
504 } else {
505 let mut heir_parent = self.nil;
506 let mut heir = deleted_left;
507 let mut heir_dir = BstDirection::Left;
508 loop {
509 let right = self.arena[heir][BstDirection::Right];
510 if right == self.nil {
511 break;
512 }
513 heir_dir = BstDirection::Right;
514 heir_parent = heir;
515 heir = right;
516 }
517
518 child = heir;
519 if heir_parent != self.nil {
520 let left = self.arena[heir][BstDirection::Left];
521 self.unlink(heir_parent, heir, heir_dir);
522 self.unlink(heir, left, BstDirection::Left);
523 self.link(heir_parent, left, BstDirection::Right);
524 child = heir_parent;
525 }
526 self.link(parent, heir, dir);
527 self.link(heir, deleted_left, BstDirection::Left);
528 self.link(heir, deleted_right, BstDirection::Right);
529 self.arena[heir].level = self.arena[deleted].level;
530 }
531
532 parent = self.arena[child].parent;
533 loop {
534 let child_level = self.arena[child].level;
535 let left_level = self.arena[self.arena[child][BstDirection::Left]].level;
536 let right_level = self.arena[self.arena[child][BstDirection::Right]].level;
537
538 if left_level + 1 < child_level || right_level + 1 < child_level {
539 let new_child_level = child_level - 1;
540 self.arena[child].level = new_child_level;
541 let mut right = self.arena[child][BstDirection::Right];
542 if right_level > new_child_level {
543 self.arena[right].level = new_child_level;
544 }
545
546 child = self.skew_node(child);
547 right = self.arena[child][BstDirection::Right];
548 right = self.skew_node(right);
549 right = self.arena[right][BstDirection::Right];
550 self.skew_node(right);
551 child = self.split_node(child);
552 right = self.arena[child][BstDirection::Right];
553 self.split_node(right);
554 }
555
556 if parent == self.nil {
557 self.root = child;
558 return Some(self.arena.remove(deleted).value);
559 }
560
561 child = parent;
562 parent = self.arena[child].parent;
563 }
564 }
565
566 /// Returns an immutable reference to the associated value of the specified `key`.
567 fn get(&self, key: K) -> Option<&V> {
568 self.find_node(key).map(move |node| &self.arena[node].value)
569 }
570
571 /// Returns a mutable reference to the associated value of the specified `key`.
572 fn get_mut(&mut self, key: K) -> Option<&mut V> {
573 self.find_node(key)
574 .map(move |node| &mut self.arena[node].value)
575 }
576
577 /// Returns the index of the tree node holding the specified `key`.
578 fn index(&self, key: K) -> Option<NodeIndex> {
579 self.find_node(key).map(NodeIndex)
580 }
581
582 /// Returns `true` if the map contains a value for the specified `key`.
583 fn contains_key(&self, key: K) -> bool {
584 self.find_node(key).is_some()
585 }
586
587 /// Returns the key held by the tree node indexed by `node`.
588 ///
589 /// ```
590 /// use outils::prelude::*;
591 ///
592 /// let mut aatree = AaTree::new(10);
593 /// aatree.insert("KEY-1", "VALUE-1");
594 /// let index = aatree.index(&"KEY-1").expect("KEY-1 should be present");
595 /// assert_eq!(aatree.key(index), Some(&"KEY-1"));
596 /// ```
597 fn key(&self, node: NodeIndex) -> Option<&K> {
598 let node = node.index();
599 if node == self.nil {
600 return None;
601 }
602 self.arena.get(node).map(|n| &n.key)
603 }
604}
605
606impl<K, V> Traversable<V> for AaTree<K, V>
607 where
608 K: KeyType,
609 V: ValueType,
610{
611 /// Returns the index of the root node of the `AaTree`. Since the tree can only have one root
612 /// the parameter `node` is not used.
613 ///
614 /// ```
615 /// use outils::prelude::*;
616 ///
617 /// let mut aatree = AaTree::new(10);
618 /// assert_eq!(aatree.root(NodeIndex(0)), None); // The parameter to root() doesn't matter!
619 /// aatree.insert("KEY-1", "VALUE-1");
620 ///
621 /// // The solitary key in the tree must be the root
622 /// let index = aatree.index(&"KEY-1").expect("KEY-1 should be present");
623 ///
624 /// assert_eq!(aatree.root(index), Some(index));
625 /// assert_eq!(aatree.root(NodeIndex(0)), Some(index)); // The parameter to root() doesn't matter!
626 /// ```
627 fn root(&self, _node: NodeIndex) -> Option<NodeIndex> {
628 if self.root == self.nil {
629 return None;
630 }
631 Some(NodeIndex(self.root))
632 }
633
634 /// Immutably access the value stored in the `AaTree` indexed by `node`.
635 fn value(&self, node: NodeIndex) -> Option<&V> {
636 let node = node.index();
637 if node == self.nil {
638 return None;
639 }
640 self.arena.get(node).map(|n| &n.value)
641 }
642
643 /// Mutably access the value stored in the `AaTree` indexed by `node`.
644 fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V> {
645 let node = node.index();
646 if node == self.nil {
647 return None;
648 }
649 self.arena.get_mut(node).map(|n| &mut n.value)
650 }
651
652 /// Returns the index of parent node tree node indexed by `node`.
653 fn parent(&self, node: NodeIndex) -> Option<NodeIndex> {
654 let node = node.index();
655 match self.arena.get(node) {
656 Some(n) => {
657 let parent = n.parent;
658 if parent == self.nil {
659 return None;
660 }
661 Some(NodeIndex(parent))
662 }
663 None => None,
664 }
665 }
666
667 /// Returns the index of the child node at position `pos` of the tree node indexed by `node`.
668 ///
669 /// Note that a binary search tree node will always have two children, i.e. that even if the
670 /// left child (`pos == 0`) is empty, the right child (`pos == 1`) might contain a value.
671 /// In case of a leaf node, both children will be empty:
672 ///
673 /// ```
674 /// use outils::prelude::*;
675 ///
676 /// let mut aatree = AaTree::new(10);
677 /// aatree.insert(1, "1");
678 /// aatree.insert(2, "2");
679 ///
680 /// // At this point, the AA algorithm has not had to rotate the tree, so that
681 /// // the key `2` will be the right child of the key `1`:
682 ///
683 /// let parent = aatree.index(1).expect("Key '1' should be present");
684 /// assert_eq!(aatree.child(parent, 0), None);
685 /// assert_eq!(aatree.child(parent, 1), aatree.index(2));
686 /// ```
687 fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex> {
688 let node = node.index();
689 if let Some(n) = self.arena.get(node) {
690 if pos > 1 {
691 return None;
692 }
693 let child = n.children[pos];
694 if child == self.nil {
695 return None;
696 }
697 return Some(NodeIndex(child));
698 }
699 None
700 }
701
702 /// Returns the number of child nodes of the tree node indexed by `node`.
703 ///
704 /// Note that a binary search tree node will always have two children, i.e. that even if the
705 /// left child is empty, the right child might contain a value.
706 /// In case of a leaf node, both children will be empty, but the number of (empty) children
707 /// will still be 2:
708 ///
709 /// ```
710 /// use outils::prelude::*;
711 ///
712 /// let mut aatree = AaTree::new(10);
713 /// aatree.insert(1, "1");
714 /// aatree.insert(2, "2");
715 ///
716 /// // At this point, the AA algorithm has not had to rotate the tree, so that
717 /// // the key `2` will be the right child of the key `1`:
718 ///
719 /// let parent = aatree.index(1).expect("Key '1' should be present");
720 /// let child = aatree.index(2).expect("Key '2' should be present");
721 ///
722 /// assert_eq!(aatree.child_count(parent), 2);
723 /// assert_eq!(aatree.child_count(child), 2);
724 /// assert_eq!(aatree.child_count(NodeIndex(999)), 0); // Invalid index => no children
725 /// ```
726 fn child_count(&self, node: NodeIndex) -> usize {
727 let node = node.index();
728 if self.arena.contains(node) && node != self.nil {
729 return 2;
730 }
731 0
732 }
733
734 /// Returns the total number of tree nodes of the tree `self`.
735 fn node_count(&self) -> usize {
736 self.arena.len() - 1
737 }
738}
739
740impl<K, V> OrderedTree for AaTree<K, V>
741 where
742 K: KeyType,
743 V: ValueType,
744{
745 /// Returns the biggest node of the left subtree of the tree node indexed by `node`.
746 ///
747 /// ```
748 /// use outils::prelude::*; // The resulting tree is shown below:
749 /// //
750 /// let mut aatree = AaTree::new(10); // -- (3) --
751 /// // / \
752 /// for i in 0..7 { // (1) (5)
753 /// aatree.insert(i, i); // / \ / \
754 /// } // (0) (2) (4) (6)
755 ///
756 /// let n2 = aatree.index(2).expect("Key '2' should be present");
757 /// let n3 = aatree.index(3).expect("Key '3' should be present");
758 /// let n4 = aatree.index(4).expect("Key '4' should be present");
759 ///
760 /// assert_eq!(aatree.sub_predecessor(n3), Some(n2)); // 2 is biggest key in left subtree of 3.
761 /// assert_eq!(aatree.sub_predecessor(n4), None); // 4 is a leaf and thus has no subtrees.'
762 /// ```
763 fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex> {
764 self.apply(AaTree::next_from_subtree, node.index(), BstDirection::Left)
765 .map(NodeIndex)
766 }
767
768 /// Returns the smallest node of the right subtree of the tree node indexed by `node`.
769 ///
770 /// Usage is analogous to [`sub_predecessor`](#method.sub_predecessor)
771 fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex> {
772 self.apply(AaTree::next_from_subtree, node.index(), BstDirection::Right)
773 .map(NodeIndex)
774 }
775
776 /// Returns the biggest node of the whole tree which is smaller than the tree node
777 /// indexed by `node`.
778 ///
779 /// ```
780 /// use outils::prelude::*; // The resulting tree is shown below:
781 /// //
782 /// let mut aatree = AaTree::new(10); // -- (3) --
783 /// // / \
784 /// for i in 0..7 { // (1) (5)
785 /// aatree.insert(i, i); // / \ / \
786 /// } // (0) (2) (4) (6)
787 ///
788 /// let n0 = aatree.index(0).expect("Key '0' should be present");
789 /// let n3 = aatree.index(3).expect("Key '3' should be present");
790 /// let n4 = aatree.index(4).expect("Key '4' should be present");
791 ///
792 /// assert_eq!(aatree.predecessor(n4), Some(n3)); // 3 is the biggest key of the whole tree
793 /// // smaller than 4.
794 /// assert_eq!(aatree.predecessor(n0), None); // 0 is globally the smallest key of the
795 /// // whole tree and thus has no predecessor.
796 /// ```
797 fn predecessor(&self, node: NodeIndex) -> Option<NodeIndex> {
798 self.apply(AaTree::next, node.index(), BstDirection::Left)
799 .map(NodeIndex)
800 }
801
802 /// Returns the smallest node of the whole tree which is bigger than the tree node
803 /// indexed by `node`.
804 ///
805 /// Usage is analogous to [`predecessor`](#method.predecessor)
806 fn successor(&self, node: NodeIndex) -> Option<NodeIndex> {
807 self.apply(AaTree::next, node.index(), BstDirection::Right)
808 .map(NodeIndex)
809 }
810
811 /// Returns the smallest node of the left subtree of the tree node indexed by `node`.
812 ///
813 /// ```
814 /// use outils::prelude::*; // The resulting tree is shown below:
815 /// //
816 /// let mut aatree = AaTree::new(10); // -- (3) --
817 /// // / \
818 /// for i in 0..7 { // (1) (5)
819 /// aatree.insert(i, i); // / \ / \
820 /// } // (0) (2) (4) (6)
821 ///
822 /// let n0 = aatree.index(0).expect("Key '0' should be present");
823 /// let n1 = aatree.index(1).expect("Key '1' should be present");
824 /// let n3 = aatree.index(3).expect("Key '3' should be present");
825 ///
826 /// assert_eq!(aatree.first(n3), Some(n0)); // 0 is the smallest key of the left subtree of 3
827 /// assert_eq!(aatree.first(n1), Some(n0)); // 0 is the smallest key of the left subtree of 1
828 /// ```
829 fn first(&self, node: NodeIndex) -> Option<NodeIndex> {
830 self.apply(AaTree::extreme, node.index(), BstDirection::Left)
831 .map(NodeIndex)
832 }
833
834 /// Returns the biggest node of the right subtree of the tree node indexed by `node`.
835 ///
836 /// Usage is analogous to [`first`](#method.first)
837 fn last(&self, node: NodeIndex) -> Option<NodeIndex> {
838 self.apply(AaTree::extreme, node.index(), BstDirection::Right)
839 .map(NodeIndex)
840 }
841
842 /// Returns `true` if the tree node indexed by `node_u` is smaller than the tree node
843 /// indexed by `node_v`. Otherwise, and in particular if one of the specified indices
844 /// is invalid, `false` is returned.
845 ///
846 /// **Panics** if the path to the root from either of the tree nodes to be compared contains
847 /// more than 64 nodes. This is because the directions (i.e. left or right) on the path are
848 /// encoded in a bitmap of type `u64`. In practice it is **next to impossible** for this method to
849 /// panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.
850 ///
851 /// ```
852 /// use outils::prelude::*; // The resulting tree is shown below:
853 /// //
854 /// let mut aatree = AaTree::new(10); // -- (3) --
855 /// // / \
856 /// for i in 0..7 { // (1) (5)
857 /// aatree.insert(i, i); // / \ / \
858 /// } // (0) (2) (4) (6)
859 ///
860 /// let n0 = aatree.index(0).expect("Key '0' should be present");
861 /// let n1 = aatree.index(1).expect("Key '1' should be present");
862 /// let n3 = aatree.index(3).expect("Key '3' should be present");
863 ///
864 /// assert!(aatree.is_smaller(n0, n3));
865 /// assert!(!aatree.is_smaller(n3, n1));
866 /// ```
867 fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool {
868 let node_u = node_u.index();
869 let node_v = node_v.index();
870 if node_u == self.nil
871 || !self.arena.contains(node_u)
872 || node_v == self.nil
873 || !self.arena.contains(node_v)
874 {
875 return false;
876 }
877 self.arena[node_u].key < self.arena[node_v].key
878 }
879}
880
881impl<'slf, K, V> Keys<'slf, K> for AaTree<K, V>
882 where
883 K: 'slf + KeyType,
884 V: ValueType,
885{
886 /// Returns a boxed iterator over the search keys and their corresponding
887 /// tree node indices held by `self`. The keys are returned in the order
888 /// of the search keys.
889 fn keys(&'slf self) -> Box<dyn Iterator<Item=(NodeIndex, &'slf K)> + 'slf> {
890 if self.root == self.nil {
891 return Box::new(empty::<(NodeIndex, &'slf K)>());
892 }
893 Box::new(
894 BinaryInOrderIndices::new(self, NodeIndex(self.root))
895 .map(move |i| (i, &self.arena[i.index()].key)),
896 )
897 }
898}
899
900impl<'slf, K, V> Values<'slf, V> for AaTree<K, V>
901 where
902 K: KeyType,
903 V: 'slf + ValueType,
904{
905 /// Returns a boxed iterator over the stored values and their corresponding
906 /// tree node indices held by `self`. The keys are returned in the order
907 /// of the corresponding search keys.
908 fn values(&'slf self) -> Box<dyn Iterator<Item=(NodeIndex, &'slf V)> + 'slf> {
909 if self.root == self.nil {
910 return Box::new(empty::<(NodeIndex, &'slf V)>());
911 }
912 Box::new(BinaryInOrder::new(self, NodeIndex(self.root)))
913 }
914}
915
916impl<K, V> Index<NodeIndex> for AaTree<K, V>
917 where
918 K: KeyType,
919 V: ValueType,
920{
921 type Output = V;
922 fn index(&self, index: NodeIndex) -> &V {
923 &self.arena[index.index()].value
924 }
925}
926
927impl<K, V> IndexMut<NodeIndex> for AaTree<K, V>
928 where
929 K: KeyType,
930 V: ValueType,
931{
932 fn index_mut(&mut self, index: NodeIndex) -> &mut V {
933 &mut self.arena[index.index()].value
934 }
935}
936
937impl<K, V> Tgf for AaTree<K, V>
938 where
939 K: KeyType,
940 V: ValueType,
941{
942 fn to_tgf(&self) -> String {
943 let mut nodes = String::from("");
944 let mut edges = String::from("");
945 let iter = self.arena.iter();
946 for (index, node) in iter {
947 nodes.push_str(format!("{}", index).as_str());
948 nodes.push_str(" [K = ");
949 nodes.push_str(format!("{:?}", node.key).as_str());
950 nodes.push_str(", V = ");
951 nodes.push_str(format!("{:?}", node.value).as_str());
952 nodes.push_str(", L = ");
953 nodes.push_str(format!("{}", node.level).as_str());
954 nodes.push_str("]\n");
955
956 if node[BstDirection::Left] != self.nil {
957 edges.push_str(format!("{}", index).as_str());
958 edges.push_str(" ");
959 edges.push_str(format!("{}", node[BstDirection::Left]).as_str());
960 edges.push_str(" BstDirection::Left\n");
961 }
962
963 if node[BstDirection::Right] != self.nil {
964 edges.push_str(format!("{}", index).as_str());
965 edges.push_str(" ");
966 edges.push_str(format!("{}", node[BstDirection::Right]).as_str());
967 edges.push_str(" BstDirection::Right\n");
968 }
969 }
970 nodes.push_str("#\n");
971 nodes.push_str(edges.as_str());
972 nodes
973 }
974}