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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

use std::convert::Infallible;

use getset::{Getters, MutGetters, Setters};


#[derive(Debug, Clone)]
pub struct ContentTree<T> {
    nodes: Vec<ContentTreeNode<T>>
}

impl<T> ContentTree<T> {

    pub fn new_empty() -> Self {
        Self {
            nodes: Vec::new()
        }
    }

    pub fn nodes(&self) -> &Vec<ContentTreeNode<T>> {
        &self.nodes
    }
}


#[derive(Debug, Clone, Getters, MutGetters, Setters)]
pub struct ContentTreeNode<T> {

    #[getset(get = "pub", get_mut = "pub", set = "pub")]
    content: T,

    #[getset(get = "pub", get_mut = "pub", set = "pub")]
    sub_nodes: Vec<ContentTreeNode<T>>,
}

impl<T> ContentTreeNode<T> {
    pub fn new(content: T, sub_nodes: Vec<ContentTreeNode<T>>) -> Self {
        Self {
            content,
            sub_nodes
        }
    }

    pub fn new_leaf(content: T) -> Self {
        Self::new(content, vec![])
    }

    /// Return true is a leaf (`sub_contents.len() == 0`), else false
    pub fn is_leaf(&self) -> bool {
        self.sub_nodes.len() == 0
    }
}

impl<T: Clone> ContentTreeNode<T> {

    /// Walk tree using depth first approach.
    /// 
    /// Return cloned contents Vector
    pub fn walk_depth_first(&self) -> Vec<T> {
        let mut contents: Vec<T> = Vec::new();

        Self::walk_depth_first_rec(&self, &mut |node: &ContentTreeNode<T>, _current_lv: usize| -> Result<(), Infallible> {
            contents.push(node.content().clone());

            Ok(())
        }, 0).unwrap();

        contents
    }

    fn walk_depth_first_rec<O, E>(node: &ContentTreeNode<T>, f: &mut dyn FnMut(&ContentTreeNode<T>, usize) -> Result<O, E>, current_lv: usize) -> Result<(), E> {

        f(node, current_lv)?;

        if node.is_leaf() {
            return Ok(());
        }

        for sub_node in node.sub_nodes() {

            Self::walk_depth_first_rec(sub_node, f, current_lv + 1)?;
        }

        Ok(())
    }

    pub fn walk_depth_first_applying<O, E>(&self, f: &mut dyn FnMut(&ContentTreeNode<T>, usize) -> Result<O, E>) -> Result<(), E> {
        Self::walk_depth_first_rec(&self, f, 0)?;

        Ok(())
    }
}


#[cfg(test)]
mod test {
    use super::ContentTreeNode;


    fn get_content_tree_to_test() -> ContentTreeNode<u32> {
        let tree = ContentTreeNode::new(
            1,
            vec![
                ContentTreeNode::new(
                    2,
                    vec![
                        ContentTreeNode::new_leaf(3),
                        ContentTreeNode::new_leaf(4),
                        ContentTreeNode::new_leaf(5),
                    ]
                ),
                ContentTreeNode::new_leaf(6),
                ContentTreeNode::new_leaf(7),
            ]
        );

        tree
    }

    #[test]
    fn walk_depth_first() {

        let tree = get_content_tree_to_test();
        let output: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7];

        assert_eq!(tree.walk_depth_first(), output);
    }
}