Add property tests for invariants

meooow25 commented 9 months ago

These invariants are based on my understanding of RRB-trees. There seem to be a few variations of RRB-trees from what I could find online, so correct me if any of these do not apply to this implementation. Also, let me know if I missed some invariant that could be tested.

The added tests detect that:

<| can create an Unbalanced with m+1 children
>< can create a root Unbalanced with 1 child
insertAt can create a root Unbalanced with 1 child
deleteAt can create a root Unbalanced with 1 child

Side note: I found that shrinking sometimes seems to be taking forever but I haven't attempted to address it in this PR.

Fixes #16

meooow25 commented 9 months ago

@konsumlamm what do you think? Are these bugs?

konsumlamm commented 9 months ago

Yes, I'm pretty sure, though I didn't have enough time to investigate them yet. The failures for insertAt and deleteAt are probably not separate bugs, since they use ><.

konsumlamm commented 9 months ago

Those issues should now be fixed. Could you rebase, so that the CI runs again?

meooow25 commented 9 months ago

Nice, thanks for fixing!

konsumlamm commented 9 months ago

Great work, thank you very much!

konsumlamm / rrb-vector

Add property tests for invariants #17