/****************************************************************************
** $Id: qmap.cpp,v 1.12 2006/08/21 20:06:40 falbujer Exp $
**
** Implementation of QMap
**
** Created : 990406
**
** Copyright (C) 1992-2005 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;
}
