outils/tree/bst/aaforest.rs
1//!
2//! `AaForest<V>` is an unweighted balanced binary forest data structure.
3//!
4use slab;
5use std::ops::{Index, IndexMut};
6use crate::tree::bst::{BalancedBinaryForest, BstDirection, OrderedTree};
7use crate::tree::traversal::{BinaryPreOrderIndices, Traversable};
8use crate::types::{NodeIndex, Tgf, Values, ValueType};
9
10#[cfg(test)]
11mod tests;
12
13#[derive(Debug, Clone)]
14struct Node<V>
15 where
16 V: ValueType,
17{
18 value: V,
19 level: usize,
20 parent: usize,
21 children: [usize; 2],
22}
23
24impl<V> Node<V>
25 where
26 V: ValueType,
27{
28 fn new() -> Self {
29 Node {
30 value: V::default(),
31 level: 0,
32 parent: 0,
33 children: [0, 0],
34 }
35 }
36
37 fn new_leaf(value: V) -> Self {
38 Node {
39 value,
40 level: 1,
41 parent: 0,
42 children: [0, 0],
43 }
44 }
45}
46
47impl<V> Index<BstDirection> for Node<V>
48 where
49 V: ValueType,
50{
51 type Output = usize;
52 fn index(&self, index: BstDirection) -> &usize {
53 &self.children[index as usize]
54 }
55}
56
57impl<V> IndexMut<BstDirection> for Node<V>
58 where
59 V: ValueType,
60{
61 fn index_mut(&mut self, index: BstDirection) -> &mut usize {
62 &mut self.children[index as usize]
63 }
64}
65
66impl<V> Index<usize> for Node<V>
67 where
68 V: ValueType,
69{
70 type Output = usize;
71 fn index(&self, index: usize) -> &usize {
72 &self.children[index as usize]
73 }
74}
75
76impl<V> IndexMut<usize> for Node<V>
77 where
78 V: ValueType,
79{
80 fn index_mut(&mut self, index: usize) -> &mut usize {
81 &mut self.children[index as usize]
82 }
83}
84
85/// `AaForest<V>` is a data structure for holding balanced binary trees. Its tree nodes
86/// are held in a [memory arena][1] and are addressed through their associated `NodeIndex`.
87///
88/// `AaForest` is parameterized over:
89/// - Associated values of type `V`, where `V` must implement the trait [`ValueType`][2]
90///
91/// The balancing method for maintaining a tree height of log(n) where n is the number nodes
92/// in the tree is described here: [AA tree][3].
93///
94/// Forest trees can be joined and split as required by the provided operations, which will
95/// also take care of the re-balancing of the trees. The in-order of the forest trees implies an
96/// ordered sequence of values - this order does not depend on the order traits of the type `V`
97/// (i.e. [`std::cmp::Ord`][4]) but solely on the in-order of the nodes which is under the control
98/// of the user (see the documentation of [`split`](#method.split) and [`append`](#method.append)).
99///
100/// ```
101/// use outils::prelude::*;
102/// use outils::tree::traversal::BinaryInOrderValues;
103/// let mut aaforest = AaForest::new(10);
104///
105/// // Insert values into the forest - each value will be a single-node tree in the forest.
106/// let n1 = aaforest.insert(1);
107/// let n2 = aaforest.insert(2);
108/// let n3 = aaforest.insert(3);
109///
110/// // Link the single-node trees, constructing the in-order sequence 1,2,3.
111/// aaforest.append(n1, n2);
112/// aaforest.append(n2, n3);
113///
114/// let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, n1).collect();
115/// assert_eq!(seq, vec![&1, &2, &3]);
116/// ```
117/// [1]: https://en.wikipedia.org/wiki/Region-based_memory_management
118/// [2]: ../../../types/trait.ValueType.html
119/// [3]: https://en.wikipedia.org/wiki/AA_tree
120/// [4]: https://doc.rust-lang.org/std/cmp/trait.Ord.html
121///
122#[derive(Clone, Debug)]
123pub struct AaForest<V>
124 where
125 V: ValueType,
126{
127 arena: slab::Slab<Node<V>>,
128 nil: usize,
129 jdummy: usize,
130 sdummy: usize,
131}
132
133impl<V> AaForest<V>
134 where
135 V: ValueType,
136{
137 /// Construct a new empty `AaForest` with an initial capacity of `size`.
138 pub fn new(size: usize) -> Self {
139 let mut a = slab::Slab::with_capacity(size + 3);
140 let n = a.insert(Node::new());
141 let dj = a.insert(Node::new());
142 let ds = a.insert(Node::new());
143 AaForest {
144 arena: a,
145 nil: n,
146 jdummy: dj,
147 sdummy: ds,
148 }
149 }
150
151 #[inline]
152 fn is_valid_index(&self, node: usize) -> bool {
153 node > self.sdummy && self.arena.contains(node)
154 }
155
156 fn skew_node(&mut self, node: usize) -> usize {
157 if node == self.nil {
158 return node;
159 }
160
161 let node_level = self.arena[node].level;
162 let left = self.arena[node][BstDirection::Left];
163 let left_level = self.arena[left].level;
164 let mut ret = node;
165
166 if node_level == left_level {
167 let parent = self.arena[node].parent;
168 let dir = if self.arena[parent][BstDirection::Left] == node {
169 BstDirection::Left
170 } else {
171 BstDirection::Right
172 };
173 let left_right = self.arena[left][BstDirection::Right];
174
175 ret = left;
176 self.link(parent, left, dir);
177 self.link(left, node, BstDirection::Right);
178 self.link(node, left_right, BstDirection::Left);
179 }
180 ret
181 }
182
183 fn split_node(&mut self, node: usize) -> usize {
184 if node == self.nil {
185 return node;
186 }
187
188 let node_level = self.arena[node].level;
189 let right = self.arena[node][BstDirection::Right];
190 let right_right = self.arena[right][BstDirection::Right];
191 let right_right_level = self.arena[right_right].level;
192 let mut ret = node;
193
194 if right_right_level == node_level && node_level != 0 {
195 let parent = self.arena[node].parent;
196 let dir = if self.arena[parent][BstDirection::Left] == node {
197 BstDirection::Left
198 } else {
199 BstDirection::Right
200 };
201 let right_left = self.arena[right][BstDirection::Left];
202
203 ret = right;
204 self.link(parent, right, dir);
205 self.link(right, node, BstDirection::Left);
206 self.link(node, right_left, BstDirection::Right);
207 self.arena[right].level += 1;
208 }
209 ret
210 }
211
212 fn link(&mut self, parent: usize, child: usize, dir: BstDirection) {
213 if parent == child {
214 return;
215 }
216 if parent != self.nil {
217 self.arena[parent][dir] = child;
218 if child != self.nil {
219 self.arena[child].parent = parent;
220 }
221 } else {
222 self.arena[child].parent = self.nil;
223 }
224 }
225
226 fn unlink(&mut self, parent: usize, child: usize, dir: BstDirection) {
227 if parent == child {
228 return;
229 }
230 if parent != self.nil {
231 self.arena[parent][dir] = self.nil;
232 if child != self.nil {
233 self.arena[child].parent = self.nil;
234 }
235 }
236 }
237
238 fn init_dummy(&mut self, dummy: usize) {
239 self.arena[dummy].parent = self.nil;
240 self.arena[dummy][BstDirection::Left] = self.nil;
241 self.arena[dummy][BstDirection::Right] = self.nil;
242 self.arena[dummy].level = 1;
243 }
244
245 fn next_from_subtree(&self, node: usize, dir: BstDirection) -> usize {
246 let mut parent = self.arena[node][dir];
247 let other_dir = dir.other();
248 loop {
249 let child = self.arena[parent][other_dir];
250 if child == self.nil {
251 break;
252 }
253 parent = child;
254 }
255 parent
256 }
257
258 fn next(&self, node: usize, dir: BstDirection) -> usize {
259 let mut child = self.next_from_subtree(node, dir);
260 if child != self.nil {
261 return child;
262 }
263
264 child = self.arena[node].parent;
265 if child == self.nil {
266 return self.nil;
267 }
268 let other_dir = dir.other();
269 let mut parent_dir = if self.arena[child][BstDirection::Left] == node {
270 BstDirection::Left
271 } else {
272 BstDirection::Right
273 };
274 if parent_dir == other_dir {
275 return child;
276 }
277
278 let mut parent = self.arena[child].parent;
279 loop {
280 if parent == self.nil {
281 return self.nil;
282 }
283 parent_dir = if self.arena[parent][BstDirection::Left] == child {
284 BstDirection::Left
285 } else {
286 BstDirection::Right
287 };
288 if parent_dir == other_dir {
289 return parent;
290 }
291 child = parent;
292 parent = self.arena[child].parent;
293 }
294 }
295
296 fn extreme(&self, node: usize, dir: BstDirection) -> usize {
297 let mut parent = node;
298 let mut child = self.arena[parent][dir];
299 loop {
300 if child == self.nil {
301 break;
302 }
303 parent = child;
304 child = self.arena[parent][dir];
305 }
306 parent
307 }
308
309 fn root_and_height(&self, node: usize) -> (usize, usize) {
310 let mut root = node;
311 let mut height = 0;
312 loop {
313 if self.arena[root].parent == self.nil {
314 break;
315 }
316 height += 1;
317 root = self.arena[root].parent;
318 }
319 (root, height)
320 }
321
322 fn directions_to_root(&self, node: usize, height: usize) -> u64 {
323 let mut path: u64 = 0;
324 let mut child = node;
325 let mut parent = self.arena[child].parent;
326 let mut dir = if self.arena[parent][BstDirection::Left] == child {
327 BstDirection::Left
328 } else {
329 BstDirection::Right
330 };
331 let mut i = height;
332
333 loop {
334 if parent == self.nil {
335 break;
336 }
337 path |= (dir as u64) << (i as u64);
338 child = parent;
339 parent = self.arena[child].parent;
340 dir = if self.arena[parent][BstDirection::Left] == child {
341 BstDirection::Left
342 } else {
343 BstDirection::Right
344 };
345 i -= 1;
346 }
347 path >> 1
348 }
349
350 fn apply(
351 &self,
352 f: fn(&AaForest<V>, usize, BstDirection) -> usize,
353 node: usize,
354 dir: BstDirection,
355 ) -> Option<usize> {
356 if self.arena.contains(node) {
357 let ret = f(self, node, dir);
358 if ret <= self.sdummy {
359 return None;
360 }
361 return Some(ret);
362 }
363 None
364 }
365
366 fn isolate(&mut self, node: usize) -> usize {
367 if node == self.nil {
368 return self.nil;
369 }
370
371 let isolated = node;
372 let isolated_left = self.arena[isolated][BstDirection::Left];
373 let isolated_right = self.arena[isolated][BstDirection::Right];
374 let mut parent = self.arena[node].parent;
375 let dir = if self.arena[parent][BstDirection::Left] == node {
376 BstDirection::Left
377 } else {
378 BstDirection::Right
379 };
380
381 self.unlink(parent, isolated, dir);
382 self.unlink(isolated, isolated_left, BstDirection::Left);
383 self.unlink(isolated, isolated_right, BstDirection::Right);
384
385 let mut child;
386
387 if isolated_left == self.nil {
388 if isolated_right == self.nil {
389 child = parent;
390 } else {
391 child = isolated_right;
392 self.link(parent, child, dir);
393 self.arena[child].level = self.arena[isolated].level;
394 }
395 } else if isolated_right == self.nil {
396 child = isolated_left;
397 self.link(parent, child, dir);
398 self.arena[child].level = self.arena[isolated].level;
399 } else {
400 let mut heir_parent = self.nil;
401 let mut heir = isolated_left;
402 let mut heir_dir = BstDirection::Left;
403 loop {
404 let right = self.arena[heir][BstDirection::Right];
405 if right == self.nil {
406 break;
407 }
408 heir_dir = BstDirection::Right;
409 heir_parent = heir;
410 heir = right;
411 }
412
413 child = heir;
414 if heir_parent != self.nil {
415 let left = self.arena[heir][BstDirection::Left];
416 self.unlink(heir_parent, heir, heir_dir);
417 self.unlink(heir, left, BstDirection::Left);
418 self.link(heir_parent, left, BstDirection::Right);
419 child = heir_parent;
420 }
421 self.link(parent, heir, dir);
422 self.link(heir, isolated_left, BstDirection::Left);
423 self.link(heir, isolated_right, BstDirection::Right);
424 self.arena[heir].level = self.arena[isolated].level;
425 }
426
427 parent = self.arena[child].parent;
428 loop {
429 child = self.fix_node_balance(child);
430
431 if parent == self.nil {
432 return child;
433 }
434
435 child = parent;
436 parent = self.arena[child].parent;
437 }
438 }
439
440 fn fix_node_balance(&mut self, node: usize) -> usize {
441 let mut parent = node;
442 let parent_level = self.arena[parent].level;
443 let left_level = self.arena[self.arena[parent][BstDirection::Left]].level;
444 let right_level = self.arena[self.arena[parent][BstDirection::Right]].level;
445
446 if left_level + 1 < parent_level || right_level + 1 < parent_level {
447 let new_parent_level = parent_level - 1;
448 self.arena[parent].level = new_parent_level;
449 let mut right = self.arena[parent][BstDirection::Right];
450 if right_level > new_parent_level {
451 self.arena[right].level = new_parent_level;
452 }
453
454 parent = self.skew_node(parent);
455 right = self.arena[parent][BstDirection::Right];
456 right = self.skew_node(right);
457 right = self.arena[right][BstDirection::Right];
458 self.skew_node(right);
459 parent = self.split_node(parent);
460 right = self.arena[parent][BstDirection::Right];
461 self.split_node(right);
462 }
463 parent
464 }
465
466 fn join_at(&mut self, at: usize, left: usize, right: usize) -> usize {
467 self.arena[at].level = 1;
468 let mut parent = self
469 .append(NodeIndex(left), NodeIndex(at))
470 .map_or(self.nil, |p| p.index());
471 parent = self
472 .append(NodeIndex(parent), NodeIndex(right))
473 .map_or(self.nil, |p| p.index());
474 parent
475 }
476
477 fn rotate(&mut self, parent: usize, child: usize) {
478 let grandparent = self.arena[parent].parent;
479 let parent_dir = if self.arena[grandparent][BstDirection::Left] == parent {
480 BstDirection::Left
481 } else {
482 BstDirection::Right
483 };
484 let child_dir = if self.arena[parent][BstDirection::Left] == child {
485 BstDirection::Left
486 } else {
487 BstDirection::Right
488 };
489 let other_dir = child_dir.other();
490 let grandchild = self.arena[child][other_dir];
491
492 self.unlink(grandparent, parent, parent_dir);
493 self.unlink(parent, child, child_dir);
494 self.unlink(child, grandchild, other_dir);
495
496 let other_child = if child_dir == BstDirection::Right {
497 let left = self.arena[parent][BstDirection::Left];
498 self.unlink(parent, left, BstDirection::Left);
499 self.join_at(parent, left, grandchild)
500 } else {
501 let right = self.arena[parent][BstDirection::Right];
502 self.unlink(parent, right, BstDirection::Right);
503 self.join_at(parent, grandchild, right)
504 };
505 self.link(grandparent, child, parent_dir);
506 self.link(child, other_child, other_dir);
507 }
508}
509
510impl<V> Traversable<V> for AaForest<V>
511 where
512 V: ValueType,
513{
514 /// Returns the index of the root node of the tree containing the tree node indexed by `node`.
515 /// In case of an invalid index, `None` is returned.
516 fn root(&self, node: NodeIndex) -> Option<NodeIndex> {
517 let node = node.index();
518 if node <= self.sdummy || !self.arena.contains(node) {
519 return None;
520 }
521 let mut child = node;
522 let mut parent = self.arena[child].parent;
523 loop {
524 if parent == self.nil {
525 break;
526 }
527 child = parent;
528 parent = self.arena[child].parent;
529 }
530 Some(NodeIndex(child))
531 }
532
533 /// Immutably access the value stored in the tree node indexed by `node`.
534 fn value(&self, node: NodeIndex) -> Option<&V> {
535 let node = node.index();
536 if node <= self.sdummy {
537 return None;
538 }
539 self.arena.get(node).map(|n| &n.value)
540 }
541
542 /// Mutably access the value stored in the tree node indexed by `node`.
543 fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V> {
544 let node = node.index();
545 if node <= self.sdummy {
546 return None;
547 }
548 self.arena.get_mut(node).map(|n| &mut n.value)
549 }
550
551 /// Returns the index of parent node tree node indexed by `node`.
552 fn parent(&self, node: NodeIndex) -> Option<NodeIndex> {
553 let node = node.index();
554 match self.arena.get(node) {
555 Some(n) => {
556 let parent = n.parent;
557 if parent <= self.sdummy {
558 return None;
559 }
560 Some(NodeIndex(parent))
561 }
562 None => None,
563 }
564 }
565
566 /// Returns the index of the child node at position `pos` of the tree node indexed by `node`.
567 ///
568 /// Note that a binary tree node will always have two children, i.e. that even if the
569 /// left child (`pos == 0`) is empty, the right child (`pos == 1`) might contain a value.
570 /// In case of a leaf node, both children will be empty:
571 ///
572 /// ```
573 /// use outils::prelude::*;
574 ///
575 /// let mut aaforest = AaForest::new(10);
576 /// let n1 = aaforest.insert(1);
577 /// let n2 = aaforest.insert(2);
578 /// aaforest.append(n1, n2);
579 ///
580 /// // At this point, the AA algorithm has not had to rotate the tree, so that
581 /// // `n2` will be the right child of `n1`:
582 ///
583 /// assert_eq!(aaforest.child(n1, 0), None);
584 /// assert_eq!(aaforest.child(n1, 1), Some(n2));
585 /// ```
586 fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex> {
587 let node = node.index();
588 if let Some(n) = self.arena.get(node) {
589 if pos > 1 {
590 return None;
591 }
592 let child = n[pos];
593 if child <= self.sdummy {
594 return None;
595 }
596 return Some(NodeIndex(child));
597 }
598 None
599 }
600
601 /// Returns the number of child nodes of the tree node indexed by `node`.
602 ///
603 /// Note that a binary tree node will always have two children, i.e. that even if the
604 /// left child is empty, the right child might contain a value.
605 /// In case of a leaf node, both children will be empty, but the number of (empty) children
606 /// will still be 2:
607 ///
608 /// ```
609 /// use outils::prelude::*;
610 ///
611 /// let mut aaforest = AaForest::new(10);
612 /// let n1 = aaforest.insert(1);
613 /// let n2 = aaforest.insert(2);
614 /// aaforest.append(n1, n2);
615 ///
616 /// // At this point, the AA algorithm has not had to rotate the tree, so that
617 /// // `n2` will be the right child of `n1`:
618 ///
619 /// assert_eq!(aaforest.child_count(n1), 2);
620 /// assert_eq!(aaforest.child_count(n2), 2);
621 /// assert_eq!(aaforest.child_count(NodeIndex(999)), 0); // Invalid index => no children
622 /// ```
623 fn child_count(&self, node: NodeIndex) -> usize {
624 let node = node.index();
625 if self.arena.contains(node) && node > self.sdummy {
626 return 2;
627 }
628 0
629 }
630
631 /// Returns the total number of tree nodes of the forest trees in `self`.
632 fn node_count(&self) -> usize {
633 self.arena.len() - 3
634 }
635}
636
637impl<V> OrderedTree for AaForest<V>
638 where
639 V: ValueType,
640{
641 /// Returns the biggest node of the left subtree of the tree node indexed by `node`.
642 ///
643 /// ```
644 /// use outils::prelude::*; // The resulting tree is shown below:
645 /// //
646 /// let mut aaforest = AaForest::new(10); // -- (3) --
647 /// // / \
648 /// let mut indices = Vec::new(); // (1) (5)
649 /// indices.push(aaforest.insert(0)); // / \ / \
650 /// // (0) (2) (4) (6)
651 /// for i in 1..7 {
652 /// indices.push(aaforest.insert(i));
653 /// aaforest.append(indices[i-1], indices[i]);
654 /// }
655 ///
656 /// // 2 is biggest key in left subtree of 3.
657 /// assert_eq!(aaforest.sub_predecessor(indices[3]), Some(indices[2]));
658 /// // 4 is a leaf and thus has no subtrees.
659 /// assert_eq!(aaforest.sub_predecessor(indices[4]), None);
660 /// ```
661 fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex> {
662 self.apply(
663 AaForest::next_from_subtree,
664 node.index(),
665 BstDirection::Left,
666 )
667 .map(NodeIndex)
668 }
669
670 /// Returns the smallest node of the right subtree of the tree node indexed by `node`.
671 ///
672 /// Usage is analogous to [`sub_predecessor`](#method.sub_predecessor)
673 fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex> {
674 self.apply(
675 AaForest::next_from_subtree,
676 node.index(),
677 BstDirection::Right,
678 )
679 .map(NodeIndex)
680 }
681
682 /// Returns the biggest node of the whole tree which is smaller than the tree node
683 /// indexed by `node`.
684 ///
685 /// ```
686 /// use outils::prelude::*; // The resulting tree is shown below:
687 /// //
688 /// let mut aaforest = AaForest::new(10); // -- (3) --
689 /// // / \
690 /// let mut indices = Vec::new(); // (1) (5)
691 /// indices.push(aaforest.insert(0)); // / \ / \
692 /// // (0) (2) (4) (6)
693 /// for i in 1..7 {
694 /// indices.push(aaforest.insert(i));
695 /// aaforest.append(indices[i-1], indices[i]);
696 /// }
697 ///
698 /// // 3 is the biggest key of the whole tree smaller than 4.
699 /// assert_eq!(aaforest.predecessor(indices[4]), Some(indices[3]));
700 /// // 0 is globally the smallest key of the whole tree and thus has no predecessor.
701 /// assert_eq!(aaforest.predecessor(indices[0]), None);
702 /// ```
703 fn predecessor(&self, node: NodeIndex) -> Option<NodeIndex> {
704 self.apply(AaForest::next, node.index(), BstDirection::Left)
705 .map(NodeIndex)
706 }
707
708 /// Returns the smallest node of the whole tree which is bigger than the tree node
709 /// indexed by `node`.
710 ///
711 /// Usage is analogous to [`predecessor`](#method.predecessor)
712 fn successor(&self, node: NodeIndex) -> Option<NodeIndex> {
713 self.apply(AaForest::next, node.index(), BstDirection::Right)
714 .map(NodeIndex)
715 }
716
717 /// Returns the smallest node of the left subtree of the tree node indexed by `node`.
718 ///
719 /// ```
720 /// use outils::prelude::*; // The resulting tree is shown below:
721 /// //
722 /// let mut aaforest = AaForest::new(10); // -- (3) --
723 /// // / \
724 /// let mut indices = Vec::new(); // (1) (5)
725 /// indices.push(aaforest.insert(0)); // / \ / \
726 /// // (0) (2) (4) (6)
727 /// for i in 1..7 {
728 /// indices.push(aaforest.insert(i));
729 /// aaforest.append(indices[i-1], indices[i]);
730 /// }
731 ///
732 /// // 0 is the smallest key of the left subtree of 3
733 /// assert_eq!(aaforest.first(indices[3]), Some(indices[0]));
734 /// // 0 is the smallest key of the left subtree of 1
735 /// assert_eq!(aaforest.first(indices[1]), Some(indices[0]));
736 /// ```
737 fn first(&self, node: NodeIndex) -> Option<NodeIndex> {
738 self.apply(AaForest::extreme, node.index(), BstDirection::Left)
739 .map(NodeIndex)
740 }
741
742 /// Returns the biggest node of the right subtree of the tree node indexed by `node`.
743 ///
744 /// Usage is analogous to [`first`](#method.first)
745 fn last(&self, node: NodeIndex) -> Option<NodeIndex> {
746 self.apply(AaForest::extreme, node.index(), BstDirection::Right)
747 .map(NodeIndex)
748 }
749
750 /// Returns `true` if the tree node indexed by `node_u` is smaller than the tree node
751 /// indexed by `node_v`. Otherwise, and in particular if one of the specified indices
752 /// is invalid, or if the nodes do not belong to the same forest tree, `false` is returned.
753 ///
754 /// **Panics** if the path to the root from either of the tree nodes to be compared contains
755 /// more than 64 nodes. This is because the directions (i.e. left or right) on the path are
756 /// encoded in a bitmap of type `u64`. In practice it is **next to impossible** for this method to
757 /// panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.
758 ///
759 /// ```
760 /// use outils::prelude::*; // The resulting tree is shown below:
761 /// //
762 /// let mut aaforest = AaForest::new(10); // -- (3) --
763 /// // / \
764 /// let mut indices = Vec::new(); // (1) (5)
765 /// indices.push(aaforest.insert(0)); // / \ / \
766 /// // (0) (2) (4) (6)
767 /// for i in 1..7 {
768 /// indices.push(aaforest.insert(i));
769 /// aaforest.append(indices[i-1], indices[i]);
770 /// }
771 ///
772 /// assert!(aaforest.is_smaller(indices[0], indices[3]));
773 /// assert!(!aaforest.is_smaller(indices[3], indices[1]));
774 /// ```
775 fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool {
776 let node_u = node_u.index();
777 let node_v = node_v.index();
778 if !self.is_valid_index(node_u) || !self.is_valid_index(node_v) || node_u == node_v {
779 return false;
780 }
781
782 let (root_u, height_u) = self.root_and_height(node_u);
783 let (root_v, height_v) = self.root_and_height(node_v);
784
785 if root_u != root_v || root_u == self.nil {
786 return false;
787 }
788
789 let path_u = self.directions_to_root(node_u, height_u);
790 let path_v = self.directions_to_root(node_v, height_v);
791
792 let mut i = 0;
793 let mut mask = 1;
794
795 loop {
796 if (i >= height_u) || (i >= height_v) || ((path_u & mask) != (path_v & mask)) {
797 break;
798 }
799 i += 1;
800 mask <<= 1;
801 }
802 if (i < height_u) && ((path_u & mask) == 0) || (i < height_v) && ((path_v & mask) != 0) {
803 return true;
804 }
805 false
806 }
807}
808
809impl<V> BalancedBinaryForest<V> for AaForest<V>
810 where
811 V: ValueType,
812{
813 // Insert a new singleton node containing `value` into the forest.
814 fn insert(&mut self, value: V) -> NodeIndex {
815 NodeIndex(self.arena.insert(Node::new_leaf(value)))
816 }
817
818 /// Removes the tree node indexed by `node` from the tree if present, in this case returning
819 /// the associated value.
820 ///
821 /// ```
822 /// use outils::prelude::*; // The resulting tree is shown below:
823 /// use outils::tree::traversal::BinaryInOrderValues; //
824 /// // -- (3) --
825 /// let mut aaforest = AaForest::new(10); // / \
826 /// // (1) (5)
827 /// let mut indices = Vec::new(); // / \ / \
828 /// indices.push(aaforest.insert(0)); // (0) (2) (4) (6)
829 ///
830 /// for i in 1..7 {
831 /// indices.push(aaforest.insert(i));
832 /// aaforest.append(indices[i-1], indices[i]);
833 /// }
834 ///
835 /// assert_eq!(aaforest.remove(indices[5]), Some(5));
836 /// let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, indices[0]).collect();
837 /// assert_eq!(seq, vec![&0, &1, &2, &3, &4, &6]);
838 /// ```
839 fn remove(&mut self, node: NodeIndex) -> Option<V> {
840 let node = node.index();
841 if node <= self.sdummy {
842 return None;
843 }
844
845 self.arena.get(node)?;
846 self.isolate(node);
847 Some(self.arena.remove(node).value)
848 }
849
850 /// Splits the sequence of tree nodes represented by the forest tree containing the tree node
851 /// indexed by `node`.
852 ///
853 /// If `dir == BstDirection::Left`, `node` will index the last tree node of the left sequence,
854 /// while if `dir == BstDirection::Right`, `node` will index the first tree node of the right
855 /// sequence (both with respect to in-order). The roots of the resulting sequences will be
856 /// returned as a tuple.
857 ///
858 /// ```
859 /// use outils::prelude::*; // The resulting trees are shown below:
860 /// use outils::tree::traversal::BinaryInOrderValues; //
861 /// // -- (3) --
862 /// let mut aaforest1 = AaForest::new(10); // / \
863 /// let mut aaforest2 = AaForest::new(10); // (1) (5)
864 /// // / \ / \
865 /// let mut indices1 = Vec::new(); // (0) (2) (4) (6)
866 /// indices1.push(aaforest1.insert(0));
867 /// let mut indices2 = Vec::new();
868 /// indices2.push(aaforest2.insert(0));
869 ///
870 /// for i in 1..7 {
871 /// indices1.push(aaforest1.insert(i));
872 /// aaforest1.append(indices1[i-1], indices1[i]);
873 /// indices2.push(aaforest2.insert(i));
874 /// aaforest2.append(indices2[i-1], indices2[i]);
875 /// }
876 ///
877 /// // Split the tree at 3 and keep 3 as part of the left (i.e. _smaller_) tree.
878 /// let result1 = aaforest1.split(indices1[3], BstDirection::Left);
879 /// match(result1) {
880 /// (Some(left), Some(right)) => {
881 /// let seq_left: Vec<&usize> = BinaryInOrderValues::new(&aaforest1, left).collect();
882 /// assert_eq!(seq_left, vec![&0, &1, &2, &3]);
883 /// let seq_right: Vec<&usize> = BinaryInOrderValues::new(&aaforest1, right).collect();
884 /// assert_eq!(seq_right, vec![&4, &5, &6]);
885 /// }
886 /// _ => {
887 /// panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)")
888 /// }
889 /// }
890 ///
891 /// // Split the tree at 3 and keep 3 as part of the right (i.e. _bigger_) tree.
892 /// let result2 = aaforest2.split(indices2[3], BstDirection::Right);
893 /// match(result2) {
894 /// (Some(left), Some(right)) => {
895 /// let seq_left: Vec<&usize> = BinaryInOrderValues::new(&aaforest2, left).collect();
896 /// assert_eq!(seq_left, vec![&0, &1, &2]);
897 /// let seq_right: Vec<&usize> = BinaryInOrderValues::new(&aaforest2, right).collect();
898 /// assert_eq!(seq_right, vec![&3, &4, &5, &6]);
899 /// }
900 /// _ => {
901 /// panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)");
902 /// }
903 /// }
904 /// ```
905 fn split(
906 &mut self,
907 node: NodeIndex,
908 dir: BstDirection,
909 ) -> (Option<NodeIndex>, Option<NodeIndex>) {
910 let node = node.index();
911 if node <= self.sdummy || !self.arena.contains(node) {
912 return (None, None);
913 }
914
915 let dummy = self.sdummy;
916 self.init_dummy(dummy);
917
918 if dir == BstDirection::Left {
919 let succ = self.next_from_subtree(node, BstDirection::Right);
920 if succ == self.nil {
921 self.link(node, dummy, BstDirection::Right);
922 } else {
923 self.link(succ, dummy, BstDirection::Left);
924 }
925 } else {
926 let pred = self.next_from_subtree(node, BstDirection::Left);
927 if pred == self.nil {
928 self.link(node, dummy, BstDirection::Left);
929 } else {
930 self.link(pred, dummy, BstDirection::Right);
931 }
932 }
933
934 let mut parent = self.arena[dummy].parent;
935
936 loop {
937 if parent == self.nil {
938 break;
939 }
940 self.rotate(parent, dummy);
941 parent = self.arena[dummy].parent;
942 }
943
944 let left = self.arena[dummy][BstDirection::Left];
945 let right = self.arena[dummy][BstDirection::Right];
946
947 self.unlink(dummy, left, BstDirection::Left);
948 self.unlink(dummy, right, BstDirection::Right);
949 self.arena[dummy].level = 0;
950
951 if left == self.nil {
952 return (None, Some(NodeIndex(right)));
953 }
954 if right == self.nil {
955 return (Some(NodeIndex(left)), None);
956 }
957
958 (Some(NodeIndex(left)), Some(NodeIndex(right)))
959 }
960
961 /// Splits the whole sequence of tree nodes represented by the forest tree containing the tree
962 /// node indexed by `node` into singleton (i.e. sole leaf) nodes.
963 ///
964 /// If the tree nodes to be split is known beforehand, it can be specified optionally as
965 /// the `size_hint` of the returned `Vec` containing the split tree nodes.
966 ///
967 /// Generally, this operation will be much faster than calling `split` on each node of the
968 /// sequence separately, the reason being that no re-balancing is necessary when it is known
969 /// beforehand that every tree node will be split.
970 ///
971 /// ```
972 /// use outils::prelude::*; // The resulting tree is shown below:
973 /// //
974 /// let mut aaforest = AaForest::new(10); // -- (3) --
975 /// // / \
976 /// let mut indices = Vec::new(); // (1) (5)
977 /// indices.push(aaforest.insert(0)); // / \ / \
978 /// // (0) (2) (4) (6)
979 /// for i in 1..7 {
980 /// indices.push(aaforest.insert(i));
981 /// aaforest.append(indices[i-1], indices[i]);
982 /// }
983 ///
984 /// let split_nodes = aaforest.split_all(indices[0], Some(7));
985 /// assert_eq!(split_nodes.len(), indices.len());
986 ///
987 /// // After splitting the forest tree, every one of its former nodes should be a singleton:
988 /// for i in 0..7 {
989 /// assert!(split_nodes.contains(&indices[i]));
990 /// assert_eq!(aaforest.parent(indices[i]), None);
991 /// assert_eq!(aaforest.child(indices[i], 0), None);
992 /// assert_eq!(aaforest.child(indices[i], 1), None);
993 /// }
994 /// ```
995 fn split_all(&mut self, node: NodeIndex, size_hint: Option<usize>) -> Vec<NodeIndex> {
996 let nodes: Vec<NodeIndex> = match size_hint {
997 Some(s) => BinaryPreOrderIndices::with_capacity(self, node, s).collect(),
998 None => BinaryPreOrderIndices::new(self, node).collect(),
999 };
1000
1001 for n in &nodes {
1002 self.arena[n.index()].level = 1;
1003 self.arena[n.index()].parent = self.nil;
1004 self.arena[n.index()][BstDirection::Left] = self.nil;
1005 self.arena[n.index()][BstDirection::Right] = self.nil;
1006 }
1007 nodes
1008 }
1009
1010 /// Concatenate the sequences of tree nodes represented by the forest trees containing the
1011 /// tree nodes indexed by `node_u` and `node_v`, respectively.
1012 ///
1013 /// With respect to in-order, the former sequence will represent the _smaller_ part of the
1014 /// new sequence, the latter sequence the _bigger_ part. The root of the resulting sequence will
1015 /// be returned.
1016 ///
1017 /// ```
1018 /// use outils::prelude::*;
1019 /// use outils::tree::traversal::BinaryInOrderValues;
1020 /// let mut aaforest = AaForest::new(10);
1021 ///
1022 /// // Insert values into the forest - each value will be a single-node tree in the forest.
1023 /// let mut indices = Vec::new();
1024 /// for i in 0..7 {
1025 /// indices.push(aaforest.insert(i));
1026 /// }
1027 ///
1028 /// // Construct the _smaller_ tree, containing the in-order sequence 0,1,2,3
1029 /// let mut left = indices[0];
1030 /// left = aaforest.append(left, indices[1]).expect("Result should not be None");
1031 /// left = aaforest.append(left, indices[2]).expect("Result should not be None");
1032 /// left = aaforest.append(left, indices[3]).expect("Result should not be None");
1033 ///
1034 /// { // Restrict scope of the borrow of `aaforest`.
1035 /// let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, left).collect();
1036 /// assert_eq!(seq, vec![&0, &1, &2, &3]);
1037 /// }
1038 ///
1039 /// // Construct the _bigger_ tree, containing the in-order sequence 4,5,6
1040 /// let mut right = indices[4];
1041 /// right = aaforest.append(right, indices[5]).expect("Result should not be None");
1042 /// right = aaforest.append(right, indices[6]).expect("Result should not be None");
1043 ///
1044 /// { // Restrict scope of the borrow of `aaforest`.
1045 /// let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, right).collect();
1046 /// assert_eq!(seq, vec![&4, &5, &6]);
1047 /// }
1048 ///
1049 /// // Link left and right, constructing the in-order sequence 0,1,2,3,4,5,6.
1050 /// let root = aaforest.append(left, right).expect("Result should not be None");
1051 /// let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, root).collect();
1052 /// assert_eq!(seq, vec![&0, &1, &2, &3, &4, &5, &6]);
1053 /// ```
1054 fn append(&mut self, node_u: NodeIndex, node_v: NodeIndex) -> Option<NodeIndex> {
1055 let root_v = self.root(node_v).map_or(self.nil, |r| r.index());
1056 let root_u = self.root(node_u).map_or(self.nil, |r| r.index());
1057
1058 if root_u == self.nil {
1059 if root_v == self.nil {
1060 return None;
1061 } else {
1062 return Some(NodeIndex(root_v));
1063 }
1064 } else if root_v == self.nil {
1065 return Some(NodeIndex(root_u));
1066 }
1067
1068 let dir = if self.arena[root_u].level < self.arena[root_v].level {
1069 BstDirection::Left
1070 } else {
1071 BstDirection::Right
1072 };
1073
1074 let dest = if self.arena[root_u].level < self.arena[root_v].level {
1075 root_v
1076 } else {
1077 root_u
1078 };
1079
1080 let src = if self.arena[root_u].level < self.arena[root_v].level {
1081 root_u
1082 } else {
1083 root_v
1084 };
1085
1086 let target_level = self.arena[src].level;
1087 let mut parent = self.nil;
1088 let mut child = dest;
1089 let other_dir = dir.other();
1090
1091 loop {
1092 if self.arena[child].level == target_level {
1093 break;
1094 }
1095 parent = child;
1096 child = self.arena[parent][dir];
1097 }
1098
1099 self.unlink(parent, child, dir);
1100
1101 let dummy = self.jdummy;
1102 self.init_dummy(dummy);
1103 self.arena[dummy].level = target_level;
1104 self.link(dummy, child, other_dir);
1105 self.link(dummy, src, dir);
1106 self.link(parent, dummy, dir);
1107
1108 child = dummy;
1109 parent = self.arena[child].parent;
1110
1111 loop {
1112 child = self.skew_node(child);
1113 self.split_node(child);
1114
1115 if parent == self.nil {
1116 break;
1117 }
1118
1119 child = parent;
1120 parent = self.arena[child].parent;
1121 }
1122 let root = self.isolate(dummy);
1123 self.init_dummy(dummy);
1124 Some(NodeIndex(root))
1125 }
1126}
1127
1128impl<'slf, V> Values<'slf, V> for AaForest<V>
1129 where
1130 V: 'slf + ValueType,
1131{
1132 /// Returns a boxed iterator over the stored values and their corresponding
1133 /// tree node indices held by `self`. The values are not returned in any
1134 /// particular order.
1135 fn values(&'slf self) -> Box<dyn Iterator<Item=(NodeIndex, &'slf V)> + 'slf> {
1136 Box::new(
1137 self.arena
1138 .iter()
1139 .filter(move |n| n.0 > self.sdummy)
1140 .map(move |(i, n)| (NodeIndex(i), &n.value)),
1141 )
1142 }
1143}
1144
1145impl<V> Index<NodeIndex> for AaForest<V>
1146 where
1147 V: ValueType,
1148{
1149 type Output = V;
1150 fn index(&self, index: NodeIndex) -> &V {
1151 &self.arena[index.index()].value
1152 }
1153}
1154
1155impl<V> IndexMut<NodeIndex> for AaForest<V>
1156 where
1157 V: ValueType,
1158{
1159 fn index_mut(&mut self, index: NodeIndex) -> &mut V {
1160 &mut self.arena[index.index()].value
1161 }
1162}
1163
1164impl<V> Tgf for AaForest<V>
1165 where
1166 V: ValueType,
1167{
1168 fn to_tgf(&self) -> String {
1169 let mut nodes = String::from("");
1170 let mut edges = String::from("");
1171 let iter = self.arena.iter();
1172 for (index, node) in iter {
1173 nodes.push_str(format!("{}", index).as_str());
1174 if index == self.nil {
1175 nodes.push_str(" [K = NIL");
1176 } else if index == self.jdummy || index == self.sdummy {
1177 nodes.push_str(" [K = DUMMY");
1178 } else {
1179 nodes.push_str(" [K = ");
1180 nodes.push_str(format!("{:?}", node.value).as_str());
1181 }
1182 nodes.push_str(", L = ");
1183 nodes.push_str(format!("{}", node.level).as_str());
1184 nodes.push_str("]\n");
1185
1186 if node[BstDirection::Left] != self.nil {
1187 edges.push_str(format!("{}", index).as_str());
1188 edges.push_str(" ");
1189 edges.push_str(format!("{}", node[BstDirection::Left]).as_str());
1190 edges.push_str(" BstDirection::Left\n");
1191 }
1192
1193 if node[BstDirection::Right] != self.nil {
1194 edges.push_str(format!("{}", index).as_str());
1195 edges.push_str(" ");
1196 edges.push_str(format!("{}", node[BstDirection::Right]).as_str());
1197 edges.push_str(" BstDirection::Right\n");
1198 }
1199 }
1200 nodes.push_str("#\n");
1201 nodes.push_str(edges.as_str());
1202 nodes
1203 }
1204}