tree.c

Go to the documentation of this file.

/* Adapted from... */
/*
 * ANSI C Library for maintainance of AVL Balanced Trees
 *
 * ref.:
 *  G. M. Adelson-Velskij & E. M. Landis
 *  Doklady Akad. Nauk SSSR 146 (1962), 263-266
 *
 * see also:
 *  D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
 *
 * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
 * Released under GNU General Public License (GPL) version 2
 * 
**/
#include "ctl/ctldef.h"
#include "ctl/tree.h"

#ifndef CTL_UNIT


/* Manufacture relative offset trees from templates, for unique and multi-copy sets */
#define tree_temp_offset        ctlt_relative(0)
#define tree_temp_multiple      ctlt_unique
#include "ctl/tree.temp.h"
#undef tree_temp_multiple
#define tree_temp_multiple      ctlt_multiple
#include "ctl/tree.temp.h"
#undef tree_temp_multiple
#undef tree_temp_offset
/* Manufacture non-invasive tree base for map/multimap */
#define tree_temp_offset        ctlt_after
#define tree_temp_multiple      ctlt_unique
#include "ctl/tree.temp.h"
#undef tree_temp_multiple
#define tree_temp_multiple      ctlt_multiple
#include "ctl/tree.temp.h"
#undef tree_temp_multiple
#undef tree_temp_offset


#else /* CTL_UNIT */
#include <stdio.h>
#include "unit/unit.h"
#include "ctl/iset.h"
#include "ctl/imultiset.h"
#include "ctl/ctlstring.h"

typedef struct TestData
{
    int             value;
    ctlt_node_type(ctlt_relative(0),ctlt_unique)    link;
} TestData;

static int TestDataValues( const TestData* t1, const TestData* t2 )
{
    return t1->value - t2->value;
}

/* Was static, but the warning about eating this got too tiresome */
size_t printTestData( const void* data, char* buff, size_t buffSize )
{
    TestData* tdata = (TestData*)data;
    return snprintf( buff, buffSize, "%d", tdata->value );
}

void Test_iset(void);
void Test_imultiset(void);

void Test_Tree(void)
{
    TestData array[20];
    {
        ctl_tree_auto(ctlt_relative(offsetof(TestData,link)),ctlt_unique, TestDataValues, testTree );
        {
            /* Initialize array and build tree from array */
            int valCurr = 1;
            array_foreach( TestData, array, curr )
            {
                curr->value = valCurr++;
                ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, insert)( &testTree, curr );
            }
        }
        /* Show me tree */
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
        /* See that we have the predicted number of nodes */
        Test_Error( ctl_tree_size(ctlt_relative(offsetof(TestData,link)),ctlt_unique, &testTree ) == countof(array) );
        {
            /* Step through each sequentially */
            int valCurr = 1;
            ctl_iset_foreach(TestData,link, &testTree, tcurr )
            {
/*              printf( "%d ", tcurr->value ); */
                Test_Error( tcurr->value == valCurr++ )
            }
        }
        {
            /* Step through each in reverse */
            int valCurr = countof(array);
            ctl_iset_foreach_reverse(TestData,link, &testTree, tcurr )
            {
                Test_Error( tcurr->value == valCurr-- )
            }
        }
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
        {
            TestData tmp = { 5, {0} };
            const void* found = ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, find)( &testTree, &tmp );
            Test_Error( NULL != found );
            Test_Error( ((TestData*)found)->value == tmp.value );
        }
        ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, reset)( &testTree );
    }
    {
        /* Shuffle array */
        array_foreach( TestData, array, curr )
        {
            int iRand = rand()%countof(array);
            int tmp = curr->value;
            curr->value = array[iRand].value;
            array[iRand].value = tmp;
        }
    }
    {
        /* Assemble tree from shuffled values */
        ctl_tree_auto(ctlt_relative(offsetof(TestData,link)),ctlt_unique, TestDataValues, testTree );
        array_foreach( TestData, array, curr )
        {
            ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, insert)( &testTree, curr );
        }
        {
            TestData tmp = { 5, {0} };
            const void* found = ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, find)( &testTree, &tmp );
            Test_Error( NULL != found );
            Test_Error( ((TestData*)found)->value == tmp.value );
        }
        /* See that we have the predicted number of nodes */
        Test_Error( ctl_tree_size(ctlt_relative(offsetof(TestData,link)),ctlt_unique, &testTree ) == countof(array) );
        {
            /* Step through each sequentially */
            int valCurr = 1;
            ctl_iset_foreach(TestData,link, &testTree, tcurr )
            {
                Test_Error( tcurr->value == valCurr++ )
            }
        }
        {
            /* Step through each in reverse */
            int valCurr = countof(array);
            ctl_iset_foreach_reverse(TestData,link, &testTree, tcurr )
            {
                Test_Error( tcurr->value == valCurr-- )
            }
        }
        /* Show me tree */
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
        {
            TestData tmp = { 5, {0} };
            const void* found = ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, remove)( &testTree, &tmp );
            Test_Error( NULL != found );
            Test_Error( ((TestData*)found)->value == tmp.value );
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
            tmp.value = 7;
            found = ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, remove)( &testTree, &tmp );
            Test_Error( NULL != found );
            Test_Error( ((TestData*)found)->value == tmp.value );
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
        }
        /* Show me tree */
        ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, reset)( &testTree );
    }
    /*
     * A couple more tests
     */
    UNIT_TEST(Test_iset);
    UNIT_TEST(Test_imultiset);
}

