tree.temp.h

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
 * 
**/
#ifndef tree_temp_offset
#error The 'tree_temp_offset' template parameter was not defined.  
#endif

#ifndef tree_temp_multiple
#error The 'tree_temp_multiple' template parameter was not defined.  
#endif

/* Balance maintainance after especially nasty swings */
#define tree_fixup(root) \
{\
    if( (root)->balance < 0 )\
    {\
        (root)->left->balance = 0;\
        (root)->right->balance = 1;\
    }\
    else if( (root)->balance > 0 )\
    {\
        (root)->left->balance = -1;\
        (root)->right->balance = 0;\
    }\
    else\
    {\
        (root)->left->balance = 0;\
        (root)->right->balance = 0;\
    }\
    (root)->balance = 0;\
}

/* Swing to the left
 * Warning: no balance maintainance
 */
#define tree_swl(root)\
{\
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *a_swr = (root);\
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *b_swr = a_swr->right;\
    (root) = b_swr;\
    a_swr->right = b_swr->left;\
    b_swr->left = a_swr;\
}

/* Swing to the right
 * Warning: no balance maintainance
 */
#define tree_swr(root)\
{\
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *a_swr = (root);\
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *b_swr = a_swr->left;\
    (root) = b_swr;\
    a_swr->left = b_swr->right;\
    b_swr->right = a_swr;\
}

/* 
 * Compare two nodes, jumping through appropriate hoops
 * tree Tree the nodes belong to
 * n1 The 'lesser', or left node
 * n2 The 'greater', or right node
 * return Exactly like qsort wants
 */
#define tree_compare( tree, n1, n2 )            (tree)->compare( ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, (tree),(n1)), ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, (tree),(n2)) )

/* 
 * Copy one tree to another tree, setting a new root in the target tree
 * treedst Tree new tree
 * treesrc Tree original tree
 * dstroot New root node for tree
 */
#define tree_copy( treedst, dstroot, treesrc )  { (treedst)->root = (dstroot); (treedst)->compare = (treesrc)->compare; ctlt_offset_for_relative(tree_temp_offset,(treedst)->data_offset = (treesrc)->data_offset;) (treedst)->size = 0; }

/* 
 * Integrate findings from sutree treesrc into treedst tree
 * treedst Tree new tree
 * treesrc Tree original tree
 */
#define tree_integrate( treedst, treesrc )      { (treedst)->size += (treesrc)->size; (treedst)->found = (treesrc)->found; }

static bool ctl_tree_(tree_temp_offset,tree_temp_multiple, _insert )( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node );
static int ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node );
static int ctl_tree_(tree_temp_offset,tree_temp_multiple, _removeroot )( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree );

/*
 * Insert element a into the AVL tree t
 * tree The tree we are attempting to add a node to
 * node A fresh, new node to add to this tree
 * true if the depth of the tree has grown
 * Warning: do not insert elements already present in the tree
 *
 * tree->found is normally clear 
 *
 * If tree->tree_temp_multiple is clear, tree->found will be set if a 
 * node of the same value is found
 *
 * If a node is already linked to the tree, node->found will 
 * be that node.
 */
