|
Packit |
1c1d7e |
/****************************************************************************
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Implementation of QMap
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Created : 990406
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file is part of the tools module of the Qt GUI Toolkit.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file may be distributed under the terms of the Q Public License
|
|
Packit |
1c1d7e |
** as defined by Trolltech AS of Norway and appearing in the file
|
|
Packit |
1c1d7e |
** LICENSE.QPL included in the packaging of this file.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file may be distributed and/or modified under the terms of the
|
|
Packit |
1c1d7e |
** GNU General Public License version 2 as published by the Free Software
|
|
Packit |
1c1d7e |
** Foundation and appearing in the file LICENSE.GPL included in the
|
|
Packit |
1c1d7e |
** packaging of this file.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
|
|
Packit |
1c1d7e |
** licenses may use this file in accordance with the Qt Commercial License
|
|
Packit |
1c1d7e |
** Agreement provided with the Software.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
|
|
Packit |
1c1d7e |
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
|
|
Packit |
1c1d7e |
** information about Qt Commercial License Agreements.
|
|
Packit |
1c1d7e |
** See http://www.trolltech.com/qpl/ for QPL licensing information.
|
|
Packit |
1c1d7e |
** See http://www.trolltech.com/gpl/ for GPL licensing information.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Contact info@trolltech.com if any conditions of this licensing are
|
|
Packit |
1c1d7e |
** not clear to you.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
**********************************************************************/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#include "qmap.h"
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
typedef QMapNodeBase* NodePtr;
|
|
Packit |
1c1d7e |
typedef QMapNodeBase Node;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void QMapPrivateBase::rotateLeft( NodePtr x, NodePtr& root)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
NodePtr y = x->right;
|
|
Packit |
1c1d7e |
x->right = y->left;
|
|
Packit |
1c1d7e |
if (y->left !=0)
|
|
Packit |
1c1d7e |
y->left->parent = x;
|
|
Packit |
1c1d7e |
y->parent = x->parent;
|
|
Packit |
1c1d7e |
if (x == root)
|
|
Packit |
1c1d7e |
root = y;
|
|
Packit |
1c1d7e |
else if (x == x->parent->left)
|
|
Packit |
1c1d7e |
x->parent->left = y;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
x->parent->right = y;
|
|
Packit |
1c1d7e |
y->left = x;
|
|
Packit |
1c1d7e |
x->parent = y;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void QMapPrivateBase::rotateRight( NodePtr x, NodePtr& root )
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
NodePtr y = x->left;
|
|
Packit |
1c1d7e |
x->left = y->right;
|
|
Packit |
1c1d7e |
if (y->right != 0)
|
|
Packit |
1c1d7e |
y->right->parent = x;
|
|
Packit |
1c1d7e |
y->parent = x->parent;
|
|
Packit |
1c1d7e |
if (x == root)
|
|
Packit |
1c1d7e |
root = y;
|
|
Packit |
1c1d7e |
else if (x == x->parent->right)
|
|
Packit |
1c1d7e |
x->parent->right = y;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
x->parent->left = y;
|
|
Packit |
1c1d7e |
y->right = x;
|
|
Packit |
1c1d7e |
x->parent = y;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void QMapPrivateBase::rebalance( NodePtr x, NodePtr& root)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
x->color = Node::Red;
|
|
Packit |
1c1d7e |
while ( x != root && x->parent->color == Node::Red ) {
|
|
Packit |
1c1d7e |
if ( x->parent == x->parent->parent->left ) {
|
|
Packit |
1c1d7e |
NodePtr y = x->parent->parent->right;
|
|
Packit |
1c1d7e |
if (y && y->color == Node::Red) {
|
|
Packit |
1c1d7e |
x->parent->color = Node::Black;
|
|
Packit |
1c1d7e |
y->color = Node::Black;
|
|
Packit |
1c1d7e |
x->parent->parent->color = Node::Red;
|
|
Packit |
1c1d7e |
x = x->parent->parent;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
if (x == x->parent->right) {
|
|
Packit |
1c1d7e |
x = x->parent;
|
|
Packit |
1c1d7e |
rotateLeft( x, root );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
x->parent->color = Node::Black;
|
|
Packit |
1c1d7e |
x->parent->parent->color = Node::Red;
|
|
Packit |
1c1d7e |
rotateRight (x->parent->parent, root );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
NodePtr y = x->parent->parent->left;
|
|
Packit |
1c1d7e |
if ( y && y->color == Node::Red ) {
|
|
Packit |
1c1d7e |
x->parent->color = Node::Black;
|
|
Packit |
1c1d7e |
y->color = Node::Black;
|
|
Packit |
1c1d7e |
x->parent->parent->color = Node::Red;
|
|
Packit |
1c1d7e |
x = x->parent->parent;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
if (x == x->parent->left) {
|
|
Packit |
1c1d7e |
x = x->parent;
|
|
Packit |
1c1d7e |
rotateRight( x, root );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
x->parent->color = Node::Black;
|
|
Packit |
1c1d7e |
x->parent->parent->color = Node::Red;
|
|
Packit |
1c1d7e |
rotateLeft( x->parent->parent, root );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
root->color = Node::Black;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
NodePtr QMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,
|
|
Packit |
1c1d7e |
NodePtr& leftmost,
|
|
Packit |
1c1d7e |
NodePtr& rightmost )
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
NodePtr y = z;
|
|
Packit |
1c1d7e |
NodePtr x;
|
|
Packit |
1c1d7e |
NodePtr x_parent;
|
|
Packit |
1c1d7e |
if (y->left == 0) {
|
|
Packit |
1c1d7e |
x = y->right;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
if (y->right == 0)
|
|
Packit |
1c1d7e |
x = y->left;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
y = y->right;
|
|
Packit |
1c1d7e |
while (y->left != 0)
|
|
Packit |
1c1d7e |
y = y->left;
|
|
Packit |
1c1d7e |
x = y->right;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if (y != z) {
|
|
Packit |
1c1d7e |
z->left->parent = y;
|
|
Packit |
1c1d7e |
y->left = z->left;
|
|
Packit |
1c1d7e |
if (y != z->right) {
|
|
Packit |
1c1d7e |
x_parent = y->parent;
|
|
Packit |
1c1d7e |
if (x)
|
|
Packit |
1c1d7e |
x->parent = y->parent;
|
|
Packit |
1c1d7e |
y->parent->left = x;
|
|
Packit |
1c1d7e |
y->right = z->right;
|
|
Packit |
1c1d7e |
z->right->parent = y;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
x_parent = y;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if (root == z)
|
|
Packit |
1c1d7e |
root = y;
|
|
Packit |
1c1d7e |
else if (z->parent->left == z)
|
|
Packit |
1c1d7e |
z->parent->left = y;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
z->parent->right = y;
|
|
Packit |
1c1d7e |
y->parent = z->parent;
|
|
Packit |
1c1d7e |
// Swap the colors
|
|
Packit |
1c1d7e |
Node::Color c = y->color;
|
|
Packit |
1c1d7e |
y->color = z->color;
|
|
Packit |
1c1d7e |
z->color = c;
|
|
Packit |
1c1d7e |
y = z;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
x_parent = y->parent;
|
|
Packit |
1c1d7e |
if (x)
|
|
Packit |
1c1d7e |
x->parent = y->parent;
|
|
Packit |
1c1d7e |
if (root == z)
|
|
Packit |
1c1d7e |
root = x;
|
|
Packit |
1c1d7e |
else if (z->parent->left == z)
|
|
Packit |
1c1d7e |
z->parent->left = x;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
z->parent->right = x;
|
|
Packit |
1c1d7e |
if ( leftmost == z ) {
|
|
Packit |
1c1d7e |
if (z->right == 0)
|
|
Packit |
1c1d7e |
leftmost = z->parent;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
leftmost = x->minimum();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if (rightmost == z) {
|
|
Packit |
1c1d7e |
if (z->left == 0)
|
|
Packit |
1c1d7e |
rightmost = z->parent;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
rightmost = x->maximum();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if (y->color != Node::Red) {
|
|
Packit |
1c1d7e |
while (x != root && (x == 0 || x->color == Node::Black)) {
|
|
Packit |
1c1d7e |
if (x == x_parent->left) {
|
|
Packit |
1c1d7e |
NodePtr w = x_parent->right;
|
|
Packit |
1c1d7e |
if (w->color == Node::Red) {
|
|
Packit |
1c1d7e |
w->color = Node::Black;
|
|
Packit |
1c1d7e |
x_parent->color = Node::Red;
|
|
Packit |
1c1d7e |
rotateLeft(x_parent, root);
|
|
Packit |
1c1d7e |
w = x_parent->right;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if ((w->left == 0 || w->left->color == Node::Black) &&
|
|
Packit |
1c1d7e |
(w->right == 0 || w->right->color == Node::Black)) {
|
|
Packit |
1c1d7e |
w->color = Node::Red;
|
|
Packit |
1c1d7e |
x = x_parent;
|
|
Packit |
1c1d7e |
x_parent = x_parent->parent;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
if (w->right == 0 || w->right->color == Node::Black) {
|
|
Packit |
1c1d7e |
if (w->left)
|
|
Packit |
1c1d7e |
w->left->color = Node::Black;
|
|
Packit |
1c1d7e |
w->color = Node::Red;
|
|
Packit |
1c1d7e |
rotateRight(w, root);
|
|
Packit |
1c1d7e |
w = x_parent->right;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
w->color = x_parent->color;
|
|
Packit |
1c1d7e |
x_parent->color = Node::Black;
|
|
Packit |
1c1d7e |
if (w->right)
|
|
Packit |
1c1d7e |
w->right->color = Node::Black;
|
|
Packit |
1c1d7e |
rotateLeft(x_parent, root);
|
|
Packit |
1c1d7e |
break;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
NodePtr w = x_parent->left;
|
|
Packit |
1c1d7e |
if (w->color == Node::Red) {
|
|
Packit |
1c1d7e |
w->color = Node::Black;
|
|
Packit |
1c1d7e |
x_parent->color = Node::Red;
|
|
Packit |
1c1d7e |
rotateRight(x_parent, root);
|
|
Packit |
1c1d7e |
w = x_parent->left;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if ((w->right == 0 || w->right->color == Node::Black) &&
|
|
Packit |
1c1d7e |
(w->left == 0 || w->left->color == Node::Black)) {
|
|
Packit |
1c1d7e |
w->color = Node::Red;
|
|
Packit |
1c1d7e |
x = x_parent;
|
|
Packit |
1c1d7e |
x_parent = x_parent->parent;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
if (w->left == 0 || w->left->color == Node::Black) {
|
|
Packit |
1c1d7e |
if (w->right)
|
|
Packit |
1c1d7e |
w->right->color = Node::Black;
|
|
Packit |
1c1d7e |
w->color = Node::Red;
|
|
Packit |
1c1d7e |
rotateLeft(w, root);
|
|
Packit |
1c1d7e |
w = x_parent->left;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
w->color = x_parent->color;
|
|
Packit |
1c1d7e |
x_parent->color = Node::Black;
|
|
Packit |
1c1d7e |
if (w->left)
|
|
Packit |
1c1d7e |
w->left->color = Node::Black;
|
|
Packit |
1c1d7e |
rotateRight(x_parent, root);
|
|
Packit |
1c1d7e |
break;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if (x)
|
|
Packit |
1c1d7e |
x->color = Node::Black;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return y;
|
|
Packit |
1c1d7e |
}
|