test_yc_tree.c

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

#ifdef _MSC_VER
    #pragma warning(disable:4127)
    #pragma warning(disable:4244)
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../../young/youngc.h"

#ifdef  __cplusplus
    using namespace youngc;
    #define  EXTERN  extern "C"
#else
    #define  EXTERN  extern
#endif

static size_t lastlevel = 0;

extern void destroy_int( void* ptr );
extern int copy_int( void* lhs, const void* rhs );
EXTERN bool verify_red_black_tree( bbstree* self );
EXTERN size_t bbstree_node_height( const bbstree_node* pos, const bbstree_node* top );
EXTERN bool bbstree_foreach( bbstree* self,
                             void (*op_node)(bbstree*, const bbstree_node*) );

static void print_node( bbstree* tree, const bbstree_node* node )
{
    size_t nowlevel = bbstree_node_height( node, tree->m_header.parent );
    int value = *( (int*)bbstree_itr_deref( (bbstree_node*)node ) );
    if( nowlevel == 0 )
        printf( "\nprint breadth first:\n" );
    if( nowlevel > lastlevel )
        printf( "\n" );
    lastlevel = nowlevel;
    /* 打印结果：节点值|颜色|（根/左/右）节点->父节点值|节点高度 */
    printf( "%d|%c|%s->%d|H%d, ",
            value,
            RED == node->color ? 'R' : 'B',
            nowlevel == 0 ? "ROOT" : (node == node->parent->left ? "LC" : "RC"),
            nowlevel == 0 ? value : *( (int*)bbstree_itr_deref(node->parent) ),
            nowlevel );
}

static void print_int( void* ptr )
{
     printf( "%d, ", *((int*)ptr) );
}

static void print_tree( bbstree* tree, bool dir )
{
    bbstree_iterator begin = bbstree_begin( tree );
    bbstree_iterator end = bbstree_end( tree );

    if( true == dir )
    {
        while( begin != end )
        {
            print_int( bbstree_itr_deref(begin) );
            bbstree_itr_inc( &begin );
        }
    }
    else
    {
        while( begin != end )
        {
            bbstree_itr_dec( &end );
            print_int( bbstree_itr_deref(end) );
        }
    }

    printf( "\n" );
}

static void print_verify( bbstree* tree )
{
    if( true == verify_red_black_tree(tree) )
        printf( "The tree is red black tree!\n\n" );
    else
        printf( "The tree is not red black tree!\n\n" );
}

static void print_bread_tree( bbstree* tree )
{
    chkarray queue;
    size_t nowheight = 0, lastheight = 0;
    bbstree_iterator curr = tree->m_header.parent;
    chkarr_init( &queue, sizeof(bbstree_iterator), 0, NULL, NULL, NULL, NULL,
                   NULL, NULL, pool_alloc, pool_free );

    if( tree->m_node_count > 0 )
    {
        printf( "\nprint_bread_tree:\n" );

        chkarr_push_back( &queue, &curr );
        while( !chkarr_empty(&queue) )
        {
            curr = *( (bbstree_iterator*)chkarr_front(&queue) );
            nowheight = bbstree_node_height( curr, tree->m_header.parent );
            if( nowheight > lastheight )
                printf( "\n" );
            lastheight = nowheight;
            printf( "%d|%c|%s->%d|H%d, ",
                    *((int*)bbstree_itr_deref(curr)),
                    RED == curr->color ? 'R' : 'B',
                    nowheight == 0 ? "ROOT" : (curr == curr->parent->left ? "LC" : "RC"),
                    nowheight == 0 ? *((int*)bbstree_itr_deref(curr))
                                   : *((int*)bbstree_itr_deref(curr->parent)),
                    nowheight );
            chkarr_pop_front( &queue );
            if( curr->left )
                chkarr_push_back( &queue, &(curr->left) );
            if( curr->right )
                chkarr_push_back( &queue, &(curr->right) );
        }

        printf( "\n\n" );
    }

    chkarr_destroy( &queue );
}

