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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
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>,
}
pub enum InsertDirection {
Left,
Right,
}
impl<T: Copy + Display> 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);
}
pub fn insert(&mut self, v: T, predicate: fn(T, T) -> InsertDirection) {
self.root_node.insert(v, predicate);
}
pub fn level_order(&self) {
let mut a: Vec<T> = vec![];
self.root_node.level_order_rec(0, &mut a);
for elem in a {
print!("{},", elem);
}
println!();
}
}
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)))
}
pub fn insert(&mut self, item: T, predicate: fn(T, T) -> InsertDirection) {
match predicate(item, self.value) {
InsertDirection::Left => {
if let Some(node) = &mut self.left {
node.insert(item, predicate);
} else {
self.left = Some(Box::new(TreeNode::new(item)))
}
}
InsertDirection::Right => {
if let Some(node) = &mut self.right {
node.insert(item, predicate);
} else {
self.right = Some(Box::new(TreeNode::new(item)))
}
}
}
}
pub fn level_order_rec(&self, level: usize, arr: &mut Vec<T>) {
if arr.len() < level {
arr.push(self.value);
}
arr.insert(level, self.value);
if let Some(node) = &self.left { node.level_order_rec(level + 1, arr);}
if let Some(node) = &self.right { node.level_order_rec(level + 1, arr);}
}
}
|
