/*---------------------------------------------------------------------------*/
/* btree.cpp                                                                 */
/* copyright (c) innovaphone 2001                                            */
/*                                                                           */
/*---------------------------------------------------------------------------*/

#include <platform.h>
#include "../ilib/btree.h"

USING_NAMESPACE;

btree::btree()
{
    left = 0;
    right = 0;
    count = 1;
}

class btree * btree::btree_find(const void * key)
{
    if(!this) return 0;

    int compare = btree_compare(const_cast <void*>(key));
    if(!compare) return this;
    if(compare<0) return left->btree_find(const_cast <void*>(key));
    return right->btree_find(const_cast <void*>(key));
}

class btree * btree::btree_find_first_left(const void * key)
{
    if(!this) return 0;

    int compare = key? btree_compare(const_cast <void*>(key)):-1;

    if(!compare) return this;

    if(compare<0) {
        if(left) {
            class btree * r = left->btree_find_first_left(key);
            if(r) return r;
        }
        return this;
    }
    else {
        return right->btree_find_first_left(key);
    }
}

class btree * btree::btree_find_first_right(const void * key)
{
    if(!this) return 0;

    int compare = key? btree_compare(const_cast <void*>(key)):1;

    if(!compare) return this;

    if(compare>0) {
        if(right) {
            class btree * r = right->btree_find_first_right(key);
            if(r) return r;
        }
        return this;
    }
    else {
        return left->btree_find_first_right(key);
    }
}

class btree * btree::btree_find_next_left(const void * key)
{
    if(!this) return 0;

    int compare;
    if(key) compare = btree_compare(const_cast <void*>(key));
    else compare = -1;

    if(!compare) {
        class btree * r = right;
        while(r && r->left) r = r->left;
        return r;
    }
    if(compare<0) {
        if(left) {
            class btree * r = left->btree_find_next_left(key);
            if(r) return r;
        }
        return this;
    }
    else {
        if(right) return right->btree_find_next_left(key);
        return 0;
    }
}

class btree * btree::btree_find_next_right(const void * key)
{
    if(!this) return 0;

    int compare;
    if(key) compare = btree_compare(const_cast <void*>(key));
    else compare = 1;

    if(!compare) {
        class btree * r = left;
        while(r && r->right) r = r->right;
        return r;
    }
    if(compare>0) {
        if(right) {
            class btree * r = right->btree_find_next_right(key);
            if(r) return r;
        }
        return this;
    }
    else {
        if(left) return left->btree_find_next_right(key);
        return 0;
    }
}

class btree * btree::btree_find_left()
{
    if (!this) return 0;
    if (!left) return this;
    return left->btree_find_left();
}

class btree * btree::btree_find_right()
{
    if (!this) return 0;
    if (!right) return this;
    return right->btree_find_right();
}

class btree * btree::btree_put(class btree * in)
{
    if(!this) return in;

    int compare = btree_compare(in);

    if(compare<0) {
        left = left->btree_put(in);
        count +=in->count;
        return rotate_right();
    }
    else if(compare>0) {
        right = right->btree_put(in);
        count +=in->count;
        return rotate_left();
    }
    else {
        ASSERT(false,"btree-put");
    }
    return this;
}

class btree * btree::btree_put(class btree * in, bool & before, class btree * & p)
{
    if(!this) {
        before = false;
        p = 0;
        return in;
    }

    int compare = btree_compare(in);

    if(compare<0) {
        left = left->btree_put(in,before,p);
        if(left==in) {
            before = true;
            p = this;
        }
        count +=in->count;
        return rotate_right();
    }
    else if(compare>0) {
        right = right->btree_put(in,before,p);
        if(right==in) {
            before = false;
            p = this;
        }
        count +=in->count;
        return rotate_left();
    }
    else {
        ASSERT(false,"btree-put");
    }
    return this;
}

class btree * btree::btree_get(class btree * out)
{
    ASSERT(this,"btree-get");
    if(this==out) {
        int left_count = left? left->count:0;
        int right_count = right? right->count:0;
        class btree * ret;

        if(left_count>right_count) {
            ret = right->btree_put(left);
        }
        else {
            if(right) {
                ret = left->btree_put(right);
            }
            else {
                ret = 0;
            }
        }
        right = 0;
        left = 0;
        count = 1;
        return ret;
    }
    else {
        if(btree_compare(out)<0) {
            left = left->btree_get(out);
            count -=1;
            if(right) return rotate_left();
            return this;
        }
        else {
            right = right->btree_get(out);
            count -=1;
            if(left) return rotate_right();
            return this;
        }
    }
    return 0;
}

class btree * btree::rotate_right()
{
    int left_count = left->count;
    int right_count = right? right->count:0;
    int left_right_count = left->right? left->right->count:0;
    int left_left_count = left->left? left->left->count:0;
    int new_count = left_right_count+right_count+1;

    if(left_count-right_count>0 && left_count-right_count>new_count-left_left_count) {
        class btree * save_left = left;
        left = left->right;
        save_left->right = this;
        save_left->count = count;
        count = new_count;
        save_left->btree_rotated_right();
        return save_left;
    }
    return this;
}

class btree * btree::rotate_left()
{
    int right_count = right->count;
    int left_count = left? left->count:0;
    int right_left_count = right->left? right->left->count:0;
    int right_right_count = right->right? right->right->count:0;
    int new_count = right_left_count+left_count+1;

    if(right_count-left_count>0 && right_count-left_count>new_count-right_right_count) {
        class btree * save_right = right;
        right = right->left;
        save_right->left = this;
        save_right->count = count;
        count = new_count;
        save_right->btree_rotated_left();
        return save_right;
    }
    return this;
}

void btree::set_count(class btree * changed)
{
    if (changed) {
        if (left != changed && left && btree_compare(changed) < 0) {
            left->set_count(changed);
        }
        else if (right != changed && right && btree_compare(changed) > 0) {
            right->set_count(changed);
        }
    }
    count = 1 + (left ? left->count : 0) + (right ? right->count : 0);
}

void btree::tree_leak_check()
{
    if(!this) return;
    leak_check();
    if(left) left->tree_leak_check();
    if(right) right->tree_leak_check();
}