void test_tree(void)
{
    bbstree tree;

    printf( "\nsize of rbtree_color_t = %d\n", sizeof(rbtree_color_t) );

    bbstree_init( &tree, sizeof(int), copy_int, destroy_int,
                  NULL, cmp_int, pool_alloc, pool_free );

    while( 1 )
    {
        int choice = 0;

        printf( "\n\n" );
        printf( "  1: test bbstree_init_copy\n" );
        printf( "  2: test bbstree_assign_copy\n" );
        printf( "  3: test bbstree_init_move\n" );
        printf( "  4: test bbstree_assign_move\n" );
        printf( "  5: test bbstree_swap\n" );
        printf( "  6: test bbstree_count\n" );
        printf( "  7: test bbstree_find\n" );
        printf( "  8: test bbstree_lower_bound\n" );
        printf( "  9: test bbstree_upper_bound\n" );
        printf( " 10: test bbstree_equal_range\n" );
        printf( " 11: test bbstree_erase_pos\n" );
        printf( " 12: test bbstree_erase_range\n" );
        printf( " 13: test bbstree_erase_key\n" );
        printf( " 14: test bbstree_insert_unique_value\n" );
        printf( " 15: test bbstree_insert_unique_pos\n" );
        printf( " 16: test bbstree_insert_equal_value\n" );
        printf( " 17: test bbstree_insert_equal_pos\n" );
        printf( " 18: test bbstree_replace_key_unique_pos\n" );
        printf( " 19: test bbstree_replace_key_unique\n" );
        printf( " 20: test bbstree_replace_key_equal_pos\n" );
        printf( " 21: test bbstree_replace_key_equal\n" );
        printf( " 22: test bbstree_max_size\n" );
        printf( " 23: test bbstree_size\n" );
        printf( " 24: test bbstree_begin\n" );
        printf( " 25: test bbstree_end\n" );
        printf( " 26: test verify_red_black_tree\n" );
        printf( " 27: print bread tree\n" );
        printf( " 28: print sequence\n" );
        printf( "  0: exit\n\n\n" );

        scanf( "%d", &choice );

        switch( choice )
        {
            case 0:
                goto EXIT;
            case 1:
            {
                bbstree tree1;
                bbstree_init_copy( &tree1, &tree );
                printf( "src:\n" );
                print_bread_tree( &tree );
                printf( "dst:\n" );
                print_bread_tree( &tree1 );
                bbstree_destroy( &tree );
                bbstree_init_copy( &tree, &tree1 );
                bbstree_destroy( &tree1 );
                break;
            }
            case 2:
            {
                bbstree tree1;
                bbstree_init( &tree1, sizeof(int), copy_int,
                              destroy_int, NULL, cmp_int, pool_alloc, pool_free );
                bbstree_assign_copy( &tree1, &tree );
                printf( "src:\n" );
                print_bread_tree( &tree );
                printf( "dst:\n" );
                print_bread_tree( &tree1 );
                bbstree_destroy( &tree );
                bbstree_assign_copy( &tree, &tree1 );
                bbstree_destroy( &tree1 );
                break;
            }
            case 3:
            {
                bbstree tree1;
                bbstree_init_move( &tree1, &tree );
                printf( "src:\n" );
                print_bread_tree( &tree );
                printf( "dst:\n" );
                print_bread_tree( &tree1 );
                bbstree_destroy( &tree1 );
                break;
            }
            case 4:
            {
                bbstree tree1;
                bbstree_init( &tree1, sizeof(int), copy_int,
                              destroy_int, NULL, cmp_int, pool_alloc, pool_free );
                bbstree_assign_move( &tree1, &tree );
                printf( "src:\n" );
                print_bread_tree( &tree );
                printf( "dst:\n" );
                print_bread_tree( &tree1 );
                bbstree_destroy( &tree1 );
                break;
            }
            case 5:
            {
                break;
            }
            case 6:
            {
                int key = 0;
                printf( "please input find int key:\n" );
                scanf( "%d", &key );
                printf( "count of %d: %u\n", key, bbstree_count(&tree, &key) );
                break;
            }
            case 7:
            {
                int key = 0;
                bbstree_iterator itr;
                printf( "please input find int key:\n" );
                scanf( "%d", &key );
                itr = bbstree_find( &tree, &key );
                if( bbstree_end(&tree) != itr )
                {
                    printf( "address: %p\n", itr );
                    printf( "data: %d\n", *((int*)bbstree_itr_deref(itr)) );
                }
                else