/****************************************************************************

** 

**

** 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;

}