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
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
/*!
A zipper module for accessing `TreeNode`s.
Inspired by https://stackoverflow.com/a/36168919/6449910
Copyright © 2020 Santtu Söderholm
*/
use super::*;
/// A [zipper](https://en.wikipedia.org/wiki/Zipper_%28data_structure%29)
/// of `TreeNode`s. Makes it possible to traverse the tree and
/// access a specific child/parent in constant time.
#[derive(Debug)]
pub struct TreeZipper {
node: TreeNode,
parent: Option<Box<TreeZipper>>,
index_in_parent: Option<usize>,
}
impl TreeZipper {
/// A `TreeZipper` constructor. A new `TreeZipper`
/// consists of nothing but the root node.
pub fn new(
node: TreeNode,
parent: Option<Box<TreeZipper>>,
index_in_parent: Option<usize>,
) -> Self {
Self {
node: node,
parent: parent,
index_in_parent: index_in_parent,
}
}
/// Adds a child node to the contained node.
/// Returns and `Ok`-wrapped empty value if sucessful,
/// else returns the given `TreeNode` wrapped in an `Err`.
pub fn push_child(&mut self, tree_node: TreeNode) -> Result<(), TreeNode> {
match self.node.push_child(tree_node) {
Ok(()) => Ok(()),
Err(node) => Err(node),
}
}
/// Removes the last child node from the contained node and returns it in an `Option`.
pub fn pop_child(&mut self) -> Option<TreeNode> {
match self.node.pop_child() {
Some(child) => Some(child),
None => None,
}
}
/// Adds a sequence of children to `self.node.children`.
pub fn append_children(&mut self, children: &mut Vec<TreeNode>) {
self.node.append_children(children);
}
/// Optionally returns a shared reference to the children of the focused-on node.
pub fn shared_children(&self) -> &Option<Vec<TreeNode>> {
self.node.shared_children()
}
/// Optionally returns a mutable reference to the children of the focused-on node.
pub fn mut_children(&mut self) -> &mut Option<Vec<TreeNode>> {
self.node.mut_children()
}
/// Moves focus to a specific child of a node.
/// Returns `Ok(TreeZipper)` focused
/// on the child, if successful. Otherwise
/// returns with `Err(TreeZipper)`
pub fn focus_on_child(mut self, index: usize) -> Result<Self, Self> {
let child: TreeNode;
if let Some(children) = self.node.mut_children() {
if !children.is_empty() && index < children.len() {
child = children.swap_remove(index);
} else {
eprintln!("Child with given index does not exist.\nReturning parent...\n");
return Err(self);
}
} else {
eprintln!(
"Tried accessing children in a node that can't have them.\nComputer says no...\n"
);
return Err(self);
}
Ok(Self {
node: child,
parent: Some(Box::new(self)),
index_in_parent: Some(index),
})
}
/// Moves focus to the parent of the current node,
/// or at least tries to. Returns with `Ok(TreeZipper)`
/// if successful and `Err(message: &str)` if not.
pub fn focus_on_parent(self) -> Result<Self, Self> {
// Destructuring the provided TreeZipper
let Self {
node,
parent,
index_in_parent,
} = self;
// Destructuring the parent provided by the above destructure
let Self {
node: mut parent_node,
parent: parent_parent,
index_in_parent: parent_index_in_parent,
} = match parent {
Some(parent) => *parent,
None => {
// eprintln!("No parent, returning unmodified zipper...\n");
return Err(Self {
node: node,
parent: parent,
index_in_parent: index_in_parent,
});
}
};
let index = match index_in_parent {
Some(index) => index,
None => {
eprintln!("Parent found but something funky going on with index in parent...\n");
return Err(Self {
node: node,
parent: parent_parent,
index_in_parent: index_in_parent,
});
}
};
// Perform the opposite of Vec::swap_remove
if let Some(children) = parent_node.mut_children() {
children.push(node);
let len = children.len();
children.swap(index, len - 1);
} else {
return Err(Self {
node: node,
parent: parent_parent,
index_in_parent: index_in_parent,
});
}
Ok(Self {
node: parent_node,
parent: parent_parent,
index_in_parent: parent_index_in_parent,
})
}
/// A function that walks up the tree (zipper) until no more parents are encountered.
pub fn walk_to_root(mut self) -> Self {
loop {
self = match self.focus_on_parent() {
Ok(parent) => parent,
Err(self_unchanged) => {
self = self_unchanged;
break;
}
};
}
self
}
/// Walks up the tree until a parent of a given section level is encountered.
pub fn walk_to_parent_section_level(mut self, section_level: usize) -> Self {
loop {
match self.node.shared_data() {
TreeNodeType::Document { .. } => break,
TreeNodeType::Section { level, .. } => {
// If the parent section level is equal to the given section_level,
// return self, else continue walking up the tree
if *level <= section_level {
break;
} else if section_level > *level {
panic!("Received instruction to walk down to a section level {} when walking up the doctree to level {}. Computer says no...", section_level, level)
} else {
self = match self.focus_on_parent() {
Ok(parent) => parent,
Err(node_itself) => return node_itself,
}
}
}
_ => {
self = match self.focus_on_parent() {
Ok(parent) => parent,
Err(node_itself) => return node_itself,
}
}
}
}
self
}
/// Moves the focus to the last child of the current focus.
pub fn focus_on_last_child(self) -> Result<Self, Self> {
let children_len = if let Some(children) = self.node.shared_children() {
self.n_of_children()
} else {
eprintln!("Cannot focus on last child, as current node is not allowed any children.\nComputer says no...\n");
return Err(self);
};
let with_focus_on_latest_child = match self.focus_on_child(children_len - 1) {
Ok(tree_zipper) => tree_zipper,
Err(parent) => return Err(parent),
};
Ok(with_focus_on_latest_child)
}
/// Moves focus to the given nth sibling.
pub fn focus_on_sibling(self, sibling_index: usize) -> Result<Self, Self> {
let parent = if let Some(parent) = &self.parent {
match self.focus_on_parent() {
Ok(parent) => parent,
Err(unmodified_self) => return Err(unmodified_self),
}
} else {
return Err(self);
};
let sibling = match parent.focus_on_child(sibling_index) {
Ok(child) => child,
Err(parent_itself) => {
eprintln!("No such sibling.\nReturning parent...\n");
return Err(parent_itself);
}
};
Ok(sibling)
}
/// Given a variant `TreeNodeType`, constructs a TreeNode from the data and
/// pushes it to current node's children.
pub fn push_data(
mut self,
node_data: TreeNodeType,
node_id: NodeId,
target_label: Option<Vec<String>>,
classes: Option<Vec<String>>,
) -> Result<Self, Self> {
let new_node = TreeNode::new(node_data, node_id, target_label, classes);
match self.push_child(new_node) {
Ok(()) => Ok(self),
Err(node) => Err(self),
}
}
/// Given a variant `TreeNodeType`, constructs a TreeNode from the data,
/// pushes it to current node's children and focuses on it.
pub fn push_data_and_focus(
mut self,
node_data: TreeNodeType,
node_id: NodeId,
target_label: Option<Vec<String>>,
classes: Option<Vec<String>>,
) -> Result<Self, Self> {
let new_node = TreeNode::new(node_data, node_id, target_label, classes);
match self.push_child(new_node) {
Ok(()) => (),
Err(node) => return Err(self),
};
let node_result = match self.focus_on_last_child() {
Ok(child_zipper) => Ok(child_zipper),
Err(node_itself) => {
eprintln!(
"Warning: Couldn't focus on latest child node.\nReturning node itself.\n"
);
Err(node_itself)
}
};
node_result
}
/// Returns a shared reference to the parent of the node.
/// Else returns `None`.
pub fn shared_parent_ref(&self) -> Option<&TreeZipper> {
use std::borrow::Borrow;
if let Some(parent) = &self.parent {
Some(parent.borrow())
} else {
None
}
}
/// Returns a shared reference to the sibling of the current node at a given index,
/// if there is one. Else returns `None`.
pub fn shared_sibling_data(&self, sibling_index: usize) -> Option<&TreeNodeType> {
let parent_ref = if let Some(parent) = self.shared_parent_ref() {
parent
} else {
return None;
};
if let Some(children) = parent_ref.node.shared_children() {
if let Some(sibling) = children.get(sibling_index) {
Some(sibling.shared_data())
} else {
None
}
} else {
None
}
}
/// Returns the index of the focused-on node in its parent, if there is a parent available.
pub fn index_in_parent(&self) -> Option<usize> {
self.index_in_parent
}
/// Returns the number of children of the current node.
pub fn n_of_children(&self) -> usize {
if let Some(children) = self.node.shared_children() {
children.len()
} else {
panic!("Tried retrieving the number of children for node, but children not allowed.\nComputer says no...\n")
}
}
/// Returns a shared reference to the data of the current node.
pub fn shared_data(&self) -> &TreeNodeType {
self.node.shared_data()
}
/// Reurn the id of the contained node.
pub fn node_id(&self) -> NodeId {
self.node.id()
}
/// Returns a shared reference to the contained node.
pub fn shared_node(&self) -> &TreeNode {
&self.node
}
/// Returns a mutable reference to the contained node.
pub fn mut_node(&mut self) -> &mut TreeNode {
&mut self.node
}
}