static bool ctl_tree_(tree_temp_offset,tree_temp_multiple, _insert )( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node )
{
    /* initialize */
    int diff;
    /* Inserting a node that's already linked in there is an error! */
    /* This assert doesn't catch every case, but it's here to catch some of them */
    assert( node != tree->root );
    tree->found = NULL;
    node->left = 0;
    node->right = 0;
    node->balance = 0;
    /* insert into an empty tree */
    if (!tree->root)
    {
        tree->root = node;
        tree->size++;
        return true;
    }
    diff = tree_compare( tree, tree->root, node );
    if( diff > 0 )
    {
        /* insert into the left sutree */
        if (tree->root->left)
        {
            ctl_tree(tree_temp_offset,tree_temp_multiple) left_sutree;
            tree_copy( &left_sutree, tree->root->left, tree );
            if (ctl_tree_(tree_temp_offset,tree_temp_multiple, _insert ) (&left_sutree, node))
            {
                int tmpBalance = tree->root->balance--;
                tree_integrate( tree, &left_sutree );
                if( 0 == tmpBalance )
                    return true;
                if( 1 == tmpBalance )
                    return false;
                if (tree->root->left->balance < 0)
                {
                    tree_swr (tree->root);
                    tree->root->balance = 0;
                    tree->root->right->balance = 0;
                }
                else
                {
                    tree_swl (tree->root->left);
                    tree_swr (tree->root);
                    tree_fixup (tree->root);
                }
            }
            else
            {
                tree_integrate( tree, &left_sutree );
                tree->root->left = left_sutree.root;
            }
            return false;
        }
        else
        {
            tree->root->left = node;
            (tree)->size++; /* Tree grew */
            if (tree->root->balance--)
                return false;
            return true;
        }
    }
#if ctlt_multi_value(tree_temp_multiple)
    else
#else
    else if( diff < 0 ) 
#endif
    {
        /* insert into the right sutree */
        if (tree->root->right)
        {
            ctl_tree(tree_temp_offset,tree_temp_multiple) right_sutree;
            tree_copy( &right_sutree, tree->root->right, tree );
            if (ctl_tree_(tree_temp_offset,tree_temp_multiple, _insert ) (&right_sutree, node))
            {
                int tmpBalance = tree->root->balance++;
                tree_integrate( tree, &right_sutree );
                if( -1 == tmpBalance )
                    return false;
                if( 0 == tmpBalance )
                    return true;
                if (tree->root->right->balance > 0)
                {
                    tree_swl (tree->root);
                    tree->root->balance = 0;
                    tree->root->left->balance = 0;
                }
                else
                {
                    tree_swr (tree->root->right);
                    tree_swl (tree->root);
                    tree_fixup (tree->root);
                }
            }
            else
            {
                tree_integrate( tree, &right_sutree );
                tree->root->right = right_sutree.root;
            }
            return false;
        }
        else
        {
            tree->root->right = node;
            (tree)->size++; /* Tree grew */
            if (tree->root->balance++)
                return false;
            return true;
        }
    }
#if ctlt_multi_not_value(tree_temp_multiple)
    /* else that value is already in there */
    tree->found = tree->root;
    return false;
#endif
}


/*
 * Remove the root of the AVL tree 
 * tree The tree we're popping the top off
 *
 * This is where the actual work of removing the node happens, when 
 * it's been found while recursing into the tree.
 * 
 * Warning: dumps core if tree is empty
 */
static int ctl_tree_(tree_temp_offset,tree_temp_multiple, _removeroot )( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    int ch;
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node;
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *root = tree->root;
    /* Warning: dumps core if tree is empty */
    assert(root);
    /* See if we can trivially remove the root node - if left or right are clear, we can patch this up easy. */
    if (!root->left)
    {
        (tree)->found = root;
        (tree)->size--; /* Tree shrinks */
        if (!root->right)
        {
            tree->root = 0;
            return -1;
        }
        tree->root = root->right;
        return -1;
    }
    if (!root->right)
    {
        (tree)->found = root;
        tree->root = root->left;
        (tree)->size--;     /* Tree shrinks */
        return -1;
    }
    /* Recurse down and see if we can rotate/pop something to make one side of root clear */
    if (root->balance < 0)
    {
        /* remove from the left sutree */
        node = root->left;
        while (node->right)
            node = node->right;
    }
    else
    {
        /* remove from the right sutree */
        node = root->right;
        while (node->left)
            node = node->left;
    }
    /* This decrements count for us */
    ch = ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove ) (tree, node);
    root = tree->root;
    node->left = root->left;
    node->right = root->right;
    node->balance = root->balance;
    tree->root = node;
    if (node->balance == 0)
        return ch;
    return 0;
}

/*
 * Remove an explicit node element from the AVL tree 
 * tree Tree to insert element into
 * node node to remove
 * return -1 if the depth of the tree has shrunk
 * Warning: if the element is not present in the tree, returns 0 as if it had been removed succesfully.
 */
