unsafe_bst/lib.rs
1#![warn(non_snake_case)]
2#![cfg_attr(feature = "document-features", doc = document_features::document_features!())]
3
4pub mod nodes{
5 #[derive(Debug,Clone)]
6 ///Creates a node with a value
7 /// ````
8 /// use unsafe_bst::*;
9 /// let n = nodes::Node{val: 14};
10 /// ````
11 pub struct Node{
12 pub val: i64,
13 }
14 impl Node{
15 ///Prints the value of the node
16 pub fn print(&self) -> i64{
17 print!("{}\n", self.val);
18 return self.val;
19 }
20 }
21 }
22 ///Module that houses all Binary Tree Operations
23 pub mod binary_tree{
24 use std::borrow::BorrowMut;
25 use crate::{nodes::{self, Node}, stats::Stats};
26 pub enum Label{
27 Check,
28 Else,
29 Condition,
30 }
31 #[derive(Debug,Clone)]
32 /**A Binary Tree has a root node, and possibly a left and right subtree.
33 Option is used to allow the possibility that a left/right subtree is not defined.
34 Box is used to control recursive errors: i.e. there is only a Box when there is a subtree */
35 pub struct BinTree{
36 ///Holds the Root Node of the tree
37 pub root: crate::nodes::Node,
38 ///The Possibility of a left subtree
39 pub left: Option<Box<BinTree>>,
40 ///The Possibility of a right subtree
41 pub right: Option<Box<BinTree>>,
42
43 }
44 impl BinTree{
45 pub fn find(&self, key: i64) -> bool{
46 //!Find is called by a tree and inputs a key. returns true if the key is in the node.
47 //! ```rust
48 //! use unsafe_bst::*;
49 //! let mut tree = binary_tree::BinTree{..Default::default()};
50 //! tree.add_node(nodes::Node{val:14});
51 //! tree.add_node(nodes::Node{val:15});
52 //! tree.add_node(nodes::Node{val:13});
53 //! assert_eq!(tree.find(17),false);
54 //! assert!(tree.find(14));
55 //! ```
56 let mut b = false;
57 if self.root.val == key{
58 //println!("Found {key}");
59 b = true;
60 }else{
61 if self.root.val > key{
62 if self.left.is_some(){
63 b = self.left.as_ref().unwrap().find(key);
64 }
65 }else if self.right.is_some(){
66 b = self.right.as_ref().unwrap().find(key);
67 }
68 }
69 return b;
70 }
71 pub fn add_node(&mut self, node: crate::nodes::Node){
72 //!Add is called by a tree and inputs a Node. The node is added to the tree if it not already in the tree, following basic BST rules
73 //! i.e. smaller values of root are to the left, larger values to the right.
74 //! ```rust
75 //! use unsafe_bst::*;
76 //! let mut tree = binary_tree::BinTree{..Default::default()};
77 //! tree.add_node(nodes::Node{val:14});
78 //! ```
79 if node.val == self.root.val {println!("Node already in tree"); return;}
80 if node.val == -1 {return;}
81 if self.root.val == -1 {
82 self.root = node;
83 return;
84 }
85 if self.root.val > node.val{
86 match self.left{
87 Some(_) => self.left.as_mut().unwrap().add_node(node),
88 None => self.left = Some(Box::new(BinTree {root: node, ..Default::default() })),
89 }
90 }else{
91 match self.right{
92 Some(_) => self.right.as_mut().unwrap().add_node(node),
93 None => self.right = Some(Box::new(BinTree {root: node, ..Default::default() })),
94 }
95 }
96 }
97 pub fn print_def(&self){
98 println!("{}",self.print_2(0, 1));
99 }
100 pub fn print(&self, spacing: i64 ) -> String{
101 //!Prints a tree in the following format:
102 //! <pre>
103 //! left-subtree
104 //! root
105 //! right-subtree
106 //! </pre>
107 //! spacing should be 0, as 5 spaces are hardcoded into print for each non-root line.
108 //! ```rust
109 //! use unsafe_bst::*;
110 //! let mut tree = binary_tree::BinTree{..Default::default()};
111 //! tree.add_node(nodes::Node{val:14});
112 //! tree.add_node(nodes::Node{val:15});
113 //! tree.add_node(nodes::Node{val:13});
114 //! tree.print(0);
115 //! ```
116 let mut r:String = String::new();
117 let space = spacing + 5;
118 if self.root.val == -1 {return r;}
119 if self.right.is_some() && self.right.as_ref().unwrap().root.val != -1{
120 let t = self.right.as_ref().unwrap().print(space);
121 r = format!("{}{}\n",r,t);
122 }
123 for _n in 5..=space{
124 r = format!("{} ",r);
125 }
126 r = format!("{}{}\n",r,self.root.val);
127 if self.left.is_some() && self.left.as_ref().unwrap().root.val != -1{
128 let t = self.left.as_ref().unwrap().print(space);
129 r = format!("{}{}\n",r,t);
130 }
131 return r.trim_end().to_owned();
132 }
133 pub fn print_2(&self, spacing: i64 ,spacing2:i64) -> String{
134 //!Prints a tree in the following format:
135 //! <pre>
136 //! left-subtree
137 //! root
138 //! right-subtree
139 //! </pre>
140 //! takes 2 params, spacing: how many spaces should the root have, and spacing2: how many spaces for each subtree call
141 //! ```rust
142 //! use unsafe_bst::*;
143 //! let mut tree = binary_tree::BinTree{..Default::default()};
144 //! tree.add_node(nodes::Node{val:14});
145 //! tree.add_node(nodes::Node{val:15});
146 //! tree.add_node(nodes::Node{val:13});
147 //! tree.print(0);
148 //! ```
149 let mut r:String = String::new();
150 let space = spacing + spacing2;
151 if self.root.val == -1 {return r;}
152 for _n in spacing2..space{
153 r = format!("{} ",r);
154 }
155 r = format!("{}{}\n",r,self.root.val);
156
157 if self.left.is_some() && self.left.as_ref().unwrap().root.val != -1{
158 let t = self.left.as_ref().unwrap().print_2(space,spacing2);
159 r = format!("{}{}\n",r,t);
160 }
161 if self.right.is_some() && self.right.as_ref().unwrap().root.val != -1{
162 let t = self.right.as_ref().unwrap().print_2(space,spacing2);
163 r = format!("{}{}\n",r,t);
164 }
165
166 return r.trim_end().to_owned();
167 }
168
169 pub fn delete( &mut self, node: i64){
170 //!Deletes an inputted value from the tree. Follows BST deletion rules:
171 //! 1. Leaf node (no left/right-subtree): Node is 'deleted' (set to -1)
172 //! 2. Single Child Node (either left or right-subtree): values of tree are shifted up
173 //! 3. Two child nodes (left and right sub-tree): successor() is used to find the best replacement for the deleted node
174 //! Library Creator Note: This function uses an enum and its types as a way to use GOTO functionality. This is to get around borrowing rules.
175 //! ```rust
176 //! use unsafe_bst::*;
177 //! let mut tree = binary_tree::BinTree{..Default::default()};
178 //! tree.add_node(nodes::Node{val:14});
179 //! tree.add_node(nodes::Node{val: 3});
180 //! tree.delete(14);
181 //! //Tree now has root = 3
182 //! tree.print(0);
183 //! ```
184 if !self.find(node){return;}
185 let mut label = Label::Check;
186 let mut b = self;
187 let mut v: Vec<i64> = Vec::new();
188 'a: loop{
189 match label{
190 Label::Check => {
191 if b.root.val == node{
192 label = Label::Condition;
193 }else{
194 label = Label::Else;
195 }
196 },
197 Label::Else => {
198 if b.root.val > node{
199 if b.left.is_some(){
200 b = b.left.as_mut().unwrap();
201 }
202 }else{
203 if b.right.is_some(){
204 b = b.right.as_mut().unwrap();
205 }
206 }
207
208 label = Label::Check;
209 },
210 Label::Condition => {
211 if b.left.is_none() && b.right.is_none() {
212 b.root.val = -1;
213 break 'a;
214 }
215 //get
216 if b.left.is_some() && b.right.is_none() {
217 b.left.as_mut().unwrap().repopulate(&mut v);
218 break 'a;
219 }
220 if b.left.is_none() && b.right.is_some() {
221 b.right.as_mut().unwrap().repopulate(&mut v);
222 break 'a;
223 }
224 if b.left.is_some() && b.right.is_some() {
225 let c = b.successor().root.val;
226 //let temp = b.root.val;
227 b.delete(c);
228 b.root.val = c;
229 break 'a;
230 }
231
232 },
233 }
234 }
235 }
236 fn repopulate(&mut self, v: &mut Vec<i64>){
237 v.push(self.root.val);
238 if self.left.is_some(){
239 self.left.as_mut().unwrap().repopulate(v);
240 }
241 if self.right.is_some(){
242 self.right.as_mut().unwrap().repopulate(v);
243 }
244 }
245 pub fn successor(&mut self) -> &mut BinTree{
246 //!Successor returns a BinTree of the next largest value in the tree from the root (of self)
247 //! ```rust
248 //! use unsafe_bst::*;
249 //! let mut tree = binary_tree::BinTree{..Default::default()};
250 //! tree.add_node(nodes::Node{val:14});
251 //! tree.add_node(nodes::Node{val:17});
252 //! tree.add_node(nodes::Node{val:15});
253 //! assert_eq!(15,tree.successor().root.val);
254 //! ```
255 let mut b: &mut BinTree = self.right.as_mut().unwrap().borrow_mut();
256 while b.root.val != -1 {
257 if b.left.is_none(){break;}
258 else{
259 b = b.shift_left();
260 }
261 }
262 return b;
263 }
264 pub fn shift_left(&mut self) -> &mut BinTree{
265 //!Shift Left returns the left-subtree of a tree
266 return self.left.as_mut().unwrap().borrow_mut();
267 }
268 pub fn shift_right(&mut self) -> &mut BinTree{
269 //!Shift Right returns the right-subtree of a tree
270 return unsafe{self.right.as_mut().unwrap_unchecked().borrow_mut()};
271 }
272 pub fn get_predecessor(&mut self) -> nodes::Node{
273 //!Get Predecessor returns the Node with the next smallest value to root (self)
274 let mut b: &mut BinTree = self.left.as_mut().unwrap().borrow_mut();
275 while b.right.is_some(){
276 b = b.shift_right();
277 }
278 return b.root.clone();
279 }
280 pub fn get_successor(&mut self) -> nodes::Node{
281 //!Get Successor returns the Node with the next largest value to root (self)
282 let mut b: &mut BinTree = self.right.as_mut().unwrap().borrow_mut();
283 while b.left.is_some(){
284 b = b.shift_left();
285 }
286 return b.root.clone();
287 }
288 pub fn balance(&mut self, s: &mut Stats) -> BinTree{
289 //!Balance attempts to make a perfect BST when it can, else it makes a tree with minimum height
290 let mut b_t: BinTree = BinTree{..Default::default()};
291 let mut v = s.list.clone();
292 v.sort();
293 s.list = Vec::new();
294 //self is empty, and v has all values
295 let a = v.len() as usize;
296 if a > 0{
297 b_t.build(&mut v, 0, a-1, s);}
298 b_t
299 }
300 fn build(&mut self, v: &mut Vec<i64>, start: usize, end: usize, s: &mut Stats){
301 if start>end{
302 return;
303 }
304 let mid:usize = ((start+end)/2).try_into().unwrap();
305 let roo = v[mid];
306 s.list.push(roo);
307 //println!("{roo}");
308 self.add_node(Node { val: roo });
309
310 if mid>0{
311 self.build(v, start, (mid-1).try_into().unwrap(), s);
312 }
313 self.build(v, (mid+1).try_into().unwrap(), end, s);
314 return;
315 }
316 pub fn height(&mut self, i: i64, v: &mut Vec<i64>){
317 if self.left.is_some(){
318 self.left.as_mut().unwrap().height(i+1, v);
319
320 }
321 if self.right.is_some(){
322 self.right.as_mut().unwrap().height(i+1, v);
323
324 }
325 v.push(i);
326 }
327 }
328 #[warn(unconditional_recursion)]
329 impl Default for BinTree{
330 fn default() -> Self {
331 BinTree{root: nodes::Node{val: -1}, left: None, right: None}
332 }
333 }
334 }
335 ///Module that holds statistics for the BST
336 /// #[derive(Debug,Clone)]
337 pub mod stats{
338
339 #[derive(Debug,Clone)]
340 pub struct Stats{
341 pub count: i64,
342 pub list: Vec<i64>,
343 }
344 impl Stats{
345 pub fn add(&mut self, val: i64){
346 //!Add adds values to a Stats variable if the value is not in it already
347 match self.list.binary_search(&val){
348 Ok(_s) => return,
349 Err(_s) =>{
350 self.list.push(val);
351 self.count+=1;
352 },
353 }
354
355 }
356 pub fn add_list(&mut self, lis: Vec<i64>) -> bool{
357 //!Add_list combines two vectors together, returning true if every value was unique to the stats/tree
358 let pre = self.count + lis.len() as i64;
359 for l in &lis{
360 self.add(*l);
361
362 }
363
364 if pre != self.list.len() as i64 {
365 return false;
366 }
367
368 return true;
369 }
370 pub fn remove(&mut self, val: i64) -> bool{
371 //!Removes a value from the list, or returns false
372 let k = 0;
373 let b = self.list.remove(self.list.iter().position(|&r | r == val).unwrap_or_else(|| k));
374 if b == val{
375 self.count-=1;
376 return true;
377 }
378 return false;
379 }
380 pub fn print_count(&mut self){
381 //!Prints # of nodes have been added correctly
382 println!("# of Nodes: {}",self.count);
383 }
384 pub fn print_list(&mut self){
385 //!Prints all the node values added correctly
386 if self.list.len() == 0{return;}
387 print!("List of Nodes: ");
388 let last = self.list.last().unwrap();
389 for num in &self.list{
390 print!("{}",num);
391 if last == num {print!("\n")} else {print!(", ")}
392 }
393 }
394 pub fn print(&mut self){
395 //!Calls print_count() and print_list()
396 self.print_count();
397 self.print_list();
398 }
399 }
400
401 impl Default for Stats{
402 fn default() -> Self {
403 Stats{count: 0, list: Vec::new()}
404 }
405 }
406}
407pub mod depreciated_functions{
408 /*
409 impl crate::binary_tree::BinTree{
410 fn add_next(&mut self, node: crate::nodes::Node){
411 if node.val == -1 {return;}
412 if self.root.val == -1 {
413 self. root = node;
414 return;
415 }
416 if self.root.val > node.val{
417 if !self.left.is_some(){
418 self.left = Some(Box::new(crate::binary_tree::BinTree{root: node, ..Default::default()}));
419 }else{
420 unsafe {let _ = &self.left.as_mut().unwrap_unchecked().add_next(node);}
421 }
422 }else{
423 if !self.right.is_some(){
424 self.right = Some(Box::new(crate::binary_tree::BinTree{root: node, ..Default::default()}));
425 }else{
426 unsafe {let _ = &self.right.as_mut().unwrap_unchecked().add_next(node);}
427 }
428 }
429 }
430 pub fn add_2(&mut self, node: nodes::Node){
431 if node.val == -1 {return;}
432 if self.root.val == -1 {
433 self. root = node;
434 return;
435 }
436 if self.root.val > node.val{
437 match self.left{
438 Some(_) => {self.left.as_mut().unwrap().add_2(node)},
439 None => self.left = Some(Box::new(BinTree{root: node, ..Default::default()})),
440 }
441 }else{
442 match self.right{
443 Some(_) => {self.right.as_mut().unwrap().add_2(node)},
444 None => self.right = Some(Box::new(BinTree{root: node, ..Default::default()})),
445 }
446 }
447 }
448
449 }
450 */
451}
452
453
454#[test]
455fn add_node_test(){
456 let mut b_t = binary_tree::BinTree{..Default::default()};
457 b_t.add_node(nodes::Node { val: 14 });
458
459 assert_eq!(b_t.root.val, 14);
460}
461#[test]
462fn equal_bst_test(){
463 let mut b_t = binary_tree::BinTree{..Default::default()};
464 let mut b_t2 = binary_tree::BinTree{..Default::default()};
465
466 assert_eq!(b_t.print(0),b_t2.print(0));
467
468 b_t.add_node(nodes::Node { val: 14 });
469
470 assert_ne!(b_t.print(0),b_t2.print(0));
471
472 b_t2.add_node(nodes::Node { val: 14 });
473 assert_eq!(b_t.print(0),b_t2.print(0));
474}
475
476#[test]
477fn print_test(){
478 let mut b_t = binary_tree::BinTree{..Default::default()};
479 b_t.add_node(nodes::Node { val: 14 });
480 b_t.add_node(nodes::Node { val: 13 });
481 b_t.add_node(nodes::Node { val: 15 });
482 let s = b_t.print(0);
483 println!("{s}");
484 assert_ne!(s,"");
485
486}
487#[test]
488fn delete_test(){
489 let mut b_t = binary_tree::BinTree{..Default::default()};
490 let mut b_t2 = binary_tree::BinTree{..Default::default()};
491 b_t.add_node(nodes::Node { val: 14 });
492 b_t.add_node(nodes::Node { val: 13 });
493 b_t.add_node(nodes::Node { val: 15 });
494 b_t2.add_node(nodes::Node { val: 14 });
495 b_t2.add_node(nodes::Node { val: 13 });
496 b_t2.add_node(nodes::Node { val: 15 });
497 assert_eq!(b_t.print(0),b_t2.print(0));
498 b_t.add_node(nodes::Node { val: 16 });
499
500 println!("b1{}",b_t.print(0));
501 println!("b2{}",b_t2.print(0));
502
503
504 assert_ne!(b_t.print(0),b_t2.print(0));
505 b_t.delete(16);
506 println!("b2{}",b_t.print(0));
507 assert_eq!(b_t.print(0),b_t2.print(0));
508}
509
510#[test]
511fn print_2_test(){
512 let mut b_t = binary_tree::BinTree{..Default::default()};
513 b_t.add_node(nodes::Node { val: 14 });
514 b_t.add_node(nodes::Node { val: 13 });
515 b_t.add_node(nodes::Node { val: 15 });
516 assert_ne!(b_t.print_2(0, 0),b_t.print_2(0,1));
517}
518
519#[test]
520fn height_test_1(){
521 let mut b_t = binary_tree::BinTree{..Default::default()};
522 b_t.add_node(nodes::Node { val: 14 });
523 b_t.add_node(nodes::Node { val: 13 });
524 b_t.add_node(nodes::Node { val: 12 });
525 let i = 0;
526 let mut v: Vec<i64> = Vec::new();
527 b_t.height(i, &mut v);
528 v.sort();
529 // v.pop().unwrap();
530 assert_eq!(2,v.pop().unwrap());
531}
532#[test]
533fn height_test_2(){
534 let mut b_t = binary_tree::BinTree{..Default::default()};
535 let mut s = stats::Stats {..Default::default()};
536 for n in 1..32{
537 b_t.add_node(nodes::Node { val: n });
538 s.add(n);
539 }
540 b_t = b_t.balance(&mut s);
541 let mut v: Vec<i64> = Vec::new();
542 let i = 0;
543 b_t.height(i, &mut v);
544 v.sort();
545 assert_eq!(4, v.pop().unwrap());
546}