Commit Graph

39 Commits

Author SHA1 Message Date
Matej Focko 4e2e227f58
ci: add GitLab CI
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-24 16:24:58 +02:00
Matej Focko dc6905b5e2
fix(mypy): fix major issues with mypy
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-22 21:07:40 +02:00
Matej Focko e28f578fc2
fix(rotations): move rotations to the tree
Move rotations to the RankedTree, which allows us to factor out the
functionality regarding rotations when root of the tree changes.

Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-22 21:00:18 +02:00
Matej Focko 7b5bf0ec3a
fix(rbt): improve naming and add docstrings
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-22 00:38:48 +02:00
Matej Focko 2b02eac10e
fix(rbt): use explicit colours instead of constants
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-20 15:47:03 +02:00
Matej Focko d39e11713c
feat(rbt): finish delete
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-20 12:02:52 +02:00
Matej Focko 02ce49c86e
feat(rb): add mockup
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-20 11:50:56 +02:00
Matej Focko 3bba030d53
feat: handle root change in rotate function
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-20 11:50:48 +02:00
Matej Focko a8de124eeb
chore(flake): fix flake remarks
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-20 11:50:08 +02:00
Matej Focko 33f820f8de
chore: add readme
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-18 22:30:41 +02:00
Matej Focko 02a7d5da0e
chore: add license and agreement
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-18 13:40:44 +02:00
Matej Focko 9c3452f4b5
feat: factor out property based tests
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-18 13:39:54 +02:00
Matej Focko f74c582401
chore: add clean to makefile targets
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-16 00:26:49 +02:00
Matej Focko c3d757204c
chore: unify max_examples across tests
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-16 00:26:27 +02:00
Matej Focko d4d0b65f45
feat: implement inorder traversal of ranked tree
Fixes #4

Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-15 18:07:50 +02:00
Matej Focko 6fb09cd89b
chore(wavl): refactor
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-12 12:23:31 +02:00
Matej Focko 88d691225e
chore(avl): refactor
Fixes #2

Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-12 12:20:55 +02:00
Matej Focko 705d5cfa17
fix: do not allow duplicit keys
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-12 12:20:24 +02:00
Matej Focko 32ec9e9866
chore: remove debug statements
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 17:03:30 +02:00
Matej Focko 0882e6575d
fix(wavl): do not recursively fixup after delete
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:43:02 +02:00
Matej Focko 2433928d36
fix(wavl): propagate root rotation to the helper functions for delete
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:42:37 +02:00
Matej Focko 457ab180d0
feat: add example usage of comparator
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:42:06 +02:00
Matej Focko e50cca7a14
tests: generate AVL vs WAVL difference by contradiction
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:40:10 +02:00
Matej Focko f05aa87f4b
tests: extend AVL and change parameters of WAVL
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:39:30 +02:00
Matej Focko f67468b637
fix(ranked_tree): transplant by double-delete
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:39:07 +02:00
Matej Focko d8a746268b
fix(comparator): propagate similarity
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:38:44 +02:00
Matej Focko 6bde21f85c
fix(avl): be more explicit in `is_correct`
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:38:17 +02:00
Matej Focko 93ac86366b
chore: update makefile
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-05-07 15:38:01 +02:00
Matej Focko db35a07738
feat: implement comparator for trees
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-02-03 11:35:12 +01:00
Matej Focko a4c896edbf
refactor(tree): split dot generation
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-02-03 11:08:19 +01:00
Matej Focko 458ffdb3ff
fix(wavl): do not check for v if not needed
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-01-30 15:49:32 +01:00
Matej Focko f66dec1e03
chore: update tests and add avl tests
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-01-30 15:04:08 +01:00
Matej Focko 518ee5b970
ravl: add ravl tree
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-01-30 15:03:59 +01:00
Matej Focko 4a832e1de8
feat: add avl and split wavl
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-01-30 15:03:34 +01:00
Matej Focko f960a24eb6
chore: add makefile
• formatting
• linting
• type check
• test runner

Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-01-30 15:02:43 +01:00
Matej Focko bc981a8bb4
node: add type signatures
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-01-30 15:02:28 +01:00
Matej Focko cea0ac2ba2
chore: add gitignore
Signed-off-by: Matej Focko <mfocko@redhat.com>
2022-01-30 14:41:34 +01:00
Matej Focko 70261aed50
Add python implementation and tests
Signed-off-by: Matej Focko <me@mfocko.xyz>
2021-01-04 10:46:12 +01:00
Matej Focko 329e59ca15
Initial commit
Signed-off-by: Matej Focko <me@mfocko.xyz>
2021-01-04 10:45:40 +01:00