v / vlib / datatypes / bstree_test.v
166 lines · 139 sloc · 3.95 KB · c847d111dea18c42e209fed198fb2d0ff3d78c1a
Raw 


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 if accessing the left node of the leftmost non root node panics


89fn test_to_left_on_leftmost_nonroot() {


90    mut bst := BSTree[int]{}


91


92    assert bst.insert(20)


93    assert bst.insert(10)


94    assert bst.insert(30)


95


96    min := bst.min() or { -1 }


97    assert min == 10


98    left_val := bst.to_left(min) or { -1 }


99    assert left_val == -1


100}


101


102// Check if accessing the right node of the rightmost non root node panics


103fn test_to_right_on_rightmost_nonroot() {


104    mut bst := BSTree[int]{}


105


106    assert bst.insert(20)


107    assert bst.insert(10)


108    assert bst.insert(30)


109


110    max := bst.max() or { -1 }


111    assert max == 30


112    right_val := bst.to_right(max) or { -1 }


113    assert right_val == -1


114}


115


116// Check the remove operation if it is able to remove


117// all elements required, and maintains the BST propriety.


118fn test_remove_from_bst_one() {


119    mut bst := BSTree[int]{}


120    assert bst.insert(10)


121    assert bst.insert(20)


122    assert bst.insert(21)


123    assert bst.insert(1)


124    assert bst.in_order_traversal() == [1, 10, 20, 21]


125    assert bst.remove(21)


126


127    assert bst.in_order_traversal() == [1, 10, 20]


128}


129


130// Another test n the remove BST, this remove an intermediate node


131// that it is a tricky operation.


132fn test_remove_from_bst_two() {


133    mut bst := BSTree[int]{}


134    assert bst.insert(10)


135    assert bst.insert(20)


136    assert bst.insert(21)


137    assert bst.insert(1)


138    assert bst.in_order_traversal() == [1, 10, 20, 21]


139    assert bst.remove(20)


140


141    assert bst.in_order_traversal() == [1, 10, 21]


142}


143


144// check if we are able to get the max from the BST.


145fn test_get_max_in_bst() {


146    mut bst := BSTree[int]{}


147    assert (bst.max() or { -1 }) == -1


148    assert bst.insert(10)


149    assert bst.insert(20)


150    assert bst.insert(21)


151    assert bst.insert(1)


152    max := bst.max() or { -1 }


153    assert max == 21


154}


155


156// check if we are able to get the min from the BST.


157fn test_get_min_in_bst() {


158    mut bst := BSTree[int]{}


159    assert (bst.min() or { -1 }) == -1


160    assert bst.insert(10)


161    assert bst.insert(20)


162    assert bst.insert(21)


163    assert bst.insert(1)


164    min := bst.min() or { -1 }


165    assert min == 1


166}


167