Missing tests for inorder, postorder, and preorder.
Beakerboy opened this issue · 6 comments
The test script appears to just call these methods without making any assertions. I guess it ensures the coverage is at 100% but does nothing to prove these methods do what they are supposed to do.
on that topic…what are they supposed to do? Is it just a way to dump the data from the tree to stdout the aid troubleshooting? There has to be a better way like an xml, json, or yml export.
I need a red/black tree library for a project and this seems to be the only thing in python. If you have any changes you would like to see, let me know. My fork has some updates. I’m probably going to add an export function as well as a RbtFactory class to create and validate exported trees. It looks like this library can create a tree from scratch, but cannot load a specified structure, correct?
I’m going to populate the issues queue on my fork with the issues and features I plan on adding. I also have the GitHub discussions feature enabled for my repository. Feel free to hop over there to add your opinion on the future path for this code.
the README states that a hard to find bug is fixed in this library. Which test is the one that demonstrates this bug is fixed, such that if the code were changed back to the original, the test would fail?
Those functions traverse the tree according to the corresponding traversal orderings (i.e. in-order, post-order, and pre-order) and print the nodes in that sequence as they go. The goal of the tests is to make sure the code runs without error (I think I briefly broke it at one point during my debugging), but I agree it would be better if they actually properly checked stdout for the correct contents.
Thanks for your contributions! Yes, you're correct that this cannot currently load a specified structure.
Good question about the bug - I believe both test_long and test_complex_delete demonstrate that it is fixed (for the record, the fix is the change I made to rbtree.py in 90894bd; such a small problem, but such a pain to find.)
Thanks, after asking the question I looked it up and learned what the terms mean. My plan is to change these from printing functions to iterators, so a user can traverse the tree and do whatever they want with the nodes returned in the specified order.
When I add the “create a tree” code, we should be able to test this buggy scenario in a more compact manner correct? I’d love it if you could think of other weird edge conditions worth testing.
Great! That sounds like a definite improvement.
Possibly. I think the goal of test_complex_delete was to test it as compactly as possible. Are you saying we could basically load in a prebuilt-tree that was primed to have the error occur if the logic is wrong?
The goal of test_long was just to do a ton of stuff with the tree so that hopefully if there were any other bugs they would be caught. The fact that nothing else turned up makes me pretty confident there aren't any more sneaky bugs. However, if there were any I'm sure they would be in the tree re-balancing logic (like this one was).
Ah, if test_complex_delete does it in a compact test, then that definitely needs to stay, unless loading a tree can do it faster.
some edge conditions I want to make sure are tested are things like deleting from an empty tree, searching an empty tree, indexing on an empty tree, traversing an empty tree. Doing these on a tree with exclusively duplicates. Causing rotations on branches of duplicates.
In general, if all execution paths are followed somewhere, and the comparator edges are intentionally triggered, it should be good, right? I often forget about intentionally thinking through ternary statements and complex boolean statements within ‘if’ statements, the things that coverage reports do not always highlight.
Fixed in #4 ! Thanks for all the contributions!