quarkrs/structures/
tree.rs

1
2
3struct TreeNode<T> {
4    key: String,
5    value: T,
6    arcs: Vec<TreeNode<T>>
7}
8
9impl<T> Clone for TreeNode<T> where T: Clone {
10    fn clone(&self) -> Self {
11        Self { 
12            key: self.key.clone(),
13            value: self.value.clone(), 
14            arcs: self.arcs.clone() 
15        }
16    }
17}
18
19impl<T> TreeNode<T> {
20    fn new(key: &str, value: T) -> TreeNode<T>{
21        TreeNode{
22            key: key.to_string(),
23            value: value,
24            arcs: vec![]
25        }
26    }
27
28    fn add_subtree(&mut self, tree: TreeNode<T>) {
29        self.arcs.insert(self.arcs.len(), tree);
30    }
31}
32
33pub struct Tree<T> {
34    root: TreeNode<T>
35}
36
37impl<T> Tree<T> where T: Clone, T: Send {
38    pub fn new(key: &str, value: T) -> Tree<T> {
39        Tree { root: TreeNode::new(key, value) }
40    }
41
42    pub fn get_size(&self) -> usize {
43        let count = 0;
44        Tree::_get_size(self.root.clone(), count)
45    }
46
47    fn _get_size(sub_tree: TreeNode<T>, mut count: usize) -> usize {
48        for node in sub_tree.arcs {
49            count = Tree::_get_size(node, count);
50        }
51        return count + 1;
52    }
53
54    pub fn bredth_first(&self, key: &str) -> Option<T> {
55        let mut queue = self.root.arcs.clone();
56
57        while queue.len() > 0 {
58            let mut node = queue.pop().unwrap();
59            if node.key == key {
60                return Some(node.value);
61            }
62            queue.append(&mut node.arcs)
63            
64        }
65
66        return None;
67    }
68
69    pub fn depth_first(&self, key: &str) -> Option<T> {
70        Tree::_depth_first(self.root.clone(), key.to_string())
71    }
72
73    fn _depth_first(sub_tree: TreeNode<T>, key: String) -> Option<T> {
74        let mut out:Option<T> = None;
75        if sub_tree.key == key {return Some(sub_tree.value);}
76        for node in sub_tree.arcs {
77            out = Tree::_depth_first(node, key.clone());
78        }
79        return out;
80    }
81
82    fn node_search(&self, key: &str) -> Option<TreeNode<T>> {
83        let mut queue = self.root.arcs.clone();
84
85        while queue.len() > 0 {
86            let mut node = queue.pop().unwrap();
87            if node.key == key {
88                return Some(node);
89            }
90            queue.append(&mut node.arcs)
91            
92        }
93
94        return None;
95    }
96
97
98
99    // fn flood_search(&self, key: &str) -> Option<T> {
100    //     Tree::_flood_search(self.root.clone(), key.to_string())
101    // }
102
103    // fn _flood_search(sub_tree: TreeNode<T>, key: String) -> Option<T> {
104    //     if sub_tree.key == key {return Some(sub_tree.value);}
105    //     thread::spawn(move || {
106    //         let mut out = None;
107    //         for node in sub_tree.arcs {
108    //             out = Tree::_flood_search(node, key);
109    //         }
110    //         return out;
111    //     }).join().unwrap()
112    // }
113
114    pub fn insert_value(&mut self, parent_key: &str, key: &str, value: T) -> bool {
115        match self.node_search(parent_key) {
116            Some(mut parent) => {
117                parent.arcs.insert(parent.arcs.len(), TreeNode::new(key, value));
118                true
119            },
120            None => false
121        }
122    }
123
124
125    pub fn remove_subtree(&mut self, parent_tree: &str) -> bool {
126        match self.node_search(parent_tree) {
127            Some(mut tree) => {
128                tree.arcs = vec![];
129                true
130            },
131            None => false,
132        }
133    }
134
135    pub fn update_value(&self, key: &str, new_value: T) -> bool {
136        match self.node_search(key) {
137            Some(mut node) => {
138                node.value = new_value;
139                true
140            },
141            None => false,
142        }
143    }
144
145    pub fn update_key(&self, key: &str, new_key: &str) -> bool {
146        match self.node_search(key) {
147            Some(mut node) => {
148                node.key = new_key.to_string();
149                true
150            },
151            None => false,
152        }
153    }
154
155}
quarkrs/structures/tree.rs

quarkrs/structures/
tree.rs
