summaryrefslogtreecommitdiffstats
path: root/tqtinterface/qt4/src/tools/tqmap.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'tqtinterface/qt4/src/tools/tqmap.cpp')
-rw-r--r--tqtinterface/qt4/src/tools/tqmap.cpp257
1 files changed, 257 insertions, 0 deletions
diff --git a/tqtinterface/qt4/src/tools/tqmap.cpp b/tqtinterface/qt4/src/tools/tqmap.cpp
new file mode 100644
index 0000000..70d6342
--- /dev/null
+++ b/tqtinterface/qt4/src/tools/tqmap.cpp
@@ -0,0 +1,257 @@
+/****************************************************************************
+**
+** Implementation of TQMap
+**
+** Created : 990406
+**
+** Copyright (C) 2010 Timothy Pearson and (C) 1992-2008 Trolltech ASA.
+**
+** 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 "tqmap.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->tqparent = x;
+ y->tqparent = x->tqparent;
+ if (x == root)
+ root = y;
+ else if (x == x->tqparent->left)
+ x->tqparent->left = y;
+ else
+ x->tqparent->right = y;
+ y->left = x;
+ x->tqparent = y;
+}
+
+
+void TQMapPrivateBase::rotateRight( NodePtr x, NodePtr& root )
+{
+ NodePtr y = x->left;
+ x->left = y->right;
+ if (y->right != 0)
+ y->right->tqparent = x;
+ y->tqparent = x->tqparent;
+ if (x == root)
+ root = y;
+ else if (x == x->tqparent->right)
+ x->tqparent->right = y;
+ else
+ x->tqparent->left = y;
+ y->right = x;
+ x->tqparent = y;
+}
+
+
+void TQMapPrivateBase::rebalance( NodePtr x, NodePtr& root)
+{
+ x->color = Node::Red;
+ while ( x != root && x->tqparent->color == Node::Red ) {
+ if ( x->tqparent == x->tqparent->tqparent->left ) {
+ NodePtr y = x->tqparent->tqparent->right;
+ if (y && y->color == Node::Red) {
+ x->tqparent->color = Node::Black;
+ y->color = Node::Black;
+ x->tqparent->tqparent->color = Node::Red;
+ x = x->tqparent->tqparent;
+ } else {
+ if (x == x->tqparent->right) {
+ x = x->tqparent;
+ rotateLeft( x, root );
+ }
+ x->tqparent->color = Node::Black;
+ x->tqparent->tqparent->color = Node::Red;
+ rotateRight (x->tqparent->tqparent, root );
+ }
+ } else {
+ NodePtr y = x->tqparent->tqparent->left;
+ if ( y && y->color == Node::Red ) {
+ x->tqparent->color = Node::Black;
+ y->color = Node::Black;
+ x->tqparent->tqparent->color = Node::Red;
+ x = x->tqparent->tqparent;
+ } else {
+ if (x == x->tqparent->left) {
+ x = x->tqparent;
+ rotateRight( x, root );
+ }
+ x->tqparent->color = Node::Black;
+ x->tqparent->tqparent->color = Node::Red;
+ rotateLeft( x->tqparent->tqparent, root );
+ }
+ }
+ }
+ root->color = Node::Black;
+}
+
+
+NodePtr TQMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,
+ NodePtr& leftmost,
+ NodePtr& rightmost )
+{
+ NodePtr y = z;
+ NodePtr x;
+ NodePtr x_tqparent;
+ 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->tqparent = y;
+ y->left = z->left;
+ if (y != z->right) {
+ x_tqparent = y->tqparent;
+ if (x)
+ x->tqparent = y->tqparent;
+ y->tqparent->left = x;
+ y->right = z->right;
+ z->right->tqparent = y;
+ } else {
+ x_tqparent = y;
+ }
+ if (root == z)
+ root = y;
+ else if (z->tqparent->left == z)
+ z->tqparent->left = y;
+ else
+ z->tqparent->right = y;
+ y->tqparent = z->tqparent;
+ // Swap the colors
+ Node::Color c = y->color;
+ y->color = z->color;
+ z->color = c;
+ y = z;
+ } else {
+ x_tqparent = y->tqparent;
+ if (x)
+ x->tqparent = y->tqparent;
+ if (root == z)
+ root = x;
+ else if (z->tqparent->left == z)
+ z->tqparent->left = x;
+ else
+ z->tqparent->right = x;
+ if ( leftmost == z ) {
+ if (z->right == 0)
+ leftmost = z->tqparent;
+ else
+ leftmost = x->minimum();
+ }
+ if (rightmost == z) {
+ if (z->left == 0)
+ rightmost = z->tqparent;
+ else
+ rightmost = x->maximum();
+ }
+ }
+ if (y->color != Node::Red) {
+ while (x != root && (x == 0 || x->color == Node::Black)) {
+ if (x == x_tqparent->left) {
+ NodePtr w = x_tqparent->right;
+ if (w->color == Node::Red) {
+ w->color = Node::Black;
+ x_tqparent->color = Node::Red;
+ rotateLeft(x_tqparent, root);
+ w = x_tqparent->right;
+ }
+ if ((w->left == 0 || w->left->color == Node::Black) &&
+ (w->right == 0 || w->right->color == Node::Black)) {
+ w->color = Node::Red;
+ x = x_tqparent;
+ x_tqparent = x_tqparent->tqparent;
+ } 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_tqparent->right;
+ }
+ w->color = x_tqparent->color;
+ x_tqparent->color = Node::Black;
+ if (w->right)
+ w->right->color = Node::Black;
+ rotateLeft(x_tqparent, root);
+ break;
+ }
+ } else {
+ NodePtr w = x_tqparent->left;
+ if (w->color == Node::Red) {
+ w->color = Node::Black;
+ x_tqparent->color = Node::Red;
+ rotateRight(x_tqparent, root);
+ w = x_tqparent->left;
+ }
+ if ((w->right == 0 || w->right->color == Node::Black) &&
+ (w->left == 0 || w->left->color == Node::Black)) {
+ w->color = Node::Red;
+ x = x_tqparent;
+ x_tqparent = x_tqparent->tqparent;
+ } 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_tqparent->left;
+ }
+ w->color = x_tqparent->color;
+ x_tqparent->color = Node::Black;
+ if (w->left)
+ w->left->color = Node::Black;
+ rotateRight(x_tqparent, root);
+ break;
+ }
+ }
+ }
+ if (x)
+ x->color = Node::Black;
+ }
+ return y;
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-05 09:32:05 +0000