Mercurial > hg > ucx / changeset

     1.1 --- a/test/avl_tests.c	Sat Jul 15 20:46:18 2017 +0200
     1.2 +++ b/test/avl_tests.c	Sat Jul 15 22:36:29 2017 +0200
     1.3 @@ -282,3 +282,36 @@
     1.4      
     1.5      ucx_avl_free(tree);
     1.6  }
     1.7 +
     1.8 +UCX_TEST(test_ucx_avl_traverse) {
     1.9 +    UcxAVLTree *tree = ucx_avl_new(ucx_ptrcmp);
    1.10 +    
    1.11 +    size_t len = 12;
    1.12 +
    1.13 +    int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13};
    1.14 +    int val_ordered[] = {-30, -11, -5, 1, 3, 4, 10, 12, 13, 14, 15, 20};
    1.15 +    
    1.16 +    for (size_t i = 0 ; i < len ; i++) {
    1.17 +        ucx_avl_put(tree, val[i], &(val[i]));
    1.18 +    }
    1.19 +    
    1.20 +    UCX_TEST_BEGIN
    1.21 +    
    1.22 +    UcxAVLNode* node = ucx_avl_get_node(tree, (intptr_t) val_ordered[0]);
    1.23 +    for (size_t i = 0 ; i < len ; i++) {
    1.24 +        UCX_TEST_ASSERT(node->key == val_ordered[i], "AVL successor failed");
    1.25 +        node = ucx_avl_succ(node);
    1.26 +    }
    1.27 +    UCX_TEST_ASSERT(!node, "AVL maximum incorrectly has a successor");
    1.28 +    
    1.29 +    node = ucx_avl_get_node(tree, (intptr_t) val_ordered[len-1]);
    1.30 +    for (size_t i = len ; i > 0 ; i--) {
    1.31 +        UCX_TEST_ASSERT(node->key == val_ordered[i-1],"AVL predecessor failed");
    1.32 +        node = ucx_avl_pred(node);
    1.33 +    }
    1.34 +    UCX_TEST_ASSERT(!node, "AVL minimum incorrectly has a predecessor");
    1.35 +    
    1.36 +    UCX_TEST_END
    1.37 +    
    1.38 +    ucx_avl_free(tree);
    1.39 +}

     2.1 --- a/test/avl_tests.h	Sat Jul 15 20:46:18 2017 +0200
     2.2 +++ b/test/avl_tests.h	Sat Jul 15 22:36:29 2017 +0200
     2.3 @@ -39,6 +39,7 @@
     2.4  UCX_TEST(test_ucx_avl_put);
     2.5  UCX_TEST(test_ucx_avl_remove);
     2.6  UCX_TEST(test_ucx_avl_find);
     2.7 +UCX_TEST(test_ucx_avl_traverse);
     2.8  
     2.9  #ifdef	__cplusplus
    2.10  }

     3.1 --- a/test/main.c	Sat Jul 15 20:46:18 2017 +0200
     3.2 +++ b/test/main.c	Sat Jul 15 22:36:29 2017 +0200
     3.3 @@ -228,6 +228,7 @@
     3.4          ucx_test_register(suite, test_ucx_avl_put);
     3.5          ucx_test_register(suite, test_ucx_avl_remove);
     3.6          ucx_test_register(suite, test_ucx_avl_find);
     3.7 +        ucx_test_register(suite, test_ucx_avl_traverse);
     3.8  
     3.9          ucx_test_run(suite, stdout);
    3.10          fflush(stdout);

     4.1 --- a/ucx/avl.c	Sat Jul 15 20:46:18 2017 +0200
     4.2 +++ b/ucx/avl.c	Sat Jul 15 22:36:29 2017 +0200
     4.3 @@ -314,3 +314,43 @@
     4.4  size_t ucx_avl_count(UcxAVLTree *tree) {
     4.5      return ucx_avl_countn(tree->root);
     4.6  }
     4.7 +
     4.8 +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
     4.9 +    if (node->left) {
    4.10 +        UcxAVLNode* n = node->left;
    4.11 +        while (n->right) {
    4.12 +            n = n->right;
    4.13 +        }
    4.14 +        return n;
    4.15 +    } else {
    4.16 +        UcxAVLNode* n = node;
    4.17 +        while (n->parent) {
    4.18 +            if (n->parent->right == n) {
    4.19 +                return n->parent;
    4.20 +            } else {
    4.21 +                n = n->parent;
    4.22 +            }
    4.23 +        }
    4.24 +        return NULL;
    4.25 +    }
    4.26 +}
    4.27 +
    4.28 +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
    4.29 +    if (node->right) {
    4.30 +        UcxAVLNode* n = node->right;
    4.31 +        while (n->left) {
    4.32 +            n = n->left;
    4.33 +        }
    4.34 +        return n;
    4.35 +    } else {
    4.36 +        UcxAVLNode* n = node;
    4.37 +        while (n->parent) {
    4.38 +            if (n->parent->left == n) {
    4.39 +                return n->parent;
    4.40 +            } else {
    4.41 +                n = n->parent;
    4.42 +            }
    4.43 +        }
    4.44 +        return NULL;
    4.45 +    }
    4.46 +}

     5.1 --- a/ucx/avl.h	Sat Jul 15 20:46:18 2017 +0200
     5.2 +++ b/ucx/avl.h	Sat Jul 15 22:36:29 2017 +0200
     5.3 @@ -303,6 +303,22 @@
     5.4   */
     5.5  size_t ucx_avl_count(UcxAVLTree *tree);
     5.6  
     5.7 +/**
     5.8 + * Finds the in-order predecessor of the given node.
     5.9 + * @param node an AVL node
    5.10 + * @return the in-order predecessor of the given node, or <code>NULL</code> if
    5.11 + * the given node is the in-order minimum
    5.12 + */
    5.13 +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node);
    5.14 +
    5.15 +/**
    5.16 + * Finds the in-order successor of the given node.
    5.17 + * @param node an AVL node
    5.18 + * @return the in-order successor of the given node, or <code>NULL</code> if
    5.19 + * the given node is the in-order maximum
    5.20 + */
    5.21 +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node);
    5.22 +
    5.23  #ifdef	__cplusplus
    5.24  }
    5.25  #endif