static int ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node )
{
    /* Recursively search tree passing left or right sutrees to self */
    /* Call ctl_tree_(tree_temp_offset,tree_temp_multiple, _removeroot ) when we have a candidate */
    int b;
    if (tree->root == node)
        return ctl_tree_(tree_temp_offset,tree_temp_multiple, _removeroot ) (tree);
    b = tree_compare( tree, tree->root, node );
    if (b >= 0)
    {
        /* remove from the left sutree */
        int ch;
        ctl_tree(tree_temp_offset,tree_temp_multiple) left_sutree;
        tree_copy( &left_sutree, tree->root->left, tree );
        if (left_sutree.root )
        {
            ch = ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove ) (&left_sutree, node);
            tree_integrate( tree, &left_sutree );
            tree->root->left = left_sutree.root;
            if (ch)
            {
                int tmpBalance = tree->root->balance++;
                if( -1 == tmpBalance)
                    return -1;
                if( 0 == tmpBalance)
                    return 0;
                tmpBalance = tree->root->right->balance;
                if( 0 == tmpBalance )
                {
                    tree_swl (tree->root);
                    tree->root->balance = -1;
                    tree->root->left->balance = 1;
                    return 0;
                }
                if( 1 == tmpBalance )
                {
                    tree_swl (tree->root);
                    tree->root->balance = 0;
                    tree->root->left->balance = 0;
                    return -1;
                }
                tree_swr (tree->root->right);
                tree_swl (tree->root);
                tree_fixup (tree->root);
                return -1;
            }
        }
    }
    if (b <= 0)
    {
        /* remove from the right sutree */
        int ch;
        ctl_tree(tree_temp_offset,tree_temp_multiple) right_sutree;
        tree_copy( &right_sutree, tree->root->right, tree );
        if (right_sutree.root )
        {
            ch = ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove ) (&right_sutree, node);
            tree_integrate( tree, &right_sutree );
            tree->root->right = right_sutree.root;
            if (ch)
            {
                int tmpBalance = tree->root->balance--;
                if( 1 == tmpBalance )
                    return -1;
                if( 0 == tmpBalance )
                    return 0;

                tmpBalance = tree->root->left->balance;
                if( 0 == tmpBalance )
                {
                    tree_swr (tree->root);
                    tree->root->balance = 1;
                    tree->root->right->balance = -1;
                    return 0;
                }
                if( -1 == tmpBalance )
                {
                    tree_swr (tree->root);
                    tree->root->balance = 0;
                    tree->root->right->balance = 0;
                    return -1;
                }
                tree_swl (tree->root->left);
                tree_swr (tree->root);
                tree_fixup (tree->root);
                return -1;
            }
        }
    }
    return 0;
}

ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, insert)( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_offset_type(tree_temp_offset)* data )
{
    ppDebug(size_t size = tree->size;)
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = ctl_tree_data_to_node(tree_temp_offset,tree_temp_multiple, tree,data);
    ctl_tree_(tree_temp_offset,tree_temp_multiple, _insert )(tree, node);
    if( !tree->found )
    {
        assert( size < tree->size );
        return data;
    }
    return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,tree->found);
}

ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, remove)( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_offset_type(tree_temp_offset)* data )
{
    data = (ctlt_offset_type(tree_temp_offset)*)ctl_tree_(tree_temp_offset,tree_temp_multiple, find)( tree, data );
    if( data )
    {
        ppDebug(size_t size = tree->size;)
        ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = ctl_tree_data_to_node(tree_temp_offset,tree_temp_multiple, tree,data);
        ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( tree, node );
        assert( size > tree->size );
        return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node);
    }
    return NULL;
}

ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, unlink)( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_offset_type(tree_temp_offset)* data )
{
    assertobjptr( tree );
    assertptr( data, sizeof(void*) );
    {
        ppDebug(size_t size = tree->size;)
        ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = ctl_tree_data_to_node(tree_temp_offset,tree_temp_multiple, tree,data);
        ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( tree, node );
        assert( size > tree->size );
        return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node);
    }
}

void ctl_tree_(tree_temp_offset,tree_temp_multiple, recurseunlink)( ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node )
{
    if( node->left )
        ctl_tree_(tree_temp_offset,tree_temp_multiple, recurseunlink)( node->left );
    if( node->right )
        ctl_tree_(tree_temp_offset,tree_temp_multiple, recurseunlink)( node->right );
    node->left = node->right = NULL;
}

void ctl_tree_(tree_temp_offset,tree_temp_multiple, reset)( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    if( tree->root )
        ctl_tree_(tree_temp_offset,tree_temp_multiple, recurseunlink)( tree->root );
    tree->root = NULL;
    tree->size = 0;
}

