commit 2b8ee36374b5189c645c0994f41cf63721794c90
parent b1e6f7774d9a74ab67981c598dc0b1cf69c05517
Author: Remy Noulin <loader2x@gmail.com>
Date: Sat, 29 Dec 2018 18:55:24 +0100
test ok and no memory leak
.gitignore | 11 +
main.c | 41 +++
test.c | 632 +++++++++++++++++++++++++++++++++++++++++++++
wavlTree.c | 594 ++++++++++++++++++++++++++++++++++++++++++
wavlTree.h | 81 ++++++
wavlTreeNamespaceCleanup.h | 19 ++
6 files changed, 1378 insertions(+)
Diffstat:
| M | .gitignore | | | 11 | +++++++++++ |
| A | main.c | | | 41 | +++++++++++++++++++++++++++++++++++++++++ |
| A | test.c | | | 632 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | wavlTree.c | | | 594 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | wavlTree.h | | | 81 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | wavlTreeNamespaceCleanup.h | | | 19 | +++++++++++++++++++ |
6 files changed, 1378 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -1,3 +1,14 @@
+# Vim
+*.sw*
+
+# Debug
+.gdb_history
+
+# Coverage
+*.gcov
+*.gcda
+*.gcno
+
# Prerequisites
*.d
diff --git a/main.c b/main.c
@@ -0,0 +1,41 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+/* Libsheepy documentation: http://spartatek.se/libsheepy/ */
+#include "libsheepyObject.h"
+#include "wavlTree.h"
+#include "wavlTreeNamespaceCleanup.h"
+
+int argc; char **argv;
+
+/* enable/disable logging */
+/* #undef pLog */
+/* #define pLog(...) */
+
+int main(int ARGC, char** ARGV) {
+
+ argc = ARGC; argv = ARGV;
+
+ initLibsheepy(ARGV[0]);
+ setLogMode(LOG_FUNC);
+
+ wavlTreet tree;
+
+ wavlTreeinit(&tree);
+
+ tree.put(&tree, 0, 0);
+ tree.put(&tree, 1, 1);
+ tree.put(&tree, 10, 10);
+ tree.put(&tree, 5, 5);
+
+ var n = tree.get(&tree, 10);
+ logVarG(n);
+
+ tree.inOrderTraversal(tree.root);
+
+ logVarG(tree.remove(&tree, 10));
+
+ tree.clear(&tree);
+
+}
+// vim: set expandtab ts=2 sw=2:
diff --git a/test.c b/test.c
@@ -0,0 +1,632 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+/* Libsheepy documentation: http://spartatek.se/libsheepy/ */
+#include "libsheepyObject.h"
+#include "wavlTree.h"
+#include "wavlTreeNamespaceCleanup.h"
+
+int argc; char **argv;
+
+/* enable/disable logging */
+/* #undef pLog */
+/* #define pLog(...) */
+
+wavlTreet x;
+
+#define assertEquals(A,B) do{\
+ var a = A;\
+ var b = B;\
+ if (a != b) {\
+ AT;\
+ logI(BLD RED"assert failed:"RST" %d != %d\n", a, b);\
+ }\
+ }while(0)
+
+#define assertNull(p) do{\
+ if (p) {\
+ AT;\
+ logE(BLD RED"assert failed:"RST stringifyExpr(p) " not NULL\n");\
+ }\
+ }while(0)
+
+#define assertTrue(c) do{\
+ if (!(c)) {\
+ AT;\
+ logE(BLD RED"assert failed: "RST stringifyExpr(c) " expected true\n");\
+ }\
+ }while(0)
+
+void testTreeHeight() {
+ x.clear(&x);
+ x.put(&x,2, 2);
+ assertEquals(0, x.treeHeight(&x));
+ x.put(&x,3, 3);
+ assertEquals(1, x.treeHeight(&x));
+ x.put(&x,1, 1);
+ x.put(&x,0, 0);
+ assertEquals(2, x.treeHeight(&x));
+}
+
+void testInsertDoNothing() {
+ x.clear(&x);
+ x.put(&x,2, 2);
+ x.put(&x,3, 3);
+ assertEquals(0, x.rotations);
+ assertEquals(2, (int)x.root->value);
+ assertEquals(1, x.root->rank);
+
+ x.put(&x,1, 1);
+ assertEquals(2, (int)x.root->value);
+
+ assertEquals(1, x.root->rank);
+ assertEquals(0, x.rotations);
+}
+
+void testInsert100() {
+ x.clear(&x);
+ for (int i=0; i<100; i++)
+ x.put(&x,i, i);
+ assertEquals(100, x.count);
+}
+
+void testInsertMany() {
+ x.clear(&x);
+ int a[] = {477, 1193, 2130,398,1393,946,422,1381,1767,830,570,1085,741,598,1658,1801,487,1921,1918,258,135,975,1870};
+ for (int i=0; i < ARRAY_SIZE(a); i++)
+ x.put(&x,a[i], a[i]);
+ assertEquals(1193, (int) x.root->value);
+ assertEquals(1767, (int) x.root->right->value);
+ assertEquals(1393, (int) x.root->right->left->value);
+ assertEquals(1921, (int) x.root->right->right->value);
+ assertEquals(1870, (int) x.root->right->right->left->value);
+ assertEquals(1801, (int) x.root->right->right->left->left->value);
+ assertEquals(2130, (int) x.root->right->right->right->value);
+}
+
+void testDeleteMany() {
+ x.clear(&x);
+ int a[] = {477,1193,2130,398,1393,946,422,1381,1767,830,570,1085,741,598,1658,1801,487};//,1921,1918,258,135,975,1870};
+for (int i=0; i < ARRAY_SIZE(a);i++)
+ x.put(&x,a[i], a[i]);
+
+//x.inOrderTraversal(x.root);
+
+for (int i=ARRAY_SIZE(a)-1; i > 0; i--) {
+ logI("Deleting: %d value: %d", i, a[i]);
+ x.remove(&x, a[i]);
+}
+
+//x.inOrderTraversal(x.root);
+
+assertEquals(477, (int) x.root->value);
+assertEquals(0, x.root->rank); // error root rank is 2 should be 0
+assertNull(x.root->left);
+assertNull(x.root->right);
+}
+
+void testInsertOneLeftRotation() {
+ x.clear(&x);
+ x.put(&x,1, 1);
+ x.put(&x,2, 2);
+ x.put(&x,3, 3);
+
+ assertEquals(1, x.root->rank);
+ assertEquals(2, (int) x.root->value);
+ assertEquals(0, x.root->right->rank);
+}
+
+void testInsertTwoLeftRotations() {
+ x.clear(&x);
+ x.put(&x,1, 1);
+ x.put(&x,2, 2);
+ x.put(&x,3, 3);
+ x.put(&x,4, 4);
+ x.put(&x,5, 5);
+
+ assertEquals(2, x.root->rank);
+ assertEquals(2, (int) x.root->value);
+ assertEquals(2, x.rotations);
+ assertEquals(1, x.root->right->rank);
+ assertEquals(0, x.root->left->rank);
+}
+
+void testInsertThreeLeftRotations() {
+ x.clear(&x);
+ x.put(&x,1, 1);
+ x.put(&x,2, 2);
+ x.put(&x,3, 3);
+ x.put(&x,4, 4);
+ x.put(&x,5, 5);
+ x.put(&x,6, 6);
+
+ assertEquals(3, x.rotations);
+ assertEquals(4, (int) x.root->value);
+ assertEquals(2, x.root->rank);
+ assertTrue(x.root->right->rank == 1 && x.root->left->rank == 1);
+}
+
+
+void testInsertLeftRightRotation() {
+ x.clear(&x);
+ x.put(&x,3, 3);
+ x.put(&x,1, 1);
+ x.put(&x,2, 2);
+
+ assertEquals(2, x.rotations);
+ assertEquals(2, (int) x.root->value);
+ assertEquals(1, x.root->rank);
+}
+
+void testInsertRightLeftRotation() {
+ x.clear(&x);
+ x.put(&x,3, 3);
+ x.put(&x,6, 6);
+ x.put(&x,4, 4);
+
+ assertEquals(2, x.rotations);
+ assertEquals(4, (int) x.root->value);
+ assertEquals(1, x.root->rank);
+}
+
+void testInsertBuildFibonacciTree() {
+ x.clear(&x);
+ x.put(&x,8, 8);
+ x.put(&x,5, 5);
+ x.put(&x,11, 11);
+ // 3,7,10,12
+ x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
+ // 2,4,6,9
+ x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
+ x.put(&x,1, 1);
+ logI("Rotations: %d", x.rotations);
+ assertEquals(0, x.rotations);
+}
+
+void testInsertFibAfterDelete() {
+ x.clear(&x);
+ x.put(&x,8, 8); // root
+ x.put(&x,5, 5); x.put(&x,11, 11);
+ // 3,7,10,12
+ x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
+ // 2,4,6,9
+ x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
+ x.put(&x,1, 1);
+
+ x.remove(&x, 12);
+ //TODO
+}
+
+void testInsert6() {
+ x.clear(&x);
+ for (int i=0; i<6; i++)
+ x.put(&x,i, i);
+ assertEquals(3, x.rotations);
+ assertEquals(3, (int) x.root->value);
+ x.inOrderTraversal(x.root);
+}
+
+void testInsertTwoRightRotations() {
+ x.clear(&x);
+ x.put(&x,5, 5);
+ x.put(&x,4, 4);
+ x.put(&x,3, 3);
+ x.put(&x,2, 4);
+ x.put(&x,1, 1);
+
+ assertEquals(2, x.rotations);
+ assertEquals(2, x.root->rank);
+ assertEquals(4, (int) x.root->value);
+ assertEquals(0, x.root->right->rank);
+ assertEquals(1, x.root->left->rank);
+}
+
+void testDeleteNoRotation() {
+ x.clear(&x);
+ x.put(&x,2, 2);
+ x.put(&x,3, 3);
+ x.put(&x,1, 1);
+ assertEquals(2, (int)x.root->value);
+
+ // 2(1)
+ // 1(0) 3(0)
+ //x.inOrderTraversal(x.root);
+ //puts("");
+
+ x.remove(&x,3);
+
+ // 2(1)
+ // 1(0) -
+ //x.inOrderTraversal(x.root);
+
+ assertEquals(1, x.root->rank);
+ assertEquals(0, x.rotations);
+
+ // remove root
+ x.remove(&x,2);
+
+ //x.inOrderTraversal(x.root);
+
+ x.remove(&x,1);
+ assertEquals(0, x.count);
+}
+
+void testDeleteNoRotationWAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ x.put(&x,2, 2);
+ x.put(&x,3, 3);
+ x.put(&x,1, 1);
+ assertEquals(2, (int)x.root->value);
+
+ x.remove(&x,3);
+ assertEquals(1, x.root->rank);
+ assertEquals(0, x.rotations);
+
+ // remove root
+ x.remove(&x,2);
+ x.remove(&x,1);
+ assertEquals(0, x.count);
+}
+
+void testDeleteNoRotationLeftTallDecrementRank() {
+ x.clear(&x);
+ x.put(&x,2, 2);
+ x.put(&x,3, 3);
+ x.put(&x,1, 1);
+ x.put(&x,0, 0);
+ assertEquals(2, (int)x.root->value);
+
+ x.remove(&x,0);
+ /*
+ 2
+ 1 3
+ */
+ assertEquals(1, x.root->rank); // error root rank is 2 should be 1
+ assertEquals(0, x.rotations);
+}
+
+void testDeleteOneRightRotation() {
+ x.clear(&x);
+ x.put(&x,10, 10);
+ x.put(&x,8, 8); x.put(&x,12, 12);
+ x.put(&x,6, 6);
+
+ x.remove(&x,12);
+ /*
+ 8
+ 6 10
+ */
+ assertEquals(1, x.rotations);
+ assertEquals(1, x.root->rank);
+ assertEquals(8, (int) x.root->value);
+}
+
+void testDeleteOneRightRotationWAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ x.put(&x,10, 10);
+ x.put(&x,8, 8); x.put(&x,12, 12);
+ x.put(&x,6, 6);
+
+ x.remove(&x,12);
+ /*
+ 8
+ 6 10
+ */
+ assertEquals(1, x.rotations);
+ assertEquals(2, x.root->rank); // created 2,2 node, non-leaf
+ assertEquals(0, x.root->right->rank);
+ assertEquals(0, x.root->left->rank);
+ assertEquals(8, (int) x.root->value);
+}
+
+void testDeleteOneRightRotationSiblingBalanced() {
+ x.clear(&x);
+ x.put(&x,10, 10);
+ x.put(&x,8, 8);x.put(&x,12, 12);
+ x.put(&x,6,6);x.put(&x,9,9);
+
+ assertEquals(0, x.rotations);
+
+ x.remove(&x,12);
+ /* after
+ 8
+ 6 10
+ 9
+ */
+ assertEquals(2, x.root->rank);
+ assertEquals(6, (int) x.root->left->value);
+ assertEquals(1, x.root->right->rank);
+ assertEquals(0, x.root->left->rank);
+ assertEquals(8, (int) x.root->value);
+ assertEquals(1, x.rotations);
+}
+
+void testDeleteOneRightRotationSiblingBalancedWAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ x.put(&x,10, 10);
+ x.put(&x,8, 8);x.put(&x,12, 12);
+ x.put(&x,6,6);x.put(&x,9,9);
+
+ assertEquals(0, x.rotations);
+
+ x.remove(&x,12);
+ /* after
+ 8
+ 6 10
+ 9
+ */
+ assertEquals(2, x.root->rank);
+ assertEquals(6, (int) x.root->left->value);
+ assertEquals(1, x.root->right->rank);
+ assertEquals(0, x.root->right->left->rank);
+ assertEquals(0, x.root->left->rank);
+ assertEquals(8, (int) x.root->value);
+ assertEquals(1, x.rotations);
+}
+
+void testDeleteOneLeftRightRotation() {
+ x.clear(&x);
+ x.put(&x,10, 10);
+ x.put(&x,8, 8);
+ x.put(&x,12, 12);
+ x.put(&x,9, 9);
+
+ x.remove(&x,12);
+ /*
+ 9
+ 8 10
+ */
+
+ assertEquals(0, x.root->right->rank);
+ assertEquals(0, x.root->left->rank);
+ assertEquals(1, x.root->rank);
+ assertEquals(9, (int) x.root->value);
+ assertEquals(2, x.rotations);
+}
+
+void testDeleteOneLeftRightRotationWAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ x.put(&x,10, 10);
+ x.put(&x,8, 8);
+ x.put(&x,12, 12);
+ x.put(&x,9, 9);
+
+ x.remove(&x,12);
+ /*
+ 9
+ 8 10
+ */
+
+ assertEquals(0, x.root->right->rank);
+ assertEquals(0, x.root->left->rank);
+ assertEquals(2, x.root->rank); // created 2,2 node
+ assertEquals(9, (int) x.root->value);
+ assertEquals(2, x.rotations);
+}
+
+void testDelete5() {
+ x.clear(&x);
+ for (int i=0; i<6; i++)
+ x.put(&x,i, i);
+ for (int i=0; i<5; i++) {
+ logI("Root: k %d v %d Deleting: %d\n", x.root->key, x.root->value, i);
+ x.remove(&x,i);
+ }
+ assertEquals(1, x.count);
+ assertEquals(0, x.root->rank);
+}
+
+void testDelete5WAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ for (int i=0; i<6; i++)
+ x.put(&x,i, i);
+
+ // 3(2)
+ // 1(1) 4(1)
+ // 0(0) 2(0) - 5(0)
+ //x.inOrderTraversal(x.root);
+
+ //logI("Rotations before remove: %d\n", x.rotations);
+
+ for (int i=0; i<5; i++) {
+ logI("Root: k %d v %d Deleting: %d\n", x.root->key, x.root->value, i);
+ x.remove(&x,i);
+ }
+
+ //logI("Rotations after remove: %d\n", x.rotations);
+ assertEquals(1, x.count);
+ assertEquals(0, x.root->rank);
+
+ x.remove(&x,5);
+}
+
+void testDeleteFibonacciTree() {
+ x.clear(&x);
+ x.put(&x,8, 8); // root
+ x.put(&x,5, 5); x.put(&x,11, 11);
+ // 3,7,10,12
+ x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
+ // 2,4,6,9
+ x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
+ x.put(&x,1, 1);
+ logI("Rotations before remove 12 from Fibonacci: %d\n", x.rotations);
+
+ // 8(4)
+ // 5(3) 11(2)
+ // 3(2) 7(1) 10(1) 12(0)
+ // 2(1) 4(0) 6(0) - 9(0) -
+ // 1(0) -
+ //x.inOrderTraversal(x.root);
+ //puts("\n");
+
+ x.remove(&x, 12);
+
+ // 8(4)
+ // 5(3) 11(2)
+ // 3(2) 7(1) 10(1) -
+ // 2(1) 4(0) 6(0) - 9(0) -
+ // 1(0) -
+ //x.inOrderTraversal(x.root);
+
+
+ logI("Rotations after remove 12: %d\n", x.rotations);
+ logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
+ assertEquals(2, x.rotations);
+ assertEquals(5, (int) x.root->value);
+
+ x.remove(&x,4);
+
+ // 8(4)
+ // 5(3) 11(2)
+ // 3(2) 7(1) 10(1) -
+ // 2(1) - 6(0) - 9(0) -
+ // 1(0)
+ //x.inOrderTraversal(x.root);
+
+ assertEquals(2, (int) x.root->left->value);
+ assertEquals(1, x.root->left->rank);
+
+}
+
+void testDeleteFibonacciTreeWAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ x.put(&x,8, 8); // root
+ x.put(&x,5, 5); x.put(&x,11, 11);
+ // 3,7,10,12
+ x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
+ // 2,4,6,9
+ x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
+ x.put(&x,1, 1);
+
+ // 8(4)
+ // 5(3) 11(2)
+ // 3(2) 7(1) 10(1) 12(0)
+ // 2(1) 4(0) 6(0) - 9(0) -
+ // 1(0) -
+
+ x.remove(&x, 12);
+
+ logI("Rotations after remove 12: %d\n", x.rotations);
+ logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
+ assertEquals(1, x.rotations);
+ assertEquals(8, (int) x.root->value);
+ assertEquals(0, x.root->right->right->rank);
+ assertEquals(0, x.root->right->left->rank);
+ assertEquals(2, x.root->right->rank);
+}
+
+void testDeleteAlmostFibonacciTreeWAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ x.put(&x,8, 8); // root
+ x.put(&x,5, 5); x.put(&x,12, 12);
+ // 3,7,10,12
+ x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,13, 13);
+ // 2,4,6,9,11
+ x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9); x.put(&x,11,11);
+ x.put(&x,1, 1);
+
+ //x.inOrderTraversal(x.root);
+ //puts("\n");
+
+ x.remove(&x, 13);
+
+ // 8(4)
+ // 5(3) 12(2)
+ // 3(2) 7(1) 10(1) -
+ // 2(1) 4(0) 6(0) - 9(0) 11(0)
+ // 1(0) -
+ //x.inOrderTraversal(x.root);
+
+ /* int g[] = {8,5,12,3,7,10,13,2,4,6,9,11,1}; */
+ /* range(i, ARRAY_SIZE(g)) { */
+ /* var v = x.get(&x, g[i]); */
+ /* if (v == -1) { */
+ /* logI("key %d, "BLD YLW"not found"RST, g[i]); */
+ /* } */
+ /* else { */
+ /* logI("key %d, value %d", g[i], x.get(&x, g[i])); */
+ /* } */
+ /* } */
+
+ logI("Rotations after remove 13: %d\n", x.rotations);
+ logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
+ assertEquals(1, x.rotations);
+ assertEquals(8, (int) x.root->value);
+ assertEquals(1, x.root->right->right->rank);
+ assertEquals(0, x.root->right->left->rank);
+ assertEquals(2, x.root->right->rank);
+}
+
+void testDeleteManyWAVL() {
+ x.clear(&x);
+ x.deleteWAVL = true;
+ int a[] = {477,1193,2130,398,1393,946,422,1381,1767,830,570,1085,741,598,1658,1801,487,1921,1918,258,135,975,1870};
+ for (int i=0; i < ARRAY_SIZE(a); i++) {
+ logI("put: %d,\n", a[i]);
+ x.put(&x,a[i], a[i]);
+ }
+ puts("\n");
+
+ for (int i=ARRAY_SIZE(a)-1; i > 0; i--) {
+ logI("Deleting: %d value: %d\n", i, a[i]);
+ x.remove(&x, a[i]);
+ }
+
+ x.inOrderTraversal(x.root);
+
+ assertEquals(477, (int) x.root->value);
+ assertEquals(0, x.root->rank);
+ assertNull(x.root->left);
+ assertNull(x.root->right);
+}
+
+
+int main(int ARGC, char** ARGV) {
+
+ argc = ARGC; argv = ARGV;
+
+ initLibsheepy(ARGV[0]);
+ setLogMode(LOG_FUNC);
+
+ wavlTreeinit(&x);
+
+ testDelete5();
+ testDelete5WAVL();
+ testDeleteAlmostFibonacciTreeWAVL();
+ testDeleteFibonacciTree();
+ testDeleteFibonacciTreeWAVL();
+ testDeleteMany();
+ testDeleteManyWAVL();
+ testDeleteNoRotation();
+ testDeleteNoRotationLeftTallDecrementRank();
+ testDeleteNoRotationWAVL();
+ testDeleteOneLeftRightRotation();
+ testDeleteOneLeftRightRotationWAVL();
+ testDeleteOneRightRotation();
+ testDeleteOneRightRotationSiblingBalanced();
+ testDeleteOneRightRotationSiblingBalancedWAVL();
+ testDeleteOneRightRotationWAVL();
+ testInsert100();
+ testInsert6();
+ testInsertBuildFibonacciTree();
+ testInsertDoNothing();
+ testInsertFibAfterDelete();
+ testInsertLeftRightRotation();
+ testInsertMany();
+ testInsertOneLeftRotation();
+ testInsertRightLeftRotation();
+ testInsertThreeLeftRotations();
+ testInsertTwoLeftRotations();
+ testInsertTwoRightRotations();
+ testTreeHeight();
+
+ x.clear(&x);
+}
+// vim: set expandtab ts=2 sw=2:
diff --git a/wavlTree.c b/wavlTree.c
@@ -0,0 +1,594 @@
+
+#include "wavlTree.h"
+
+#define w (*tree)
+#define n (*node)
+#define p (*P)
+#define o (*O)
+#define x (*X)
+
+/* enable/disable logging */
+#undef pLog
+#define pLog(...)
+
+#define freeP(ptr) do{\
+ logI("free(%p);", ptr);\
+ free(ptr);\
+ }while(0)
+
+// namespace
+/* #define nodeHeight TOKENPASTE(WAVL_NAMESPACE, nodeHeight) */
+/* #define nodeNew TOKENPASTE(WAVL_NAMESPACE, nodeNew) */
+/* #define getEntry TOKENPASTE(WAVL_NAMESPACE, getEntry) */
+/* #define balanceAfterInsert TOKENPASTE(WAVL_NAMESPACE, balanceAfterInsert) */
+/* #define needToRotateLeft TOKENPASTE(WAVL_NAMESPACE, needToRotateLeft) */
+/* #define needToRotateRight TOKENPASTE(WAVL_NAMESPACE, needToRotateRight) */
+/* #define rotateLeft TOKENPASTE(WAVL_NAMESPACE, rotateLeft) */
+/* #define rotateRight TOKENPASTE(WAVL_NAMESPACE, rotateRight) */
+/* #define removeKV TOKENPASTE(WAVL_NAMESPACE, removeKV) */
+/* #define clear TOKENPASTE(WAVL_NAMESPACE, clear) */
+/* #define height TOKENPASTE(WAVL_NAMESPACE, height) */
+/* #define inOrderTraversal TOKENPASTE(WAVL_NAMESPACE, inOrderTraversal) */
+/* #define put TOKENPASTE(WAVL_NAMESPACE, put) */
+/* #define get TOKENPASTE(WAVL_NAMESPACE, get) */
+
+static int height(t *tree);
+static int nodeHeight(nodet *node);
+static nodet *getEntry(t *tree, keyt key);
+static valuet put(t *tree, keyt k, valuet v);
+static void inOrderTraversal(nodet *X);
+static void balanceAfterInsert(t *tree, nodet *X);
+static bool needToRotateLeft(nodet *P);
+static bool needToRotateRight(nodet *P);
+static void rotateLeft(t *tree, nodet *P);
+static void rotateRight(t *tree, nodet *P);
+static valuet removeKV(t *tree, keyt k);
+
+static void deleteEntry(t *tree, nodet *P);
+static nodet *predecessor(nodet *X);
+static void fixAfterDeleteWAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank);
+static void fixAfterDeleteAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank);
+
+static nodet *nodeNew(keyt k, valuet v, nodet *parent) {
+ nodet *r = malloc(sizeof(nodet));
+ if (!r) return NULL;
+ r->key = k;
+ r->value = v;
+ r->left = NULL;
+ r->right = NULL;
+ r->parent = parent;
+ r->rank = 0;
+ return r;
+}
+
+int height(t *tree) {
+ return nodeHeight(w.root) - 1;
+}
+
+int nodeHeight(nodet *node) {
+ if (!node) {
+ return 0;
+ }
+ return (1 + maxV(nodeHeight(n.left), nodeHeight(n.right)));
+}
+
+/**
+ * return the value associated with key k
+ */
+static valuet get(t *tree, keyt k) {
+ nodet *X = getEntry(tree, k);
+ return !X ? -1 : x.value;
+}
+
+/**
+ * return map entry for the given key
+ */
+static nodet *getEntry(t *tree, keyt key) {
+ nodet *P = w.root;
+ while (P) {
+ int cmp = CMP(key, p.key);
+ if (cmp < 0)
+ P = p.left;
+ else if (cmp > 0)
+ P = p.right;
+ else {
+ logI("Entry: %p", P);
+ return P;
+ }
+ }
+ return NULL;
+}
+
+/**
+ * associate value v with key k
+ *
+ * \return
+ * previous value for key k
+ * -1 when k is not already in the tree
+ */
+static valuet put(t *tree, keyt k, valuet v) {
+ nodet *O = w.root;
+ if (!O) {
+ // tree is empty, new node is root
+ w.root = nodeNew(k, v, NULL);
+ w.count = 1;
+ w.modCount++;
+ //return NULL;
+ return -1;
+ }
+
+ // Find the proper position for this new node
+ int cmp;
+ nodet *P;
+ do {
+ P = O;
+ cmp = CMP(k, o.key);
+ // Decide which side of the current parent-under-consideration the
+ // new node to be inserted belongs on.
+ if (cmp < 0)
+ O = o.left;
+ else if (cmp > 0)
+ O = o.right;
+ else {
+ // Looks like we collided with an object in the tree which has
+ // the same key as the key in parameters
+ // return previous value
+ valuet r = o.value;
+ o.value = v;
+ return r;
+ }
+ // If we would have run out of valid pointers in the direction we
+ // should be searching, then we are done
+ } while(O);
+
+ nodet *e = nodeNew(k, v, P);
+ logI("New %p", e);
+ if (cmp < 0) {
+ p.left = e;
+ }
+ else {
+ p.right = e;
+ }
+
+ if (!p.rank) {
+ p.rank++;
+ balanceAfterInsert(tree, P);
+ }
+
+ w.count++;
+ w.modCount++;
+
+ //return NULL;
+ return -1;
+}
+
+static void inOrderTraversal(nodet *X) {
+ if (!X) return;
+ printf("value %d, rank %d", x.value, x.rank);
+ if (x.left) {
+ printf(" left key %d", x.left->key);
+ }
+ else
+ printf(" no left");
+ if (x.right) {
+ printf(" right key %d", x.right->key);
+ }
+ else
+ printf(" no right");
+ printf("\n");
+ inOrderTraversal(x.left);
+ //printf("value %d, rank %d\n", x.value, x.rank);
+ inOrderTraversal(x.right);
+}
+
+/**
+ * - If the path of incremented ranks reaches the root of the tree stop.
+ * - If the path of incremented ranks reaches a node whose parent's rank previously differed by two and after incrementing now differ by one stop.
+ * - If the procedure increases the rank of a node x, so that it becomes equal to the rank of the parent y of x,
+ * but the other child of y has a rank that is smaller by two (so that the rank of y cannot be increased)
+ * then again the rebalancing procedure stops after performing rotations necessary.
+ *
+ * In other words:
+ * After insertion rank difference is 1,2 or 3 -
+ * check these three cases stopping after any rotations, reaching the root or when rank difference was 2 before the insertion.
+ */
+static void balanceAfterInsert(t *tree, nodet *X) {
+ for(nodet *P = x.parent ; P && (x.rank+1 != p.rank) ; x.rank++) {
+ if (p.left == X) {
+ // new node was added on the left
+ if (needToRotateRight(P)) {
+ if (!x.left || x.rank >= x.left->rank+2) {
+ x.rank--;
+ x.right->rank++;
+ rotateLeft(tree, X);
+ }
+ p.rank--;
+ rotateRight(tree, P);
+ break;
+ }
+ }
+ else {
+ if (needToRotateLeft(P)) {
+ if (!x.right || x.rank >= x.right->rank+2) {
+ x.rank--;
+ x.left->rank++;
+ rotateRight(tree, X);
+ }
+ p.rank--;
+ rotateLeft(tree, P);
+ break;
+ }
+ }
+ X = P;
+ P = x.parent;
+ }
+}
+
+static bool needToRotateLeft(nodet *P) {
+ if (!p.left) {
+ // rank of sibling is -1
+ if (p.rank == 1)
+ return true;
+ return false;
+ }
+ else if (p.rank >= p.left->rank + 2)
+ return true;
+ return false;
+}
+
+static bool needToRotateRight(nodet *P) {
+ if (!p.right) {
+ // rank of sibling is -1
+ if (p.rank == 1)
+ return true;
+ return false;
+ }
+ else if (p.rank >= p.right->rank + 2)
+ return true;
+ return false;
+}
+
+static void rotateLeft(t *tree, nodet *P) {
+ nodet *X = p.right;
+ p.right = x.left;
+ if (x.left)
+ x.left->parent = P;
+ x.parent = p.parent;
+ if (!p.parent)
+ w.root = X;
+ else if (p.parent->left == P)
+ p.parent->left = X;
+ else
+ p.parent->right = X;
+ x.left = P;
+ p.parent = X;
+ w.rotations++;
+}
+
+static void rotateRight(t *tree, nodet *P) {
+ nodet *X = p.left;
+ p.left = x.right;
+ if (x.right)
+ x.right->parent = P;
+ x.parent = p.parent;
+ if (!p.parent)
+ w.root = X;
+ else if (p.parent->right == P)
+ p.parent->right = X;
+ else
+ p.parent->left = X;
+ x.right = P;
+ p.parent = X;
+ w.rotations++;
+}
+
+/**
+ * remove key and value if key is present in tree
+ *
+ * \return
+ * previous value for key k
+ * -1 when k was not in the tree
+ */
+valuet removeKV(t *tree, keyt k) {
+ nodet *P = getEntry(tree, k);
+ if (!P)
+ //return NULL;
+ return -1;
+
+ valuet oldValue = p.value;
+ deleteEntry(tree, P);
+ return oldValue;
+}
+
+/**
+ * delete node P and then rebalance the tree
+ */
+static void deleteEntry(t *tree, nodet *P) {
+ w.modCount++;
+ w.count--;
+
+ // If strictly internal, copy successor's element to p and then make p
+ // point to successor.
+ if (p.left && p.right) {
+ nodet *X = predecessor(P);
+ p.key = x.key;
+ p.value = x.value;
+ P = X;
+ } // p has 2 children
+
+ nodet *replacement = (p.left ? p.left : p.right);
+ if (replacement) {
+ // Link replacement to parent
+ replacement->parent = p.parent;
+ nodet *sibling = NULL;
+ if (!p.parent) {
+ w.root = replacement;
+ freeP(P);
+ return;
+ }
+ else if (P == p.parent->left) {
+ p.parent->left = replacement;
+ sibling = p.parent->right;
+ } else {
+ p.parent->right = replacement;
+ sibling = p.parent->left;
+ }
+
+ // Null out links so they are OK to use by fixAfterDeletion.
+ p.left = p.right = p.parent = NULL;
+ freeP(P);
+ if (w.deleteWAVL)
+ fixAfterDeleteWAVL(tree, replacement->parent, sibling, replacement->rank);
+ else
+ fixAfterDeleteAVL(tree, replacement->parent, sibling, replacement->rank);
+ }
+ else if (!p.parent) {
+ // return if we are the only node.
+ freeP(P);
+ w.root = NULL;
+ return;
+ }
+ else {
+ // No children. Use self as phantom replacement and unlink.
+ nodet *fixPoint = p.parent;
+ nodet *sibling = NULL;
+
+ if (P == p.parent->left) {
+ p.parent->left = NULL;
+ sibling = fixPoint->right;
+ }
+ else if (P == p.parent->right) {
+ p.parent->right = NULL;
+ sibling = fixPoint->left;
+ }
+ p.parent = NULL;
+ int8_t rk = --p.rank;
+ freeP(P);
+ if (w.deleteWAVL)
+ fixAfterDeleteWAVL(tree, fixPoint, sibling, rk);
+ else
+ fixAfterDeleteAVL(tree, fixPoint, sibling, rk);
+ }
+}
+
+static int8_t rank(nodet *node) {
+ return !node ? -1 : n.rank;
+}
+
+static bool nodeIsTwoTwo(nodet *node) {
+ if (!node || !n.rank)
+ return false;
+ if (n.rank == 1) {
+ if (!n.left && !n.right)
+ return true;
+ else
+ return false;
+ }
+ else
+ return (n.left->rank == n.right->rank && (n.left->rank + 2 == n.rank));
+}
+
+static void fixAfterDeleteWAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank) {
+ nodet *node;
+ int deltaRank = parent->rank - nodeRank;
+ while (deltaRank == 3 || parent->rank == 1 && nodeIsTwoTwo(parent)) {
+ int deltaRankSibling = (!sibling) ? parent->rank + 1 : parent->rank - sibling->rank;
+ if (deltaRankSibling == 2) {
+ parent->rank--; // demote and continue loop
+ } else {
+ int deltaRankSiblingL = sibling->rank - rank(sibling->left);
+ int deltaRankSiblingR = sibling->rank - rank(sibling->right);
+
+ if (deltaRankSiblingL == 2 && deltaRankSiblingR == 2) {
+ // "double demote" in the orig. paper since both parent & sibling demote
+ parent->rank--;
+ sibling->rank--;
+ }
+ else if (parent->right == sibling) {
+ // delete was on the left
+ if (deltaRankSiblingR == 1) {
+ // single rotation
+ sibling->rank++;
+ parent->rank--;
+ if (!sibling->left)
+ parent->rank--; // demote parent again
+ rotateLeft(tree, parent);
+ }
+ else {
+ // double rotation
+ parent->rank -= 2;
+ sibling->rank--;
+ sibling->left->rank += 2;
+ rotateRight(tree, sibling);
+ rotateLeft(tree, parent);
+ }
+ break;
+ }
+ else {
+ // delete was on the right
+ if (deltaRankSiblingL == 1) {
+ // single rotation
+ sibling->rank++;
+ parent->rank--;
+ if (!sibling->right)
+ parent->rank--; // demote parent again
+ rotateRight(tree, parent);
+ }
+ else {
+ // double rotation
+ parent->rank -= 2;
+ sibling->rank--;
+ sibling->right->rank += 2;
+ rotateLeft(tree, sibling);
+ rotateRight(tree, parent);
+ }
+ break;
+ }
+ }
+
+ if (!parent->parent)
+ return;
+ node = parent;
+ parent = parent->parent;
+ sibling = (parent->left == node) ? parent->right : parent->left;
+ deltaRank = parent->rank - n.rank;
+ }
+}
+
+static void fixAfterDeleteAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank) {
+ nodet *node;
+ int balance;
+ if (!sibling)
+ // remove sibling null check inside loop by testing once here
+ balance = -1 - nodeRank;
+ else
+ balance = sibling->rank - nodeRank;
+
+ while (balance != 1) {
+ // balance == 1 means prior to delete parent was balanced, break;
+ if (balance == 0) {
+ // side of delete was taller, decrement and continue
+ parent->rank--;
+ }
+ else if (parent->left == sibling) {
+ parent->rank -= 2;
+ int siblingBalance = rank(sibling->right) - rank(sibling->left);
+ if (siblingBalance == 0) {
+ // parent height unchanged after rotate so break
+ sibling->rank++;
+ parent->rank++;
+ rotateRight(tree, parent);
+ break;
+ }
+ else if (siblingBalance > 0) {
+ sibling->right->rank++;
+ sibling->rank--;
+ rotateLeft(tree, sibling);
+ }
+ rotateRight(tree, parent);
+ parent = parent->parent;
+ }
+ else {
+ // delete on left
+ parent->rank -= 2;
+ int siblingBalance = rank(sibling->right) - rank(sibling->left);
+ if (siblingBalance == 0) {
+ // parent height unchanged after rotate so break
+ sibling->rank++;
+ parent->rank++;
+ rotateLeft(tree, parent);
+ break;
+ }
+ else if (siblingBalance < 0) {
+ sibling->left->rank++;
+ sibling->rank--;
+ rotateRight(tree, sibling);
+ }
+ rotateLeft(tree, parent);
+ parent = parent->parent;
+ }
+
+ if (!parent->parent)
+ return;
+ node = parent;
+ parent = parent->parent;
+ sibling = (parent->left == node) ? parent->right : parent->left;
+ balance = sibling->rank - n.rank;
+ }
+}
+
+static void freeNodes(nodet *X) {
+ if (!X) return;
+ freeNodes(x.left);
+ freeNodes(x.right);
+ freeP(X);
+}
+
+static void clear(t *tree) {
+ freeNodes(w.root);
+ w.modCount++;
+ w.count = 0;
+ w.root = NULL;
+ w.rotations = 0;
+ w.deleteWAVL = false;
+}
+
+// TODO getFirstEntry...
+// TODO add leftMost, rightMost
+
+static nodet *predecessor(nodet *X) {
+ if (!X)
+ return NULL;
+ else if (x.left) {
+ nodet *P = x.left;
+ while (p.right)
+ P = p.right;
+ return P;
+ }
+ else {
+ nodet *P = x.parent;
+ nodet *ch = X;
+ while (P && ch == p.left) {
+ ch = P;
+ P = p.parent;
+ }
+ return P;
+ }
+}
+
+// TODO iterator
+
+/**
+ * initialize tree data
+ */
+/* #undef put */
+/* #undef get */
+/* #undef inOrderTraversal */
+/* #undef clear */
+bool init(t *tree) {
+ if (!tree) return false;
+
+ w.count = 0;
+ w.modCount = 0;
+ w.rotations = 0;
+ w.deleteWAVL = false;
+ w.root = NULL;
+
+ /* w.get = TOKENPASTE(WAVL_NAMESPACE, get); */
+ /* w.put = TOKENPASTE(WAVL_NAMESPACE, put); */
+ /* w.treeHeight = height; */
+ /* w.remove = removeKV; */
+ /* w.inOrderTraversal = TOKENPASTE(WAVL_NAMESPACE, inOrderTraversal); */
+ /* w.clear = TOKENPASTE(WAVL_NAMESPACE, clear); */
+
+ w.get = get;
+ w.put = put;
+ w.treeHeight = height;
+ w.remove = removeKV;
+ w.inOrderTraversal = inOrderTraversal;
+ w.clear = clear;
+
+ return true;
+}
+
+// vim: set expandtab ts=2 sw=2:
diff --git a/wavlTree.h b/wavlTree.h
@@ -0,0 +1,81 @@
+#pragma once
+
+#include "libsheepyObject.h"
+#undef put
+
+/**
+ * WAVL Tree
+ *
+ * The WAVL tree combines elements of AVL & Red-black trees.
+ *
+ * The WAVL tree deletion is described in the 2015 paper "Rank Balanced Trees"
+ * The related RAVL tree is described in the 2016 paper "Deletion Without Rebalancing in Binary Search Trees"
+ * available at:
+ * http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf
+ * http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pdf
+ *
+ *
+ * in this implementation:
+ * - key is int
+ * - value is int
+ *
+ * the code is inspired by:
+ * https://github.com/dmcmanam/bbst-showdown
+ */
+
+// namespace
+#ifndef WAVL_NAMESPACE
+#define WAVL_NAMESPACE wavlTree
+#endif
+#define keyt TOKENPASTE(WAVL_NAMESPACE, keyt)
+#define valuet TOKENPASTE(WAVL_NAMESPACE, valuet)
+#define nodet TOKENPASTE(WAVL_NAMESPACE, nodet)
+#define t TOKENPASTE(WAVL_NAMESPACE, t)
+#define St TOKENPASTE(WAVL_NAMESPACE, St)
+#define init TOKENPASTE(WAVL_NAMESPACE, init)
+
+// TODO namespace cleanup
+
+typedef int keyt;
+typedef int valuet;
+//typedef char* valuet;
+
+typedef struct St t;
+
+
+
+typedef struct nodet nodet;
+struct nodet {
+ keyt key;
+ valuet value;
+ nodet *left;
+ nodet *right;
+ nodet *parent;
+ int8_t rank;
+};
+
+typedef int (*heightFt) (t *tree);
+typedef valuet (*getFt) (t *tree, keyt k);
+typedef valuet (*putFt) (t *tree, keyt k, valuet v);
+typedef valuet (*removeKVFt) (t *tree, keyt k);
+typedef void (*inOrderTraversalFt)(nodet *X);
+typedef void (*clearFt) (t *tree);
+
+struct St {
+ size_t count; // number of entries in the tree
+ size_t modCount; // number of structural modifications to the tree
+ size_t rotations;
+ bool deleteWAVL;
+ nodet *root;
+ getFt get;
+ putFt put;
+ heightFt treeHeight;
+ removeKVFt remove;
+ inOrderTraversalFt inOrderTraversal;
+ clearFt clear;
+
+};
+
+bool init(t *tree);
+
+// vim: set expandtab ts=2 sw=2:
diff --git a/wavlTreeNamespaceCleanup.h b/wavlTreeNamespaceCleanup.h
@@ -0,0 +1,19 @@
+#undef keyt
+#undef valuet
+#undef nodet
+#undef t
+#undef St
+#undef init
+// #undef nodeHeight
+// #undef nodeNew
+// #undef height
+// #undef getEntry
+// #undef put
+// #undef inOrderTraversal
+// #undef fixAfterInsert
+// #undef needToRotateLeft
+// #undef needToRotateRight
+// #undef rotateLeft
+// #undef rotateRight
+// #undef removeKV
+// #undef clear
