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

use arena::{Arena, NodeId};
use std::marker::PhantomData;

/// A single node in the tree. Has a reference to the first child and the next
/// sibling.
#[derive(Clone, Copy, Debug, Default)]
pub struct Node {
    pub child: Option<NodeId>,
    pub sibling: Option<NodeId>
}
impl Node {
    /// Convenience function for creating a node with children and no siblings
    pub fn with_child<T: Into<Option<NodeId>>>(child: T) -> Self {
        Self {
            child: child.into(),
            ..Default::default()
        }
    }
}

/// An easy way to create a list of nodes. The first node will point to the
/// next, etc...
#[derive(Clone, Copy)]
pub struct NodeList<T: AsMut<Node>> {
    start: Option<NodeId>,
    cursor: Option<NodeId>,
    __marker: PhantomData<*const T>
}
// For some reason, a NodeList can't derive Default unless the generics
// parameter is also a defaultable type. This of course makes no sense, since
// PhantomData has a Default.
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> {
    /// Create a new instance
    pub fn new() -> Self {
        Self::default()
    }
    /// Push a new node to this list
    pub fn push(&mut self, node: NodeId, arena: &mut Arena<T>) {
        self.push_all(&[node], arena);
    }
    /// Push a slice of nodes to this list. Each node will get linked to the
    /// next one. If one of the nodes already have siblings, they'll be added
    /// as well.
    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 idx = *cursor;
                while let Some(sibling) = arena[idx].as_mut().sibling {
                    idx = sibling;
                }
                let mut dest = arena[idx].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)
        }
    }
    /// Return the first node in the list
    pub fn node(&self) -> Option<NodeId> {
        self.start
    }
}

/// An iterator over a node's siblings. Keeps going to the next sibling until
/// it reaches the end.
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)
    }
}