ntree_rs/
lib.rs

1//! Definition of a node with an arbitrary number of children.
2
3mod traversal;
4pub use traversal::*;
5
6/// Asynchronous marker.
7pub struct Asynchronous;
8
9/// Synchronous marker.
10pub struct Synchronous;
11
12#[macro_export]
13macro_rules! node {
14    ($value:expr) => (Node::new($value));
15    ($value:expr, $($children:expr),*) => {
16        {
17            let mut tmp_node = Node::new($value);
18            $(tmp_node.children.push($children);)*
19            tmp_node
20        }
21    };
22}
23
24/// Represents the minimum unit in a tree, containing a value of type T and all
25/// those nodes children of the node itself, if any.
26#[derive(Debug)]
27pub struct Node<T> {
28    pub value: T,
29    pub children: Vec<Node<T>>,
30}
31
32impl<T> Node<T> {
33    pub fn new(value: T) -> Self {
34        Node {
35            value,
36            children: vec![],
37        }
38    }
39
40    pub fn with_children(mut self, children: Vec<Node<T>>) -> Self {
41        self.children = children;
42        self
43    }
44
45    /// Returns the number of descendants the node has. This method return 0 if, and only if,
46    /// the node has no children.
47    pub fn size(&self) -> usize {
48        self.children
49            .iter()
50            .fold(self.children.len(), |len, node| -> usize {
51                len.saturating_add(node.size())
52            })
53    }
54
55    /// Returns the length of the longest branch in the tree rooted by self. Also known as the
56    /// height of the tree. This method returns 1 if, and only if, the node has no children.
57    pub fn height(&self) -> usize {
58        self.children
59            .iter()
60            .map(|node| node.height())
61            .max()
62            .unwrap_or_default()
63            .saturating_add(1)
64    }
65}
66
67impl<T: Clone> Clone for Node<T> {
68    fn clone(&self) -> Self {
69        Self {
70            value: self.value.clone(),
71            children: self.children.clone(),
72        }
73    }
74}
75
76impl<T: PartialEq> PartialEq for Node<T> {
77    fn eq(&self, other: &Self) -> bool {
78        self.value == other.value && self.children == other.children
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_node_new() {
88        let root = Node::new(42);
89        assert_eq!(root.value, 42);
90        assert_eq!(root.children.len(), 0);
91    }
92
93    #[test]
94    fn test_node_value_mut() {
95        let mut root = Node::new(42);
96        assert_eq!(root.value, 42);
97
98        root.value = 123;
99        assert_eq!(root.value, 123);
100    }
101
102    #[test]
103    fn test_node_add_child() {
104        let mut root = node!(10);
105        root.children.push(node!(20));
106        root.children.push(node!(30));
107
108        assert_eq!(root.children.len(), 2);
109    }
110
111    #[test]
112    fn test_node_children_mut() {
113        let mut root = node!(10, node!(20), node!(30));
114        root.children.swap(0, 1);
115        assert_eq!(root, node!(10, node!(30), node!(20)));
116    }
117
118    #[test]
119    fn test_node_remove_child() {
120        let mut root = node!(10, node!(20), node!(30));
121        let removed = root.children.remove(0);
122        assert_eq!(removed.value, 20);
123        assert_eq!(root.children.len(), 1);
124    }
125
126    #[test]
127    fn test_node_size() {
128        let root = node!(10, node!(20, node!(40)), node!(30, node!(50), node!(60)));
129        assert_eq!(root.size(), 5);
130    }
131
132    #[test]
133    fn test_node_height() {
134        let root = node!(10, node!(20, node!(40)), node!(30, node!(50), node!(60)));
135        assert_eq!(root.height(), 3);
136    }
137
138    #[test]
139    fn test_node_copy() {
140        let original = node!(10, node!(20), node!(30));
141        let mut copy = original.clone();
142
143        assert_eq!(copy, original);
144
145        copy.children.remove(0);
146        assert_ne!(copy, original);
147    }
148}
ntree_rs/lib.rs

ntree_rs/
lib.rs
