diff options
author | Timothy Pearson <kb9vqf@pearsoncomputing.net> | 2012-01-26 20:43:47 -0600 |
---|---|---|
committer | Timothy Pearson <kb9vqf@pearsoncomputing.net> | 2012-01-26 20:43:47 -0600 |
commit | 27917305452f2a55ae3be74e83b8a724248ec43f (patch) | |
tree | 0bfa420031e546c3cfba2a63e92d7d4191d885b6 /qtinterface/tqmap.cpp | |
parent | dc87fbcfcf77bc9bed86b9ec03aa8163a7bf15d4 (diff) | |
download | tqtinterface-27917305452f2a55ae3be74e83b8a724248ec43f.tar.gz tqtinterface-27917305452f2a55ae3be74e83b8a724248ec43f.zip |
Split out qt3 and tqt3 files
Diffstat (limited to 'qtinterface/tqmap.cpp')
-rw-r--r-- | qtinterface/tqmap.cpp | 243 |
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 |