/****************************************************************************
**
** Implementation of TQMap
**
** Created : 990406
**
** Copyright (C) 2010 Timothy Pearson and (C) 1992-2008 Trolltech ASA.
**
** This file is part of the tools module of the TQt GUI Toolkit.
**
** This file may be used under the terms of the GNU General
** Public License versions 2.0 or 3.0 as published by the Free
** Software Foundation and appearing in the files LICENSE.GPL2
** and LICENSE.GPL3 included in the packaging of this file.
** Alternatively you may (at your option) use any later version
** of the GNU General Public License if such license has been
** publicly approved by Trolltech ASA (or its successors, if any)
** and the KDE Free TQt Foundation.
**
** Please review the following information to ensure GNU General
** Public Licensing requirements will be met:
** http://trolltech.com/products/qt/licenses/licensing/opensource/.
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
** or contact the sales department at sales@trolltech.com.
**
** This file may be used under the terms of the Q Public License as
** defined by Trolltech ASA and appearing in the file LICENSE.TQPL
** included in the packaging of this file.  Licensees holding valid TQt
** Commercial licenses may use this file in accordance with the TQt
** Commercial License Agreement provided with the Software.
**
** This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
** INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
** A PARTICULAR PURPOSE. Trolltech reserves all rights not granted
** herein.
**
**********************************************************************/

#include "tqmap.h"

typedef TQMapNodeBase* NodePtr;
typedef TQMapNodeBase Node;


void TQMapPrivateBase::rotateLeft( NodePtr x, NodePtr& root)
{
    NodePtr y = x->right;
    x->right = y->left;
    if (y->left !=0)
	y->left->tqparent = x;
    y->tqparent = x->tqparent;
    if (x == root)
	root = y;
    else if (x == x->tqparent->left)
	x->tqparent->left = y;
    else
	x->tqparent->right = y;
    y->left = x;
    x->tqparent = y;
}


void TQMapPrivateBase::rotateRight( NodePtr x, NodePtr& root )
{
    NodePtr y = x->left;
    x->left = y->right;
    if (y->right != 0)
	y->right->tqparent = x;
    y->tqparent = x->tqparent;
    if (x == root)
	root = y;
    else if (x == x->tqparent->right)
	x->tqparent->right = y;
    else
	x->tqparent->left = y;
    y->right = x;
    x->tqparent = y;
}


void TQMapPrivateBase::rebalance( NodePtr x, NodePtr& root)
{
    x->color = Node::Red;
    while ( x != root && x->tqparent->color == Node::Red ) {
	if ( x->tqparent == x->tqparent->tqparent->left ) {
	    NodePtr y = x->tqparent->tqparent->right;
	    if (y && y->color == Node::Red) {
		x->tqparent->color = Node::Black;
		y->color = Node::Black;
		x->tqparent->tqparent->color = Node::Red;
		x = x->tqparent->tqparent;
	    } else {
		if (x == x->tqparent->right) {
		    x = x->tqparent;
		    rotateLeft( x, root );
		}
		x->tqparent->color = Node::Black;
		x->tqparent->tqparent->color = Node::Red;
		rotateRight (x->tqparent->tqparent, root );
	    }
	} else {
	    NodePtr y = x->tqparent->tqparent->left;
	    if ( y && y->color == Node::Red ) {
		x->tqparent->color = Node::Black;
		y->color = Node::Black;
		x->tqparent->tqparent->color = Node::Red;
		x = x->tqparent->tqparent;
	    } else {
		if (x == x->tqparent->left) { 
		    x = x->tqparent;
		    rotateRight( x, root );
		}
		x->tqparent->color = Node::Black;
		x->tqparent->tqparent->color = Node::Red;
		rotateLeft( x->tqparent->tqparent, root );
	    }
	}
    }
    root->color = Node::Black;
}


NodePtr TQMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,
					     NodePtr& leftmost,
					     NodePtr& rightmost )
{
    NodePtr y = z;
    NodePtr x;
    NodePtr x_tqparent;
    if (y->left == 0) {
	x = y->right;
    } else {
	if (y->right == 0)
	    x = y->left;
	else
	    {
		y = y->right;
		while (y->left != 0)
		    y = y->left;
		x = y->right;
	    }
    }
    if (y != z) {
	z->left->tqparent = y; 
	y->left = z->left;
	if (y != z->right) {
	    x_tqparent = y->tqparent;
	    if (x)
		x->tqparent = y->tqparent;
	    y->tqparent->left = x;
	    y->right = z->right;
	    z->right->tqparent = y;
	} else {
	    x_tqparent = y;  
	}
	if (root == z)
	    root = y;
	else if (z->tqparent->left == z)
	    z->tqparent->left = y;
	else 
	    z->tqparent->right = y;
	y->tqparent = z->tqparent;
	// Swap the colors
	Node::Color c = y->color;
	y->color = z->color;
	z->color = c;
	y = z;
    } else {       
	x_tqparent = y->tqparent;
	if (x)
	    x->tqparent = y->tqparent;   
	if (root == z)
	    root = x;
	else if (z->tqparent->left == z)
	    z->tqparent->left = x;
	else
	    z->tqparent->right = x;
	if ( leftmost == z ) {
	    if (z->right == 0)
		leftmost = z->tqparent;
	    else
		leftmost = x->minimum();
	}
	if (rightmost == z) {
	    if (z->left == 0)
		rightmost = z->tqparent;  
	    else
		rightmost = x->maximum();
	}
    }
    if (y->color != Node::Red) { 
	while (x != root && (x == 0 || x->color == Node::Black)) {
	    if (x == x_tqparent->left) {
		NodePtr w = x_tqparent->right;
		if (w->color == Node::Red) {
		    w->color = Node::Black;
		    x_tqparent->color = Node::Red;
		    rotateLeft(x_tqparent, root);
		    w = x_tqparent->right;
		}
		if ((w->left == 0 || w->left->color == Node::Black) &&
		    (w->right == 0 || w->right->color == Node::Black)) {
		    w->color = Node::Red;
		    x = x_tqparent;
		    x_tqparent = x_tqparent->tqparent;
		} else {
		    if (w->right == 0 || w->right->color == Node::Black) {
			if (w->left)
			    w->left->color = Node::Black;
			w->color = Node::Red;
			rotateRight(w, root);
			w = x_tqparent->right;
		    }
		    w->color = x_tqparent->color;
		    x_tqparent->color = Node::Black;
		    if (w->right)
			w->right->color = Node::Black;
		    rotateLeft(x_tqparent, root);
		    break;
		}
	    } else {
		NodePtr w = x_tqparent->left;
		if (w->color == Node::Red) {
		    w->color = Node::Black;
		    x_tqparent->color = Node::Red;
		    rotateRight(x_tqparent, root);
		    w = x_tqparent->left;
		}
		if ((w->right == 0 || w->right->color == Node::Black) &&
		    (w->left == 0 || w->left->color == Node::Black)) {
		    w->color = Node::Red;
		    x = x_tqparent;
		    x_tqparent = x_tqparent->tqparent;
		} else {
		    if (w->left == 0 || w->left->color == Node::Black) {
			if (w->right) 
			    w->right->color = Node::Black;
			w->color = Node::Red;
			rotateLeft(w, root);
			w = x_tqparent->left;
		    }
		    w->color = x_tqparent->color;
		    x_tqparent->color = Node::Black;
		    if (w->left)
			w->left->color = Node::Black;
		    rotateRight(x_tqparent, root);
		    break;
		}
	    }
	}
	if (x)
	    x->color = Node::Black;
    }
    return y;
}