Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add property tests for btree functions #8

Open
luc-tielen opened this issue Dec 24, 2021 · 1 comment
Open

Add property tests for btree functions #8

luc-tielen opened this issue Dec 24, 2021 · 1 comment
Milestone

Comments

@luc-tielen
Copy link
Owner

  • Create new Spec module for testing btree functionality in LLVM.
  • Specialize LLVM to a specific config: e.g. index on columns 1 and 3, ...
  • Import the specialized, foreign LLVM instructions into the Spec module (only test at the level of what is exported via Functions datatype.
  • Write property based tests for these functions (using hedgehog?).
@luc-tielen luc-tielen added this to the 0.1.0 milestone Dec 24, 2021
@luc-tielen
Copy link
Owner Author

After some thinking, I found the following properties:

  • purge: afterwards, empty = true / size = 0
  • swap A B
    • swap 1x: B = A, A = B
    • swap 2x: A = A, B = B (identity)
  • insert:
    • if empty tree: before empty = true, after empty = false
    • elem already in tree: no change
    • elem not yet in tree: size + 1
    • insert A + insert B = insert B + insert A
  • insertRange: same as insert, size + max N (depends on how many elements already in tree)
  • isEmpty: true for empty trees, false otherwise
  • contains: true if elem is in tree, false otherwise

Other functions should be unit-tested / tested indirectly via "integration" tests:

  • init(Empty)
  • destroy
  • begin
  • end
  • lowerBound
  • upperBound

@luc-tielen luc-tielen modified the milestones: 0.1.0, 0.2.0 Apr 30, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant