test/avl_tests.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "avl_tests.h"

#include <ucx/utils.h>

static int node_height(UcxAVLNode *node) {
    if(!node) {
        return 0;
    }
    
    int left = 0;
    int right = 0;
    if(node->left) {
        left = node_height(node->left);
    }
    if(node->right) {
        right = node_height(node->right);
    }
    
    return left > right ? left+1 : right+1;
}

static int check_tree(UcxAVLNode *node) {
    if(!node) {
        return 1;
    }
    
    int left_height = node_height(node->left);
    int right_height = node_height(node->right);
    int bf = -left_height + right_height;
    if(bf < -1 || bf > 1) {
        return 0;
    }
    int height = left_height > right_height ? left_height : right_height;
    height++;
    if(height != node->height) {
        return 0;
    }
    
    if(!check_tree(node->left)) {
        return 0;
    }
    if(!check_tree(node->right)) {
        return 0;
    }
    
    return 1;
}

UCX_TEST(test_ucx_avl_put) {
    UcxAVLTree *tree1 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree4 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree5 = ucx_avl_new(ucx_cmp_ptr);
    
    char *data1 = (char*)"data1";
    char *data2 = (char*)"data2";
    char *data3 = (char*)"data3";
    
    UCX_TEST_BEGIN
    
    ucx_avl_put(tree1, 2, (char*)data2);
    ucx_avl_put(tree1, 1, (char*)data1);
    ucx_avl_put(tree1, 3, (char*)data3);
    
    UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)");
    UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)");
    UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)");
    
    for(int i=0;i<100000;i++) {
        ucx_avl_put(tree2, i, data1);
    }
    UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
    
    for(int i=100000;i>=0;i--) {
        ucx_avl_put(tree3, i, data1);
    }
    UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
    
    for(int i=0;i<100;i++) {
        ucx_avl_put(tree4, i, data1);
    }
    for(int i=400;i<500;i++) {
        ucx_avl_put(tree4, i, data2);
    }
    for(int i=399;i>200;i--) {
        ucx_avl_put(tree4, i, data3);
    }
    for(int i=800;i<1000;i++) {
        ucx_avl_put(tree4, i, data1);
    }
    UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
    UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0");
    UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1");
    UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99");
    UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400");
    UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410");
    UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350");
    UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900");
    
    int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4};
    int len = sizeof(values) / sizeof(int);
    for(int i=0;i<len;i++) {
        ucx_avl_put(tree5, values[i], NULL);
    }
    UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)");
            
    UCX_TEST_END
    
    ucx_avl_free(tree1);
    ucx_avl_free(tree2);
    ucx_avl_free(tree3);
    ucx_avl_free(tree4);
    ucx_avl_free(tree5);
}

