Example unit test for splay_tree.move
The codebase could benefit from more rigorous unit tests. This would allow developers to make changes while being confident that functionality is not negatively affected.
Currently, the tests in flow::splay_tree mainly test a tree with the keys 1, 2, 3, 4, and 5. The following is an example of a test that verifies functionality using a complex tree and many operations in a fashion that mimics a real world use case.
#[test]
fun test_comprehensive() {
// create a tree and insert all these elements. Assert they still within the tree
let tree = init_tree<u64>(true);
let random_arr: vector<u64> = vector<u64>[6369, 4106, 1341, 5981, 5581, 8316, 8344, 126, 6002, 573, 1182,
7056, 4177, 3867, 9516, 761, 9522, 8803, 5577, 7715, 7290, 2047,
1942, 9626, 7676, 315, 9822, 6599, 8426, 4801, 3425, 1986, 4122,
9046, 9534, 114, 3900, 8204, 233, 1781, 6195, 9595, 7236, 7533,
3513, 7298, 6417, 4793, 3497, 9225
];
let i: u64 = 0;
while (i < vector::length(&random_arr)) {
let element = *vector::borrow(&random_arr, i);
insert(&mut tree, element, element);
i = i + 1;
};
assert!(vector::length(&tree.nodes) == vector::length(&random_arr), 1);
assert!(vector::length(&tree.removed_nodes) == 0, 1);
...
// play with the tree
splay(&mut tree, 7676);
remove(&mut tree, 9225);
remove(&mut tree, 7056);
insert(&mut tree, 8686, 8686);
remove(&mut tree, 6599);
splay(&mut tree, 5577);
// we added removed 3 more, inserted 1, so add 2 to removal count and make sure that's the length of the removed_nodes
assert!(vector::length(&tree.removed_nodes) == removed_count + 2, 1);
...
// play with the tree
splay(&mut tree, 9822);
splay(&mut tree, 9822);
splay(&mut tree, 9822);
splay(&mut tree, 9522);
splay(&mut tree, 9522);
splay(&mut tree, 6417);
...
// add more elements
let more_random = vector<u64>[12349, 11751, 15113, 14205, 13975, 13886, 10210, 18627, 15555, 17889, 14963, 12379, 16604, 17760, 10214, 10101, 19780, 17323, 16171, 17640, 11920, 19467, 15552, 11295, 19482, 10276, 16163, 18347, 11243, 12461, 11846, 17803, 17348, 12824, 10925, 12236, 11365, 12851, 17954, 17872, 13713, 12466, 10616, 18954, 13373, 14535, 18781, 12816, 11690, 10060];
let i: u64 = 0;
while (i < vector::length(&more_random)) {
let element = *vector::borrow(&more_random, i);
insert(&mut tree, element, element);
i = i + 1;
};
...
// checking operations work as normal
splay(&mut tree, 11243);
splay(&mut tree, 10210);
splay(&mut tree, 12349);
}The full test has been provided to Laminar.