static size_t ctl_tree_(tree_temp_offset,tree_temp_multiple, recursetally)( ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node )
{
    if( node )
        return 1 + ctl_tree_(tree_temp_offset,tree_temp_multiple, recursetally( node->left )) + ctl_tree_(tree_temp_offset,tree_temp_multiple, recursetally)( node->right );
    return 0;
}

size_t ctl_tree_(tree_temp_offset,tree_temp_multiple, tally)( const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    /* This DID iterate the nodes from begin->end, but that actually  */
    /* visited nodes many times.  See ctl_tree_next for what  */
    /* would've been needed.  The tree keeps a count, but this  */
    /* is mainly to verify that this cound is correct. */
    size_t size = ctl_tree_(tree_temp_offset,tree_temp_multiple, recursetally)( tree->root );
    assert( size == tree->size );
    return size;
}

static size_t ctl_tree_(tree_temp_offset,tree_temp_multiple, recursedepth)( const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node, size_t currDepth )
{
    if( node )
    {
        size_t d1 = ctl_tree_(tree_temp_offset,tree_temp_multiple, recursedepth)( node->left, currDepth+1 );
        size_t d2 = ctl_tree_(tree_temp_offset,tree_temp_multiple, recursedepth)( node->right, currDepth+1 );
        return max(d1,d2);
    }
    return currDepth;
}

size_t ctl_tree_(tree_temp_offset,tree_temp_multiple, depth)( const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    return ctl_tree_(tree_temp_offset,tree_temp_multiple, recursedepth)( tree->root, 1 );
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, front)( const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = tree->root;
    if( !node )
        return NULL;
    while( node->left )
        node = node->left;
    return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node);
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, back)( const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = tree->root;
    if( !node )
        return NULL;
    while( node->left )
        node = node->left;
    return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node);
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, find)( const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, const ctlt_offset_type(tree_temp_offset)* data )
{
    tree_compare compare = tree->compare;
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node = tree->root;
    while( node )
    {
        int diff = compare( data, ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node) );
        if( diff > 0 )
            node = node->right;
        else if( diff < 0 )
            node = node->left;
        else
            return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node);
    }
    return NULL;
}

ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, pop_front)( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = tree->root;
    if( !node )
        return NULL;
    while( node->left )
        node = node->left;
    ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( tree, node );
    return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node);
}

ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, pop_back)( ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = tree->root;
    if( !node )
        return NULL;
    while( node->right )
        node = node->right;
    ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( tree, node );
    return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node);
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_begin)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack, const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree )
{
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = tree->root;
    stack->tree = tree;
    stack->sp = stack->stack;
    *stack->sp++ = NULL;    /* When we pop NULL off, we're done. */
    while( node )
    {
        *stack->sp++ = node;
        node = node->left;
    }
    /* Heap/stack/BSS/whatever is probably already corrupted if this assert hits */
    assert( memberof(stack->stack,stack->sp) );
    return ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_next)( stack );
}

static bool ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_begin_from_no_iterate)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack, const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, const ctlt_offset_type(tree_temp_offset)* data )
{
    tree_compare compare = tree->compare;
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node = tree->root;
    stack->tree = tree;
    stack->sp = stack->stack;
    *stack->sp++ = NULL;    /* When we pop NULL off, we're done. */
    while( node )
    {
        int diff = compare( data, ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node) );
        if( diff > 0 )
        {
            node = node->right;
        }
        else 
#if ctlt_multi_not_value(tree_temp_multiple)
        if( diff < 0 )  /* If we allow tree_temp_multiple of the same value, we must carry on iterating leftward until we hit NULL */
#endif
        {
            *stack->sp++ = node;
            node = node->left;
        }
#if ctlt_multi_not_value(tree_temp_multiple)
        else
        {
            /* We found the unique value we were looking for */
            *stack->sp++ = node;
            /* Heap/stack/BSS/whatever is probably already corrupted if this assert hits */
            assert( memberof(stack->stack,stack->sp) );
            return true;
        }
#endif
    }
    /* Heap/stack/BSS/whatever is probably already corrupted if this assert hits */
    assert( memberof(stack->stack,stack->sp) );
    return false;
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_begin_from)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack, const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, const ctlt_offset_type(tree_temp_offset)* data )
{
    /* Heap/stack/BSS/whatever is probably already corrupted if this assert hits */
    if( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_begin_from_no_iterate)( stack, tree, data ) )
        return ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_next)( stack );
    /* If value wasn't found, or wasn't unique we probably iterated past a starting value we wanted. */
    /* Seek right until we are at first instance */
    {
        tree_compare compare = tree->compare;
        const ctlt_offset_type(tree_temp_offset)* curr = ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_next)( stack );
        while( curr && compare( data, curr ) > 0 )
            curr = ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_next)( stack );
        return curr;
    }
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_next)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack )
{
    /* Pop node */
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node = *--stack->sp;
    if( node )
    {
        if( node->right )
        {
            /* Add search path to go left from right node */
            const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* next = node->right;
            while( next )
            {
                *stack->sp++ = next;
                next = next->left;
            }
        }
        stack->node = node;
        return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, stack->tree,node);
    }
    stack->node = NULL;
    return NULL;
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_rbegin)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack, const ctl_tree(tree_temp_offset,tree_temp_multiple) *tree )
{
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple) *node = tree->root;
    stack->tree = tree;
    stack->bReverse = true;
    stack->sp = stack->stack;
    *stack->sp++ = NULL;    /* When we pop NULL off, we're done. */
    while( node )
    {
        *stack->sp++ = node;
        node = node->right;
    }
    /* Heap/stack/BSS/whatever is probably already corrupted if this assert hits */
    assert( memberof(stack->stack,stack->sp) );
    return ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_prev)( stack );
}

