cl_structures/
tree.rs

1//! An insert-only unordered tree, backed by a [Vec]
2//!
3//! # Examples
4//! ```
5//! use cl_structures::tree::{Tree, Node};
6//! // A tree can be created
7//! let mut tree = Tree::new();
8//! // Provided with a root node
9//! let root = tree.root("This is the root node").unwrap();
10//!
11//! // Nodes can be accessed by indexing
12//! assert_eq!(*tree[root].as_ref(), "This is the root node");
13//! // Nodes' data can be accessed directly by calling `get`/`get_mut`
14//! assert_eq!(tree.get(root).unwrap(), &"This is the root node")
15//! ```
16
17// TODO: implement an Entry-style API for doing traversal algorithms
18
19pub use self::tree_ref::Ref;
20use std::ops::{Index, IndexMut};
21
22pub mod tree_ref;
23
24/// An insert-only unordered tree, backed by a [Vec]
25#[derive(Debug)]
26pub struct Tree<T> {
27    nodes: Vec<Node<T>>,
28}
29
30impl<T> Default for Tree<T> {
31    fn default() -> Self {
32        Self { nodes: Default::default() }
33    }
34}
35
36/// Getters
37impl<T> Tree<T> {
38    pub fn get(&self, index: Ref<T>) -> Option<&T> {
39        self.get_node(index).map(|node| &node.value)
40    }
41    pub fn get_mut(&mut self, index: Ref<T>) -> Option<&mut T> {
42        self.get_node_mut(index).map(|node| &mut node.value)
43    }
44    pub fn get_node(&self, index: Ref<T>) -> Option<&Node<T>> {
45        self.nodes.get(usize::from(index))
46    }
47    pub fn get_node_mut(&mut self, index: Ref<T>) -> Option<&mut Node<T>> {
48        self.nodes.get_mut(usize::from(index))
49    }
50}
51
52/// Tree operations
53impl<T> Tree<T> {
54    pub fn new() -> Self {
55        Self { nodes: Default::default() }
56    }
57
58    /// Creates a new root for the tree.
59    ///
60    /// If the tree already has a root, the value will be returned.
61    pub fn root(&mut self, value: T) -> Result<Ref<T>, T> {
62        if self.is_empty() {
63            // Create an index for the new node
64            let node = Ref::new_unchecked(self.nodes.len());
65            // add child to tree
66            self.nodes.push(Node::from(value));
67            Ok(node)
68        } else {
69            Err(value)
70        }
71    }
72
73    pub fn get_root(&mut self) -> Option<Ref<T>> {
74        match self.nodes.is_empty() {
75            true => None,
76            false => Some(Ref::new_unchecked(0)),
77        }
78    }
79
80    /// Insert a value into the tree as a child of the parent node
81    ///
82    /// # Panics
83    /// May panic if the node [Ref] is from a different tree
84    pub fn insert(&mut self, value: T, parent: Ref<T>) -> Ref<T> {
85        let child = Ref::new_unchecked(self.nodes.len());
86        // add child to tree before parent
87        self.nodes.push(Node::with_parent(value, parent));
88        // add child to parent
89        self[parent].children.push(child);
90
91        child
92    }
93
94    /// Gets the depth of a node
95    ///
96    /// # Panics
97    /// May panic if the node [Ref] is from a different tree
98    pub fn depth(&self, node: Ref<T>) -> usize {
99        match self[node].parent {
100            Some(node) => self.depth(node) + 1,
101            None => 0,
102        }
103    }
104
105    /// Gets the number of branches in the tree
106    pub fn branches(&self) -> usize {
107        self.nodes.iter().fold(0, |edges, node| edges + node.len())
108    }
109}
110
111/// Standard data structure functions
112impl<T> Tree<T> {
113    pub fn len(&self) -> usize {
114        self.nodes.len()
115    }
116    pub fn is_empty(&self) -> bool {
117        self.nodes.is_empty()
118    }
119}
120
121impl<T> Index<Ref<T>> for Tree<T> {
122    type Output = Node<T>;
123    fn index(&self, index: Ref<T>) -> &Self::Output {
124        self.get_node(index).expect("Ref should be inside Tree")
125    }
126}
127impl<T> IndexMut<Ref<T>> for Tree<T> {
128    fn index_mut(&mut self, index: Ref<T>) -> &mut Self::Output {
129        self.get_node_mut(index).expect("Ref should be inside Tree")
130    }
131}
132
133/// A node in a [Tree]
134#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
135pub struct Node<T> {
136    value: T,
137    /// The parent
138    parent: Option<Ref<T>>,
139    /// The children
140    children: Vec<Ref<T>>,
141}
142
143impl<T> Node<T> {
144    pub const fn new(value: T) -> Self {
145        Self { value, parent: None, children: vec![] }
146    }
147    pub const fn with_parent(value: T, parent: Ref<T>) -> Self {
148        Self { value, parent: Some(parent), children: vec![] }
149    }
150
151    pub fn get(&self) -> &T {
152        self.as_ref()
153    }
154    pub fn get_mut(&mut self) -> &mut T {
155        self.as_mut()
156    }
157    pub fn swap(&mut self, value: T) -> T {
158        std::mem::replace(&mut self.value, value)
159    }
160
161    pub fn parent(&self) -> Option<Ref<T>> {
162        self.parent
163    }
164    pub fn children(&self) -> &[Ref<T>] {
165        &self.children
166    }
167
168    pub fn len(&self) -> usize {
169        self.children.len()
170    }
171
172    pub fn is_empty(&self) -> bool {
173        self.children.is_empty()
174    }
175}
176
177impl<T> AsRef<T> for Node<T> {
178    fn as_ref(&self) -> &T {
179        &self.value
180    }
181}
182impl<T> AsMut<T> for Node<T> {
183    fn as_mut(&mut self) -> &mut T {
184        &mut self.value
185    }
186}
187
188impl<T> From<T> for Node<T> {
189    #[inline]
190    fn from(value: T) -> Self {
191        Self::new(value)
192    }
193}
194
195#[cfg(test)]
196mod test {
197    #[allow(unused)]
198    use super::*;
199
200    #[test]
201    fn add_children() {
202        let mut tree = Tree::new();
203        let root = tree.root(0).unwrap();
204        let one = tree.insert(1, root);
205        let two = tree.insert(2, root);
206        assert_eq!([one, two].as_slice(), tree[root].children());
207    }
208    #[test]
209    fn nest_children() {
210        let mut tree = Tree::new();
211        let root = tree.root(0).unwrap();
212        let one = tree.insert(1, root);
213        let two = tree.insert(2, one);
214        assert_eq!(&[one], tree[root].children());
215        assert_eq!(&[two], tree[one].children());
216        assert_eq!(tree[two].children(), &[]);
217    }
218
219    #[test]
220    fn compares_equal() {}
221}
cl_structures/tree.rs

cl_structures/
tree.rs
