truetree/
lib.rs

1use core::fmt;
2use std::borrow::BorrowMut;
3use std::cmp::max;
4use std::fmt::{Debug, Display};
5use std::mem::{replace, swap};
6use std::ops::Not;
7use std::collections::HashSet;
8use std::hash::Hash;
9
10#[derive(Debug, PartialEq, Clone, Copy)]
11#[repr(u8)]
12pub enum Side {
13    Left = 0,
14    Right = 1,
15}
16
17impl Not for Side {
18    type Output = Self;
19    fn not(self) -> Self::Output {
20        match self {
21            Side::Left => Side::Right,
22            Side::Right => Side::Left
23        }
24    }
25}
26
27#[derive(Debug, Clone, PartialEq)]
28struct Node<T: Clone + Ord + Eq + Debug + Display + Hash> {
29    children: [Tree<T>; 2],
30    value: T,
31    duplicates: HashSet<T>,
32    height: usize,
33}
34
35impl<T: Clone + Ord + Eq + Debug + Display + Hash> fmt::Pointer for Node<T> {
36    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37        let ptr = self as *const Self;
38        fmt::Pointer::fmt(&ptr, f)
39    }
40}
41
42impl<T: Clone + Ord + Eq + Debug + Display + Hash> fmt::Display for Node<T> {
43    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
44        write!(f, "{:?}", self)
45    }
46}
47
48type Tree<T> = Option<Box<Node<T>>>;
49
50#[derive(Debug, PartialEq, Clone)]
51pub struct AvlTree<T: Clone + Ord + Eq + Debug + Display + Hash> {
52    root: Tree<T>,
53}
54
55#[cfg(test)]
56mod test_tree {
57    use super::*;
58    use std::cmp::Ordering;
59
60    #[derive(Clone, Eq, PartialEq, Debug, Hash)]
61    struct Position {
62        x: i32,
63        y: i32,
64    }
65
66    impl Ord for Position {
67        fn cmp(&self, other: &Self) -> Ordering {
68            self.x.cmp(&other.x)
69        }
70    }
71
72    impl PartialOrd for Position {
73        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
74            Some(self.cmp(other))
75        }
76    }
77
78    impl fmt::Display for Position {
79        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
80            write!(f, "\"{},{}\"", self.x, self.y)
81        }
82    }
83
84    const TEST_1: u64 = 42;
85    const TEST_2: u64 = 420;
86    const TEST_3: u64 = 66;
87    const TEST_4: u64 = 88;
88    const TEST_5: u64 = 99;
89
90
91    #[test]
92    fn test_create() {
93        let tree: AvlTree<u64> = AvlTree::new();
94        assert!(tree.root.is_none());
95        assert!(tree.is_empty())
96    }
97
98    #[test]
99    fn test_insert() {
100        let mut tree: AvlTree<u64> = AvlTree::new();
101        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
102        assert!(res.is_ok());
103        assert!(!tree.is_empty());
104        assert!(tree.root.is_some());
105        assert_eq!(tree.root.unwrap().value, TEST_1);
106    }
107
108    #[test]
109    fn test_insert_twice() {
110        let mut tree: AvlTree<u64> = AvlTree::new();
111        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
112        assert!(res.is_ok());
113        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_2);
114        assert!(res.is_ok());
115        assert!(!tree.is_empty());
116        assert!(tree.root.is_some());
117        assert_eq!(tree.root.as_ref().unwrap().value, TEST_1);
118        assert!(tree.root.as_ref().unwrap().children[Side::Right as usize].is_some());
119        assert!(tree.root.as_ref().unwrap().children[Side::Left as usize].is_none());
120        assert_eq!(tree.root.as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_2);
121    }
122
123    #[test]
124    fn test_insert_thrice() {
125        let mut tree: AvlTree<u64> = AvlTree::new();
126        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
127        assert!(res.is_ok());
128        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_2);
129        assert!(res.is_ok());
130        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_3);
131        assert!(res.is_ok());
132        assert!(!tree.is_empty());
133        assert!(tree.root.is_some());
134        assert_eq!(tree.root.as_ref().unwrap().value, TEST_3);
135        assert!(tree.root.as_ref().unwrap().children[Side::Right as usize].is_some());
136        assert_eq!(tree.root.as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_2);
137        assert!(tree.root.as_ref().unwrap().children[Side::Left as usize].is_some());
138        assert_eq!(tree.root.as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_1);
139    }
140
141    #[test]
142    fn test_contains() {
143        let mut tree: AvlTree<u64> = AvlTree::new();
144        tree.insert(&TEST_1).expect("Insert failed")
145            .insert(&TEST_2).expect("Insert failed")
146            .insert(&TEST_3).expect("Insert failed")
147            .insert(&TEST_4).expect("Insert failed");
148
149        assert!(tree.contains(&TEST_1));
150        assert!(tree.contains(&TEST_2));
151        assert!(tree.contains(&TEST_3));
152        assert!(tree.contains(&TEST_4));
153        assert!(!tree.contains(&TEST_5));
154        tree.insert(&TEST_5).expect("Insert failed");
155        assert!(tree.contains(&TEST_5));
156    }
157
158    #[test]
159    fn test_insert_complex() {
160        let mut tree: AvlTree<u64> = AvlTree::new();
161        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&1);
162        assert!(res.is_ok());
163        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&2);
164        assert!(res.is_ok());
165        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&3);
166        assert!(res.is_ok());
167        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&4);
168        assert!(res.is_ok());
169        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&5);
170        assert!(res.is_ok());
171        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&6);
172        assert!(res.is_ok());
173        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&7);
174        assert!(res.is_ok());
175        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&8);
176        assert!(res.is_ok());
177        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&9);
178        assert!(res.is_ok());
179        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&10);
180        assert!(res.is_ok());
181        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&11);
182        assert!(res.is_ok());
183        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&12);
184        assert!(res.is_ok());
185        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&13);
186        assert!(res.is_ok());
187        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&14);
188        assert!(res.is_ok());
189        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&15);
190        assert!(res.is_ok());
191        assert!(!tree.is_empty());
192        assert_eq!(tree.root.unwrap().height, 4)
193    }
194
195
196    #[test]
197    fn test_insert_heap_var() {
198        let mut tree: AvlTree<u64> = AvlTree::new();
199        {
200            let value: u64 = 67;
201            let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&value);
202            assert!(res.is_ok());
203            drop(value);
204        }
205        assert!(!tree.is_empty());
206        assert_eq!(tree.root.unwrap().value, 67)
207    }
208
209    #[test]
210    fn test_delete_heap() {
211        let mut tree: AvlTree<u64> = AvlTree::new();
212        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_1);
213        assert!(res.is_ok());
214        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_2);
215        assert!(res.is_ok());
216        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_3);
217        assert!(res.is_ok());
218        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_4);
219        assert!(res.is_ok());
220        let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&TEST_5);
221        assert!(res.is_ok());
222        assert!(!tree.is_empty());
223        assert_eq!(tree.root.as_ref().unwrap().value, TEST_3);
224        tree.clear();
225        assert_eq!(tree.depth(), 0);
226        tree.delete();
227    }
228
229    #[test]
230    fn test_delete_complex() {
231        let mut tree: AvlTree<u64> = AvlTree::new();
232        {
233            let payload: u64 = 67;
234            let res: Result<&mut AvlTree<u64>, &str> = tree.insert(&payload);
235            assert!(res.is_ok());
236            drop(payload);
237        }
238        assert!(!tree.is_empty());
239        assert_eq!(tree.root.as_ref().unwrap().value, 67);
240        tree.delete();
241    }
242
243    #[test]
244    fn test_height() {
245        let mut tree: AvlTree<u64> = AvlTree::new();
246        let _res = tree.insert(&TEST_1).expect("Failed insert")
247            .insert(&TEST_2).expect("Failed insert")
248            .insert(&TEST_3).expect("Failed insert")
249            .insert(&TEST_4).expect("Failed insert")
250            .insert(&TEST_5).expect("Failed insert");
251        assert_eq!(tree.height(), 3);
252    }
253
254    #[test]
255    fn test_balancing() {
256        let tree: AvlTree<u64> = AvlTree::new();
257        assert!(tree.is_balanced());
258        tree.delete();
259        let mut tree: AvlTree<u64> = AvlTree::new();
260        let _res = tree.insert(&TEST_1).expect("Failed insert")
261            .insert(&TEST_2).expect("Failed insert")
262            .insert(&TEST_3).expect("Failed insert")
263            .insert(&TEST_4).expect("Failed insert")
264            .insert(&TEST_5).expect("Failed insert");
265        assert!(tree.is_correct());
266        assert!(tree.is_balanced());
267    }
268
269    #[test]
270    fn test_remove() {
271        let mut tree: AvlTree<u64> = AvlTree::new();
272        let _res = tree.insert(&TEST_1).expect("Failed insert")
273            .insert(&TEST_2).expect("Failed insert")
274            .insert(&TEST_3).expect("Failed insert")
275            .insert(&TEST_4).expect("Failed insert")
276            .insert(&TEST_5).expect("Failed insert");
277        assert!(tree.is_correct());
278        assert!(tree.is_balanced());
279        assert_eq!(tree.height(), 3);
280        let res: Result<&mut AvlTree<u64>, &str> = tree.remove(&TEST_1);
281        assert!(res.is_ok());
282        assert_eq!(tree.height(), 3);
283        assert!(tree.is_balanced());
284        let res: Result<&mut AvlTree<u64>, &str> = tree.remove(&TEST_2);
285        assert!(res.is_ok());
286        assert_eq!(tree.height(), 2);
287        assert!(tree.is_balanced());
288        let res: Result<&mut AvlTree<u64>, &str> = tree.remove(&TEST_2);
289        assert!(res.is_err());
290        assert_eq!(tree.height(), 2);
291        assert!(tree.is_balanced());
292        let _res = tree.remove(&TEST_3).expect("Failed removed");
293        let _res = tree.remove(&TEST_4).expect("Failed removed");
294        let _res = tree.remove(&TEST_5).expect("Failed removed");
295        assert_eq!(tree.height(), 0);
296    }
297
298    #[test]
299    fn test_min_max() {
300        let mut tree: AvlTree<u64> = AvlTree::new();
301        let _res = tree.insert(&TEST_1).expect("Failed insert")
302            .insert(&TEST_2).expect("Failed insert")
303            .insert(&TEST_3).expect("Failed insert")
304            .insert(&TEST_4).expect("Failed insert")
305            .insert(&TEST_5).expect("Failed insert");
306        assert!(tree.min().is_some());
307        assert_eq!(tree.min().unwrap(), TEST_1);
308        assert!(tree.max().is_some());
309        assert_eq!(tree.max().unwrap(), TEST_2);
310    }
311
312    #[test]
313    fn test_width_count_depth() {
314        let mut tree: AvlTree<u64> = AvlTree::new();
315        let _res = tree.insert(&TEST_1).expect("Failed insert")
316            .insert(&TEST_2).expect("Failed insert")
317            .insert(&TEST_3).expect("Failed insert")
318            .insert(&TEST_4).expect("Failed insert")
319            .insert(&TEST_5).expect("Failed insert");
320        assert_eq!(tree.depth(), 3);
321        assert_eq!(tree.width(), 3);
322        assert_eq!(tree.count(), 5);
323    }
324
325    #[test]
326    fn test_get_set() {
327        let mut tree: AvlTree<Position> = AvlTree::new();
328        let _res = tree.insert(&Position { x: 1, y: 0 }).expect("Failed insert")
329            .insert(&Position { x: 2, y: 0 }).expect("Failed insert")
330            .insert(&Position { x: 3, y: 0 }).expect("Failed insert")
331            .insert(&Position { x: 4, y: 0 }).expect("Failed insert")
332            .insert(&Position { x: 5, y: 1 }).expect("Failed insert")
333            .insert(&Position { x: 5, y: 2 }).expect("Failed insert")
334            .insert(&Position { x: 5, y: 3 }).expect("Failed insert")
335            .insert(&Position { x: 5, y: 4 }).expect("Failed insert")
336            .insert(&Position { x: 5, y: 5 }).expect("Failed insert");
337        assert_eq!(tree.get_set(&Position { x: 5, y: -1 }).len(), 5);
338    }
339
340    #[test]
341    fn test_remove_duplicates() {
342        let mut tree: AvlTree<Position> = AvlTree::new();
343        let _res = tree.insert(&Position { x: 1, y: 0 }).expect("Failed insert")
344            .insert(&Position { x: 2, y: 0 }).expect("Failed insert")
345            .insert(&Position { x: 3, y: 0 }).expect("Failed insert")
346            .insert(&Position { x: 5, y: 1 }).expect("Failed insert")
347            .insert(&Position { x: 5, y: 2 }).expect("Failed insert")
348            .insert(&Position { x: 5, y: 3 }).expect("Failed insert")
349            .insert(&Position { x: 5, y: 4 }).expect("Failed insert")
350            .insert(&Position { x: 5, y: 5 }).expect("Failed insert");
351        assert_eq!(tree.depth(), 3);
352        let res=tree.remove(&Position { x: 5, y: -1 });
353        assert!(res.is_err());
354        assert_eq!(res.unwrap_err(), "The value was not found");
355        assert_eq!(tree.depth(), 3);
356        let res=tree.remove(&Position { x: 5, y: 1 });
357        assert!(res.is_ok());
358        assert_eq!(tree.depth(), 3);
359        assert!(tree.contains(&Position { x: 5, y: 1 }));
360        assert!(!tree.contains_exact(&Position { x: 5, y: 1 }));
361        let res=tree.remove(&Position { x: 5, y: 2 });
362        assert!(res.is_ok());
363        assert_eq!(tree.depth(), 3);
364        let res=tree.remove(&Position { x: 5, y: 3 });
365        assert!(res.is_ok());
366        assert_eq!(tree.depth(), 3);
367        let res=tree.remove(&Position { x: 5, y: 4 });
368        assert!(res.is_ok());
369        assert_eq!(tree.depth(), 3);
370        let res=tree.remove(&Position { x: 5, y: 5 });
371        assert!(res.is_ok());
372        assert_eq!(tree.depth(), 2);
373    }
374}
375
376/// This is a balanced tree implementation (also called as AVL tree)
377/// We allow you to define a custom type T to pass a the tree payload
378/// This payload should have the clone, ord, eq, debug and display trait derived
379/// The Ord trait is used to insert the values and to get it (this allow to match only partial payload)
380/// The Eq trait is used to remove a node
381/// The Clone trait is used to copy the value inside the tree
382/// The Display trait is used to print/dump the tree
383impl<'a, T: 'a + Clone + Ord + Eq + Debug + Display + Hash> AvlTree<T> {
384    /// Create a new tree (a tree is defined as an optional heap pointer to a Node of type T)
385    /// By default we made a wrapper around the internal implementation with a root node
386    pub fn new() -> Self {
387        AvlTree {
388            root: None
389        }
390    }
391
392    /// Create a new tree (a tree is defined as an optional heap pointer to a Node of type T)
393    /// with a default value, all value passed are cloned and should implement Clone, Ord, Eq and Debug
394    /// There is an example of such Payload creation in integration_avl
395    pub fn with(value: &T) -> Self {
396        AvlTree {
397            root: Node::create_tree(value)
398        }
399    }
400
401    /// Insert a value in the tree and return itself if no errors (by default we allow duplicate key value (using Eq trait, not Ord)
402    /// You can chain multiple insert
403    pub fn insert(&mut self, value: &T) -> Result<&mut Self, &str> {
404        if self.root.is_none() {
405            self.root = Node::create_tree(value)
406        } else {
407            if !self.root.as_mut().unwrap().insert(value.clone()) {
408                return Err("Can not insert same value twice");
409            }
410        }
411        Ok(&mut *self)
412    }
413
414    /// Delete all the values in the tree, the structure holding the tree should theoretically not be reused
415    /// This is effectively the same as clear()
416    pub fn delete(mut self) -> () {
417        if !self.root.is_none() {
418            Node::delete(self.root.borrow_mut())
419        }
420        drop(self);
421    }
422
423    /// Delete all the values in the tree, the structure holding the tree can be reused afterwards
424    /// This is effectively the same as delete()
425    pub fn clear(&mut self) -> () {
426        if !self.root.is_none() {
427            Node::delete(self.root.borrow_mut())
428        }
429    }
430    /// Remove a value from the tree and return itself if was successful else return an error
431    /// Warning we use Eq to remove the correct value, if you don't know all the fields, use the get which use Ord only
432    /// See integration for an example.
433    pub fn remove(&mut self, value: &T) -> Result<&mut Self, &str> {
434        if self.root.is_none() {
435            Err("You don't have any node in the tree")
436        } else {
437            let res: Option<T> = Node::remove(&mut self.root, value);
438            if res.is_none() {
439                Err("The value was not found")
440            } else if &res.unwrap() != value {
441                Err("ERROR ! The value removed was not the correct one.")
442            } else {
443                Ok(&mut *self)
444            }
445        }
446    }
447
448    /// Print the tree as a JSON formatted string,
449    /// It's possible to prettify it with the boolean
450    pub fn print(&self, prettify: bool) -> () {
451        if self.root.is_none() {
452            println!("You don't have any node in the tree");
453        } else {
454            println!("{}", self.root.as_ref().unwrap().dump(prettify));
455        }
456    }
457
458    /// Dump the tree as a JSON formatted string,
459    /// It's possible to prettify it with the boolean
460    pub fn dump(&self, prettify: bool) -> Result<String, &str> {
461        if self.root.is_none() {
462            Err("You don't have any node in the tree")
463        } else {
464            Ok(self.root.as_ref().unwrap().dump(prettify))
465        }
466    }
467
468    /// Get a value based only on Ord (not Eq), this allow loosy check in case of complex payload
469    /// This return only the value or none, for a subtree see find
470    /// If duplicate keys this will return only the tree ordered first one
471    pub fn get(&self, value: &T) -> Option<T> {
472        let tree: &Tree<T> = Node::get(&self.root, value);
473        return tree.as_ref().map_or(None, |x| Some(x.value.clone()));
474    }
475
476    /// Get a value based only on Ord (not Eq), this allow loosy check in case of complex payload
477    /// This return only the value or none, for a subtree see find
478    /// If duplicate keys this will return the exact match if any else None
479    pub fn get_exact(&self, value: &T) -> Option<T> {
480        let set: HashSet<T> = self.get_set(value);
481        let value: Option<&T> = set.get(value);
482        return if value.is_none() { None } else { Some(value.unwrap().clone()) };
483    }
484
485    /// Get the set of value based only on Ord (not Eq), this allow loosy check in case of complex payload
486    /// This return only the value or none, for a subtree see find
487    pub fn get_set(&self, value: &T) -> HashSet<T> {
488        let tree: &Tree<T> = Node::get(&self.root, value);
489        return if tree.is_none() {
490            HashSet::new()
491        } else {
492            let mut set: HashSet<T> = tree.as_ref().unwrap().duplicates.clone();
493            set.insert(tree.as_ref().unwrap().value.clone());
494            set
495        };
496    }
497
498
499    /// Find a value and return it as the subtree (equivalent as get but allow to chain operation on the subtree)
500    /// Warning this is Ord based so if there is duplicate you might get the wrong value here but you can check the duplicates to find it
501    pub fn find(&self, value: &T) -> Result<Self, &str> {
502        let tree: &Tree<T> = Node::get(&self.root, value);
503        if tree.is_none() {
504            return Err("Not found");
505        }
506        return Ok(AvlTree {
507            root: tree.clone()
508        });
509    }
510
511
512    /// Check if a value is contained in the tree with Ord trait only
513    pub fn contains(&self, value: &T) -> bool {
514        Node::get(&self.root, value).is_some()
515    }
516
517    /// Check if a value is contained in the tree with Eq trait
518    pub fn contains_exact(&self, value: &T) -> bool {
519        let res: HashSet<T> = self.get_set(value);
520        return res.contains(value);
521    }
522
523    /// Check if the tree is empty or not
524    pub fn is_empty(&self) -> bool {
525        self.root.is_none()
526    }
527
528    /// Failing case for test
529    pub fn fail(&mut self) -> Result<&mut Self, &str> {
530        Err("Oups, I always fail")
531    }
532
533    /// Working case for test
534    pub fn works(&mut self) -> Result<&mut Self, &str> {
535        Ok(&mut *self)
536    }
537
538    /// Return the height of the tree as a fast heuristic (this could be wrong if you tampered the tree)
539    pub fn height(&self) -> usize {
540        self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.height())
541    }
542
543    /// Return the true depth of the tree by going through all the nodes
544    pub fn depth(&self) -> usize {
545        self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.depth())
546    }
547    /// Get the number of leaves, a leave is a node which has one or more children missing (so a node with only one child is a leave also)
548    ///     1          1
549    ///      \        / \
550    ///       2      2   3
551    /// Those have a width of 2
552    pub fn width(&self) -> usize {
553        self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.width())
554    }
555
556    /// Get the number of nodes in the tree
557    pub fn count(&self) -> usize {
558        self.root.as_ref().map_or(0, |node: &Box<Node<T>>| node.count())
559    }
560
561    /// Get the minimum of the tree (or the left most)
562    pub fn min(&self) -> Option<T> {
563        self.root.as_ref().map_or(None, |node: &Box<Node<T>>| Some(node.min().clone()))
564    }
565
566    /// Get the maximum of the tree (or the right most)
567    pub fn max(&self) -> Option<T> {
568        self.root.as_ref().map_or(None, |node: &Box<Node<T>>| Some(node.max().clone()))
569    }
570
571    /// Check if the tree is balanced (this is quite intensive but gave correct result)
572    pub fn is_balanced(&self) -> bool {
573        self.root.as_ref().map_or(true, |node: &Box<Node<T>>| node.is_balanced())
574    }
575
576    /// Check if the heights are correct (might have not be registered correctly, this is a soft check)
577    pub fn is_correct(&self) -> bool {
578        self.root.as_ref().map_or(true, |node: &Box<Node<T>>| node.sanity_check())
579    }
580}
581
582#[cfg(test)]
583mod test_node {
584    use super::*;
585
586    const TEST_1: u64 = 42;
587    const TEST_2: u64 = 420;
588    const TEST_3: u64 = 66;
589    const TEST_4: u64 = 88;
590    const TEST_5: u64 = 99;
591
592    #[test]
593    fn test_side() {
594        assert_eq!(Side::Left as u8, 0);
595        assert_eq!(Side::Right as u8, 1);
596        assert_eq!(!Side::Left, Side::Right);
597        assert_eq!(!Side::Right, Side::Left);
598        assert_eq!(!!Side::Right, Side::Right);
599    }
600
601    #[test]
602    fn test_create() {
603        let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
604            children: [
605                Some(Box::new(Node {
606                    children: [None, None],
607                    value: TEST_2,
608                    duplicates: HashSet::with_capacity(0),
609                    height: 1,
610                })),
611                None
612            ],
613            value: TEST_1,
614            duplicates: HashSet::with_capacity(0),
615            height: 2,
616        }));
617        let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
618        assert!(ref_tree.is_some());
619        assert_eq!(ref_tree.unwrap().height, 2);
620        assert_eq!(ref_tree.unwrap().value, TEST_1);
621        assert_eq!(ref_tree.unwrap().children.len(), 2);
622        assert_eq!(ref_tree.unwrap().children[1], None);
623        assert!(ref_tree.unwrap().children[0].is_some());
624        assert_eq!(ref_tree.unwrap().children[0].as_ref().unwrap().value, TEST_2);
625        assert_eq!(ref_tree.unwrap().children[0].as_ref().unwrap().height, 1);
626    }
627
628    #[test]
629    fn test_sanity_check() {
630        let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
631            children: [
632                Some(Box::new(Node {
633                    children: [None, None],
634                    value: TEST_2,
635                    duplicates: HashSet::with_capacity(0),
636                    height: 1,
637                })),
638                Some(Box::new(Node {
639                    children: [None, None],
640                    value: TEST_3,
641                    duplicates: HashSet::with_capacity(0),
642                    height: 1,
643                })),
644            ],
645            value: TEST_1,
646            duplicates: HashSet::with_capacity(0),
647            height: 2,
648        }));
649        let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
650        assert!(ref_tree.is_some());
651        assert_eq!(ref_tree.unwrap().sanity_check(), true);
652        assert_eq!(ref_tree.unwrap().is_balanced(), true);
653        let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
654            children: [
655                Some(Box::new(Node {
656                    children: [None, None],
657                    value: TEST_2,
658                    duplicates: HashSet::with_capacity(0),
659                    height: 1,
660                })),
661                Some(Box::new(Node {
662                    children: [None, None],
663                    value: TEST_3,
664                    duplicates: HashSet::with_capacity(0),
665                    height: 2,// incorrect height here (will fail sanity but not balanced)
666                })),
667            ],
668            value: TEST_1,
669            duplicates: HashSet::with_capacity(0),
670            height: 2,
671        }));
672        let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
673        assert!(ref_tree.is_some());
674        assert_eq!(ref_tree.unwrap().sanity_check(), false);
675        assert_eq!(ref_tree.unwrap().is_balanced(), true);
676        let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
677            children: [
678                Some(Box::new(Node {
679                    children: [Some(Box::new(Node {
680                        children: [None, None],
681                        value: TEST_3,
682                        duplicates: HashSet::with_capacity(0),
683                        height: 1,
684                    })), None],
685                    value: TEST_2,
686                    duplicates: HashSet::with_capacity(0),
687                    height: 2,
688                })),
689                None,
690            ],
691            value: TEST_1,
692            duplicates: HashSet::with_capacity(0),
693            height: 3,
694        }));
695        let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
696        assert!(ref_tree.is_some());
697        assert_eq!(ref_tree.unwrap().sanity_check(), true);
698        assert_eq!(ref_tree.unwrap().is_balanced(), false);
699        assert_eq!(ref_tree.unwrap().depth(), ref_tree.unwrap().height);
700
701        let tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
702            children: [
703                Some(Box::new(Node {
704                    children: [Some(Box::new(Node {
705                        children: [None, None],
706                        value: TEST_3,
707                        duplicates: HashSet::with_capacity(0),
708                        height: 1,
709                    })), None],
710                    value: TEST_2,
711                    duplicates: HashSet::with_capacity(0),
712                    height: 22121,
713                })),
714                None,
715            ],
716            value: TEST_1,
717            duplicates: HashSet::with_capacity(0),
718            height: 3,
719        }));
720        let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
721        assert!(ref_tree.is_some());
722        assert_eq!(ref_tree.unwrap().sanity_check(), false);
723        assert_eq!(ref_tree.unwrap().is_balanced(), false);
724        assert_eq!(ref_tree.unwrap().depth(), ref_tree.unwrap().height)
725    }
726
727    #[test]
728    ///           1              2
729    ///         /  \            / \
730    ///        2    3    ->    4   1
731    ///       / \                 / \
732    ///      4   5               5   3
733    ///
734    ///
735    fn test_rotate_right() {
736        let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
737            children: [
738                Some(Box::new(Node {
739                    children: [Some(Box::new(Node {
740                        children: [None, None],
741                        value: TEST_4,
742                        duplicates: HashSet::with_capacity(0),
743                        height: 1,
744                    })), Some(Box::new(Node {
745                        children: [None, None],
746                        value: TEST_5,
747                        duplicates: HashSet::with_capacity(0),
748                        height: 1,
749                    }))],
750                    value: TEST_2,
751                    duplicates: HashSet::with_capacity(0),
752                    height: 2,
753                })),
754                Some(Box::new(Node {
755                    children: [None, None],
756                    value: TEST_3,
757                    duplicates: HashSet::with_capacity(0),
758                    height: 1,
759                })),
760            ],
761            value: TEST_1,
762            duplicates: HashSet::with_capacity(0),
763            height: 3,
764        }));
765        let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
766        assert_eq!(ref_tree.value, TEST_1);
767        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
768        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
769        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
770        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
771        let res: bool = tree.as_mut().unwrap().rotate(Side::Right);
772        assert!(res);
773        let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
774        assert_eq!(ref_tree.value, TEST_2);
775        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
776        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_1);
777        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_5);
778        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
779    }
780
781    #[test]
782    ///           3              1
783    ///          / \            / \
784    ///         1   5    <-    2   3
785    ///        / \                / \
786    ///       2   4              4   5
787    ///
788    ///
789    fn test_rotate_left() {
790        let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
791            children: [
792                Some(Box::new(Node {
793                    children: [None, None],
794                    value: TEST_2,
795                    duplicates: HashSet::with_capacity(0),
796                    height: 1,
797                })),
798                Some(Box::new(Node {
799                    children: [Some(Box::new(Node {
800                        children: [None, None],
801                        value: TEST_4,
802                        duplicates: HashSet::with_capacity(0),
803                        height: 1,
804                    })), Some(Box::new(Node {
805                        children: [None, None],
806                        value: TEST_5,
807                        duplicates: HashSet::with_capacity(0),
808                        height: 1,
809                    }))],
810                    value: TEST_3,
811                    duplicates: HashSet::with_capacity(0),
812                    height: 2,
813                })),
814            ],
815            value: TEST_1,
816            duplicates: HashSet::with_capacity(0),
817            height: 3,
818        }));
819        let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
820        assert_eq!(ref_tree.value, TEST_1);
821        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
822        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
823        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
824        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
825        let res: bool = tree.as_mut().unwrap().rotate(Side::Left);
826        assert!(res);
827        let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
828        assert_eq!(ref_tree.value, TEST_3);
829        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_1);
830        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
831        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_4);
832        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
833    }
834
835    #[test]
836    fn test_rotate_left_right() {
837        let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
838            children: [
839                Some(Box::new(Node {
840                    children: [None, None],
841                    value: TEST_2,
842                    duplicates: HashSet::with_capacity(0),
843                    height: 1,
844                })),
845                Some(Box::new(Node {
846                    children: [Some(Box::new(Node {
847                        children: [None, None],
848                        value: TEST_4,
849                        duplicates: HashSet::with_capacity(0),
850                        height: 1,
851                    })), Some(Box::new(Node {
852                        children: [None, None],
853                        value: TEST_5,
854                        duplicates: HashSet::with_capacity(0),
855                        height: 1,
856                    }))],
857                    value: TEST_3,
858                    duplicates: HashSet::with_capacity(0),
859                    height: 2,
860                })),
861            ],
862            value: TEST_1,
863            duplicates: HashSet::with_capacity(0),
864            height: 3,
865        }));
866
867        let res: bool = tree.as_mut().unwrap().rotate(Side::Left);
868        assert!(res);
869        let res: bool = tree.as_mut().unwrap().rotate(Side::Right);
870        assert!(res);
871        let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
872        assert_eq!(ref_tree.value, TEST_1);
873        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
874        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
875        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
876        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
877    }
878
879    #[test]
880    fn test_rotate_right_left() {
881        let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
882            children: [
883                Some(Box::new(Node {
884                    children: [Some(Box::new(Node {
885                        children: [None, None],
886                        value: TEST_4,
887                        duplicates: HashSet::with_capacity(0),
888                        height: 1,
889                    })), Some(Box::new(Node {
890                        children: [None, None],
891                        value: TEST_5,
892                        duplicates: HashSet::with_capacity(0),
893                        height: 1,
894                    }))],
895                    value: TEST_2,
896                    duplicates: HashSet::with_capacity(0),
897                    height: 2,
898                })),
899                Some(Box::new(Node {
900                    children: [None, None],
901                    value: TEST_3,
902                    duplicates: HashSet::with_capacity(0),
903                    height: 1,
904                })),
905            ],
906            value: TEST_1,
907            duplicates: HashSet::with_capacity(0),
908            height: 3,
909        }));
910        let res: bool = tree.as_mut().unwrap().rotate(Side::Right);
911        assert!(res);
912        let res: bool = tree.as_mut().unwrap().rotate(Side::Left);
913        assert!(res);
914        let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
915        assert_eq!(ref_tree.value, TEST_1);
916        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().value, TEST_2);
917        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Left as usize].as_ref().unwrap().value, TEST_4);
918        assert_eq!(ref_tree.children[Side::Left as usize].as_ref().unwrap().children[Side::Right as usize].as_ref().unwrap().value, TEST_5);
919        assert_eq!(ref_tree.children[Side::Right as usize].as_ref().unwrap().value, TEST_3);
920    }
921
922    #[test]
923    fn test_rebalance() {
924        let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
925            children: [
926                Some(Box::new(Node {
927                    children: [Some(Box::new(Node {
928                        children: [None, None],
929                        value: TEST_3,
930                        duplicates: HashSet::with_capacity(0),
931                        height: 1,
932                    })), None],
933                    value: TEST_2,
934                    duplicates: HashSet::with_capacity(0),
935                    height: 2,
936                })),
937                None,
938            ],
939            value: TEST_1,
940            duplicates: HashSet::with_capacity(0),
941            height: 3,
942        }));
943        let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
944        assert!(ref_tree.is_some());
945        assert_eq!(ref_tree.unwrap().sanity_check(), true);
946        assert_eq!(ref_tree.unwrap().is_balanced(), false);
947        assert_eq!(ref_tree.unwrap().depth(), ref_tree.unwrap().height);
948        let res: bool = tree.as_mut().unwrap().rebalance();
949        assert!(res);
950        let ref_tree: &Box<Node<u64>> = tree.as_ref().unwrap();
951        assert_eq!(ref_tree.sanity_check(), true);
952        assert_eq!(ref_tree.is_balanced(), true);
953        assert_eq!(ref_tree.depth(), ref_tree.height);
954    }
955
956    #[test]
957    fn test_rebalance_twice() {
958        let mut tree: Option<Box<Node<u64>>> = Some(Box::new(Node {
959            children: [
960                Some(Box::new(Node {
961                    children: [Some(Box::new(Node {
962                        children: [None, None],
963                        value: TEST_3,
964                        duplicates: HashSet::with_capacity(0),
965                        height: 1,
966                    })), None],
967                    value: TEST_2,
968                    duplicates: HashSet::with_capacity(0),
969                    height: 2,
970                })),
971                None,
972            ],
973            value: TEST_1,
974            duplicates: HashSet::with_capacity(0),
975            height: 3,
976        }));
977        let res: bool = tree.as_mut().unwrap().rebalance();
978        assert!(res);
979        let res: bool = tree.as_mut().unwrap().rebalance();
980        assert!(!res);
981    }
982
983    #[test]
984    fn test_create_tree() {
985        let tree: Tree<u64> = Node::create_tree(&TEST_1);
986        let ref_tree: Option<&Box<Node<u64>>> = tree.as_ref();
987        assert!(ref_tree.is_some());
988        assert_eq!(ref_tree.unwrap().value, TEST_1);
989        assert_eq!(ref_tree.unwrap().height, 1);
990        assert!(ref_tree.unwrap().children[Side::Left as usize].is_none());
991        assert!(ref_tree.unwrap().children[Side::Right as usize].is_none());
992    }
993
994    #[test]
995    fn test_create_node() {
996        let node: Node<u64> = Node::create_node(&TEST_1);
997        assert_eq!(node.value, TEST_1);
998        assert_eq!(node.height, 1);
999        assert!(node.children[Side::Left as usize].is_none());
1000        assert!(node.children[Side::Right as usize].is_none());
1001    }
1002
1003    #[test]
1004    fn test_insert() {
1005        let mut node: Node<u64> = Node::create_node(&1);
1006        let res: bool = node.insert(2);
1007        assert!(res);
1008        let res: bool = node.insert(3);
1009        assert!(res);
1010        let res: bool = node.insert(4);
1011        assert!(res);
1012        let res: bool = node.insert(5);
1013        assert!(res);
1014        let res: bool = node.insert(6);
1015        assert!(res);
1016        let res: bool = node.insert(7);
1017        assert!(res);
1018        let res: bool = node.insert(8);
1019        assert!(res);
1020        assert_eq!(node.height, 4)
1021    }
1022
1023    #[test]
1024    fn test_width_depth_count() {
1025        let mut node: Node<u64> = Node::create_node(&1);
1026        assert_eq!(node.count(), 1);
1027        assert_eq!(node.depth(), 1);
1028        assert_eq!(node.width(), 1);
1029        let res: bool = node.insert(2);
1030        assert!(res);
1031        assert_eq!(node.count(), 2);
1032        assert_eq!(node.depth(), 2);
1033        assert_eq!(node.width(), 2);
1034        let res: bool = node.insert(3);
1035        assert!(res);
1036        assert_eq!(node.count(), 3);
1037        assert_eq!(node.depth(), 2);
1038        assert_eq!(node.width(), 2);
1039        let res: bool = node.insert(4);
1040        assert!(res);
1041        assert_eq!(node.count(), 4);
1042        assert_eq!(node.depth(), 3);
1043        assert_eq!(node.width(), 3);
1044        let res: bool = node.insert(5);
1045        assert!(res);
1046        assert_eq!(node.count(), 5);
1047        assert_eq!(node.depth(), 3);
1048        assert_eq!(node.width(), 3);
1049        let res: bool = node.insert(6);
1050        assert!(res);
1051        assert_eq!(node.count(), 6);
1052        assert_eq!(node.depth(), 3);
1053        assert_eq!(node.width(), 4);
1054        let res: bool = node.insert(7);
1055        assert!(res);
1056        assert_eq!(node.count(), 7);
1057        assert_eq!(node.depth(), 3);
1058        assert_eq!(node.width(), 4);
1059        let res: bool = node.insert(8);
1060        assert!(res);
1061        assert_eq!(node.count(), 8);
1062        assert_eq!(node.depth(), 4);
1063        assert_eq!(node.width(), 5);
1064        let res: bool = node.insert(9);
1065        assert!(res);
1066        assert_eq!(node.count(), 9);
1067        assert_eq!(node.depth(), 4);
1068        assert_eq!(node.width(), 5);
1069        let res: bool = node.insert(10);
1070        assert!(res);
1071        assert_eq!(node.count(), 10);
1072        assert_eq!(node.depth(), 4);
1073        assert_eq!(node.width(), 6);
1074        let res: bool = node.insert(11);
1075        assert!(res);
1076        assert_eq!(node.count(), 11);
1077        assert_eq!(node.depth(), 4);
1078        assert_eq!(node.width(), 6);
1079        let res: bool = node.insert(12);
1080        assert!(res);
1081        assert_eq!(node.count(), 12);
1082        assert_eq!(node.depth(), 4);
1083        assert_eq!(node.width(), 7);
1084        let res: bool = node.insert(13);
1085        assert!(res);
1086        assert_eq!(node.count(), 13);
1087        assert_eq!(node.depth(), 4);
1088        assert_eq!(node.width(), 7);
1089        let res: bool = node.insert(14);
1090        assert!(res);
1091        assert_eq!(node.count(), 14);
1092        assert_eq!(node.depth(), 4);
1093        assert_eq!(node.width(), 8);
1094        let res: bool = node.insert(15);
1095        assert!(res);
1096        assert_eq!(node.count(), 15);
1097        assert_eq!(node.depth(), 4);
1098        assert_eq!(node.width(), 8);
1099        let res: bool = node.insert(16);
1100        assert!(res);
1101        assert_eq!(node.count(), 16);
1102        assert_eq!(node.depth(), 5);
1103        assert_eq!(node.width(), 9);
1104    }
1105
1106    #[test]
1107    fn test_delete() {
1108        let mut tree: Tree<u64> = Node::create_tree(&1);
1109        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1110        let res: bool = node.insert(2);
1111        assert!(res);
1112        let res: bool = node.insert(3);
1113        assert!(res);
1114        let res: bool = node.insert(4);
1115        assert!(res);
1116        let res: bool = node.insert(5);
1117        assert!(res);
1118        let res: bool = node.insert(6);
1119        assert!(res);
1120        let res: bool = node.insert(7);
1121        assert!(res);
1122        let res: bool = node.insert(8);
1123        assert!(res);
1124        assert_eq!(node.height, 4);
1125        Node::delete(&mut tree);
1126    }
1127
1128    #[test]
1129    fn test_min_max() {
1130        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1131        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1132        let res: bool = node.insert(TEST_2);
1133        assert!(res);
1134        let res: bool = node.insert(TEST_3);
1135        assert!(res);
1136        let res: bool = node.insert(TEST_4);
1137        assert!(res);
1138        let res: bool = node.insert(TEST_4);
1139        assert!(res);
1140        assert_eq!(node.max(), &TEST_2);
1141        assert_eq!(node.min(), &TEST_1);
1142    }
1143
1144    #[test]
1145    fn test_dump() {
1146        #[derive(Clone, Ord, PartialOrd, Eq, PartialEq, Debug, Hash)]
1147        struct Position {
1148            x: i32,
1149        }
1150        impl fmt::Display for Position {
1151            fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1152                write!(f, "\"{}\"", self.x)
1153            }
1154        }
1155        let mut tree: Tree<Position> = Node::create_tree(&Position {
1156            x: 10
1157        });
1158        let node: &mut Box<Node<Position>> = tree.as_mut().unwrap();
1159
1160        assert_eq!(node.dump(false), "[\"10\",null,null]");
1161        let res: bool = node.insert(Position {
1162            x: 20
1163        });
1164        assert!(res);
1165        let res: bool = node.insert(Position {
1166            x: 30
1167        });
1168        assert!(res);
1169        let res: bool = node.insert(Position {
1170            x: 50
1171        });
1172        assert!(res);
1173        let res: bool = node.insert(Position {
1174            x: 40
1175        });
1176        assert!(res);
1177
1178        assert_eq!(node.dump(false), "[\"20\",[\"10\",null,null],[\"40\",[\"30\",null,null],[\"50\",null,null]]]");
1179        assert_eq!(node.dump(true), r#"[
1180   "20",
1181   [
1182      "10",
1183      null,
1184      null
1185   ],
1186   [
1187      "40",
1188      [
1189         "30",
1190         null,
1191         null
1192      ],
1193      [
1194         "50",
1195         null,
1196         null
1197      ]
1198   ]
1199]"#)
1200    }
1201
1202    #[test]
1203    fn test_remove_min() {
1204        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1205
1206        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1207        let res: bool = node.insert(TEST_2);
1208        assert!(res);
1209        let res: bool = node.insert(TEST_3);
1210        assert!(res);
1211        let res: bool = node.insert(TEST_4);
1212        assert!(res);
1213        assert_eq!(tree.as_ref().unwrap().height, 3);
1214        assert!(tree.as_ref().unwrap().is_balanced());
1215        let res: u64 = Node::remove_min(&mut tree);
1216        assert_eq!(res, TEST_1);
1217        assert_eq!(tree.as_ref().unwrap().height, 2);
1218        assert!(tree.as_ref().unwrap().is_balanced());
1219    }
1220
1221    #[test]
1222    fn test_remove() {
1223        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1224
1225        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1226        let res: bool = node.insert(TEST_2);
1227        assert!(res);
1228        let res: bool = node.insert(TEST_3);
1229        assert!(res);
1230        let res: bool = node.insert(TEST_4);
1231        assert!(res);
1232        assert_eq!(tree.as_ref().unwrap().height, 3);
1233        assert!(tree.as_ref().unwrap().is_balanced());
1234        let res: Option<u64> = Node::remove(&mut tree, &TEST_4);
1235        assert!(res.is_some());
1236        assert_eq!(res.unwrap(), TEST_4);
1237        assert_eq!(tree.as_ref().unwrap().height, 2);
1238        assert!(tree.as_ref().unwrap().is_balanced());
1239    }
1240
1241    #[test]
1242    fn test_remove_complex() {
1243        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1244
1245        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1246        let res: bool = node.insert(TEST_2);
1247        assert!(res);
1248        let res: bool = node.insert(TEST_3);
1249        assert!(res);
1250        let res: bool = node.insert(TEST_4);
1251        assert!(res);
1252        assert_eq!(tree.as_ref().unwrap().height, 3);
1253        assert!(tree.as_ref().unwrap().is_balanced());
1254        let res: Option<u64> = Node::remove(&mut tree, &TEST_4);
1255        assert!(res.is_some());
1256        assert_eq!(res.unwrap(), TEST_4);
1257        assert_eq!(tree.as_ref().unwrap().height, 2);
1258        assert!(tree.as_ref().unwrap().is_balanced());
1259
1260        let res: Option<u64> = Node::remove(&mut tree, &TEST_4);
1261        assert!(res.is_none());
1262
1263        let res: Option<u64> = Node::remove(&mut tree, &TEST_2);
1264        assert!(res.is_some());
1265        assert_eq!(res.unwrap(), TEST_2);
1266
1267        let res: Option<u64> = Node::remove(&mut tree, &TEST_1);
1268        assert!(res.is_some());
1269        assert_eq!(res.unwrap(), TEST_1);
1270
1271        let res: Option<u64> = Node::remove(&mut tree, &TEST_3);
1272        assert!(res.is_some());
1273        assert_eq!(res.unwrap(), TEST_3);
1274
1275        assert!(tree.as_ref() == None)
1276    }
1277
1278
1279    #[test]
1280    fn test_get() {
1281        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1282        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1283        let res: bool = node.insert(TEST_2);
1284        assert!(res);
1285        let res: bool = node.insert(TEST_3);
1286        assert!(res);
1287        let res: bool = node.insert(TEST_4);
1288        assert!(res);
1289        let tree: &Tree<u64> = Node::get(&tree, &TEST_2);
1290        assert!(tree.is_some());
1291        assert_eq!(tree.as_ref().unwrap().value, TEST_2);
1292        assert_eq!(tree.as_ref().unwrap().height, 2);
1293    }
1294
1295    #[test]
1296    fn test_get_missing() {
1297        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1298        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1299        let res: bool = node.insert(TEST_2);
1300        assert!(res);
1301        let res: bool = node.insert(TEST_3);
1302        assert!(res);
1303        let res: bool = node.insert(TEST_4);
1304        assert!(res);
1305        let tree: &Tree<u64> = Node::get(&tree, &TEST_5);
1306        assert!(tree.is_none());
1307    }
1308
1309    #[test]
1310    fn test_get_remove() {
1311        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1312        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1313        let res: bool = node.insert(TEST_2);
1314        assert!(res);
1315        let res: bool = node.insert(TEST_3);
1316        assert!(res);
1317        let tree2: &Tree<u64> = Node::get(&tree, &TEST_2);
1318        assert!(tree2.is_some());
1319        assert_eq!(tree2.as_ref().unwrap().value, TEST_2);
1320        let old: u64 = tree2.as_ref().unwrap().value.clone();
1321        let removed: Option<u64> = Node::remove(&mut tree, &TEST_2);
1322        assert!(removed.is_some());
1323        assert_eq!(removed.unwrap(), TEST_2);
1324        assert_eq!(old, TEST_2);
1325        let removed: Option<u64> = Node::remove(&mut tree, &TEST_2);
1326        assert!(removed.is_none());
1327        let tree2: &Tree<u64> = Node::get(&tree, &TEST_2);
1328        assert!(tree2.is_none());
1329    }
1330
1331    #[test]
1332    fn test_get_not_modifying() {
1333        let mut tree: Tree<u64> = Node::create_tree(&TEST_1);
1334        let node: &mut Box<Node<u64>> = tree.as_mut().unwrap();
1335        let res: bool = node.insert(TEST_2);
1336        assert!(res);
1337        let res: bool = node.insert(TEST_3);
1338        assert!(res);
1339        let tree_get: &Tree<u64> = Node::get(&tree, &TEST_3);
1340        assert!(tree_get.is_some());
1341        assert_eq!(tree_get.as_ref().unwrap().value, TEST_3);
1342        let mut tree2: Tree<u64> = tree_get.clone();
1343        let removed: Option<u64> = Node::remove(&mut tree, &TEST_2);
1344        assert!(removed.is_some());
1345        assert_eq!(removed.unwrap(), TEST_2);
1346        let removed2: Option<u64> = Node::remove(&mut tree2, &TEST_2);
1347        assert!(removed2.is_some());
1348        assert_eq!(removed2.unwrap(), TEST_2);
1349        assert_eq!(tree2, tree);
1350        let l_ptr: String = format!("{:018p}", tree.unwrap());
1351        let r_ptr: String = format!("{:018p}", tree2.unwrap());
1352        assert_ne!(l_ptr, r_ptr);
1353    }
1354}
1355
1356impl<'a, T: 'a + Clone + Ord + Eq + Debug + Display + Hash> Node<T> {
1357    fn insert(&mut self, new_value: T) -> bool {
1358        if new_value <= self.value && self.value <= new_value {
1359            if self.duplicates.contains(&new_value) {
1360                return false;
1361            }
1362            self.duplicates.insert(new_value);
1363            return true;
1364        }
1365        let mut res = true;
1366        let target_node: &mut Tree<T> = if new_value <= self.value { &mut self.children[Side::Left as usize] } else { &mut self.children[Side::Right as usize] };
1367        match target_node {
1368            &mut Some(ref mut subnode) => {
1369                res = subnode.insert(new_value);
1370            }
1371            &mut None => {
1372                let new_node = Node { children: [None, None], value: new_value, duplicates: HashSet::with_capacity(0), height: 1 };
1373                let boxed_node = Some(Box::new(new_node));
1374                *target_node = boxed_node;
1375            }
1376        }
1377        self.update_height();
1378        self.rebalance();
1379        res
1380    }
1381
1382    fn create_tree(value: &T) -> Tree<T> {
1383        Some(Box::new(Self::create_node(value)))
1384    }
1385
1386    fn create_node(value: &T) -> Self {
1387        Node {
1388            children: [None, None],
1389            value: value.clone(),
1390            duplicates: HashSet::with_capacity(0),
1391            height: 1,
1392        }
1393    }
1394
1395    fn delete(node: &mut Tree<T>) {
1396        if node.is_some() {
1397            Self::delete(node.as_mut().unwrap().children[Side::Left as usize].take().borrow_mut());
1398            Self::delete(node.as_mut().unwrap().children[Side::Right as usize].take().borrow_mut());
1399            node.as_mut().unwrap().duplicates.clear();
1400            node.take();
1401        }
1402    }
1403
1404    fn remove_min(node: &mut Tree<T>) -> T {
1405        if node.is_none() {
1406            panic!("You should not pass a NULL in that function");
1407        }
1408        if node.as_ref().unwrap().children[Side::Left as usize].is_none() {
1409            let right = node.as_mut().unwrap().children[Side::Right as usize].take();
1410            return replace(node, right).unwrap().value;
1411        }
1412        let value: T = Self::remove_min(&mut node.as_mut().unwrap().children[Side::Left as usize]);
1413        node.as_mut().unwrap().update_height();
1414        node.as_mut().unwrap().rebalance();
1415        return value;
1416    }
1417
1418    fn remove(node: &mut Tree<T>, value: &T) -> Option<T> {
1419        if node.is_some() {
1420            return if &node.as_ref().unwrap().value <= value && value <= &node.as_ref().unwrap().value {
1421                if &node.as_ref().unwrap().value == value && node.as_ref().unwrap().duplicates.is_empty() {
1422                    if node.as_ref().unwrap().children[Side::Right as usize].is_some() {
1423                        let value: T = Self::remove_min(&mut node.as_mut().unwrap().children[Side::Right as usize]);
1424                        let old: T = replace(&mut node.as_mut().unwrap().value, value);
1425                        node.as_mut().unwrap().rebalance();
1426                        Some(old)
1427                    } else {
1428                        let left: Tree<T> = node.as_mut().unwrap().children[Side::Left as usize].take();
1429                        let tree: Tree<T> = replace(node, left);
1430                        if node.is_some() {
1431                            node.as_mut().unwrap().rebalance();
1432                        }
1433                        tree.map_or(None, |node| Some(node.value))
1434                    }
1435                } else {
1436
1437                    if &node.as_ref().unwrap().value == value {
1438                        let new_value: Option<T> = node.as_ref().unwrap().duplicates.iter().next().cloned();
1439                        if new_value.is_none() {
1440                            return None;
1441                        }
1442                        let new_value: T = new_value.unwrap();
1443                        node.as_mut().unwrap().duplicates.remove(&new_value);
1444                        Some(replace(&mut node.as_mut().unwrap().value, new_value))
1445                    } else {
1446                        if node.as_mut().unwrap().duplicates.remove(&value){
1447                            Some(value.clone())
1448                        }else{
1449                            None
1450                        }
1451
1452                    }
1453                }
1454            } else {
1455                let target_node: &mut Tree<T> = if value <= &node.as_mut().unwrap().value { &mut node.as_mut().unwrap().children[Side::Left as usize] } else { &mut node.as_mut().unwrap().children[Side::Right as usize] };
1456                let res: Option<T> = Self::remove(target_node, value);
1457                node.as_mut().unwrap().rebalance();
1458                res
1459            };
1460        }
1461        return None;
1462    }
1463
1464    fn get(tree: &'a Tree<T>, value: &T) -> &'a Tree<T> {
1465        if tree.is_some() {
1466            if &tree.as_ref().unwrap().value <= value && &tree.as_ref().unwrap().value >= value {
1467                return tree;
1468            }
1469            return if value > &tree.as_ref().unwrap().value {
1470                Node::get(&tree.as_ref().unwrap().children[Side::Right as usize], value)
1471            } else {
1472                Node::get(&tree.as_ref().unwrap().children[Side::Left as usize], value)
1473            };
1474        }
1475        &None
1476    }
1477
1478    fn left_height(&self) -> usize {
1479        self.children[Side::Left as usize].as_ref().map_or(0, |left| left.height)
1480    }
1481
1482    fn right_height(&self) -> usize {
1483        self.children[Side::Right as usize].as_ref().map_or(0, |right| right.height)
1484    }
1485
1486    fn update_height(&mut self) {
1487        self.height = 1 + max(self.left_height(), self.right_height());
1488    }
1489
1490    fn height(&self) -> usize {
1491        self.height
1492    }
1493
1494    fn dump(&self, prettify: bool) -> String {
1495        self._dump(prettify,1)
1496    }
1497
1498    fn _dump(&self, prettify: bool, height: usize)->String {
1499        let mut pad = String::new();
1500        if prettify {
1501            pad = "   ".repeat(height);
1502        }
1503        let mut string_node: String = format!("[{}{},{}", (if prettify { "\n".to_string() } else { String::new() }) + &*pad, self.value, (if prettify { "\n".to_string() } else { String::new() }) + &*pad);
1504        if self.children[Side::Left as usize].is_some() {
1505            string_node += &*self.children[Side::Left as usize].as_ref().unwrap()._dump(prettify, height+1);
1506        } else {
1507            string_node += "null";
1508        }
1509
1510        if self.children[Side::Right as usize].is_some() {
1511            string_node += &*(",".to_owned()+&( if prettify { "\n".to_string() + &*pad } else { String::new() }));
1512            string_node += &*self.children[Side::Right as usize].as_ref().unwrap()._dump(prettify, height+1);
1513        } else {
1514            string_node+=",";
1515            string_node += &*((if prettify { "\n".to_string() } else { String::new() }) + &*pad + "null");
1516        }
1517        return string_node + &*(if prettify { "\n".to_string() + &*( "   ".repeat(max(height,1)-1)) } else { String::new() }) + "]";
1518    }
1519
1520    fn sanity_check(&self) -> bool {
1521        let mut is_correct: bool = self.height() == (1 + max(self.left_height(), self.right_height()));
1522        if self.children[Side::Left as usize].is_some() {
1523            is_correct &= self.children[Side::Left as usize].as_ref().unwrap().sanity_check();
1524        }
1525        if self.children[Side::Right as usize].is_some() {
1526            is_correct &= self.children[Side::Right as usize].as_ref().unwrap().sanity_check();
1527        }
1528        return is_correct;
1529    }
1530
1531    fn is_balanced(&self) -> bool {
1532        let mut lh: usize = 0;
1533        let mut lb: bool = true;
1534        if self.children[Side::Left as usize].is_some() {
1535            lh = self.children[Side::Left as usize].as_ref().unwrap().depth();
1536            lb = self.children[Side::Left as usize].as_ref().unwrap().is_balanced();
1537        }
1538        let mut rh: usize = 0;
1539        let mut rb: bool = true;
1540        if self.children[Side::Right as usize].is_some() {
1541            rh = self.children[Side::Right as usize].as_ref().unwrap().depth();
1542            rb = self.children[Side::Right as usize].as_ref().unwrap().is_balanced();
1543        }
1544        let diff: usize;
1545        if lh < rh {
1546            diff = rh - lh;
1547        } else {
1548            diff = lh - rh;
1549        }
1550        if diff <= 1 && lb && rb {
1551            return true;
1552        }
1553        return false;
1554    }
1555
1556    fn depth(&self) -> usize {
1557        let mut left: usize = 0;
1558        if self.children[Side::Left as usize].is_some() {
1559            left = self.children[Side::Left as usize].as_ref().unwrap().depth()
1560        }
1561        let mut right: usize = 0;
1562        if self.children[Side::Right as usize].is_some() {
1563            right = self.children[Side::Right as usize].as_ref().unwrap().depth()
1564        }
1565        return 1 + max(left, right);
1566    }
1567
1568    fn balance_factor(&self) -> i8 {
1569        let left_height = self.left_height();
1570        let right_height = self.right_height();
1571
1572        if left_height >= right_height {
1573            (left_height - right_height) as i8
1574        } else {
1575            -((right_height - left_height) as i8)
1576        }
1577    }
1578
1579    fn rotate(&mut self, side: Side) -> bool {
1580        if self.children[!side as usize].is_none() {
1581            return false;
1582        }
1583
1584        let right_node: &mut Box<Node<T>> = self.children[!side as usize].as_mut().unwrap();
1585        let right_left_tree = right_node.children[side as usize].take();
1586        let right_right_tree = right_node.children[!side as usize].take();
1587
1588        let mut new_left_tree = replace(&mut self.children[!side as usize], right_right_tree);
1589        swap(&mut self.value, &mut new_left_tree.as_mut().unwrap().value);
1590        let left_tree = self.children[side as usize].take();
1591
1592        let new_left_node = new_left_tree.as_mut().unwrap();
1593        new_left_node.children[!side as usize] = right_left_tree;
1594        new_left_node.children[side as usize] = left_tree;
1595        self.children[side as usize] = new_left_tree;
1596
1597        if let Some(node) = self.children[side as usize].as_mut() {
1598            node.update_height();
1599        }
1600
1601        self.update_height();
1602
1603        true
1604    }
1605
1606    fn rebalance(&mut self) -> bool {
1607        match self.balance_factor() {
1608            -2 => {
1609                let right_node = self.children[Side::Right as usize].as_mut().unwrap();
1610                if right_node.balance_factor() == 1 {
1611                    right_node.rotate(Side::Right);
1612                }
1613                self.rotate(Side::Left);
1614                true
1615            }
1616            2 => {
1617                let left_node = self.children[Side::Left as usize].as_mut().unwrap();
1618                if left_node.balance_factor() == -1 {
1619                    left_node.rotate(Side::Left);
1620                }
1621                self.rotate(Side::Right);
1622                true
1623            }
1624            _ => {
1625                self.update_height();
1626                false
1627            }
1628        }
1629    }
1630
1631    fn count(&self) -> usize {
1632        let left: usize;
1633        if self.children[Side::Left as usize].is_some() {
1634            left = self.children[Side::Left as usize].as_ref().unwrap().count()
1635        } else {
1636            left = 0;
1637        }
1638        let right: usize;
1639        if self.children[Side::Right as usize].is_some() {
1640            right = self.children[Side::Right as usize].as_ref().unwrap().count()
1641        } else {
1642            right = 0;
1643        }
1644        return 1 + self.duplicates.len() + left + right;
1645    }
1646
1647    fn max(&self) -> &T {
1648        if self.children[Side::Right as usize].is_some() {
1649            self.children[Side::Right as usize].as_ref().unwrap().max()
1650        } else {
1651            return &self.value;
1652        }
1653    }
1654
1655    fn min(&self) -> &T {
1656        if self.children[Side::Left as usize].is_some() {
1657            self.children[Side::Left as usize].as_ref().unwrap().min()
1658        } else {
1659            return &self.value;
1660        }
1661    }
1662
1663    fn width(&self) -> usize {
1664        let left: usize;
1665        if self.children[Side::Left as usize].is_some() {
1666            left = self.children[Side::Left as usize].as_ref().unwrap().width()
1667        } else {
1668            left = 1;
1669        }
1670        let right: usize;
1671        if self.children[Side::Right as usize].is_some() {
1672            right = self.children[Side::Right as usize].as_ref().unwrap().width()
1673        } else {
1674            right = 1;
1675        }
1676        if self.children[Side::Left as usize].is_none() && self.children[Side::Right as usize].is_none() {
1677            return 1;
1678        }
1679        return left + right;
1680    }
1681}
truetree/lib.rs

truetree/
lib.rs