void Test_iset(void)
{
    ctl_pool_auto(TestData, scratch,16);
    ctl_iset_auto(TestData,link, TestDataValues, testTree );
    const int range = 16;
    int iterations = rand_between(int32,100,300);
    {
        int seed = 16;
        TestData* addthis;
        while( seed-- )
        {
            ctl_pool_alloc( TestData, &scratch, addthis );
            addthis->value = seed;
            {
                /* If we don't get back the same pointer, it's already in there. */
                TestData* found = ctl_iset_insert(TestData,link, &testTree, addthis );
                if( found != addthis )
                    ctl_pool_free(TestData, &scratch, addthis );
            }
        }
    }
    while( iterations-- )
    {
        {
            TestData delthis;
            delthis.value = rand()%range;
/*          printf( "Delete %d\n", delthis.value ); */
            {
                TestData* found = ctl_iset_remove(TestData,link, &testTree, &delthis );
                if( found )
                    ctl_pool_free(TestData, &scratch, found );
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, &found->link ); */
            }
        }
        {
            TestData* addthis;
            ctl_pool_alloc( TestData, &scratch, addthis );
            addthis->value = rand()%range;
/*          printf( "Add %d\n", addthis->value ); */
            {
                /* If we don't get back the same pointer, it's already in there. */
                TestData* found = ctl_iset_insert(TestData,link, &testTree, addthis );
                if( found != addthis )
                    ctl_pool_free(TestData, &scratch, addthis );
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, &addthis->link ); */
            }
        }
        {
            /* Exercise iterators */
            TestData from, to;
            int prev;
            size_t total;
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
            total = 0;
            prev = -1;
/*          printf( "Simple\n" ); */
            {
                ctl_iset_foreach(TestData,link, &testTree, curr )
                {
                    Test_Error( prev < curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            prev = -1;
            {
                ctl_iset_foreach_const(TestData,link, &testTree, curr )
                {
                    Test_Error( prev < curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            prev = (int)(~0u>>1);
            {
                ctl_iset_foreach_reverse(TestData,link, &testTree, curr )
                {
                    Test_Error( prev > curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            prev = (int)(~0u>>1);
            {
                ctl_iset_foreach_reverse_const(TestData,link, &testTree, curr )
                {
                    Test_Error( prev > curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_iset_size(TestData,link, &testTree) );
            }
            /* Now do partial sets */
/*          printf( "Partial\n" ); */
            total = 0;
            from.value = rand()%range;
            prev = from.value-1;
            {
                ctl_iset_from(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value >= from.value );
                    Test_Error( prev < curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            prev = from.value-1;
            {
                ctl_iset_from_const(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value >= from.value );
                    Test_Error( prev < curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            prev = from.value+1;
            {
                ctl_iset_from_reverse(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value <= from.value );
                    Test_Error( prev > curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            prev = from.value+1;
            {
                ctl_iset_from_reverse_const(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value <= from.value );
                    Test_Error( prev > curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
            /* Now do subsets */
/*          printf( "Subset\n" ); */
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value-1;
            {
                ctl_iset_from_to(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value >= from.value && curr->value < to.value  );
                    Test_Error( prev < curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value-1;
            {
                ctl_iset_from_to_const(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value >= from.value && curr->value < to.value );
                    Test_Error( prev < curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value+1;
            {
                ctl_iset_from_to_reverse(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value <= from.value && curr->value > to.value );
                    Test_Error( prev > curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value+1;
            {
                ctl_iset_from_to_reverse_const(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value <= from.value && curr->value > to.value );
                    Test_Error( prev > curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_iset_size(TestData,link, &testTree) );
            }
        }
    }
    ctl_iset_reset( TestData,link, &testTree );
    ctl_pool_destroy(TestData, &scratch);
}

void Test_imultiset(void)
{
    ctl_pool_auto(TestData, scratch,16);
    ctl_imultiset_auto(TestData,link, TestDataValues, testTree );
    const int range = 16;
    int iterations = rand_between(int32,100,300);
    while( iterations-- )
    {
        {
            TestData delthis;
            delthis.value = rand()%range;
/*printf( "Delete %d\n", delthis.value ); */
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
            {
                TestData* found = ctl_imultiset_remove(TestData,link, &testTree, &delthis );
                if( found )
                    ctl_pool_free(TestData, &scratch, found );
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, &found->link ); */
            }
        }
        {
            TestData* addthis;
            ctl_pool_alloc( TestData, &scratch, addthis );
            addthis->value = rand()%range;
/*printf( "Add %d\n", addthis->value ); */
            {
                /* If we don't get back the same pointer, it's already in there. */
                TestData* found = ctl_imultiset_insert(TestData,link, &testTree, addthis );
                if( found != addthis )
                    ctl_pool_free(TestData, &scratch, addthis );
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, &addthis->link ); */
            }
        }
        {
            /* Exercise iterators */
            TestData from, to;
            int prev;
            size_t total;
/* ctl_tree_(ctlt_relative(offsetof(TestData,link)),ctlt_unique, pretty_print)( &testTree, printTestData, NULL ); */
            total = 0;
            prev = -1;
/*          printf( "Simple\n" ); */
            {
                ctl_imultiset_foreach(TestData,link, &testTree, curr )
                {
                    Test_Error( prev <= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            prev = -1;
            {
                ctl_imultiset_foreach_const(TestData,link, &testTree, curr )
                {
                    Test_Error( prev <= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            prev = (int)(~0u>>1);
            {
                ctl_imultiset_foreach_reverse(TestData,link, &testTree, curr )
                {
                    Test_Error( prev >= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            prev = (int)(~0u>>1);
            {
                ctl_imultiset_foreach_reverse_const(TestData,link, &testTree, curr )
                {
                    Test_Error( prev >= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total == ctl_imultiset_size(TestData,link, &testTree) );
            }
            /* Now do partial multisets */
/*          printf( "Partial\n" ); */
            total = 0;
            from.value = rand()%range;
            prev = from.value-1;
            {
                ctl_imultiset_from(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value >= from.value );
                    Test_Error( prev <= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            prev = from.value-1;
            {
                ctl_imultiset_from_const(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value >= from.value );
                    Test_Error( prev <= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            prev = from.value+1;
            {
                ctl_imultiset_from_reverse(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value <= from.value );
                    Test_Error( prev >= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            prev = from.value+1;
            {
                ctl_imultiset_from_reverse_const(TestData,link, &testTree, &from, curr )
                {
                    Test_Error( curr->value <= from.value );
                    Test_Error( prev >= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
            /* Now do susets */
/*          printf( "Subset\n" ); */
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value-1;
            {
                ctl_imultiset_from_to(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value >= from.value && curr->value < to.value  );
                    Test_Error( prev <= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value-1;
            {
                ctl_imultiset_from_to_const(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value >= from.value && curr->value < to.value );
                    Test_Error( prev <= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value+1;
            {
                ctl_imultiset_from_to_reverse(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value <= from.value && curr->value > to.value );
                    Test_Error( prev >= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
            total = 0;
            from.value = rand()%range;
            to.value = rand()%range;
            prev = from.value+1;
            {
                ctl_imultiset_from_to_reverse_const(TestData,link, &testTree, &from, &to, curr )
                {
                    Test_Error( curr->value <= from.value && curr->value > to.value );
                    Test_Error( prev >= curr->value );
                    prev = curr->value;
                    total++;
                }
                Test_Error( total <= ctl_imultiset_size(TestData,link, &testTree) );
            }
        }
    }
    ctl_imultiset_reset( TestData,link, &testTree );
    ctl_pool_destroy(TestData, &scratch);
}

#endif /* CTL_UNIT */