gemla/tree/
mod.rs

1//! An unbalanced binary tree type where each node has an optional left and right child.
2//!
3//! # Examples
4//!
5//! ```
6//! use gemla::btree;
7//!
8//! // Tree with 2 nodes, one root node and one on the left side
9//! let mut t = btree!(1, btree!(2),);
10//!
11//! assert_eq!(t.height(), 2);
12//! assert_eq!(t.left.unwrap().val, 2);
13//! assert_eq!(t.right, None);
14//!
15//! t.right = Some(Box::new(btree!(3)));
16//! assert_eq!(t.right.unwrap().val, 3);
17//! ```
18
19use serde::{Deserialize, Serialize};
20use std::cmp::max;
21
22/// An unbalanced binary tree type where each node has an optional left and right child.
23///
24/// # Examples
25///
26/// ```
27/// use gemla::btree;
28///
29/// // Tree with 2 nodes, one root node and one on the left side
30/// let mut t = btree!(1, btree!(2),);
31///
32/// assert_eq!(t.height(), 2);
33/// assert_eq!(t.left.unwrap().val, 2);
34/// assert_eq!(t.right, None);
35///
36/// t.right = Some(Box::new(btree!(3)));
37/// assert_eq!(t.right.unwrap().val, 3);
38/// ```
39#[derive(Default, Serialize, Deserialize, PartialEq, Debug)]
40pub struct Tree<T> {
41    /// The value stored in this node
42    pub val: T,
43
44    /// The left child node, if any
45    pub left: Option<Box<Tree<T>>>,
46
47    /// The right child node, if any
48    pub right: Option<Box<Tree<T>>>,
49}
50
51/// Short-hand for constructing Trees. `btree!` takes 3 arguments, the first being the
52/// value of the root node, and the other two being child nodes. The last two arguments are
53/// optional.
54///
55/// ```
56/// use gemla::tree::*;
57/// use gemla::btree;
58///
59/// # fn main() {
60/// // A tree with two child nodes.
61/// let t = btree!(1, btree!(2), btree!(3));
62/// assert_eq!(t,
63///     Tree::new(1,
64///         Some(Box::new(Tree::new(2, None, None))),
65///         Some(Box::new(Tree::new(3, None, None)))));
66///
67/// // A tree with only a left node.
68/// let t_left = btree!(1, btree!(2),);
69/// assert_eq!(t_left,
70///     Tree::new(1,
71///         Some(Box::new(Tree::new(2, None, None))),
72///         None));
73///
74/// // A tree with only a right node.
75/// let t_right = btree!(1, , btree!(3));
76/// assert_eq!(t_right,
77///     Tree::new(1,
78///         None,
79///         Some(Box::new(Tree::new(3, None, None)))));
80///
81/// // A tree with no child nodes.
82/// let t_single = btree!(1);
83/// assert_eq!(t_single,
84///     Tree::new(1,
85///         None,
86///         None));
87/// # }
88/// ```
89#[macro_export]
90macro_rules! btree {
91    ($val:expr, $l:expr, $r:expr) => {
92        $crate::tree::Tree::new($val, Some(Box::new($l)), Some(Box::new($r)))
93    };
94    ($val:expr, , $r:expr) => {
95        $crate::tree::Tree::new($val, None, Some(Box::new($r)))
96    };
97    ($val:expr, $l:expr,) => {
98        $crate::tree::Tree::new($val, Some(Box::new($l)), None)
99    };
100    ($val:expr) => {
101        $crate::tree::Tree::new($val, None, None)
102    };
103}
104
105impl<T> Tree<T> {
106    /// Constructs a new [`Tree`] object
107    ///
108    /// # Examples
109    ///
110    /// ```
111    /// use gemla::tree::*;
112    ///
113    /// let t = Tree::new(1, None, None);
114    /// assert_eq!(t, Tree {
115    ///     val: 1,
116    ///     left: None,
117    ///     right: None
118    /// });
119    /// ```
120    pub fn new(val: T, left: Option<Box<Tree<T>>>, right: Option<Box<Tree<T>>>) -> Tree<T> {
121        Tree { val, left, right }
122    }
123
124    /// Obtains the height of the longest branch in a [`Tree`]
125    ///
126    /// # Examples
127    ///
128    /// ```
129    /// use gemla::tree::*;
130    /// use gemla::btree;
131    ///
132    /// let t =
133    ///     btree!("a",
134    ///         btree!("aa",
135    ///             btree!("aaa"),),
136    ///         btree!("ab"));
137    /// assert_eq!(t.height(), 3);
138    /// ```
139    pub fn height(&self) -> usize {
140        match (self.left.as_ref(), self.right.as_ref()) {
141            (Some(l), Some(r)) => max(l.height(), r.height()) + 1,
142            (Some(l), None) => l.height() + 1,
143            (None, Some(r)) => r.height() + 1,
144            _ => 1,
145        }
146    }
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152
153    #[test]
154    fn test_new() {
155        assert_eq!(
156            Tree::new(30, None, Some(Box::new(Tree::new(20, None, None)))),
157            Tree {
158                val: 30,
159                left: None,
160                right: Some(Box::new(Tree {
161                    val: 20,
162                    left: None,
163                    right: None,
164                })),
165            }
166        );
167    }
168
169    #[test]
170    fn test_height() {
171        assert_eq!(1, btree!(1).height());
172
173        assert_eq!(3, btree!(1, btree!(2), btree!(2, btree!(3),)).height());
174    }
175}
gemla/tree/mod.rs

gemla/tree/
mod.rs
