/****************************************************************************
** 
**
** Implementation of QMap
**
** Created : 990406
**
** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
**
** This file is part of the tools module of the Qt GUI Toolkit.
**
** This file may be distributed under the terms of the Q Public License
** as defined by Trolltech AS of Norway and appearing in the file
** LICENSE.QPL included in the packaging of this file.
**
** This file may be distributed and/or modified under the terms of the
** GNU General Public License version 2 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.
**
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
** licenses may use this file in accordance with the Qt Commercial License
** Agreement provided with the Software.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
**   information about Qt Commercial License Agreements.
** See http://www.trolltech.com/qpl/ for QPL licensing information.
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact info@trolltech.com if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/

#include "qmap.h"

typedef QMapNodeBase* NodePtr;
typedef QMapNodeBase Node;


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


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


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


NodePtr QMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,
					     NodePtr& leftmost,
					     NodePtr& rightmost )
{
    NodePtr y = z;
    NodePtr x;
    NodePtr x_parent;
    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->parent = y; 
	y->left = z->left;
	if (y != z->right) {
	    x_parent = y->parent;
	    if (x)
		x->parent = y->parent;
	    y->parent->left = x;
	    y->right = z->right;
	    z->right->parent = y;
	} else {
	    x_parent = y;  
	}
	if (root == z)
	    root = y;
	else if (z->parent->left == z)
	    z->parent->left = y;
	else 
	    z->parent->right = y;
	y->parent = z->parent;
	// Swap the colors
	Node::Color c = y->color;
	y->color = z->color;
	z->color = c;
	y = z;
    } else {       
	x_parent = y->parent;
	if (x)
	    x->parent = y->parent;   
	if (root == z)
	    root = x;
	else if (z->parent->left == z)
	    z->parent->left = x;
	else
	    z->parent->right = x;
	if ( leftmost == z ) {
	    if (z->right == 0)
		leftmost = z->parent;
	    else
		leftmost = x->minimum();
	}
	if (rightmost == z) {
	    if (z->left == 0)
		rightmost = z->parent;  
	    else
		rightmost = x->maximum();
	}
    }
    if (y->color != Node::Red) { 
	while (x != root && (x == 0 || x->color == Node::Black)) {
	    if (x == x_parent->left) {
		NodePtr w = x_parent->right;
		if (w->color == Node::Red) {
		    w->color = Node::Black;
		    x_parent->color = Node::Red;
		    rotateLeft(x_parent, root);
		    w = x_parent->right;
		}
		if ((w->left == 0 || w->left->color == Node::Black) &&
		    (w->right == 0 || w->right->color == Node::Black)) {
		    w->color = Node::Red;
		    x = x_parent;
		    x_parent = x_parent->parent;
		} 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_parent->right;
		    }
		    w->color = x_parent->color;
		    x_parent->color = Node::Black;
		    if (w->right)
			w->right->color = Node::Black;
		    rotateLeft(x_parent, root);
		    break;
		}
	    } else {
		NodePtr w = x_parent->left;
		if (w->color == Node::Red) {
		    w->color = Node::Black;
		    x_parent->color = Node::Red;
		    rotateRight(x_parent, root);
		    w = x_parent->left;
		}
		if ((w->right == 0 || w->right->color == Node::Black) &&
		    (w->left == 0 || w->left->color == Node::Black)) {
		    w->color = Node::Red;
		    x = x_parent;
		    x_parent = x_parent->parent;
		} 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_parent->left;
		    }
		    w->color = x_parent->color;
		    x_parent->color = Node::Black;
		    if (w->left)
			w->left->color = Node::Black;
		    rotateRight(x_parent, root);
		    break;
		}
	    }
	}
	if (x)
	    x->color = Node::Black;
    }
    return y;
}