diff options
author | (no author) <(no author)@afe2bf4a-e733-0410-8a33-86f594647bc7> | 2005-08-08 20:01:03 (GMT) |
---|---|---|
committer | (no author) <(no author)@afe2bf4a-e733-0410-8a33-86f594647bc7> | 2005-08-08 20:01:03 (GMT) |
commit | 001e27ddbb1bfaa351b5f268b22418fb0557d6c2 (patch) | |
tree | a390a2400721fd1ed137738bd2679ab33ed0306f /qtools/qmap.cpp | |
parent | 0559d5795f6e2adc993577a4dd55b5370d31677c (diff) | |
download | Doxygen-001e27ddbb1bfaa351b5f268b22418fb0557d6c2.zip Doxygen-001e27ddbb1bfaa351b5f268b22418fb0557d6c2.tar.gz Doxygen-001e27ddbb1bfaa351b5f268b22418fb0557d6c2.tar.bz2 |
This commit was manufactured by cvs2svn to create tagRelease_1_4_4_20050804
'Release_1_4_4_20050804'.
Diffstat (limited to 'qtools/qmap.cpp')
-rw-r--r-- | qtools/qmap.cpp | 254 |
1 files changed, 0 insertions, 254 deletions
diff --git a/qtools/qmap.cpp b/qtools/qmap.cpp deleted file mode 100644 index 1d2510a..0000000 --- a/qtools/qmap.cpp +++ /dev/null @@ -1,254 +0,0 @@ -/**************************************************************************** -** -** -** 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; -} |