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
use arena::{Arena, NodeId};
use std::marker::PhantomData;
#[derive(Clone, Copy, Debug, Default)]
pub struct Node {
pub child: Option<NodeId>,
pub sibling: Option<NodeId>
}
impl Node {
pub fn with_child<T: Into<Option<NodeId>>>(child: T) -> Self {
Self {
child: child.into(),
..Default::default()
}
}
}
#[derive(Clone, Copy)]
pub struct NodeList<T: AsMut<Node>> {
start: Option<NodeId>,
cursor: Option<NodeId>,
__marker: PhantomData<*const T>
}
impl<T: AsMut<Node>> Default for NodeList<T> {
fn default() -> Self {
Self {
start: None,
cursor: None,
__marker: PhantomData::default()
}
}
}
impl<T: AsMut<Node>> NodeList<T> {
pub fn new() -> Self {
Self::default()
}
pub fn push(&mut self, node: NodeId, arena: &mut Arena<T>) {
self.push_all(&[node], arena);
}
pub fn push_all(&mut self, nodes: &[NodeId], arena: &mut Arena<T>) {
if nodes.is_empty() {
return;
}
if let Some(ref mut cursor) = self.cursor {
for &src in nodes {
let mut dest = arena[*cursor].as_mut();
while let Some(sibling) = dest.sibling {
dest = arena[sibling].as_mut();
}
dest.sibling = Some(src);
*cursor = src;
}
} else {
assert_eq!(self.start, None);
self.start = Some(nodes[0]);
self.cursor = self.start;
return self.push_all(&nodes[1..], arena)
}
}
pub fn node(&self) -> Option<NodeId> {
self.start
}
}
pub struct NodeIter<'a, T: 'a + AsRef<Node>> {
pub arena: &'a Arena<'a, T>,
pub cursor: Option<NodeId>
}
impl<'a, T: AsRef<Node>> Iterator for NodeIter<'a, T> {
type Item = NodeId;
fn next(&mut self) -> Option<Self::Item> {
let current = self.cursor?;
self.cursor = self.arena[current].as_ref().sibling;
Some(current)
}
}