bst_hashmap/
lib.rs

1mod bst;
2pub mod bst_hashmap;
3
4// let mut map = BstHashmap::<i32, String>::default();
5// 
6// map.insert(5, "five".to_string());
7// map.insert(3, "three".to_string());
8// map.insert(7, "seven".to_string());
9// map.insert(6, "six".to_string());
10// map.insert(8, "eight".to_string());
11// 
12// if let Some(value) = map.search(7) {
13//     println!("Found key 7 with value: {}", value);
14// } else {
15//     println!("Key 7 not found");
16// }
17// 
18// if let Some((min_key, min_val)) = map.min(5) {
19//     println!("Min in subtree of 5: key = {}, value = {}", min_key, min_val);
20// }
21// 
22// if let Some((max_key, max_val)) = map.max(5) {
23//     println!("Max in subtree of 5: key = {}, value = {}", max_key, max_val);
24// }
25// 
26// map.remove(7);
27// println!("Removed key 7");
28// 
29// if map.search(7).is_none() {
30//     println!("Key 7 no longer found after removal");
31// }
32
33#[cfg(test)]
34mod tests {
35    use super::bst::Bst;
36    use super::bst_hashmap::BstHashmap;
37
38    #[test]
39    fn test_insert_and_search() {
40        let mut map = BstHashmap::default();
41        map.insert(5, "five");
42        map.insert(3, "three");
43        map.insert(7, "seven");
44
45        assert_eq!(map.search(5), Some("five"));
46        assert_eq!(map.search(3), Some("three"));
47        assert_eq!(map.search(7), Some("seven"));
48        assert_eq!(map.search(10), None);
49    }
50
51    #[test]
52    fn test_min_max() {
53        let mut map = BstHashmap::default();
54        map.insert(10, "ten");
55        map.insert(5, "five");
56        map.insert(15, "fifteen");
57        map.insert(3, "three");
58        map.insert(7, "seven");
59
60        assert_eq!(map.min(10), Some((3, "three")));
61        assert_eq!(map.max(10), Some((15, "fifteen")));
62        assert_eq!(map.min(5), Some((3, "three")));
63        assert_eq!(map.max(5), Some((7, "seven")));
64    }
65
66    #[test]
67    fn test_remove() {
68        let mut map = BstHashmap::default();
69        map.insert(5, "five");
70        map.insert(3, "three");
71        map.insert(7, "seven");
72
73        map.remove(3);
74        assert_eq!(map.search(3), None);
75
76        map.remove(5);
77        assert_eq!(map.search(5), None);
78
79        assert_eq!(map.search(7), Some("seven"));
80    }
81
82    #[test]
83    fn basic_bst_operations() {
84        let mut bst = Bst::default();
85
86        bst.insert(3, "val3");
87        bst.insert(4, "val4");
88        bst.insert(6, "val6");
89        bst.insert(7, "val7");
90        bst.insert(2, "val2");
91
92        let node = bst.search(6);
93        assert!(node.is_some(), "Node with key 6 should be found");
94        let node_ref = node.unwrap();
95        assert_eq!(node_ref.borrow().key, 6);
96
97        let min_node = bst.min(Some(node_ref.clone()));
98        assert!(min_node.is_some(), "Min should exist in subtree");
99        assert_eq!(min_node.unwrap().borrow().key, 6);
100
101        let max_node = bst.max(Some(node_ref));
102        assert!(max_node.is_some(), "Max should exist in subtree");
103        assert_eq!(max_node.unwrap().borrow().key, 7);
104
105        assert_eq!(bst.root.as_ref().unwrap().borrow().key, 3);
106    }
107
108    #[test]
109    fn remove_leaf_node() {
110        let mut bst = Bst::default();
111        bst.insert(5, "val5");
112        bst.insert(3, "val3");
113        bst.insert(7, "val7");
114
115        let node = bst.search(3);
116        assert!(node.is_some());
117        bst.remove(node);
118
119        assert!(bst.search(3).is_none());
120
121        assert_eq!(bst.root.as_ref().unwrap().borrow().key, 5);
122        assert!(bst.search(7).is_some());
123    }
124
125    #[test]
126    fn remove_node_with_one_child() {
127        let mut bst = Bst::default();
128        bst.insert(5, "val5");
129        bst.insert(3, "val3");
130        bst.insert(4, "val4"); // filho direito de 3
131
132        let node = bst.search(3);
133        assert!(node.is_some());
134        bst.remove(node);
135
136        assert!(bst.search(3).is_none());
137        assert!(bst.search(4).is_some());
138        assert_eq!(bst.root.as_ref().unwrap().borrow().key, 5);
139    }
140
141    #[test]
142    fn remove_node_with_two_children() {
143        let mut bst = Bst::default();
144        bst.insert(5, "val5");
145        bst.insert(3, "val3");
146        bst.insert(7, "val7");
147        bst.insert(6, "val6");
148        bst.insert(8, "val8");
149
150        let node = bst.search(7);
151        assert!(node.is_some());
152        bst.remove(node);
153
154        assert!(bst.search(7).is_none());
155        assert!(bst.search(6).is_some());
156        assert!(bst.search(8).is_some());
157    }
158
159    #[test]
160    fn remove_root_node() {
161        let mut bst = Bst::default();
162        bst.insert(5, "val5");
163        bst.insert(3, "val3");
164        bst.insert(7, "val7");
165
166        let root_node = bst.root.clone();
167        bst.remove(root_node);
168
169        assert!(bst.root.is_some());
170        assert_ne!(bst.root.as_ref().unwrap().borrow().key, 5);
171    }
172}
bst_hashmap/lib.rs

bst_hashmap/
lib.rs
