tree_mem_sort/lib.rs
1//! # Tree-Memory-Sort
2//!
3//! An in-memory topological sort algorithm for trees based on Group Theory
4//!
5//! ### Design
6//!
7//! This algorithm uses in-memory swapping directly on the array which nodes are stored.
8//! Since swap operations satisfy the axioms of Group Theory,
9//! the topological sort can be made more efficient by using a group generator.
10//!
11//! A group generator is an array which stores an index for every node index.
12//! When swap operations are performed on the array instead of the data,
13//! it is possible to predict where nodes will be stored in the solution
14//! without changing the meaning of the current node indices.
15//!
16//! Once a solution has been found, the group generator can be used to
17//! retrace the swapping operations required to order the tree.
18//!
19//! The order which swaps are retraced might be different than the solving phase:
20//!
21//! ```text
22//! `a, b, c` => `a, (c, b)` => `(c, a), b` => `c, a, b` (solving phase)
23//! `c, a, b` => `(b), a, (c)` => `(a, b), c` => `a, b, c` (retrace phase)
24//! ```
25//!
26//!
27//! ### Primes example
28//!
29//! This example shows how the algorithm works using some simple numbers.
30//!
31//! Assume that you have two equations:
32//!
33//! ```text
34//! 12 = 2 * 6
35//! 6 = 3 * 2
36//! ```
37//!
38//! If you arrange these equations as a tree,
39//! you will naturally start at the top `12` and list
40//! children of each node in the same order as in the equations.
41//!
42//! When using an automated theorem prover that re-writes
43//! a tree like this, it can get messy.
44//! Some algorithms relies on a well-ordered tree to perform efficiently.
45//!
46//! By performing topological sort on the tree,
47//! it can be restored to a well-ordered form:
48//!
49//! ```text
50//! Tree i i'
51//! --------------------------
52//! 12 3 => 0
53//! |- 2 2 => 1
54//! |- 6 1 => 2
55//! |- 3 4 => 3
56//! |- 2 0 => 4
57//! ```
58//!
59//! The algorithm does not change the relative connections inside the tree,
60//! just how nodes are stored in memory.
61//! However, it needs to change the indices such they point to the correct nodes.
62//!
63//! Source code:
64//!
65//! ```rust
66//! extern crate tree_mem_sort;
67//!
68//! use tree_mem_sort::sort;
69//!
70//! #[derive(Debug)]
71//! pub struct Number {
72//! /// The value of the number.
73//! pub value: u32,
74//! /// Which number this was factored from.
75//! pub parent: Option<usize>,
76//! /// Prime factors.
77//! pub children: Vec<usize>,
78//! }
79//!
80//! fn main() {
81//! let mut nodes = vec![
82//! Number {
83//! value: 2,
84//! parent: Some(1),
85//! children: vec![],
86//! }, // 0
87//! Number {
88//! value: 6,
89//! parent: Some(0),
90//! children: vec![4, 0],
91//! }, // 1
92//! Number {
93//! value: 2,
94//! parent: Some(2),
95//! children: vec![],
96//! }, // 2
97//! Number {
98//! value: 12,
99//! parent: None,
100//! children: vec![2, 1],
101//! }, // 3
102//! Number {
103//! value: 3,
104//! parent: Some(2),
105//! children: vec![],
106//! }, // 4
107//! ];
108//! for i in 0..nodes.len() {
109//! println!("{}: {:?}", i, nodes[i]);
110//! }
111//! // Prints `[2, 6, 2, 12, 3]`
112//! println!("{:?}", nodes.iter().map(|n| n.value).collect::<Vec<u32>>());
113//!
114//! sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
115//! println!("");
116//! for i in 0..nodes.len() {
117//! println!("{}: {:?}", i, nodes[i]);
118//! }
119//! // Prints `[12, 2, 6, 3, 2]`
120//! println!("{:?}", nodes.iter().map(|n| n.value).collect::<Vec<u32>>());
121//! }
122//! ```
123//!
124//! ### Limitations
125//!
126//! The `sort` algorithm assumes that each node is referenced by maximum one parent.
127//! If you share nodes between parent nodes, the algorithm might enter an infinite loop.
128//!
129//! One can use `sort_dag` to sort a tree where nodes can have multiple parents.
130//! In order for the algorithm to work with shared nodes,
131//! the tree must be a Directed Acyclic Graph (DAG).
132//! If the tree is not a DAG, the algorithm will run in an infinite loop.
133//!
134//! ### Why topological sort on trees? Why not use DAG representation?
135//!
136//! The idea is to preserve the following properties, and otherwise minimize work:
137//!
138//! - Each child is greater than their parent
139//! - Each sibling is greater than previous siblings
140//!
141//! Topological sorts is often associated with Directed Acyclic Graphs (DAG) and not trees.
142//! This algorithm works on DAGs, but not on all trees with shared nodes.
143//!
144//! - If every node is referenced by maximum one parent, then it is automatically a DAG
145//! - Trees with ordered children encode arrows among siblings, which affects whether it is a DAG
146//!
147//! For example, the following tree with shared nodes is not a DAG:
148//!
149//! ```text
150//! A
151//! |- B
152//! |- D
153//! |- C
154//! |- C
155//! |- D
156//! ```
157//!
158//! Notice that `B` orders `D` before `C`, so `D` is less than `C`.
159//! However, since `D` is a child of `C` it must be greater than `C`.
160//! This leads to a contradiction.
161//!
162//! If you try to sort the tree above using `sort_dag`, it will run in an infinite loop.
163//!
164//! Trees are easy to reason about and has a more efficient encoding for this library's common usage.
165//! For `N` children, the arrows of an equivalent DAG requires at least `N` arrows.
166//! In addition, these arrows must be arranged in a such way that the children becomes a total order.
167//! This is necessary to determine the order for every pair of children.
168//! By using a tree with ordered children, the memory required for arrows is zero,
169//! because the children are stored in an array anyway.
170//!
171//! A left-child first traversal of a tree without shared nodes
172//! can be used to produce a topological order.
173//! However, building indices from traversal of a tree makes all indices
174//! of a right-child larger than the indices of a left-child.
175//! This moves nodes around more than desirable.
176//!
177//! For forests, a tree traversal also requires an extra pass through all nodes.
178//! Here, the algorithm that sorts trees also works for forests without modification.
179//!
180//! A topological sort of a tree has the property that if you push a new node
181//! at the end of the array storing the nodes, which node's parent is any existing node,
182//! then the new tree is topologically sorted.
183//! The same is not true for indices built from tree traversal.
184
185#![deny(missing_docs)]
186
187/// Performs in-memory topological sort on a tree where
188/// order is determined by every child being greater than their parent,
189/// and every sibling being greater than previous siblings.
190pub fn sort<T, P, C>(nodes: &mut [T], parent: P, children: C)
191 where P: Fn(&mut T) -> &mut Option<usize>,
192 C: Fn(&mut T) -> &mut [usize]
193{
194 // This problem can be solved efficiently using Group Theory.
195 // This avoids the need for cloning nodes into a new array,
196 // while performing the minimum work to get a normalized tree.
197 //
198 // Create a group generator that is modified by swapping to find a solution.
199 // The group generator keeps track of indices, such that child-parent relations
200 // do not have to change until later.
201 //
202 // Use the order in the generator to detect whether a swap has been performed.
203 // The condition for swapping `a, b` is `gen[a] > gen[b]`.
204 let mut gen: Vec<usize> = (0..nodes.len()).collect();
205 loop {
206 let mut changed = false;
207 for i in 0..nodes.len() {
208 let children = children(&mut nodes[i]);
209 for j in 0..children.len() {
210 let a = children[j];
211 // Store child after its parent.
212 if gen[i] > gen[a] {
213 gen.swap(i, a);
214 changed = true;
215 }
216 // Check all pairs of children.
217 for k in j + 1..children.len() {
218 let b = children[k];
219
220 // Store children in sorted order.
221 if gen[a] > gen[b] {
222 gen.swap(a, b);
223 changed = true;
224 }
225 }
226 }
227 }
228 if !changed {
229 break;
230 }
231 }
232
233 // Update the tree data with the new indices from the generator.
234 // Do this before performing the actual swapping,
235 // since the generator maps from old indices to new indices.
236 for i in 0..nodes.len() {
237 let p = parent(&mut nodes[i]);
238 *p = p.map(|p| gen[p]);
239 for ch in children(&mut nodes[i]) {
240 *ch = gen[*ch]
241 }
242 }
243
244 // Swap nodes using the group generator as guide.
245 // When swapping has been performed, update the generator to keep track of state.
246 // This is because multiple swaps sharing elements might require multiple steps.
247 //
248 // The order which swaps are retraced might be different than the solving phase:
249 //
250 // `a, b, c` => `a, (c, b)` => `(c, a), b` => `c, a, b` (solving phase)
251 // `c, a, b` => `(b), a, (c)` => `(a, b), c` => `a, b, c` (retrace phase)
252 //
253 // However, since the generator solution is produced by swapping operations,
254 // it is guaranteed to be restorable to the identity generator when retracing.
255 // In fact, it works for any permutation of the identity generator.
256 //
257 // There is no need to loop more than once because each index is stored uniquely by lookup,
258 // such that if `g[i] = i` then there exists no `j != i` such that `g[j] = i`.
259 //
260 // Retrace by putting nodes where they belong (`g[i]`).
261 // Once a node is put where it belongs, no need further work is needed for `g[i]`.
262 // It means that the problem has been reduced from size `n` to `n-1`.
263 //
264 // However, in order to put one node from `i` to where it belongs `g[i]`,
265 // one must also keep track of the node who occupied the previous `j = g[i]`.
266 // Not only keep track of the node data, but where it belongs `g[j]` too.
267 //
268 // Fortunately, the old position (`i`) is free as a temporary location.
269 // This is why `i` and `g[i]` are swapped.
270 // The same swap is done in the group generator to track where the new node belongs:
271 // `gen[j] => gen[i]`
272 //
273 // This procedure is repeated for the new node `i`,
274 // putting it where it belongs `g[i]`, and in return receive a new task `gen[j] => gen[i]`.
275 // The task is repeated until `i` belongs to where it should be,
276 // then it goes to the next step, where the same procedure is repeated.
277 // All nodes which have previously been put where they belong does not need any work,
278 // and there is no need to go back, since no node will be swapped with an earlier location.
279 for i in 0..nodes.len() {
280 while gen[i] != i {
281 let j = gen[i];
282 nodes.swap(i, j);
283 gen.swap(i, j);
284 }
285 }
286}
287
288/// The same algorithm as `sort`, but for Directed Acyclic Graphs (DAGs),
289/// encoded as trees with shared nodes.
290///
291/// WARNING: To avoid an infinite loop, one must be careful about the order of children.
292/// E.g. if `A` has children `C, B` and `B` has child `C`, then the tree is not a DAG.
293/// This is because the order of children is preserved after sorting.
294pub fn sort_dag<T, P, C>(nodes: &mut [T], parents: P, children: C)
295 where P: Fn(&mut T) -> &mut [usize],
296 C: Fn(&mut T) -> &mut [usize]
297{
298 let mut gen: Vec<usize> = (0..nodes.len()).collect();
299 loop {
300 let mut changed = false;
301 for i in 0..nodes.len() {
302 let children = children(&mut nodes[i]);
303 for j in 0..children.len() {
304 let a = children[j];
305 // Store child after its parent.
306 if gen[i] > gen[a] {
307 gen.swap(i, a);
308 changed = true;
309 }
310 // Check all pairs of children.
311 for k in j + 1..children.len() {
312 let b = children[k];
313
314 // Store children in sorted order.
315 if gen[a] > gen[b] {
316 gen.swap(a, b);
317 changed = true;
318 }
319 }
320 }
321 }
322 if !changed {
323 break;
324 }
325 }
326
327 for i in 0..nodes.len() {
328 for p in parents(&mut nodes[i]) {
329 *p = gen[*p];
330 }
331 for ch in children(&mut nodes[i]) {
332 *ch = gen[*ch]
333 }
334 }
335
336 for i in 0..nodes.len() {
337 while gen[i] != i {
338 let j = gen[i];
339 nodes.swap(i, j);
340 gen.swap(i, j);
341 }
342 }
343}
344
345#[cfg(test)]
346mod tests {
347 use super::*;
348
349 #[derive(PartialEq, Debug)]
350 struct Node {
351 val: u32,
352 parent: Option<usize>,
353 children: Vec<usize>,
354 }
355
356 #[test]
357 fn empty() {
358 let mut nodes: Vec<Node> = vec![];
359 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
360 assert_eq!(nodes.len(), 0);
361 }
362
363 #[test]
364 fn one() {
365 let mut nodes: Vec<Node> = vec![Node {
366 val: 0,
367 parent: None,
368 children: vec![],
369 }];
370 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
371 assert_eq!(
372 nodes,
373 vec![Node {
374 val: 0,
375 parent: None,
376 children: vec![]
377 }]
378 );
379 }
380
381 #[test]
382 fn two() {
383 let mut nodes: Vec<Node> = vec![
384 Node {
385 val: 0,
386 parent: None,
387 children: vec![],
388 },
389 Node {
390 val: 1,
391 parent: None,
392 children: vec![],
393 },
394 ];
395 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
396 assert_eq!(
397 nodes,
398 vec![
399 Node {
400 val: 0,
401 parent: None,
402 children: vec![]
403 },
404 Node {
405 val: 1,
406 parent: None,
407 children: vec![]
408 },
409 ]
410 );
411
412 let mut nodes: Vec<Node> = vec![
413 Node {
414 val: 1,
415 parent: Some(1),
416 children: vec![],
417 },
418 Node {
419 val: 0,
420 parent: None,
421 children: vec![0],
422 },
423 ];
424 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
425 assert_eq!(
426 nodes,
427 vec![
428 Node {
429 val: 0,
430 parent: None,
431 children: vec![1]
432 },
433 Node {
434 val: 1,
435 parent: Some(0),
436 children: vec![]
437 },
438 ]
439 );
440 }
441
442 #[test]
443 fn three() {
444 let mut nodes: Vec<Node> = vec![
445 Node {
446 val: 2,
447 parent: Some(1),
448 children: vec![],
449 },
450 Node {
451 val: 1,
452 parent: Some(2),
453 children: vec![0],
454 },
455 Node {
456 val: 0,
457 parent: None,
458 children: vec![1],
459 },
460 ];
461 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
462 assert_eq!(
463 nodes,
464 vec![
465 Node {
466 val: 0,
467 parent: None,
468 children: vec![1]
469 },
470 Node {
471 val: 1,
472 parent: Some(0),
473 children: vec![2]
474 },
475 Node {
476 val: 2,
477 parent: Some(1),
478 children: vec![]
479 }
480 ]
481 );
482
483 let mut nodes: Vec<Node> = vec![
484 Node {
485 val: 1,
486 parent: Some(2),
487 children: vec![1],
488 },
489 Node {
490 val: 2,
491 parent: Some(0),
492 children: vec![],
493 },
494 Node {
495 val: 0,
496 parent: None,
497 children: vec![0],
498 },
499 ];
500 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
501 assert_eq!(
502 nodes,
503 vec![
504 Node {
505 val: 0,
506 parent: None,
507 children: vec![1]
508 },
509 Node {
510 val: 1,
511 parent: Some(0),
512 children: vec![2]
513 },
514 Node {
515 val: 2,
516 parent: Some(1),
517 children: vec![]
518 }
519 ]
520 );
521
522 let mut nodes: Vec<Node> = vec![
523 Node {
524 val: 2,
525 parent: Some(2),
526 children: vec![],
527 },
528 Node {
529 val: 1,
530 parent: Some(2),
531 children: vec![],
532 },
533 Node {
534 val: 0,
535 parent: None,
536 children: vec![1, 0],
537 },
538 ];
539 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
540 assert_eq!(
541 nodes,
542 vec![
543 Node {
544 val: 0,
545 parent: None,
546 children: vec![1, 2]
547 },
548 Node {
549 val: 1,
550 parent: Some(0),
551 children: vec![]
552 },
553 Node {
554 val: 2,
555 parent: Some(0),
556 children: vec![]
557 }
558 ]
559 );
560
561 let mut nodes: Vec<Node> = vec![
562 Node {
563 val: 1,
564 parent: Some(2),
565 children: vec![],
566 },
567 Node {
568 val: 2,
569 parent: Some(2),
570 children: vec![],
571 },
572 Node {
573 val: 0,
574 parent: None,
575 children: vec![0, 1],
576 },
577 ];
578 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
579 assert_eq!(
580 nodes,
581 vec![
582 Node {
583 val: 0,
584 parent: None,
585 children: vec![1, 2]
586 },
587 Node {
588 val: 1,
589 parent: Some(0),
590 children: vec![]
591 },
592 Node {
593 val: 2,
594 parent: Some(0),
595 children: vec![]
596 }
597 ]
598 );
599
600 let mut nodes: Vec<Node> = vec![
601 Node {
602 val: 1,
603 parent: Some(1),
604 children: vec![],
605 },
606 Node {
607 val: 0,
608 parent: None,
609 children: vec![0, 2],
610 },
611 Node {
612 val: 2,
613 parent: Some(1),
614 children: vec![],
615 },
616 ];
617 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
618 assert_eq!(
619 nodes,
620 vec![
621 Node {
622 val: 0,
623 parent: None,
624 children: vec![1, 2]
625 },
626 Node {
627 val: 1,
628 parent: Some(0),
629 children: vec![]
630 },
631 Node {
632 val: 2,
633 parent: Some(0),
634 children: vec![]
635 }
636 ]
637 );
638
639 let mut nodes: Vec<Node> = vec![
640 Node {
641 val: 2,
642 parent: Some(1),
643 children: vec![],
644 },
645 Node {
646 val: 0,
647 parent: None,
648 children: vec![2, 0],
649 },
650 Node {
651 val: 1,
652 parent: Some(1),
653 children: vec![],
654 },
655 ];
656 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
657 assert_eq!(
658 nodes,
659 vec![
660 Node {
661 val: 0,
662 parent: None,
663 children: vec![1, 2]
664 },
665 Node {
666 val: 1,
667 parent: Some(0),
668 children: vec![]
669 },
670 Node {
671 val: 2,
672 parent: Some(0),
673 children: vec![]
674 }
675 ]
676 );
677 }
678
679 #[test]
680 fn four() {
681 let mut nodes: Vec<Node> = vec![
682 Node {
683 val: 3,
684 parent: Some(1),
685 children: vec![],
686 },
687 Node {
688 val: 2,
689 parent: Some(2),
690 children: vec![0],
691 },
692 Node {
693 val: 1,
694 parent: Some(3),
695 children: vec![1],
696 },
697 Node {
698 val: 0,
699 parent: None,
700 children: vec![2],
701 },
702 ];
703 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
704 assert_eq!(
705 nodes,
706 vec![
707 Node {
708 val: 0,
709 parent: None,
710 children: vec![1]
711 },
712 Node {
713 val: 1,
714 parent: Some(0),
715 children: vec![2]
716 },
717 Node {
718 val: 2,
719 parent: Some(1),
720 children: vec![3]
721 },
722 Node {
723 val: 3,
724 parent: Some(2),
725 children: vec![]
726 }
727 ]
728 );
729
730 let mut nodes: Vec<Node> = vec![
731 Node {
732 val: 2,
733 parent: Some(2),
734 children: vec![1],
735 },
736 Node {
737 val: 3,
738 parent: Some(0),
739 children: vec![],
740 },
741 Node {
742 val: 1,
743 parent: Some(3),
744 children: vec![0],
745 },
746 Node {
747 val: 0,
748 parent: None,
749 children: vec![2],
750 },
751 ];
752 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
753 assert_eq!(
754 nodes,
755 vec![
756 Node {
757 val: 0,
758 parent: None,
759 children: vec![1]
760 },
761 Node {
762 val: 1,
763 parent: Some(0),
764 children: vec![2]
765 },
766 Node {
767 val: 2,
768 parent: Some(1),
769 children: vec![3]
770 },
771 Node {
772 val: 3,
773 parent: Some(2),
774 children: vec![]
775 }
776 ]
777 );
778
779 let mut nodes: Vec<Node> = vec![
780 Node {
781 val: 2,
782 parent: Some(3),
783 children: vec![1],
784 },
785 Node {
786 val: 3,
787 parent: Some(0),
788 children: vec![],
789 },
790 Node {
791 val: 0,
792 parent: None,
793 children: vec![3],
794 },
795 Node {
796 val: 1,
797 parent: Some(2),
798 children: vec![0],
799 },
800 ];
801 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
802 assert_eq!(
803 nodes,
804 vec![
805 Node {
806 val: 0,
807 parent: None,
808 children: vec![1]
809 },
810 Node {
811 val: 1,
812 parent: Some(0),
813 children: vec![2]
814 },
815 Node {
816 val: 2,
817 parent: Some(1),
818 children: vec![3]
819 },
820 Node {
821 val: 3,
822 parent: Some(2),
823 children: vec![]
824 }
825 ]
826 );
827
828 let mut nodes: Vec<Node> = vec![
829 Node {
830 val: 2,
831 parent: Some(2),
832 children: vec![],
833 },
834 Node {
835 val: 3,
836 parent: Some(3),
837 children: vec![],
838 },
839 Node {
840 val: 1,
841 parent: Some(3),
842 children: vec![0],
843 },
844 Node {
845 val: 0,
846 parent: None,
847 children: vec![2, 1],
848 },
849 ];
850 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
851 assert_eq!(
852 nodes,
853 vec![
854 Node {
855 val: 0,
856 parent: None,
857 children: vec![1, 3]
858 },
859 Node {
860 val: 1,
861 parent: Some(0),
862 children: vec![2]
863 },
864 Node {
865 val: 2,
866 parent: Some(1),
867 children: vec![]
868 },
869 Node {
870 val: 3,
871 parent: Some(0),
872 children: vec![]
873 }
874 ]
875 );
876
877 let mut nodes: Vec<Node> = vec![
878 Node {
879 val: 3,
880 parent: Some(3),
881 children: vec![],
882 },
883 Node {
884 val: 1,
885 parent: None,
886 children: vec![],
887 },
888 Node {
889 val: 2,
890 parent: Some(3),
891 children: vec![],
892 },
893 Node {
894 val: 0,
895 parent: None,
896 children: vec![2, 0],
897 },
898 ];
899 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
900 assert_eq!(
901 nodes,
902 vec![
903 Node {
904 val: 0,
905 parent: None,
906 children: vec![2, 3]
907 },
908 Node {
909 val: 1,
910 parent: None,
911 children: vec![]
912 },
913 Node {
914 val: 2,
915 parent: Some(0),
916 children: vec![]
917 },
918 Node {
919 val: 3,
920 parent: Some(0),
921 children: vec![]
922 }
923 ]
924 );
925
926 let mut nodes: Vec<Node> = vec![
927 Node {
928 val: 3,
929 parent: Some(2),
930 children: vec![],
931 },
932 Node {
933 val: 2,
934 parent: Some(2),
935 children: vec![],
936 },
937 Node {
938 val: 1,
939 parent: Some(3),
940 children: vec![1, 0],
941 },
942 Node {
943 val: 0,
944 parent: None,
945 children: vec![2],
946 },
947 ];
948 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
949 assert_eq!(
950 nodes,
951 vec![
952 Node {
953 val: 0,
954 parent: None,
955 children: vec![1]
956 },
957 Node {
958 val: 1,
959 parent: Some(0),
960 children: vec![2, 3]
961 },
962 Node {
963 val: 2,
964 parent: Some(1),
965 children: vec![]
966 },
967 Node {
968 val: 3,
969 parent: Some(1),
970 children: vec![]
971 }
972 ]
973 );
974
975 let mut nodes: Vec<Node> = vec![
976 Node {
977 val: 0,
978 parent: None,
979 children: vec![3, 2],
980 },
981 Node {
982 val: 2,
983 parent: Some(3),
984 children: vec![],
985 },
986 Node {
987 val: 3,
988 parent: Some(0),
989 children: vec![],
990 },
991 Node {
992 val: 1,
993 parent: Some(0),
994 children: vec![1],
995 },
996 ];
997 sort(&mut nodes, |n| &mut n.parent, |n| &mut n.children);
998 assert_eq!(
999 nodes,
1000 vec![
1001 Node {
1002 val: 0,
1003 parent: None,
1004 children: vec![1, 3]
1005 },
1006 Node {
1007 val: 1,
1008 parent: Some(0),
1009 children: vec![2]
1010 },
1011 Node {
1012 val: 2,
1013 parent: Some(1),
1014 children: vec![]
1015 },
1016 Node {
1017 val: 3,
1018 parent: Some(0),
1019 children: vec![]
1020 },
1021 ]
1022 );
1023 }
1024}