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
|
/// A simple flat append-only tree data structure. Represented as a Vec.
pub struct Tree<T>(Vec<Node<T>>);
/// The associated Node to the Tree.
/// Somewhat optimized for memory usage rather than CPU cycles.
/// firstborn is accessed as oldest_child and youngest_child is computed.
pub struct Node<T> {
parent: Option<NodeId>,
previous_sibling: Option<NodeId>,
next_sibling: Option<NodeId>,
firstborn: Option<NodeId>,
data: T
}
/// Nodes themselves are not held onto and used, instead we use a NodeId,
/// only valid in the context of a particular Tree. There is not a great
/// way to enforce this validity that I know of, unfortunately.
#[derive(Copy, Clone)]
pub struct NodeId(usize);
impl<T> Tree<T> {
/// Create a new Tree with a root element.
/// You should only make one Tree in any given context.
/// Otherwise there are safety risks with using the wrong NodeId for a Tree.
pub fn new(data: T) -> Tree<T> {
Tree(vec![Node {
parent: None, previous_sibling: None,
next_sibling: None, firstborn: None,
data
}])
}
/// Get a raw Node for viewing familial relations.
/// This unwrap() should be safe with one Tree
/// instance as NodeIds may not be directly constructed.
fn get(&self, id: NodeId) -> &Node<T> {
&self.0[id.0]
}
/// Get a raw Node for modifying familial relations.
/// This unwrap() should be safe with one Tree
/// instance as NodeIds may not be directly constructed.
fn get_mut(&mut self, id: NodeId) -> &mut Node<T> {
&mut self.0[id.0]
}
/// Get the data associated with a Node.
pub fn data(&mut self, id: NodeId) -> &mut T {
&mut self.get_mut(id).data
}
/// Get the data associated with a Node.
// pub fn data(&self, id: NodeId) -> Option<T> {
// match self.0.get(id.0) {
// Some(Node{ data, .. }) => Some(*data),
// None => None
// }
// }
/// Get the root node of the Tree.
pub fn root(&self) -> NodeId { NodeId(0) }
/// Get the root node(s) of the Tree.
// pub fn root(&self) -> Vec<NodeId> {
// let mut roots = Vec::new();
// for (i, node) in self.0.iter().enumerate() {
// if let Node{ parent, .. } = node && let None = parent {
// roots.push(NodeId(i));
// }
// }
// return roots;
// }
/// Get all the direct children of a Node.
pub fn children(&self, id: NodeId) -> Vec<NodeId> {
let mut result = Vec::new();
if let Some(node) = self.0.get(id.0) {
let mut child = node.firstborn;
while let Some(id) = child {
result.push(id);
child = self.0.get(id.0).map(|x| x.next_sibling).flatten();
}
}
return result;
}
/// Get the eldest child of a Node.
pub fn eldest_child(&self, id: NodeId) -> Option<NodeId> {
self.get(id).firstborn
}
/// Get the youngest child of a Node.
pub fn youngest_child(&self, id: NodeId) -> Option<NodeId> {
let mut result = None;
if let Some(node) = self.0.get(id.0) {
let mut child = node.firstborn;
while let Some(id) = child {
result = Some(id);
child = self.0.get(id.0).map(|x| x.next_sibling).flatten();
}
}
return result;
}
/// Get the previous sibling of a Node.
pub fn previous_sibling(&self, id: NodeId) -> Option<NodeId> {
self.get(id).parent
}
/// Get the next sibling of a Node.
pub fn next_sibling(&self, id: NodeId) -> Option<NodeId> {
self.get(id).parent
}
/// Get the parent of a Node.
pub fn parent(&self, id: NodeId) -> Option<NodeId> {
self.get(id).parent
}
/// Add a Node as a direct child of another Node in the tree.
pub fn add_child(&mut self, parent: NodeId, data: T) -> NodeId {
let id = NodeId(self.0.len() - 1);
let previous_sibling = self.youngest_child(parent);
if let Some(node) = previous_sibling {
self.get_mut(node).next_sibling = Some(id);
} else {
self.get_mut(parent).firstborn = Some(id);
}
self.0.push(Node {
parent: Some(parent),
previous_sibling,
next_sibling: None,
firstborn: None,
data: data
});
return id;
}
}
|
