simha_bst/lib.rs
1pub mod bst{
2 use std::cmp::PartialOrd;
3 use std::cmp::Ord;
4 use std::cmp::PartialEq;
5 use std::cmp::Eq;
6 use std::cmp::Ordering;
7
8 #[derive(Debug, Clone)]
9 pub struct Node<T: Ord> {
10 data: T,
11 left: Option<Box<Node<T>>>,
12 right: Option<Box<Node<T>>>
13 }
14
15 impl <T> Node<T> where T: Ord + Clone{
16 ///
17 /// ```
18 /// use crate::bst::bst;
19 ///
20 /// let one = bst::Node::new(1);
21 ///
22 /// assert_eq!(*one.get_data(), 1);
23 /// ```
24 pub fn new(data: T) -> Box<Self> {
25 Box::new(Node{data, left: None, right: None})
26 }
27
28 pub fn get_data(&self) -> &T{
29 &self.data
30 }
31
32 pub fn set_data(&mut self, data: T) {
33 self.data = data;
34 }
35
36 ///
37 /// ```
38 /// use crate::bst::bst;
39 /// use crate::bst::bst::Node;
40 ///
41 /// let two = bst::Node::new(2);
42 /// let mut one = bst::Node::new(1);
43 /// one.set_left(Some(two));
44 /// let one = one;
45 ///
46 ///
47 /// assert_eq!(
48 /// one
49 /// .get_left()
50 /// .as_ref()
51 /// .map(|node| node.get_data().clone())
52 /// .unwrap(),
53 /// 2
54 /// );
55 /// ```
56 pub fn get_left(&self) -> &Option<Box<Node<T>>> {
57 &self.left
58 }
59
60 pub fn set_left(&mut self, left: Option<Box<Node<T>>>) {
61 self.left = left;
62 }
63
64 ///
65 /// ```
66 /// use crate::bst::bst;
67 /// use crate::bst::bst::Node;
68 ///
69 /// let two = bst::Node::new(2);
70 /// let mut one = bst::Node::new(1);
71 /// one.set_right(Some(two));
72 /// let one = one;
73 ///
74 ///
75 /// assert_eq!(
76 /// one
77 /// .get_right()
78 /// .as_ref()
79 /// .map(|node| node.get_data().clone())
80 /// .unwrap(),
81 /// 2
82 /// );
83 /// ```
84 pub fn get_right(&self) -> &Option<Box<Node<T>>> {
85 &self.right
86 }
87
88 pub fn set_right(&mut self, right: Option<Box<Node<T>>>) {
89 self.right = right;
90 }
91
92 fn insert(&mut self, data: T) where T: Clone {
93 if self.get_data().clone() < data {
94 let right = self.right.take();
95 self.right = match right {
96 None => Some(Node::new(data.clone())),
97 Some(mut n) => {
98 n.insert(data);
99 Some(n)
100 }
101 }
102 } else {
103 let left = self.left.take();
104 self.left = match left {
105 None => Some(Node::new(data.clone())),
106 Some(mut n) => {
107 n.insert(data);
108 Some(n)
109 }
110 }
111 }
112 }
113
114 fn infix(&self) -> Vec<T> where T: Clone {
115 let left = self.left.as_ref();
116 let right = self.right.as_ref();
117 let mut left_bracket = match left {
118 None => vec![],
119 Some(node) => node.as_ref().infix()
120 };
121
122 let right_bracket = match right {
123 None => vec![],
124 Some(node) => node.as_ref().infix()
125 };
126
127 left_bracket.push(self.data.clone());
128 for k in right_bracket {
129 left_bracket.push(k.clone());
130 }
131
132 left_bracket
133 }
134 }
135
136 impl <T> PartialOrd for Node<T> where T: Ord {
137 ///
138 /// ```
139 /// use crate::bst::bst;
140 ///
141 /// let one = bst::Node::new(1);
142 /// let two = bst::Node::new(2);
143 ///
144 /// assert!(one < two);
145 /// ```
146 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
147 Some(self.data.cmp(&other.data))
148 }
149 }
150
151 impl <T> PartialEq for Node<T> where T: Ord {
152 ///
153 /// ```
154 /// use crate::bst::bst;
155 ///
156 /// let one = bst::Node::new(1);
157 /// let two = bst::Node::new(1);
158 ///
159 /// assert!(one == two);
160 /// ```
161 fn eq(&self, other: &Self) -> bool {
162 self.data.eq(&other.data)
163 }
164 }
165
166 impl <T> Ord for Node<T> where T: Ord {
167 ///
168 /// ```
169 /// use crate::bst::bst;
170 ///
171 /// let one = bst::Node::new(1);
172 /// let two = bst::Node::new(2);
173 /// let thr = bst::Node::new(3);
174 ///
175 /// assert!(one < two);
176 /// assert!(thr > one);
177 /// assert!(one == one);
178 /// ```
179 fn cmp(&self, other: &Self) -> Ordering {
180 self.data.cmp(&other.data)
181 }
182 }
183
184 impl <T> Eq for Node<T> where T: Ord { }
185
186 #[derive(Debug)]
187 pub struct Bst<T: Ord> {
188 root: Option<Box<Node<T>>>,
189 }
190
191 impl <T> Bst<T> where T: Ord {
192 /// ```
193 /// use crate::bst::bst::Bst;
194 /// let bst: Bst<i32> = Bst::new();
195 /// assert!(bst.get_root().is_none());
196 /// ```
197 pub fn new() -> Self {
198 Bst{root: None}
199 }
200
201 pub fn get_root(&self) -> &Option<Box<Node<T>>> {
202 &self.root
203 }
204
205
206 /// ```
207 ///
208 /// use bst::bst::Bst;
209 /// let mut b = Bst::new();
210 /// b
211 /// .insert(5)
212 /// .insert(3)
213 /// .insert(4);
214 ///
215 /// assert_eq!(
216 /// b
217 /// .get_root()
218 /// .as_ref()
219 /// .map(|x| x.get_data().clone())
220 /// .unwrap(),
221 /// 5
222 /// );
223 /// assert_eq!(
224 /// b
225 /// .get_root()
226 /// .as_ref()
227 /// .unwrap()
228 /// .get_left()
229 /// .as_ref()
230 /// .map(|x| x.get_data().clone())
231 /// .unwrap(),
232 /// 3
233 /// );
234 ///
235 /// assert_eq!(
236 /// b
237 /// .get_root()
238 /// .as_ref()
239 /// .unwrap()
240 /// .get_left()
241 /// .as_ref()
242 /// .unwrap()
243 /// .get_right()
244 /// .as_ref()
245 /// .map(|x| x.get_data().clone())
246 /// .unwrap(),
247 /// 4
248 /// );
249 /// ```
250 pub fn insert(&mut self, data: T) -> &mut Self where T: Clone {
251 self.root = match self.root.take() {
252 None => Some(Node::new(data)),
253 Some(mut node) => {
254 node.insert(data);
255 Some(node)
256 }
257 };
258
259 self
260 }
261
262 /// ```
263 /// use bst::bst::Bst;
264 /// let mut b = Bst::new();
265 /// b
266 /// .insert(5)
267 /// .insert(3)
268 /// .insert(4)
269 /// .insert(6)
270 /// .insert(1);
271 /// assert_eq!(b.infix(), vec![1, 3, 4, 5, 6]);
272 /// ```
273 pub fn infix(&self) -> Vec<T> where T: Clone {
274 if self.root.as_ref().is_none() {
275 vec![]
276 } else {
277 self.root.as_ref().map(|x| x.infix() ).unwrap()
278 }
279 }
280 }
281
282 #[cfg(test)]
283 mod tests {
284 use crate::bst::Node;
285
286 #[test]
287 fn node_insert(){
288
289 let mut one = Node::new(1);
290// let mut two = Node::new(2);
291
292 one.insert(2);
293
294 assert_eq!(
295 one
296 .get_right()
297 .as_ref()
298 .map(|x| x.get_data().clone())
299 .unwrap(),
300 2
301 );
302
303 let mut one = Node::new(2);
304// let mut two = Node::new(1);
305
306 one.insert(1);
307
308 assert_eq!(
309 one
310 .get_left()
311 .as_ref()
312 .map(|x| x.get_data().clone())
313 .unwrap(),
314 1
315 );
316 }
317 }
318}