Mercurial > hg > ucx / changeset

--- a/test/avl_tests.c	Sat Jul 15 20:46:18 2017 +0200
+++ b/test/avl_tests.c	Sat Jul 15 22:36:29 2017 +0200
@@ -282,3 +282,36 @@
     
     ucx_avl_free(tree);
 }
+
+UCX_TEST(test_ucx_avl_traverse) {
+    UcxAVLTree *tree = ucx_avl_new(ucx_ptrcmp);
+    
+    size_t len = 12;
+
+    int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13};
+    int val_ordered[] = {-30, -11, -5, 1, 3, 4, 10, 12, 13, 14, 15, 20};
+    
+    for (size_t i = 0 ; i < len ; i++) {
+        ucx_avl_put(tree, val[i], &(val[i]));
+    }
+    
+    UCX_TEST_BEGIN
+    
+    UcxAVLNode* node = ucx_avl_get_node(tree, (intptr_t) val_ordered[0]);
+    for (size_t i = 0 ; i < len ; i++) {
+        UCX_TEST_ASSERT(node->key == val_ordered[i], "AVL successor failed");
+        node = ucx_avl_succ(node);
+    }
+    UCX_TEST_ASSERT(!node, "AVL maximum incorrectly has a successor");
+    
+    node = ucx_avl_get_node(tree, (intptr_t) val_ordered[len-1]);
+    for (size_t i = len ; i > 0 ; i--) {
+        UCX_TEST_ASSERT(node->key == val_ordered[i-1],"AVL predecessor failed");
+        node = ucx_avl_pred(node);
+    }
+    UCX_TEST_ASSERT(!node, "AVL minimum incorrectly has a predecessor");
+    
+    UCX_TEST_END
+    
+    ucx_avl_free(tree);
+}

--- a/test/avl_tests.h	Sat Jul 15 20:46:18 2017 +0200
+++ b/test/avl_tests.h	Sat Jul 15 22:36:29 2017 +0200
@@ -39,6 +39,7 @@
 UCX_TEST(test_ucx_avl_put);
 UCX_TEST(test_ucx_avl_remove);
 UCX_TEST(test_ucx_avl_find);
+UCX_TEST(test_ucx_avl_traverse);
 
 #ifdef	__cplusplus
 }

--- a/test/main.c	Sat Jul 15 20:46:18 2017 +0200
+++ b/test/main.c	Sat Jul 15 22:36:29 2017 +0200
@@ -228,6 +228,7 @@
         ucx_test_register(suite, test_ucx_avl_put);
         ucx_test_register(suite, test_ucx_avl_remove);
         ucx_test_register(suite, test_ucx_avl_find);
+        ucx_test_register(suite, test_ucx_avl_traverse);
 
         ucx_test_run(suite, stdout);
         fflush(stdout);

--- a/ucx/avl.c	Sat Jul 15 20:46:18 2017 +0200
+++ b/ucx/avl.c	Sat Jul 15 22:36:29 2017 +0200
@@ -314,3 +314,43 @@
 size_t ucx_avl_count(UcxAVLTree *tree) {
     return ucx_avl_countn(tree->root);
 }
+
+UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
+    if (node->left) {
+        UcxAVLNode* n = node->left;
+        while (n->right) {
+            n = n->right;
+        }
+        return n;
+    } else {
+        UcxAVLNode* n = node;
+        while (n->parent) {
+            if (n->parent->right == n) {
+                return n->parent;
+            } else {
+                n = n->parent;
+            }
+        }
+        return NULL;
+    }
+}
+
+UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
+    if (node->right) {
+        UcxAVLNode* n = node->right;
+        while (n->left) {
+            n = n->left;
+        }
+        return n;
+    } else {
+        UcxAVLNode* n = node;
+        while (n->parent) {
+            if (n->parent->left == n) {
+                return n->parent;
+            } else {
+                n = n->parent;
+            }
+        }
+        return NULL;
+    }
+}

--- a/ucx/avl.h	Sat Jul 15 20:46:18 2017 +0200
+++ b/ucx/avl.h	Sat Jul 15 22:36:29 2017 +0200
@@ -303,6 +303,22 @@
  */
 size_t ucx_avl_count(UcxAVLTree *tree);
 
+/**
+ * Finds the in-order predecessor of the given node.
+ * @param node an AVL node
+ * @return the in-order predecessor of the given node, or <code>NULL</code> if
+ * the given node is the in-order minimum
+ */
+UcxAVLNode* ucx_avl_pred(UcxAVLNode* node);
+
+/**
+ * Finds the in-order successor of the given node.
+ * @param node an AVL node
+ * @return the in-order successor of the given node, or <code>NULL</code> if
+ * the given node is the in-order maximum
+ */
+UcxAVLNode* ucx_avl_succ(UcxAVLNode* node);
+
 #ifdef	__cplusplus
 }
 #endif