summaryrefslogtreecommitdiffstats
path: root/qtinterface/interface_qt3/tqmap.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'qtinterface/interface_qt3/tqmap.cpp')
-rw-r--r--qtinterface/interface_qt3/tqmap.cpp243
1 files changed, 0 insertions, 243 deletions
diff --git a/qtinterface/interface_qt3/tqmap.cpp b/qtinterface/interface_qt3/tqmap.cpp
deleted file mode 100644
index 901d879..0000000
--- a/qtinterface/interface_qt3/tqmap.cpp
+++ /dev/null
@@ -1,243 +0,0 @@
-/*
-
-Copyright (C) 2010 Timothy Pearson <[email protected]>
-
-This library is free software; you can redistribute it and/or
-modify it under the terms of the GNU General Public
-License as published by the Free Software Foundation; either
-version 2 of the License, or (at your option) any later version.
-
-This library is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-Library General Public License for more details.
-
-You should have received a copy of the GNU Library General Public License
-along with this library; see the file COPYING.LIB. If not, write to
-the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA.
-
-*/
-
-#include <tqt.h>
-#include <tqmap.h>
-
-#ifdef USE_QT4
-
-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;
-}
-
-#endif // USE_QT4
generated by cgit v1.2.1 (git 2.18.0) at 2024-12-22 03:41:59 +0000