syn_sem/ds/
tree.rs

1use super::vec::{GenIndex, GenOptVec};
2
3#[derive(Debug)]
4pub struct Tree<V> {
5    pub(crate) nodes: GenOptVec<Node<V>>,
6}
7
8impl Tree<()> {
9    pub const ROOT: NodeIndex = NodeIndex(GenIndex::ignore_gen(0));
10}
11
12impl<V: Default> Tree<V> {
13    pub fn with_default() -> Self {
14        Self::new(V::default())
15    }
16}
17
18impl<V> Tree<V> {
19    pub fn new(root: V) -> Self {
20        // Empty root node.
21        let root_node = Node {
22            value: root,
23            parent: Tree::ROOT.0,
24            children: Vec::new(),
25        };
26
27        let mut nodes = GenOptVec::new();
28        let i = nodes.add(root_node);
29        debug_assert_eq!(i.into_inner(), Tree::ROOT.0.into_inner());
30
31        Self { nodes }
32    }
33
34    pub fn clear(&mut self) {
35        // Removes all values except the root node.
36        self.nodes.truncate(1);
37    }
38
39    pub fn is_leaf(&self, index: NodeIndex) -> bool {
40        if let Some(node) = self.nodes.get(index.0) {
41            node.children.is_empty()
42        } else {
43            false
44        }
45    }
46
47    pub fn is_non_leaf(&self, index: NodeIndex) -> bool {
48        if let Some(node) = self.nodes.get(index.0) {
49            !node.children.is_empty()
50        } else {
51            false
52        }
53    }
54
55    pub fn parent(&self, index: NodeIndex) -> Option<NodeIndex> {
56        self.nodes.get(index.0).map(|node| NodeIndex(node.parent))
57    }
58
59    pub fn get(&self, index: NodeIndex) -> Option<&V> {
60        self.nodes.get(index.0).map(|node| &node.value)
61    }
62
63    pub fn get_mut(&mut self, index: NodeIndex) -> Option<&mut V> {
64        self.nodes.get_mut(index.0).map(|node| &mut node.value)
65    }
66
67    /// Traverses sub-tree starting with the `from` node in a DFS way.
68    ///
69    /// # Panics
70    ///
71    /// Panics if the given node index is out of bounds.
72    pub fn traverse_from<F, R>(&self, from: NodeIndex, mut f: F) -> Option<R>
73    where
74        F: FnMut(&V) -> Option<R>,
75    {
76        fn traverse<V, F, R>(this: &Tree<V>, from: NodeIndex, f: &mut F) -> Option<R>
77        where
78            F: FnMut(&V) -> Option<R>,
79        {
80            let node = this.nodes.get(from.0)?;
81            let ret = f(&node.value);
82            if ret.is_some() {
83                return ret;
84            }
85
86            for child in &node.children {
87                let ret = traverse(this, NodeIndex(*child), f);
88                if ret.is_some() {
89                    return ret;
90                }
91            }
92
93            None
94        }
95
96        traverse(self, from, &mut f)
97    }
98
99    pub fn next_index(&self) -> NodeIndex {
100        NodeIndex(self.nodes.next_index())
101    }
102
103    /// Inserts a node with the given value under the parent node, then returns true if the
104    /// operation was successful.
105    pub fn insert(&mut self, parent: NodeIndex, value: V) -> Option<NodeIndex> {
106        self.nodes.get(parent.0)?;
107
108        let index = self.nodes.add(Node {
109            value,
110            parent: parent.0,
111            children: Vec::new(),
112        });
113        let parent_node = self.nodes.get_mut(parent.0).unwrap();
114        parent_node.children.push(index);
115        Some(NodeIndex(index))
116    }
117
118    /// Takes out the value at the given index.
119    ///
120    /// Other indices are not affected by this operation, but the whole sub-tree starting with the
121    /// node will be removed.
122    pub fn take(&mut self, index: NodeIndex) -> Option<V> {
123        let node = self.nodes.take(index.0)?;
124
125        // Destroys all descendants of the node.
126        for index in node.children {
127            self.take(NodeIndex(index));
128        }
129
130        Some(node.value)
131    }
132}
133
134#[derive(Debug)]
135pub struct Node<V> {
136    value: V,
137    parent: GenIndex,
138    children: Vec<GenIndex>,
139}
140
141#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
142#[repr(transparent)]
143pub struct NodeIndex(GenIndex);
syn_sem/ds/tree.rs

syn_sem/ds/
tree.rs