static bool ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_rbegin_from_no_iterate)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack, const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, const ctlt_offset_type(tree_temp_offset)* data )
{
    tree_compare compare = tree->compare;
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node = tree->root;
    stack->tree = tree;
    stack->bReverse = true;
    stack->sp = stack->stack;
    *stack->sp++ = NULL;    /* When we pop NULL off, we're done. */
    while( node )
    {
        int diff = compare( data, ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node) );
        if( diff < 0 )
        {
            node = node->left;
        }
        else 
#if ctlt_multi_not_value(tree_temp_multiple)
            if( diff > 0 )  /* If we allow tree_temp_multiple of the same value, we must carry on iterating leftward until we hit NULL */
#endif
        {
            *stack->sp++ = node;
            node = node->right;
        }
#if ctlt_multi_not_value(tree_temp_multiple)
        else
        {
            /* We found the unique value we were looking for */
            *stack->sp++ = node;
            /* Heap/stack/BSS/whatever is probably already corrupted if this assert hits */
            assert( memberof(stack->stack,stack->sp) );
            return true;
        }
#endif
    }
    /* Heap/stack/BSS/whatever is probably already corrupted if this assert hits */
    assert( memberof(stack->stack,stack->sp) );
    return false;
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_rbegin_from)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack, const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, const ctlt_offset_type(tree_temp_offset)* data )
{
    if( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_rbegin_from_no_iterate)( stack, tree, data ) )
        return ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_prev)( stack );
    /* If value wasn't found, or wasn't unique we probably iterated past a starting value we wanted. */
    {
        tree_compare compare = tree->compare;
        const ctlt_offset_type(tree_temp_offset)* curr = ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_prev)( stack );
        while( curr && compare( data, curr ) < 0 )
            curr = ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_prev)( stack );
        return curr;
    }
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_prev)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack )
{
    /* Pop node */
    const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node = *--stack->sp;
    if( node )
    {
        if( node->left )
        {
            /* Add search path to go right from left node */
            const ctlt_node_type(tree_temp_offset,tree_temp_multiple)* prev = node->left;
            while( prev )
            {
                *stack->sp++ = prev;
                prev = prev->right;
            }
        }
        stack->node = node;
        return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, stack->tree,node);
    }
    stack->node = NULL;
    return NULL;
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, unlink_curr)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack )
{
    if( stack->node )
    {
        ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( (ctl_tree(tree_temp_offset,tree_temp_multiple)*)stack->tree, (ctlt_node_type(tree_temp_offset,tree_temp_multiple)*)stack->node );
        return ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, stack->tree,stack->node);
    }
    return NULL;
}

