commit a97217b6f99c2488f6e8863f190d63e45a93a85e
parent 54bee5992078ea52f4a2b2b3da2b5aad8ccf5284
Author: Remy Noulin <loader2x@gmail.com>
Date: Sun, 30 Dec 2018 12:05:07 +0100
implement wavlTree (malloc nodes)
.gitignore | 11 ++
main.c | 56 ++++++
package.yml | 31 ++++
tree.h | 3 +
wavl.h | 603 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
wavlTest.c | 441 ++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 1145 insertions(+)
Diffstat:
| M | .gitignore | | | 11 | +++++++++++ |
| A | main.c | | | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | package.yml | | | 31 | +++++++++++++++++++++++++++++++ |
| A | tree.h | | | 3 | +++ |
| A | wavl.h | | | 603 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | wavlTest.c | | | 441 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
6 files changed, 1145 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,56 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+/* Libsheepy documentation: http://spartatek.se/libsheepy/ */
+#include "libsheepyObject.h"
+#include "wavl.h"
+
+int argc; char **argv;
+
+/* enable/disable logging */
+/* #undef pLog */
+/* #define pLog(...) */
+
+wavlDef(/* scope */, w /* wt wavl tree type and wNodet node type */, W /* function suffix: initW...*/, u32 /* keyType*/, u32 /* valueType */);
+
+wt tree;
+
+void freeKV(u32* /* keyType */ key, u32* /* valueType*/ value) {
+}
+
+#define FREEFUNC freeKV
+#define CMPFUNC CMP
+
+wavlFunctions(/* scope */, w /* wt wavl tree type*/, W /* function suffix: initW...*/, u32 /* keyType*/, u32 /* valueType */, -1 /* null key */, -1 /* null value */);
+
+int main(int ARGC, char** ARGV) {
+
+ argc = ARGC; argv = ARGV;
+
+ initLibsheepy(ARGV[0]);
+ setLogMode(LOG_FUNC);
+
+ initW(&tree);
+
+ addW(&tree, 0, 0);
+ addW(&tree, 1, 1);
+ addW(&tree, 10, 10);
+ addW(&tree, 5, 5);
+
+ var n = getW(&tree, 10);
+ logVarG(n);
+
+ // tree.inOrderTraversal(tree.root);
+ iterStartW(&tree, getFirstEntryW(&tree));
+ wNodet *node;
+ while(node = nextW(&tree)) {
+ logVarG(node->key);
+ logVarG(node->value);
+ }
+
+ delW(&tree, 10);
+
+ freeW(&tree);
+
+}
+// vim: set expandtab ts=2 sw=2:
diff --git a/package.yml b/package.yml
@@ -0,0 +1,31 @@
+---
+ name: tree
+ version: 0.0.1
+ description: "tree data stuctures: WAVL (weak AVL) tree"
+ bin: ./tree.h
+ #cflags: -DA -ggdb -std=gnu11 -fPIC -pipe
+ #lflags: -lpcre
+ repository:
+ type: git
+ url: git+https://github.com/RemyNoulin/tree.git
+ keywords:
+ - data stucture
+ author: Remy
+ license: MIT
+ bugs:
+ url: https://github.com/USER/RemyNoulin/issues
+ homepage: https://github.com/RemyNoulin/tree#readme
+ #compileHelp: # text displayed when there is a compilation error
+ #dependencies:
+ # md4c:
+ # Test configuration:
+ #testBin: ./testTree.c
+ #testCflags: -ggdb -std=gnu11 -fPIC -pipe -fprofile-arcs -ftest-coverage -Wall -Wextra
+ #testLflags: -lcheck_pic -lrt -lm -lsubunit -fprofile-arcs -ftest-coverage -rdynamic
+ # Memcheck configuration:
+ #memcheckBin: ./memcheckTree.c
+ #memcheckCmd: valgrind --leak-check=full --show-leak-kinds=all
+ #memcheckCflags: -ggdb -std=gnu11 -fPIC -pipe
+ #memcheckLflags: -rdynamic
+ #documentationCmd: # command for generating the documentation with spm doc
+ private: false # true for private package
diff --git a/tree.h b/tree.h
@@ -0,0 +1,3 @@
+#pragma once
+
+#include "wavl.h"
diff --git a/wavl.h b/wavl.h
@@ -0,0 +1,603 @@
+#pragma once
+
+#include "libsheepyObject.h"
+
+/**
+ *
+ * TODO add leftMost, rightMost pointer in tree
+ *
+ * void printTree(typeName##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);
+ * inOrderTraversal(X->right);
+ * }
+ *
+ * void inOrderTraversal(typeName##Nodet *X) {
+ * if (!X) return;
+ *
+ * inOrderTraversal(X->left);
+ * printf("value %d, rank %d\n", X->value, X->rank);
+ * inOrderTraversal(X->right);
+ * }
+ */
+
+// init
+// height
+// empty FREEFUNC
+// isEmpty
+// free
+// add CMPFUNC
+// addOrFind
+// find
+// get
+// g##suffixetKey
+// del
+// addOrFindNode
+// getNode
+// delNode
+
+// iterator
+
+#define wavlDef(scope, typeName, suffix, keyType, valueType)\
+ wavlNodeT(typeName##Nodet, keyType, valueType);\
+ wavlTreeT(typeName##t, typeName##Nodet, keyType, valueType);\
+ scope void init##suffix(typeName##t *tree);\
+ scope int height##suffix(typeName##t *tree);\
+ scope void empty##suffix(typeName##t *tree);\
+ scope bool isEmpty##suffix(typeName##t *tree);\
+ scope void free##suffix(typeName##t *tree);\
+ scope bool add##suffix(typeName##t *tree, keyType key, valueType value);\
+ scope valueType* addOrFind##suffix(typeName##t *tree, keyType key, bool *isnew);\
+ scope valueType* find##suffix(typeName##t *tree, keyType key);\
+ scope valueType get##suffix(typeName##t *tree, keyType key);\
+ scope keyType getKey##suffix(typeName##t *tree, keyType key);\
+ scope void del##suffix(typeName##t *tree, keyType key);\
+ scope typeName##Nodet* addOrFindNode##suffix(typeName##t *tree, keyType key, bool *isnew);\
+ scope typeName##Nodet* getNode##suffix(typeName##t *tree, keyType key);\
+ scope typeName##Nodet *getFirstEntry##suffix(typeName##t *tree);\
+ scope typeName##Nodet *getLastEntry##suffix(typeName##t *tree);\
+ scope void delNode##suffix(typeName##t *tree, typeName##Nodet *node);\
+ scope void iterStart##suffix(typeName##t *tree, typeName##Nodet *first);\
+ scope bool hasNext##suffix(typeName##t *tree);\
+ scope typeName##Nodet *next##suffix(typeName##t *tree);\
+ scope typeName##Nodet *prev##suffix(typeName##t *tree);\
+ scope bool removeCurrent##suffix(typeName##t *tree)
+
+#define wavlFunctions(scope, typeName, suffix, keyType, valueType, nullKeyV, nullValueV)\
+ scope void init##suffix(typeName##t *tree) {\
+ wavlInit(tree, nullKeyV, nullValueV);\
+ }\
+ internal typeName##Nodet* newNode##suffix(keyType k, typeName##Nodet *parent) {\
+ ret wavlNewNode(k, parent);\
+ }\
+ internal int nodeHeight##suffix(typeName##Nodet *node) {\
+ if (!node) {\
+ ret 0;\
+ }\
+ ret (1 + maxV(nodeHeight##suffix(node->left), nodeHeight##suffix(node->right)));\
+ }\
+ scope int height##suffix(typeName##t *tree) {\
+ ret nodeHeight##suffix(tree->root) - 1;\
+ }\
+ internal void freeNodes##suffix(typeName##Nodet *node) {\
+ if (!node) ret;\
+ freeNodes##suffix(node->left);\
+ freeNodes##suffix(node->right);\
+ FREEFUNC(&node->key, &node->value);\
+ free(node);\
+ }\
+ scope void empty##suffix(typeName##t *tree) {\
+ freeNodes##suffix(tree->root);\
+ tree->modCount++;\
+ tree->count = 0;\
+ tree->root = NULL;\
+ tree->rotations = 0;\
+ }\
+ scope bool isEmpty##suffix(typeName##t *tree) {\
+ ret tree->root == NULL;\
+ }\
+ scope void free##suffix(typeName##t *tree) {\
+ empty##suffix(tree);\
+ /* TODO free internal buffers */\
+ }\
+ /** insert new (key,value), fail when the key already exists */\
+ scope bool add##suffix(typeName##t *tree, keyType key, valueType value) {\
+ bool isnew;\
+ var node = addOrFindNode##suffix(tree, key, &isnew);\
+ if (isnew) {\
+ node->value = value;\
+ }\
+ ret isnew;\
+ }\
+ scope valueType* addOrFind##suffix(typeName##t *tree, keyType key, bool *isnew) {\
+ var node = addOrFindNode##suffix(tree, key, isnew);\
+ return &node->value;\
+ }\
+ scope valueType* find##suffix(typeName##t *tree, keyType key) {\
+ var node = getNode##suffix(tree, key);\
+ ret !node ? NULL : &node->value;\
+ }\
+ scope valueType get##suffix(typeName##t *tree, keyType key) {\
+ var node = getNode##suffix(tree, key);\
+ ret !node ? tree->nullValue : node->value;\
+ }\
+ scope keyType getKey##suffix(typeName##t *tree, keyType key) {\
+ var node = getNode##suffix(tree, key);\
+ ret !node ? tree->nullKey : node->key;\
+ }\
+ scope void del##suffix(typeName##t *tree, keyType key) {\
+ var node = getNode##suffix(tree, key);\
+ if (!node) ret;\
+ delNode##suffix(tree, node);\
+ }\
+ internal bool needToRotateLeft##suffix(typeName##Nodet *P) {\
+ if (!P->left) {\
+ /* rank of sibling is -1 */\
+ if (P->rank == 1)\
+ ret true;\
+ ret false;\
+ }\
+ elif (P->rank >= P->left->rank + 2)\
+ ret true;\
+ ret false;\
+ }\
+ internal bool needToRotateRight##suffix(typeName##Nodet *P) {\
+ if (!P->right) {\
+ /* rank of sibling is -1 */\
+ if (P->rank == 1)\
+ ret true;\
+ ret false;\
+ }\
+ elif (P->rank >= P->right->rank + 2)\
+ ret true;\
+ ret false;\
+ }\
+ internal void rotateLeft##suffix(typeName##t *tree, typeName##Nodet *P) {\
+ typeName##Nodet *node = P->right;\
+ P->right = node->left;\
+ if (node->left)\
+ node->left->parent = P;\
+ node->parent = P->parent;\
+ if (!P->parent)\
+ tree->root = node;\
+ elif (P->parent->left == P)\
+ P->parent->left = node;\
+ else\
+ P->parent->right = node;\
+ node->left = P;\
+ P->parent = node;\
+ tree->rotations++;\
+ }\
+ internal void rotateRight##suffix(typeName##t *tree, typeName##Nodet *P) {\
+ typeName##Nodet *node = P->left;\
+ P->left = node->right;\
+ if (node->right)\
+ node->right->parent = P;\
+ node->parent = P->parent;\
+ if (!P->parent)\
+ tree->root = node;\
+ elif (P->parent->right == P)\
+ P->parent->right = node;\
+ else\
+ P->parent->left = node;\
+ node->right = P;\
+ P->parent = node;\
+ tree->rotations++;\
+ }\
+ /**
+ * - 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.
+ */\
+ internal void balanceAfterInsert##suffix(typeName##t *tree, typeName##Nodet *node) {\
+ for(typeName##Nodet *P = node->parent ; P && (node->rank+1 != P->rank) ; node->rank++) {\
+ if (P->left == node) {\
+ /* new node was added on the left */\
+ if (needToRotateRight##suffix(P)) {\
+ if (!node->left || node->rank >= node->left->rank+2) {\
+ node->rank--;\
+ node->right->rank++;\
+ rotateLeft##suffix(tree, node);\
+ }\
+ P->rank--;\
+ rotateRight##suffix(tree, P);\
+ break;\
+ }\
+ }\
+ else {\
+ if (needToRotateLeft##suffix(P)) {\
+ if (!node->right || node->rank >= node->right->rank+2) {\
+ node->rank--;\
+ node->left->rank++;\
+ rotateRight##suffix(tree, node);\
+ }\
+ P->rank--;\
+ rotateLeft##suffix(tree, P);\
+ break;\
+ }\
+ }\
+ node = P;\
+ P = node->parent;\
+ }\
+ }\
+ scope typeName##Nodet* addOrFindNode##suffix(typeName##t *tree, keyType key, bool *isnew) {\
+ var O = tree->root;\
+ if (!O) {\
+ /* tree is empty, new node is root */\
+ *isnew = true;\
+ tree->root = newNode##suffix(key, NULL);\
+ tree->count = 1;\
+ tree->modCount++;\
+ ret tree->root;\
+ }\
+ \
+ /* Find the proper position for this new node */\
+ int cmp;\
+ typeName##Nodet *P;\
+ do {\
+ P = O;\
+ cmp = CMPFUNC(key, 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;\
+ elif (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 */\
+ *isnew = false;\
+ ret O;\
+ }\
+ /* If we would have run out of valid pointers in the direction we
+ * should be searching, then we are done */\
+ } while(O);\
+ \
+ *isnew = true;\
+ var e = newNode##suffix(key, P);\
+ /*logI("New %p", e);*/\
+ if (cmp < 0) {\
+ P->left = e;\
+ }\
+ else {\
+ P->right = e;\
+ }\
+ \
+ if (!P->rank) {\
+ P->rank++;\
+ balanceAfterInsert##suffix(tree, P);\
+ }\
+ \
+ tree->count++;\
+ tree->modCount++;\
+ \
+ ret e;\
+ }\
+ scope typeName##Nodet* getNode##suffix(typeName##t *tree, keyType key) {\
+ var p = tree->root;\
+ while (p) {\
+ int cmp = CMPFUNC(key, p->key);\
+ if (cmp < 0)\
+ p = p->left;\
+ elif (cmp > 0)\
+ p = p->right;\
+ else {\
+ /*logI("Entry: %p", P);*/\
+ ret p;\
+ }\
+ }\
+ ret NULL;\
+ }\
+ internal int8_t rank##suffix(typeName##Nodet *node) {\
+ ret !node ? -1 : node->rank;\
+ }\
+ internal bool nodeIsTwoTwo##suffix(typeName##Nodet *node) {\
+ if (!node || !node->rank)\
+ ret false;\
+ if (node->rank == 1) {\
+ if (!node->left && !node->right)\
+ ret true;\
+ else\
+ ret false;\
+ }\
+ else\
+ ret (node->left->rank == node->right->rank && (node->left->rank + 2 == node->rank));\
+ }\
+ internal void balanceAfterDeleteWAVL##suffix(typeName##t *tree, typeName##Nodet *parent, typeName##Nodet *sibling, int8_t nodeRank) {\
+ typeName##Nodet *node;\
+ int deltaRank = parent->rank - nodeRank;\
+ while (deltaRank == 3 || parent->rank == 1 && nodeIsTwoTwo##suffix(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##suffix(sibling->left);\
+ int deltaRankSiblingR = sibling->rank - rank##suffix(sibling->right);\
+ \
+ if (deltaRankSiblingL == 2 && deltaRankSiblingR == 2) {\
+ /* "double demote" in the orig. paper since both parent & sibling demote */\
+ parent->rank--;\
+ sibling->rank--;\
+ }\
+ elif (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##suffix(tree, parent);\
+ }\
+ else {\
+ /* double rotation */\
+ parent->rank -= 2;\
+ sibling->rank--;\
+ sibling->left->rank += 2;\
+ rotateRight##suffix(tree, sibling);\
+ rotateLeft##suffix(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##suffix(tree, parent);\
+ }\
+ else {\
+ /* double rotation */\
+ parent->rank -= 2;\
+ sibling->rank--;\
+ sibling->right->rank += 2;\
+ rotateLeft##suffix(tree, sibling);\
+ rotateRight##suffix(tree, parent);\
+ }\
+ break;\
+ }\
+ }\
+ \
+ if (!parent->parent)\
+ ret;\
+ node = parent;\
+ parent = parent->parent;\
+ sibling = (parent->left == node) ? parent->right : parent->left;\
+ deltaRank = parent->rank - node->rank;\
+ }\
+ }\
+ scope typeName##Nodet *getFirstEntry##suffix(typeName##t *tree) {\
+ typeName##Nodet *P = tree->root;\
+ if (P) {\
+ while (P->left)\
+ P = P->left;\
+ }\
+ ret P;\
+ }\
+ scope typeName##Nodet *getLastEntry##suffix(typeName##t *tree) {\
+ typeName##Nodet *P = tree->root;\
+ if (P) {\
+ while (P->right)\
+ P = P->right;\
+ }\
+ ret P;\
+ }\
+ internal typeName##Nodet *successor##suffix(typeName##Nodet *X) {\
+ if (!X)\
+ ret NULL;\
+ elif (X->right != NULL) {\
+ typeName##Nodet *P = X->right;\
+ while (P->left)\
+ P = P->left;\
+ ret P;\
+ }\
+ else {\
+ typeName##Nodet *P = X->parent;\
+ typeName##Nodet *ch = X;\
+ while (P && ch == P->right) {\
+ ch = P;\
+ P = P->parent;\
+ }\
+ ret P;\
+ }\
+ }\
+ internal typeName##Nodet *predecessor##suffix(typeName##Nodet *X) {\
+ if (!X)\
+ ret NULL;\
+ elif (X->left) {\
+ typeName##Nodet *P = X->left;\
+ while (P->right)\
+ P = P->right;\
+ ret P;\
+ }\
+ else {\
+ typeName##Nodet *P = X->parent;\
+ typeName##Nodet *ch = X;\
+ while (P && ch == P->left) {\
+ ch = P;\
+ P = P->parent;\
+ }\
+ ret P;\
+ }\
+ }\
+ scope void delNode##suffix(typeName##t *tree, typeName##Nodet *node) {\
+ tree->modCount++;\
+ tree->count--;\
+ \
+ /* If strictly internal, copy successor's element to p and then make node
+ * point to successor. */\
+ if (node->left && node->right) {\
+ typeName##Nodet *X = predecessor##suffix(node);\
+ node->key = X->key;\
+ node->value = X->value;\
+ node = X;\
+ } /* p has 2 children */\
+ \
+ typeName##Nodet *replacement = (node->left ? node->left : node->right);\
+ if (replacement) {\
+ /* Link replacement to parent */\
+ replacement->parent = node->parent;\
+ typeName##Nodet *sibling = NULL;\
+ if (!node->parent) {\
+ tree->root = replacement;\
+ FREEFUNC(&node->key, &node->value);\
+ free(node);\
+ ret;\
+ }\
+ elif (node == node->parent->left) {\
+ node->parent->left = replacement;\
+ sibling = node->parent->right;\
+ }\
+ else {\
+ node->parent->right = replacement;\
+ sibling = node->parent->left;\
+ }\
+ \
+ /* Null out links so they are OK to use by fixAfterDeletion. */\
+ node->left = node->right = node->parent = NULL;\
+ FREEFUNC(&node->key, &node->value);\
+ free(node);\
+ balanceAfterDeleteWAVL##suffix(tree, replacement->parent, sibling, replacement->rank);\
+ }\
+ elif (!node->parent) {\
+ /* return if we are the only node. */\
+ FREEFUNC(&node->key, &node->value);\
+ free(node);\
+ tree->root = NULL;\
+ ret;\
+ }\
+ else {\
+ /* No children. Use self as phantom replacement and unlink. */\
+ typeName##Nodet *fixPoint = node->parent;\
+ typeName##Nodet *sibling = NULL;\
+ \
+ if (node == node->parent->left) {\
+ node->parent->left = NULL;\
+ sibling = fixPoint->right;\
+ }\
+ elif (node == node->parent->right) {\
+ node->parent->right = NULL;\
+ sibling = fixPoint->left;\
+ }\
+ node->parent = NULL;\
+ int8_t rk = --node->rank;\
+ FREEFUNC(&node->key, &node->value);\
+ free(node);\
+ balanceAfterDeleteWAVL##suffix(tree, fixPoint, sibling, rk);\
+ }\
+ }\
+ scope void iterStart##suffix(typeName##t *tree, typeName##Nodet *first) {\
+ tree->expectedModCount = tree->modCount;\
+ tree->lastReturned = NULL;\
+ tree->next = first;\
+ }\
+ scope bool hasNext##suffix(typeName##t *tree) {\
+ ret tree->next != NULL;\
+ }\
+ scope typeName##Nodet *next##suffix(typeName##t *tree) {\
+ typeName##Nodet *e = tree->next;\
+ if (!e) ret NULL;\
+ if (tree->modCount != tree->expectedModCount) ret NULL;\
+ tree->next = successor##suffix(e);\
+ tree->lastReturned = e;\
+ ret e;\
+ }\
+ scope typeName##Nodet *prev##suffix(typeName##t *tree) {\
+ typeName##Nodet *e = tree->next;\
+ if (!e) ret NULL;\
+ if (tree->modCount != tree->expectedModCount) ret NULL;\
+ tree->next = predecessor##suffix(e);\
+ tree->lastReturned = e;\
+ ret e;\
+ }\
+ scope bool removeCurrent##suffix(typeName##t *tree) {\
+ if (!tree->lastReturned) ret false;\
+ if (tree->modCount != tree->expectedModCount) ret false;\
+ /* // deleted entries are replaced by their successors */\
+ /* if (tree->lastReturned.left && tree->lastReturned.right) */\
+ /* tree->next = tree->lastReturned; */\
+ delNode##suffix(tree, tree->lastReturned);\
+ tree->expectedModCount = tree->modCount;\
+ tree->lastReturned = NULL;\
+ ret true;\
+ }
+
+
+#define wavlNodeT(typeName, keyType, valueType)\
+ typ struct typeName typeName;\
+ struct typeName {\
+ keyType key;\
+ valueType value;\
+ typeName *left;\
+ typeName *right;\
+ typeName *parent;\
+ i8 rank;\
+ }
+
+#define wavlTreeT(typeName, nodeType, keyType, valueType)\
+ typ struct {\
+ size_t count; /* number of entries in the tree */\
+ size_t modCount; /* number of structural modifications to the tree */\
+ size_t rotations;\
+ nodeType *root;\
+ keyType nullKey;\
+ valueType nullValue;\
+ /* private iterator */\
+ size_t expectedModCount;\
+ nodeType *next;\
+ nodeType *lastReturned;\
+ /* end private iterator */\
+ } typeName
+
+#define wavlInit(t, nullKeyV, nullValueV) do {\
+ if (!t) break;\
+ t->count = 0;\
+ t->modCount = 0;\
+ t->rotations = 0;\
+ t->root = NULL;\
+ t->nullKey = nullKeyV;\
+ t->nullValue = nullValueV;\
+ t->expectedModCount = -1;\
+ t->next = NULL;\
+ t->lastReturned = NULL;\
+ } while(0)
+
+#define wavlNewNode(k, parent) ({\
+ typeof(parent) r = malloc(sizeof(*parent));\
+ if (r) {\
+ r->key = k;\
+ r->left = NULL;\
+ r->right = NULL;\
+ r->parent = parent;\
+ r->rank = 0;\
+ }\
+ r;\
+ })
+
+
+// vim: set expandtab ts=2 sw=2:
diff --git a/wavlTest.c b/wavlTest.c
@@ -0,0 +1,441 @@
+#! /usr/bin/env sheepy
+/* or direct path to sheepy: #! /usr/local/bin/sheepy */
+
+/* Libsheepy documentation: http://spartatek.se/libsheepy/ */
+#include "libsheepyObject.h"
+#include "wavl.h"
+
+int argc; char **argv;
+
+/* enable/disable logging */
+/* #undef pLog */
+/* #define pLog(...) */
+
+wavlDef(/* scope */, w /* wt wavl tree type and wNodet node type */, W /* function suffix: initW...*/, u32 /* keyType*/, u32 /* valueType */);
+
+void freeKV(u32* /* keyType */ key, u32* /* valueType*/ value) {
+}
+
+#define FREEFUNC freeKV
+#define CMPFUNC CMP
+
+wavlFunctions(/* scope */, w /* wt wavl tree type*/, W /* function suffix: initW...*/, u32 /* keyType*/, u32 /* valueType */, -1 /* null key */, -1 /* null value */);
+
+/* declare tree */
+wt 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() {
+ emptyW(&x);
+ addW(&x,2, 2);
+ assertEquals(0, heightW(&x));
+ addW(&x,3, 3);
+ assertEquals(1, heightW(&x));
+ addW(&x,1, 1);
+ addW(&x,0, 0);
+ assertEquals(2, heightW(&x));
+}
+
+void testInsertDoNothing() {
+ emptyW(&x);
+ addW(&x,2, 2);
+ addW(&x,3, 3);
+ assertEquals(0, x.rotations);
+ assertEquals(2, (int)x.root->value);
+ assertEquals(1, x.root->rank);
+
+ addW(&x,1, 1);
+ assertEquals(2, (int)x.root->value);
+
+ assertEquals(1, x.root->rank);
+ assertEquals(0, x.rotations);
+}
+
+void testInsert100() {
+ emptyW(&x);
+ for (int i=0; i<100; i++)
+ addW(&x,i, i);
+ assertEquals(100, x.count);
+}
+
+void testInsertMany() {
+ emptyW(&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++)
+ addW(&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 testInsertOneLeftRotation() {
+ emptyW(&x);
+ addW(&x,1, 1);
+ addW(&x,2, 2);
+ addW(&x,3, 3);
+
+ assertEquals(1, x.root->rank);
+ assertEquals(2, (int) x.root->value);
+ assertEquals(0, x.root->right->rank);
+}
+
+void testInsertTwoLeftRotations() {
+ emptyW(&x);
+ addW(&x,1, 1);
+ addW(&x,2, 2);
+ addW(&x,3, 3);
+ addW(&x,4, 4);
+ addW(&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() {
+ emptyW(&x);
+ addW(&x,1, 1);
+ addW(&x,2, 2);
+ addW(&x,3, 3);
+ addW(&x,4, 4);
+ addW(&x,5, 5);
+ addW(&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() {
+ emptyW(&x);
+ addW(&x,3, 3);
+ addW(&x,1, 1);
+ addW(&x,2, 2);
+
+ assertEquals(2, x.rotations);
+ assertEquals(2, (int) x.root->value);
+ assertEquals(1, x.root->rank);
+}
+
+void testInsertRightLeftRotation() {
+ emptyW(&x);
+ addW(&x,3, 3);
+ addW(&x,6, 6);
+ addW(&x,4, 4);
+
+ assertEquals(2, x.rotations);
+ assertEquals(4, (int) x.root->value);
+ assertEquals(1, x.root->rank);
+}
+
+void testInsertBuildFibonacciTree() {
+ emptyW(&x);
+ addW(&x,8, 8);
+ addW(&x,5, 5);
+ addW(&x,11, 11);
+ // 3,7,10,12
+ addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,12, 12);
+ // 2,4,6,9
+ addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9);
+ addW(&x,1, 1);
+ logI("Rotations: %d", x.rotations);
+ assertEquals(0, x.rotations);
+}
+
+void testInsertFibAfterDelete() {
+ emptyW(&x);
+ addW(&x,8, 8); // root
+ addW(&x,5, 5); addW(&x,11, 11);
+ // 3,7,10,12
+ addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,12, 12);
+ // 2,4,6,9
+ addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9);
+ addW(&x,1, 1);
+
+ delW(&x, 12);
+ //TODO
+}
+
+void testInsert6() {
+ emptyW(&x);
+ for (int i=0; i<6; i++)
+ addW(&x,i, i);
+ assertEquals(3, x.rotations);
+ assertEquals(3, (int) x.root->value);
+ // TODO x.inOrderTraversal(x.root);
+}
+
+void testInsertTwoRightRotations() {
+ emptyW(&x);
+ addW(&x,5, 5);
+ addW(&x,4, 4);
+ addW(&x,3, 3);
+ addW(&x,2, 4);
+ addW(&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 testDeleteNoRotationWAVL() {
+ emptyW(&x);
+ addW(&x,2, 2);
+ addW(&x,3, 3);
+ addW(&x,1, 1);
+ assertEquals(2, (int)x.root->value);
+
+ delW(&x,3);
+ assertEquals(1, x.root->rank);
+ assertEquals(0, x.rotations);
+
+ // remove root
+ delW(&x,2);
+ delW(&x,1);
+ assertEquals(0, x.count);
+}
+
+void testDeleteOneRightRotationWAVL() {
+ emptyW(&x);
+ addW(&x,10, 10);
+ addW(&x,8, 8); addW(&x,12, 12);
+ addW(&x,6, 6);
+
+ delW(&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 testDeleteOneRightRotationSiblingBalancedWAVL() {
+ emptyW(&x);
+ addW(&x,10, 10);
+ addW(&x,8, 8);addW(&x,12, 12);
+ addW(&x,6,6);addW(&x,9,9);
+
+ assertEquals(0, x.rotations);
+
+ delW(&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 testDeleteOneLeftRightRotationWAVL() {
+ emptyW(&x);
+ addW(&x,10, 10);
+ addW(&x,8, 8);
+ addW(&x,12, 12);
+ addW(&x,9, 9);
+
+ delW(&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 testDelete5WAVL() {
+ emptyW(&x);
+ for (int i=0; i<6; i++)
+ addW(&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);
+ delW(&x,i);
+ }
+
+ //logI("Rotations after remove: %d\n", x.rotations);
+ assertEquals(1, x.count);
+ assertEquals(0, x.root->rank);
+
+ delW(&x,5);
+}
+
+void testDeleteFibonacciTreeWAVL() {
+ emptyW(&x);
+ addW(&x,8, 8); // root
+ addW(&x,5, 5); addW(&x,11, 11);
+ // 3,7,10,12
+ addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,12, 12);
+ // 2,4,6,9
+ addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9);
+ addW(&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) -
+
+ delW(&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() {
+ emptyW(&x);
+ addW(&x,8, 8); // root
+ logVarG(getW(&x, 8));
+ addW(&x,5, 5); addW(&x,12, 12);
+ // 3,7,10,12
+ addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,13, 13);
+ // 2,4,6,9,11
+ addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9); addW(&x,11,11);
+ addW(&x,1, 1);
+
+ //x.inOrderTraversal(x.root);
+ //puts("\n");
+
+ delW(&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() {
+ emptyW(&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++) {
+ logI("put: %d,\n", a[i]);
+ addW(&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]);
+ delW(&x, a[i]);
+ }
+
+ // TODO 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);
+
+ initW(&x);
+
+ testDelete5WAVL();
+ testDeleteAlmostFibonacciTreeWAVL();
+ testDeleteFibonacciTreeWAVL();
+ testDeleteManyWAVL();
+ testDeleteNoRotationWAVL();
+ testDeleteOneLeftRightRotationWAVL();
+ testDeleteOneRightRotationSiblingBalancedWAVL();
+ testDeleteOneRightRotationWAVL();
+ testInsert100();
+ testInsert6();
+ testInsertBuildFibonacciTree();
+ testInsertDoNothing();
+ testInsertFibAfterDelete();
+ testInsertLeftRightRotation();
+ testInsertMany();
+ testInsertOneLeftRotation();
+ testInsertRightLeftRotation();
+ testInsertThreeLeftRotations();
+ testInsertTwoLeftRotations();
+ testInsertTwoRightRotations();
+ testTreeHeight();
+
+ freeW(&x);
+}
+// vim: set expandtab ts=2 sw=2:
