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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
use std::fmt::Display;
/// A binary tree structure used to parse and evaluate an expression into RPN.
///
/// Work in progress.
///
/// Type parameter must implement `Copy` trait until borrowing is implemented.
pub struct Tree<T: Copy> {
pub root_node: TreeNode<T>,
}
impl<T: Copy> Tree<T> {
/// Takes reducer function input with following signature.
///
/// The caller should ensure that reducer function returns same type as
/// the left- and right-hand side.
///
/// Example: adding LHS: <i32>, Parent: <i32>, RHS: <i32> to sum values in tree.
pub fn reduce<R>(&self, reducer: fn(Option<R>, T, Option<R>) -> R) -> R {
self.root_node.reduce(reducer)
}
/// Initialises a new Tree struct.
///
/// Needs a root value
pub fn new(root_val: T) -> Tree<T> {
Tree::<T> {
root_node: TreeNode::<T> {
value: root_val,
left: None,
right: None,
},
}
}
/// Inserts a node to the left of the root node.
pub fn insert_left(&mut self, v: T) {
self.root_node.insert_left(v);
}
/// Inserts a node to the right of the root node.
pub fn insert_right(&mut self, v: T) {
self.root_node.insert_right(v);
}
}
impl<T: Display + Copy> Display for Tree<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.root_node)
}
}
/// A node in a binary tree.
///
/// Can be used for many interesting algorithmic things.
pub struct TreeNode<T: Copy> {
pub value: T,
/// The left node, may be `None`.
pub left: Option<Box<TreeNode<T>>>,
/// The right node, may be `None`.
pub right: Option<Box<TreeNode<T>>>,
}
impl<T: Copy + Display> Display for TreeNode<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"{}{}{}",
match &self.left {
Some(v) => format!("({})<-", v),
None => "".to_string(),
},
format!("({})", self.value),
match &self.right {
Some(v) => format!("->({})", v),
None => "".to_string(),
}
)
}
}
impl<T: Copy> TreeNode<T> {
/// Initialises a new node for a Tree.
pub fn new(v: T) -> TreeNode<T> {
TreeNode {
value: v,
left: None,
right: None,
}
}
/// Recursively reduces each element in tree.
pub fn reduce<R>(&self, reducer: fn(Option<R>, T, Option<R>) -> R) -> R {
let left_val = match &self.left {
Some(node) => Some(node.reduce(reducer)),
None => None,
};
let right_val = match &self.right {
Some(node) => Some(node.reduce(reducer)),
None => None,
};
reducer(left_val, self.value, right_val)
}
/// Recursively inserts to the left of node until there is one empty space.
pub fn insert_left(&mut self, value: T) {
if let Some(node) = &mut self.left {
node.insert_left(value)
}
self.left = Some(Box::new(TreeNode {
value,
left: None,
right: None,
}));
}
/// Recursively inserts to the right of node until there is one empty space.
pub fn insert_right(&mut self, value: T) {
if let Some(node) = &mut self.right {
node.insert_right(value)
}
self.right = Some(Box::new(TreeNode::new(value)))
}
}
|
