Add reverse traversal#30
Conversation
banks
left a comment
There was a problem hiding this comment.
Looking really good!
I suggest a fuzz test to exercise more of the edges and possibly found a bug but I could be wrong!
|
@banks I added fuzz tests for the I noticed that the recurse bug is only triggered when the seek starts from a non-root node, so I added two tests. There's a comment explaining why this is the case. I hope the explanation is clear enough, otherwise I can expand it. It's kind of an unusual case, but I guess not impossible, so worth testing. The two tests are very similar, but they are different enough that I couldn't find a nice way to re-use things, I hope that's OK. |
banks
left a comment
There was a problem hiding this comment.
Great job Luiz!
I think it could be possible to work the two fuzz tests into one with some random bool input that chooses wether or not to try to start at a non-root node. Then both paths would be exercised with high probability in any given run (check runs 1000 iterations by default IIRC).
That said, I don't think it's especially problematic to have them separate either so accepting for now.
This PR implements reverse tree traversal.
It introduces a new type of
IteratorcalledReverseIteratorthat can move through a tree in reverse order using thePrevious()andSeekReverseLowerBound()methods.It also adds a new
WalkBackwards()method toNodethat works the same way asWalk()but in reverse, going from the largest to the lowest values.