const ctlt_offset_type(tree_temp_offset)* ctl_tree_(tree_temp_offset,tree_temp_multiple, unlink_curr_resume)( ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator )* stack )
{
    if( stack->node )
    {
        ctl_tree_(tree_temp_offset,tree_temp_multiple, _remove )( (ctl_tree(tree_temp_offset,tree_temp_multiple)*)stack->tree, (ctlt_node_type(tree_temp_offset,tree_temp_multiple)*)stack->node );
        if( stack->bReverse )
            return ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_rbegin_from)( stack, stack->tree, ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, stack->tree,stack->node) );
        else
            return ctl_tree_(tree_temp_offset,tree_temp_multiple, iterator_begin_from)( stack, stack->tree, ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, stack->tree,stack->node) );
    }
    return NULL;
}

#ifdef CTL_UNIT
#define CelWidth    2
static void ctl_tree_(tree_temp_offset,tree_temp_multiple, cell_printLines)( ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node, char **buff, size_t coloffset, size_t width )
{
    size_t line;
    size_t c = coloffset + width;
    size_t nLines = (width / 2);
    for (line = 1; line <= nLines; ++line)
    {
/*      if( node->left ) */
        buff[line][1 + c - line] = '/';
/*      if( node->right ) */
        buff[line][c + line] = '\\';
    }
}

static void ctl_tree_(tree_temp_offset,tree_temp_multiple, cell_print)( const ctl_tree(tree_temp_offset,tree_temp_multiple)* tree, ctlt_node_type(tree_temp_offset,tree_temp_multiple)* node, char **buff, size_t coloffset, size_t width, size_t depth, ctl_tree_printf print, ctlt_node_type(tree_temp_offset,tree_temp_multiple)* nHilight)
{
    size_t center = coloffset + (width / 2);
    char *pBuff = *buff + center;
    if (NULL == node)
    {
        memcpy (pBuff, "{}", 2);
    }
    else
    {
        char tmp[80];
        size_t len = print( ctl_tree_node_to_data(tree_temp_offset,tree_temp_multiple, tree,node), tmp, countof (tmp));
        len = min (len, width);
        pBuff -= -1 + (len / 2) + (nHilight == node) + (0 != node->balance);
        if( nHilight == node )
            *pBuff++ = '[';
        memcpy (pBuff, tmp, len);
        pBuff += len;
        if( node->balance < 0 )
            *pBuff++ = '-';
        else if( node->balance > 0 )
            *pBuff++ = '+';
        if( nHilight == node )
            *pBuff++ = ']';

        ctl_tree_(tree_temp_offset,tree_temp_multiple, cell_printLines)(node, buff, coloffset, width / 2);
        ctl_tree_(tree_temp_offset,tree_temp_multiple, cell_print)(tree, node->left, buff + 1 + width / 4, coloffset, width / 2, depth + 1, print, nHilight);
        ctl_tree_(tree_temp_offset,tree_temp_multiple, cell_print)(tree, node->right, buff + 1 + width / 4, center, width / 2, depth + 1, print, nHilight);
    }
}

void ctl_tree_(tree_temp_offset,tree_temp_multiple, pretty_print)( const ctl_tree(tree_temp_offset,tree_temp_multiple) *tree, ctl_tree_printf print, ctlt_node_type(tree_temp_offset,tree_temp_multiple)* hilight )
{
    size_t maxDepth = ctl_tree_(tree_temp_offset,tree_temp_multiple, depth)(tree);
    size_t bottomWidth = 1 << maxDepth;
    size_t lineCount = bottomWidth+maxDepth;
    char **cells = malloc (lineCount * sizeof (char *));
    size_t rowWidth = CelWidth * bottomWidth;
    size_t rowCurr;

    /* Allocate a buffer to draw into */
    for (rowCurr = 0; rowCurr < lineCount; ++rowCurr)
    {
        cells[rowCurr] = malloc (rowWidth + CelWidth + 1);
        memset (cells[rowCurr], ' ', rowWidth + CelWidth + 1);
        cells[rowCurr][rowWidth + CelWidth] = 0;
    }
    ctl_tree_(tree_temp_offset,tree_temp_multiple, cell_print)( tree, tree->root, cells, 0, rowWidth, 0, print, hilight );
    for (rowCurr = 0; rowCurr < lineCount; ++rowCurr)
    {
        puts (cells[rowCurr]);
        free (cells[rowCurr]);
    }
    free (cells);
    puts ("\n");
}
#endif /* CTL_UNIT */

/* Undefine local definitions */
#undef tree_fixup
#undef tree_swl
#undef tree_swr
#undef tree_compare
#undef tree_copy
#undef tree_integrate