v / vlib / datatypes
Raw file | 138 loc (117 sloc) | 3.31 KB | Latest commit hash ef5be22f8
1module datatypes
2
3// Make an insert of one element and check if
4// the bst is able to fin it.
5fn test_insert_into_bst_one() {
6 mut bst := BSTree[int]{}
7 assert bst.insert(10) == true
8 assert bst.contains(10) == true
9 assert bst.contains(20) == false
10}
11
12// Make the insert of more element inside the BST
13// and check if the BST is able to find all the values
14fn test_insert_into_bst_two() {
15 mut bst := BSTree[int]{}
16 assert bst.insert(10)
17 assert bst.insert(20)
18 assert bst.insert(9)
19
20 assert bst.contains(9)
21 assert bst.contains(10)
22 assert bst.contains(20)
23 assert bst.contains(11) == false
24}
25
26// Test if the in_order_traversals list return the correct
27// result array
28fn test_in_order_bst_visit_one() {
29 mut bst := BSTree[int]{}
30 assert bst.insert(10)
31 assert bst.insert(20)
32 assert bst.insert(21)
33 assert bst.insert(1)
34
35 assert bst.in_order_traversal() == [1, 10, 20, 21]
36}
37
38// Test if the post_order_bst_visit return the correct
39// result array
40fn test_post_order_bst_visit_one() {
41 mut bst := BSTree[int]{}
42 assert bst.insert(10)
43 assert bst.insert(20)
44 assert bst.insert(21)
45 assert bst.insert(1)
46
47 assert bst.post_order_traversal() == [1, 21, 20, 10]
48}
49
50// Test if the pre_order_traversal return the correct result array
51fn test_pre_order_bst_visit_one() {
52 mut bst := BSTree[int]{}
53 assert bst.insert(10)
54 assert bst.insert(20)
55 assert bst.insert(21)
56 assert bst.insert(1)
57
58 assert bst.pre_order_traversal() == [10, 1, 20, 21]
59}
60
61// After many insert check if we are abe to get the correct
62// right and left value of the root.
63fn test_get_left_root() {
64 mut bst := BSTree[int]{}
65 assert bst.insert(10)
66 assert bst.insert(20)
67 assert bst.insert(21)
68 assert bst.insert(1)
69
70 left_val := bst.to_left(10) or { -1 }
71 assert left_val == 1
72
73 right_val := bst.to_right(10) or { -1 }
74 assert right_val == 20
75}
76
77// Check if BST panic if we call some operation on an empty BST.
78fn test_get_left_on_empty_bst() {
79 mut bst := BSTree[int]{}
80
81 left_val := bst.to_left(10) or { -1 }
82 assert left_val == -1
83
84 right_val := bst.to_right(10) or { -1 }
85 assert right_val == -1
86}
87
88// Check the remove operation if it is able to remove
89// all elements required, and mantains the BST propriety.
90fn test_remove_from_bst_one() {
91 mut bst := BSTree[int]{}
92 assert bst.insert(10)
93 assert bst.insert(20)
94 assert bst.insert(21)
95 assert bst.insert(1)
96 assert bst.in_order_traversal() == [1, 10, 20, 21]
97 assert bst.remove(21)
98
99 assert bst.in_order_traversal() == [1, 10, 20]
100}
101
102// Another test n the remove BST, this remove an intermidia node
103// that it is a triky operation.
104fn test_remove_from_bst_two() {
105 mut bst := BSTree[int]{}
106 assert bst.insert(10)
107 assert bst.insert(20)
108 assert bst.insert(21)
109 assert bst.insert(1)
110 assert bst.in_order_traversal() == [1, 10, 20, 21]
111 assert bst.remove(20)
112
113 assert bst.in_order_traversal() == [1, 10, 21]
114}
115
116// check if we are able to get the max from the BST.
117fn test_get_max_in_bst() {
118 mut bst := BSTree[int]{}
119 assert (bst.max() or { -1 }) == -1
120 assert bst.insert(10)
121 assert bst.insert(20)
122 assert bst.insert(21)
123 assert bst.insert(1)
124 max := bst.max() or { -1 }
125 assert max == 21
126}
127
128// check if we are able to get the min from the BST.
129fn test_get_min_in_bst() {
130 mut bst := BSTree[int]{}
131 assert (bst.min() or { -1 }) == -1
132 assert bst.insert(10)
133 assert bst.insert(20)
134 assert bst.insert(21)
135 assert bst.insert(1)
136 min := bst.min() or { -1 }
137 assert min == 1
138}