path: root/src/usr/diag/prdf/common/util/UtilTree.C

/* IBM_PROLOG_BEGIN_TAG                                                   */
/* This is an automatically generated prolog.                             */
/*                                                                        */
/* $Source: src/usr/diag/prdf/common/util/UtilTree.C $                    */
/*                                                                        */
/* IBM CONFIDENTIAL                                                       */
/*                                                                        */
/* COPYRIGHT International Business Machines Corp. 2004,2013              */
/*                                                                        */
/* p1                                                                     */
/*                                                                        */
/* Object Code Only (OCO) source materials                                */
/* Licensed Internal Code Source Materials                                */
/* IBM HostBoot Licensed Internal Code                                    */
/*                                                                        */
/* The source code for this program is not published or otherwise         */
/* divested of its trade secrets, irrespective of what has been           */
/* deposited with the U.S. Copyright Office.                              */
/*                                                                        */
/* Origin: 30                                                             */
/*                                                                        */
/* IBM_PROLOG_END_TAG                                                     */

#include "UtilTree.H"

namespace PRDF
{

UtilTree::defaultComparator UtilTree::defComparator;
UtilTree::defaultCleanup UtilTree::defCleanup;
UtilTree::defaultCopier UtilTree::defCopy;

void UtilTree::printTree()
{
    this->printTree(0,root);
};

UtilTree::UtilTree()
    : root(NULL), comp(&defComparator), clean(&defCleanup), copy(&defCopy)
{
};

UtilTree::~UtilTree()
{
    cleanTree(root);
    root = NULL;
};

void UtilTree::empty()
{
    cleanTree(root);
};

void UtilTree::cleanTree(Node * root)
{
    if (NULL == root)
        return;

    cleanTree(root->left);
    cleanTree(root->right);

    (*clean)(root->value);
    delete root;

    return;
};

void * UtilTree::peek() const
{
    if (NULL == root)
        return NULL;
    return root->value;
};

void * UtilTree::find(void * v) const
{
    return (NULL != find(v, root) ? (find(v, root)->value) : NULL);
};

UtilTree::Node * UtilTree::find(void * v, Node * t) const
{
    if (NULL == t)
        return NULL;

    if (0 == (*comp)(v, t->value))
        return t;

    return find(v, (-1 == (*comp)(v, t->value) ? t->left : t->right));
};

void UtilTree::insert(void * v)
{
    insert(v, root);
    while (NULL != root->parent)
        root = root->parent;
    if (Node::RED == root->color)
        root->color = Node::BLACK;
};

void UtilTree::insert(void * v, Node *& t)
{
    if (NULL == t)
    {
        t = new Node(v);
        t->color = Node::RED;
    }
    else if (0 == (*comp)(v, t->value))
    {
        (*clean)(t->value);
        t->value = v;
    }
    else
    {
        Node *& temp = (-1 == (*comp)(v, t->value) ? t->left : t->right);
        if (NULL == temp)
        {
            insert(v, temp);
            temp->parent = t;
            balance_i(temp);
        }
        else
        {
            insert(v, temp);
        }
    }
};


void UtilTree::balance_i(Node * t)
{
    if (NULL == t) // Hmm...
        ;
    else if (NULL == t->parent)        // root node, fix color.
        t->color = Node::BLACK;
    else if (Node::BLACK == t->parent->color) // parent black, leave alone.
        ;
    else        // parent red.
    {
        bool parentLeft = t->parent->parent->left == t->parent;
        bool meLeft = t->parent->left == t;

        if (parentLeft != meLeft) // rotate LR or RL case (from grandparent).
        {
            if (!meLeft) // right of parent.
            {
                if (t->left)
                    t->left->parent = t->parent;
                t->parent->right = t->left;
                t->left = t->parent;
                t->parent->parent->left = t;
                t->parent = t->parent->parent;
                t->left->parent = t;
                balance_i(t->left);
            }
            else // left of parent.
            {
                if (t->right)
                    t->right->parent = t->parent;
                t->parent->left = t->right;
                t->right = t->parent;
                t->parent->parent->right = t;
                t->parent = t->parent->parent;
                t->right->parent = t;
                balance_i(t->right);
            }
        }
        else
        {
            bool hasRedUncle = false;
            if ((parentLeft ? t->parent->parent->right
                            : t->parent->parent->left) != NULL)
            {
                if ((parentLeft ? t->parent->parent->right
                            : t->parent->parent->left)->color == Node::RED)
                {
                    hasRedUncle = true;
                }
            }

            if (hasRedUncle)
            {
                t->parent->color = Node::BLACK;
                (parentLeft ? t->parent->parent->right
                            : t->parent->parent->left)->color = Node::BLACK;
                t->parent->parent->color = Node::RED;
                balance_i(t->parent->parent);
            }
            else
            {
                t = t->parent;
                if (NULL != t->parent->parent)
                    parentLeft = t->parent->parent->left == t->parent;
                meLeft = t->parent->left == t;

                if (meLeft)
                {
                    if (t->right)
                        t->right->parent = t->parent;
                    t->parent->left = t->right;
                    t->right = t->parent;
                    if (NULL != t->parent->parent)
                        if (parentLeft)
                            t->parent->parent->left = t;
                        else
                            t->parent->parent->right = t;
                    t->parent = t->parent->parent;
                    t->right->parent = t;
                    t->color = Node::BLACK;
                    t->right->color = Node::RED;
                }
                else
                {
                    if (t->left)
                        t->left->parent = t->parent;
                    t->parent->right = t->left;
                    t->left = t->parent;
                    if (NULL != t->parent->parent)
                        if (parentLeft)
                            t->parent->parent->left = t;
                        else
                            t->parent->parent->right = t;
                    t->parent = t->parent->parent;
                    t->left->parent = t;
                    t->color = Node::BLACK;
                    t->left->color = Node::RED;
                }
            }
        }
    }
}

UtilTree::UtilTree(const UtilTree & i_copy)
{
    comp = i_copy.comp;
    clean = i_copy.clean;
    copy = i_copy.copy;

    if (NULL == i_copy.root)
        root = NULL;
    else
    {
        root = new Node(NULL);
        copyNode(root, i_copy.root, NULL);
    }
};

void UtilTree::copyNode(Node * i_dest, Node * const i_src, Node * i_parent)
{
    i_dest->parent = i_parent;
    i_dest->color = i_src->color;
    i_dest->value = (*copy)(i_src->value);
    if (NULL == i_src->left)
        i_dest->left = NULL;
    else
    {
        i_dest->left = new Node(NULL);
        copyNode(i_dest->left, i_src->left, i_dest);
    }
    if (NULL == i_src->right)
        i_dest->right = NULL;
    else
    {
        i_dest->right = new Node(NULL);
        copyNode(i_dest->right, i_src->right, i_dest);
    };
};

UtilTree::iterator & UtilTree::iterator::operator++()
{
    if (NULL == _cur)
        return *(this);

    if (NULL == _cur->right)
    {
        while (_cur != NULL)
        {
            if (NULL != _cur->parent)
                if (_cur == _cur->parent->right)
                    _cur = _cur->parent;
                else
                {
                    _cur = _cur->parent;
                    break;
                }
            else
                _cur = _cur->parent;
        }
    }
    else
    {
        _cur = _cur->right;
        while (NULL != _cur->left)
            _cur = _cur->left;
    }

    return *(this);
};

UtilTree::iterator & UtilTree::iterator::operator--()
{
    if (NULL == _cur)
        return *(this);

    if (NULL == _cur->left)
    {
        while (_cur != NULL)
        {
            if (NULL != _cur->parent)
                if (_cur == _cur->parent->left)
                    _cur = _cur->parent;
                else
                {
                    _cur = _cur->parent;
                    break;
                }
            else
                _cur = _cur->parent;
        }
    }
    else
    {
        _cur = _cur->left;
        while (NULL != _cur->right)
            _cur = _cur->right;
    }

    return *(this);
};

UtilTree::iterator UtilTree::begin() const
{
    if (NULL == root)
        return end();

    Node * tmp = root;
    while (NULL != tmp->left)
        tmp = tmp->left;

    return iterator(tmp, this);
};

} // end namespace PRDF