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
|
//! A simple tree implementation which tries to not allocate all over the place.
use std::ops;
use la_arena::Arena;
#[derive(Default)]
pub(crate) struct Tree<T> {
nodes: Arena<Node<T>>,
current_path: Vec<(Idx<T>, Option<Idx<T>>)>,
}
pub(crate) type Idx<T> = la_arena::Idx<Node<T>>;
impl<T> Tree<T> {
pub(crate) fn start(&mut self)
where
T: Default,
{
let me = self.nodes.alloc(Node::new(T::default()));
if let Some((parent, last_child)) = self.current_path.last_mut() {
let slot = match *last_child {
Some(last_child) => &mut self.nodes[last_child].next_sibling,
None => &mut self.nodes[*parent].first_child,
};
let prev = slot.replace(me);
assert!(prev.is_none());
*last_child = Some(me);
}
self.current_path.push((me, None));
}
pub(crate) fn finish(&mut self, data: T) {
let (me, _last_child) = self.current_path.pop().unwrap();
self.nodes[me].data = data;
}
pub(crate) fn root(&self) -> Option<Idx<T>> {
self.nodes.iter().next().map(|(idx, _)| idx)
}
pub(crate) fn children(&self, idx: Idx<T>) -> impl Iterator<Item = Idx<T>> + '_ {
NodeIter { nodes: &self.nodes, next: self.nodes[idx].first_child }
}
pub(crate) fn clear(&mut self) {
self.nodes.clear();
self.current_path.clear();
}
}
impl<T> ops::Index<Idx<T>> for Tree<T> {
type Output = T;
fn index(&self, index: Idx<T>) -> &T {
&self.nodes[index].data
}
}
pub(crate) struct Node<T> {
data: T,
first_child: Option<Idx<T>>,
next_sibling: Option<Idx<T>>,
}
impl<T> Node<T> {
fn new(data: T) -> Node<T> {
Node { data, first_child: None, next_sibling: None }
}
}
struct NodeIter<'a, T> {
nodes: &'a Arena<Node<T>>,
next: Option<Idx<T>>,
}
impl<'a, T> Iterator for NodeIter<'a, T> {
type Item = Idx<T>;
fn next(&mut self) -> Option<Idx<T>> {
self.next.map(|next| {
self.next = self.nodes[next].next_sibling;
next
})
}
}
|
