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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
use crate::node::*;
use crate::iter::*;
//---- Structs ----//
/// Struct that contains a tree.
#[derive(Debug)]
pub struct Tree<T: NodeContent = RawNode> {
/// Tree nodes.
nodes: Vec<Node<T>>
}
//---- Implementations ----//
impl<T: NodeContent> Tree<T> {
/// Create new empty tree.
pub fn new() -> Self {
Self {
nodes: vec!(),
}
}
/// Set root node.
///
/// # Arguments
///
/// * `content` - Node content.
///
/// # Return
///
/// * An [`Option`] with the root node index (always 0).
///
pub fn set_root(&mut self, node_content: &str) -> Option<usize> {
if let Some(node) = Node::<T>::new_root(node_content) {
if self.nodes.len() == 0 {
// Create root node
self.nodes.push(node);
return Some(0);
}
}
None
}
/// Create new node and link it to its parent.
///
/// # Arguments
///
/// * `node_content` - Node content.
/// * `parent_node_index` - Parent node index.
///
/// # Return
///
/// * An [`Option`] with the new node index.
///
pub fn link_node(&mut self, node_content: &str, parent_node_index: usize) -> Option<usize> {
if parent_node_index < self.nodes.len() {
let new_node_level = self.nodes[parent_node_index].get_level() + 1;
if let Some(mut new_node) = Node::<T>::new_node(node_content, new_node_level) {
// Update new node, set parent_position and parents_children_pos
new_node.set_parent_position(parent_node_index);
let parents_children_pos = self.nodes[parent_node_index].get_num_chuildren();
new_node.set_parents_children_pos(parents_children_pos);
// Add new node to nodes array, to parent's children array and to child_map
let new_node_index = self.nodes.len();
let node_content = String::from(new_node.get_content_ref().get_val());
self.nodes.push(new_node);
self.nodes[parent_node_index].add_child(node_content, new_node_index);
return Some(new_node_index);
}
}
None
}
/// Get reference to node content.
///
/// # Arguments
///
/// * `node_index` - Node index.
///
/// # Return
///
/// * An [`Option`] with the node content reference.
///
pub fn get_node_content(&self, node_index: usize) -> Option<&T> {
if node_index < self.nodes.len() {
return Some(self.nodes[node_index].get_content_ref());
}
None
}
/// Overwrite node content. It must exist.
///
/// # Arguments
///
/// * `node_content` - Node content.
/// * `node_index` - Node index.
///
/// # Return
///
/// * An [`Option`] with the node index.
///
pub fn update_node(&mut self, node_content: &str, node_index: usize) -> Option<usize> {
if self.nodes.len() > node_index {
if let Some(new_node) = Node::<T>::new_node(node_content, self.nodes[node_index].get_level()) {
// Update parent's child_map
if let Some(parent_position) = self.nodes[node_index].get_parent_position() {
let old_node_content = String::from(self.nodes[node_index].get_content_ref().get_val());
self.nodes[parent_position].update_child(&old_node_content, node_content);
}
let current_node = self.nodes.get_mut(node_index).unwrap();
current_node.set_content(new_node.get_content());
return Some(node_index);
}
}
None
}
/// Unlink node. It doesn't remove node from the tree, it just disconnects it from parent.
///
/// This process is O(l) complexity, where `l` is the number of nodes of the same level of `node_index`.
///
/// # Arguments
///
/// * `node_index` - Node index.
///
/// # Return
///
/// * An [`Option`] with the node index.
///
pub fn unlink_node(&mut self, node_index: usize) -> Option<usize> {
if self.nodes.len() > node_index {
if let Some(parent) = self.nodes[node_index].get_parent_position() {
if let Some(parents_children_pos) = self.nodes[node_index].get_parents_children_pos() {
if self.nodes[parent].get_num_chuildren() > parents_children_pos {
let node_content = String::from(self.nodes[node_index].get_content_ref().get_val());
self.nodes[parent].remove_child(&node_content, parents_children_pos);
return Some(node_index);
}
}
}
}
None
}
/// Find node in the try by content.
///
/// The complexity of this operation is O(p), where `p` is the number of elements in the path.
///
/// # Arguments
///
/// * `path` - Path of nodes, starting from root.
///
/// # Return
///
/// * An [`Option`] with the node index.
///
pub fn find_node(&self, path: &[&str]) -> Option<usize> {
let mut last_node_index = None;
// Check root node
if self.nodes.len() > 0 && path.len() > 0 {
if self.nodes[0].get_content_ref().get_val() == path[0] {
last_node_index = Some(0);
}
else {
return None;
}
}
// Check following nodes
let mut node_index = 0;
for path_element in path[1..].iter() {
if self.nodes.len() > node_index {
if let Some(path_element_index) = self.nodes[node_index].get_child(path_element) {
last_node_index = Some(path_element_index);
node_index = path_element_index;
}
else {
return None;
}
}
else {
return None;
}
}
last_node_index
}
//TODO: traverse starting by a certain node, not root. Pass node index as argument.
/// Get iterators interface.
///
/// # Return
///
/// * Iterators interface.
///
pub fn iterators(&self) -> IterInterface<T> {
IterInterface::new(self)
}
/// Get reference to nodes array.
///
/// # Return
///
/// * Array reference.
///
pub fn get_nodes_ref(&self) -> &[Node<T>] {
&self.nodes
}
/// Get size of nodes array.
///
/// # Return
///
/// * Size.
///
pub fn get_nodes_len(&self) -> usize {
self.nodes.len()
}
// TODO
/*
/// Obtain a copy of the current tree without unlinked nodes and updating node indexes.
///
/// Node indexes of the old tree are no longer valid in the new tree returned by this function.
///
/// # Return
///
/// * Regenerated tree.
///
pub fn regenerate(&self) -> Self {
Tree::new()
}
*/
}