summaryrefslogtreecommitdiffstats
path: root/qtinterface/tqmap.cpp
diff options
context:
space:
mode:
authorTimothy Pearson <kb9vqf@pearsoncomputing.net>2012-01-26 20:43:47 -0600
committerTimothy Pearson <kb9vqf@pearsoncomputing.net>2012-01-26 20:43:47 -0600
commit27917305452f2a55ae3be74e83b8a724248ec43f (patch)
tree0bfa420031e546c3cfba2a63e92d7d4191d885b6 /qtinterface/tqmap.cpp
parentdc87fbcfcf77bc9bed86b9ec03aa8163a7bf15d4 (diff)
downloadtqtinterface-27917305452f2a55ae3be74e83b8a724248ec43f.tar.gz
tqtinterface-27917305452f2a55ae3be74e83b8a724248ec43f.zip
Split out qt3 and tqt3 files
Diffstat (limited to 'qtinterface/tqmap.cpp')
-rw-r--r--qtinterface/tqmap.cpp243
1 files changed, 0 insertions, 243 deletions
diff --git a/qtinterface/tqmap.cpp b/qtinterface/tqmap.cpp
deleted file mode 100644
index 8ab4436..0000000
--- a/qtinterface/tqmap.cpp
+++ /dev/null
@@ -1,243 +0,0 @@
-/*
-
-Copyright (C) 2010 Timothy Pearson <kb9vqf@pearsoncomputing.net>
-
-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 \ No newline at end of file