UCX_TEST(test_ucx_avl_remove) {
    UcxAVLTree *tree1 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree4 = ucx_avl_new(ucx_cmp_ptr);
    
    char *data1 = (char*)"data1";
    char *data2 = (char*)"data2";
    char *data3 = (char*)"data3";
    
    UCX_TEST_BEGIN
    ucx_avl_put(tree1, 2, (char*)data2);
    ucx_avl_put(tree1, 1, (char*)data1);
    ucx_avl_put(tree1, 3, (char*)data3);
    void *val;
    ucx_avl_remove_s(tree1, 3, NULL, &val);
    
    UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    UCX_TEST_ASSERT(val == data3,
            "wrong return value for key: 1 (tree1)");
    UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)");
    
    ucx_avl_remove_s(tree1, 2, NULL, &val);
    UCX_TEST_ASSERT(val == data2,
            "wrong return value for key: 2 (tree1)");
    UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    
    ucx_avl_remove_s(tree1, 1, NULL, &val);
    UCX_TEST_ASSERT(val == data1,
            "wrong return value for key: 1 (tree1)");
    UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
    UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)");
    
    
    for(int i=0;i<20;i++) {
        if(i==10) {
            ucx_avl_put(tree2, i, data3);
        } else if(i==15) {
            ucx_avl_put(tree2, i, data2);
        } else {
            ucx_avl_put(tree2, i, data1);
        }
    }
    
    ucx_avl_remove_s(tree2, 10, NULL, &val);
    UCX_TEST_ASSERT(val == data3,
            "wrong return value for key: 10 (tree2)");
    UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
    
    ucx_avl_remove_s(tree2, 15, NULL, &val);
    UCX_TEST_ASSERT(val == data2,
            "wrong return value for key: 15 (tree2)");
    UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
    
    for(int i=0;i<20;i++) {
        ucx_avl_remove(tree2, i);
        UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
    }
    UCX_TEST_ASSERT(tree2->root == NULL, "root not NULL (tree2)");
    
    for(int i=0;i<100000;i++) {
        ucx_avl_put(tree3, i, data1);
    }
    for(int i=100000-1;i>=0;i--) {
        ucx_avl_remove(tree3, i);
    }
    UCX_TEST_ASSERT(tree3->root == NULL, "root not NULL (tree3)");
    UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
    
    ucx_avl_put(tree4, 1, data1);
    ucx_avl_remove(tree4, 1);
    UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
    UCX_TEST_ASSERT(tree4->root == NULL, "root not NULL (tree4)");
    UCX_TEST_END
    
    ucx_avl_free(tree1);
    ucx_avl_free(tree2);
    ucx_avl_free(tree3);
    ucx_avl_free(tree4);
}

static intmax_t dist_int(const void* a, const void* b, void* n) {
    return ((intptr_t)a)-((intptr_t)b);
}

UCX_TEST(test_ucx_avl_find) {
    UcxAVLTree *tree = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr);
    UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr);
    
    size_t len = 12;
    int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13};
    
    for (size_t i = 0 ; i < len ; i++) {
        ucx_avl_put(tree, val[i], &(val[i]));
    }
    
    UCX_TEST_BEGIN
    
    void* ret;
    
    /* test present values */
    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_CLOSEST);
    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find closest failed");
    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_EXACT);
    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find exact failed");
    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed");
    ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find UB failed");
    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_CLOSEST);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find closest failed");
    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_EXACT);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find exact failed");
    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find LB failed");
    ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find UB failed");
    
    /* test missing values */
    ret = ucx_avl_find(tree,(intptr_t)-10, dist_int, UCX_AVL_FIND_CLOSEST);
    UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find closest failed");
    ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_EXACT);
    UCX_TEST_ASSERT(!ret, "AVL find exact failed");
    ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed");
    ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find UB failed");
    ret = ucx_avl_find(tree,(intptr_t)18, dist_int, UCX_AVL_FIND_CLOSEST);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 20, "AVL find closest failed");
    ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_EXACT);
    UCX_TEST_ASSERT(!ret, "AVL find exact failed");
    ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed");
    ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 4, "AVL find UB failed");
    
    int val2[] = { 10, 15 };
    ucx_avl_put(tree2, val2[0], &(val2[0]));
    ucx_avl_put(tree2, val2[1], &(val2[1]));
    ret = ucx_avl_find(tree2,(intptr_t)11, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed");
    
    int val3[] = { 15, 16, 1 };
    ucx_avl_put(tree3, val3[0], &(val3[0]));
    ucx_avl_put(tree3, val3[1], &(val3[1]));
    ucx_avl_put(tree3, val3[2], &(val3[2]));
   
    ret = ucx_avl_find(tree3, (intptr_t)13, dist_int, UCX_AVL_FIND_CLOSEST);
    UCX_TEST_ASSERT(ret && *((int*)ret) == 15, "AVL find closest failed");
    
    UCX_TEST_END
    
    ucx_avl_free(tree);
    ucx_avl_free(tree2);
    ucx_avl_free(tree3);
}

UCX_TEST(test_ucx_avl_traverse) {
    UcxAVLTree *tree = ucx_avl_new(ucx_cmp_ptr);
    
    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);
}