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