commit fa9df52519f6c34aea9e2ca66f8f8146499e61fc
parent 2b8ee36374b5189c645c0994f41cf63721794c90
Author: Remy Noulin <loader2x@gmail.com>
Date: Sat, 29 Dec 2018 20:37:12 +0100
add iterator
README.md | 10 +++
main.c | 8 ++-
wavlTree.c | 162 ++++++++++++++++++++++++++++++---------------
wavlTree.h | 24 ++++++-
wavlTreeNamespaceCleanup.h | 13 ----
5 files changed, 148 insertions(+), 69 deletions(-)
Diffstat:
5 files changed, 148 insertions(+), 69 deletions(-)
diff --git a/README.md b/README.md
@@ -0,0 +1,10 @@
+# this repo
+WAVL tree implementation in C, inspired by (dmcmanam/bbst-showdown [JAVA implementation])[https://github.com/dmcmanam/bbst-showdown].
+All tests have passed and there is no memory leak(tested with valgrind).
+
+# What is WAVL tree
+
+WAVL tree is an attempt to combine the best characteristics of a AVL trees and red-black trees. Just inserting into a WAVL tree will
+build the same tree as an AVL tree - one that is more strictly balanced than a red-black tree so WAVL trees can be expected to
+perform better in situations where red-black trees become more unbalanced. Delete in WAVL is slightly simpler than delete for AVL
+trees in that WAVL deletes perform only 1 or 2 rotations and stop instead of potentially all the way to the root.
diff --git a/main.c b/main.c
@@ -31,7 +31,13 @@ int main(int ARGC, char** ARGV) {
var n = tree.get(&tree, 10);
logVarG(n);
- tree.inOrderTraversal(tree.root);
+ // tree.inOrderTraversal(tree.root);
+ tree.iterStart(&tree, tree.getFirstEntry(&tree));
+ wavlTreenodet *node;
+ while(node = tree.nextEntry(&tree)) {
+ logVarG(node->key);
+ logVarG(node->value);
+ }
logVarG(tree.remove(&tree, 10));
diff --git a/wavlTree.c b/wavlTree.c
@@ -16,21 +16,6 @@
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);
@@ -46,8 +31,8 @@ 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 void balanceAfterDeleteWAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank);
+static void balanceAfterDeleteAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank);
static nodet *nodeNew(keyt k, valuet v, nodet *parent) {
nodet *r = malloc(sizeof(nodet));
@@ -164,20 +149,22 @@ static valuet put(t *tree, keyt k, valuet v) {
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");
+
+ /* 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);
+ printf("value %d, rank %d\n", x.value, x.rank);
inOrderTraversal(x.right);
}
@@ -338,9 +325,9 @@ static void deleteEntry(t *tree, nodet *P) {
p.left = p.right = p.parent = NULL;
freeP(P);
if (w.deleteWAVL)
- fixAfterDeleteWAVL(tree, replacement->parent, sibling, replacement->rank);
+ balanceAfterDeleteWAVL(tree, replacement->parent, sibling, replacement->rank);
else
- fixAfterDeleteAVL(tree, replacement->parent, sibling, replacement->rank);
+ balanceAfterDeleteAVL(tree, replacement->parent, sibling, replacement->rank);
}
else if (!p.parent) {
// return if we are the only node.
@@ -365,9 +352,9 @@ static void deleteEntry(t *tree, nodet *P) {
int8_t rk = --p.rank;
freeP(P);
if (w.deleteWAVL)
- fixAfterDeleteWAVL(tree, fixPoint, sibling, rk);
+ balanceAfterDeleteWAVL(tree, fixPoint, sibling, rk);
else
- fixAfterDeleteAVL(tree, fixPoint, sibling, rk);
+ balanceAfterDeleteAVL(tree, fixPoint, sibling, rk);
}
}
@@ -388,7 +375,7 @@ static bool nodeIsTwoTwo(nodet *node) {
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) {
+static void balanceAfterDeleteWAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank) {
nodet *node;
int deltaRank = parent->rank - nodeRank;
while (deltaRank == 3 || parent->rank == 1 && nodeIsTwoTwo(parent)) {
@@ -455,7 +442,7 @@ static void fixAfterDeleteWAVL(t *tree, nodet *parent, nodet *sibling, int8_t no
}
}
-static void fixAfterDeleteAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank) {
+static void balanceAfterDeleteAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank) {
nodet *node;
int balance;
if (!sibling)
@@ -533,8 +520,45 @@ static void clear(t *tree) {
w.deleteWAVL = false;
}
-// TODO getFirstEntry...
-// TODO add leftMost, rightMost
+static nodet *getFirstEntry(t *tree) {
+ nodet *P = w.root;
+ if (P) {
+ while (p.left)
+ P = p.left;
+ }
+ return P;
+}
+
+static nodet *getLastEntry(t *tree) {
+ nodet *P = w.root;
+ if (P) {
+ while (p.right)
+ P = p.right;
+ }
+ return P;
+}
+
+// TODO add leftMost, rightMost pointer in tree
+
+static nodet *successor(nodet *X) {
+ if (!X)
+ return NULL;
+ else if (x.right != NULL) {
+ nodet *P = x.right;
+ while (p.left)
+ P = p.left;
+ return P;
+ }
+ else {
+ nodet *P = x.parent;
+ nodet *ch = X;
+ while (P && ch == p.right) {
+ ch = P;
+ P = p.parent;
+ }
+ return P;
+ }
+}
static nodet *predecessor(nodet *X) {
if (!X)
@@ -546,25 +570,59 @@ static nodet *predecessor(nodet *X) {
return P;
}
else {
- nodet *P = x.parent;
+ nodet *P = x.parent;
nodet *ch = X;
while (P && ch == p.left) {
ch = P;
- P = p.parent;
+ P = p.parent;
}
return P;
}
}
-// TODO iterator
+static void iterStart(t *tree, nodet *first) {
+ w.expectedModCount = w.modCount;
+ w.lastReturned = NULL;
+ w.next = first;
+}
+
+static bool hasNext(t *tree) {
+ return w.next != NULL;
+}
+
+static nodet *nextEntry(t *tree) {
+ nodet *e = w.next;
+ if (!e) return NULL;
+ if (w.modCount != w.expectedModCount) return NULL;
+ w.next = successor(e);
+ w.lastReturned = e;
+ return e;
+}
+
+static nodet *prevEntry(t *tree) {
+ nodet *e = w.next;
+ if (!e) return NULL;
+ if (w.modCount != w.expectedModCount) return NULL;
+ w.next = predecessor(e);
+ w.lastReturned = e;
+ return e;
+}
+
+static bool removeCurrent(t *tree) {
+ if (!w.lastReturned) return false;
+ if (w.modCount != w.expectedModCount) return false;
+ /* // deleted entries are replaced by their successors */
+ /* if (w.lastReturned.left && w.lastReturned.right) */
+ /* w.next = w.lastReturned; */
+ deleteEntry(tree, w.lastReturned);
+ w.expectedModCount = w.modCount;
+ w.lastReturned = NULL;
+ return true;
+}
/**
* initialize tree data
*/
-/* #undef put */
-/* #undef get */
-/* #undef inOrderTraversal */
-/* #undef clear */
bool init(t *tree) {
if (!tree) return false;
@@ -574,19 +632,19 @@ bool init(t *tree) {
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;
+ w.getFirstEntry = getFirstEntry;
+ w.getLastEntry = getLastEntry;
+ w.iterStart = iterStart;
+ w.hasNext = hasNext;
+ w.nextEntry = nextEntry;
+ w.prevEntry = prevEntry;
+ w.removeCurrent = removeCurrent;
return true;
}
diff --git a/wavlTree.h b/wavlTree.h
@@ -34,8 +34,6 @@
#define St TOKENPASTE(WAVL_NAMESPACE, St)
#define init TOKENPASTE(WAVL_NAMESPACE, init)
-// TODO namespace cleanup
-
typedef int keyt;
typedef int valuet;
//typedef char* valuet;
@@ -60,6 +58,13 @@ 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);
+typedef nodet* (*getFirstEntryFt) (t *tree);
+typedef nodet* (*getLastEntryFt) (t *tree);
+typedef void (*iterStartFt) (t *tree, nodet *first);
+typedef bool (*hasNextFt) (t *tree);
+typedef nodet* (*nextEntryFt) (t *tree);
+typedef nodet* (*prevEntryFt) (t *tree);
+typedef bool (*removeCurrentFt) (t *tree);
struct St {
size_t count; // number of entries in the tree
@@ -67,13 +72,26 @@ struct St {
size_t rotations;
bool deleteWAVL;
nodet *root;
+
+ // private iterator
+ size_t expectedModCount;
+ nodet *next;
+ nodet *lastReturned;
+ // end private iterator
+
getFt get;
putFt put;
heightFt treeHeight;
removeKVFt remove;
inOrderTraversalFt inOrderTraversal;
clearFt clear;
-
+ getFirstEntryFt getFirstEntry;
+ getLastEntryFt getLastEntry;
+ iterStartFt iterStart;
+ hasNextFt hasNext;
+ nextEntryFt nextEntry;
+ prevEntryFt prevEntry;
+ removeCurrentFt removeCurrent;
};
bool init(t *tree);
diff --git a/wavlTreeNamespaceCleanup.h b/wavlTreeNamespaceCleanup.h
@@ -4,16 +4,3 @@
#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
