decursion 0.1.0

Write recursive algorithms without worrying about stack overflows
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

use decursion::*;

#[derive(Default)]
struct Tree {
    children: Vec<Tree>,
}

fn recursive_total_nodes(mut tree: Tree) -> usize {
    let mut result = 1;
    for child in std::mem::take(&mut tree.children) {
        result += recursive_total_nodes(child);
    }
    result
}

const N: usize = 1_000_000;
fn construct_tree() -> Tree {
    let mut tree = Tree::default();
    for _ in 0..N {
        tree = Tree {
            children: vec![tree, Tree::default()],
        };
    }
    tree
}

#[test]
#[ignore = "this test stack overflows"]
fn test_overflow() {
    let tree = construct_tree();
    assert_eq!(recursive_total_nodes(tree), N * 2 + 1);
}

async fn total_nodes(mut tree: Tree) -> usize {
    let mut result = 1;
    for child in std::mem::take(&mut tree.children) {
        result += total_nodes(child).decurse().await;
    }
    result
}

#[test]
fn test_decursed() {
    let tree = construct_tree();
    assert_eq!(run_decursing(total_nodes(tree)), N * 2 + 1);
}

impl Drop for Tree {
    fn drop(&mut self) {
        if self.children.is_empty() {
            return;
        }
        async fn safe_drop(mut tree: Tree) {
            for child in std::mem::take(&mut tree.children) {
                safe_drop(child).decurse().await;
            }
        }
        run_decursing(safe_drop(std::mem::take(self)));
    }
}