Fix tests of kd_tree

[wucke13]

openTAWS/kd_tree_sort/src/lib.rs

Line 125 in e9d1818

#[ignore]

This test is broken. When playing with the numbers, I was able to create a stack overflow. This should not be possible. Furthermore, I would advice to check the numbers - while it makes sense to have different test sizes for debug and release builds, I'm not sure that this should be a test at all. It is rather three things:

• A fuzzy test. For this, why don't we implement a stub for cargo fuzz instead? Then also one can run the test for arbitrary times without having to alter the test code.
• A performance regression test. For this, it might make sense to integrate either the cargo bench feature or criterion.rs
• A unit test checking the correctness of the tree generation (?) and lookup. In this case, this should be separated into multiple tests, testing each of the two properties isolated.

I'm not so comfortable having code this complicated without rigid validation. Hence I would also propose that we introduce tests which uses one of the other kd tree implementations of the rust universe as oracle to check our implementation.

[sevenautumns]

I'm not so comfortable having code this complicated without rigid validation. Hence I would also propose that we introduce tests which uses one of the other kd tree implementations of the rust universe

The KD Tree implementation is already tested against a primitive linear search.
Imo there is no need for testing it against more implementations

[wucke13]

I think the order of correctness guaranteed by having all queries beeing correct, or knowing that the tree is correctly implemented is not equal. The former could have bugs in the creation of the tree which are solved by other bugs in the query. The latter checks both individually. However, I agree, this is low priority ATM. I think we can look into this again after #22 is solved.

[sevenautumns]

The Tree we implemented here results in a non-standard representation of the tree as a specially balanced heap. There will be no present kd tree implementation resulting in the same tree

[wucke13]

That's a good reason not to check against other implementations. However, can we have a test case which (under heavy use of heap memory) traverses the tree to check its validity as unit test?