You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
258 lines
6.6 KiB
258 lines
6.6 KiB
/****************************************************************************
|
|
**
|
|
** Implementation of TQMap
|
|
**
|
|
** Created : 990406
|
|
**
|
|
** Copyright (C) 1992-2008 Trolltech ASA. All rights reserved.
|
|
**
|
|
** 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 "ntqmap.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->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 TQMapPrivateBase::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 TQMapPrivateBase::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 TQMapPrivateBase::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;
|
|
}
|