| -rw-r--r-- | qmake/tools/qmap.cpp | 254 |
1 files changed, 254 insertions, 0 deletions
diff --git a/qmake/tools/qmap.cpp b/qmake/tools/qmap.cpp new file mode 100644 index 0000000..3f73f81 --- a/dev/null +++ b/qmake/tools/qmap.cpp @@ -0,0 +1,254 @@ +/**************************************************************************** +** $Id$ +** +** 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; +} |