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.cpp142
1 files changed, 71 insertions, 71 deletions
diff --git a/tqtinterface/qt4/src/tools/tqmap.cpp b/tqtinterface/qt4/src/tools/tqmap.cpp
index 70d6342..e581455 100644
--- a/tqtinterface/qt4/src/tools/tqmap.cpp
+++ b/tqtinterface/qt4/src/tools/tqmap.cpp
@@ -49,16 +49,16 @@ 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;
+ y->left->parent = x;
+ y->parent = x->parent;
if (x == root)
root = y;
- else if (x == x->tqparent->left)
- x->tqparent->left = y;
+ else if (x == x->parent->left)
+ x->parent->left = y;
else
- x->tqparent->right = y;
+ x->parent->right = y;
y->left = x;
- x->tqparent = y;
+ x->parent = y;
}
@@ -67,54 +67,54 @@ 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;
+ y->right->parent = x;
+ y->parent = x->parent;
if (x == root)
root = y;
- else if (x == x->tqparent->right)
- x->tqparent->right = y;
+ else if (x == x->parent->right)
+ x->parent->right = y;
else
- x->tqparent->left = y;
+ x->parent->left = y;
y->right = x;
- x->tqparent = y;
+ x->parent = 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;
+ 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->tqparent->color = Node::Black;
+ x->parent->color = Node::Black;
y->color = Node::Black;
- x->tqparent->tqparent->color = Node::Red;
- x = x->tqparent->tqparent;
+ x->parent->parent->color = Node::Red;
+ x = x->parent->parent;
} else {
- if (x == x->tqparent->right) {
- x = x->tqparent;
+ if (x == x->parent->right) {
+ x = x->parent;
rotateLeft( x, root );
}
- x->tqparent->color = Node::Black;
- x->tqparent->tqparent->color = Node::Red;
- rotateRight (x->tqparent->tqparent, root );
+ x->parent->color = Node::Black;
+ x->parent->parent->color = Node::Red;
+ rotateRight (x->parent->parent, root );
}
} else {
- NodePtr y = x->tqparent->tqparent->left;
+ NodePtr y = x->parent->parent->left;
if ( y && y->color == Node::Red ) {
- x->tqparent->color = Node::Black;
+ x->parent->color = Node::Black;
y->color = Node::Black;
- x->tqparent->tqparent->color = Node::Red;
- x = x->tqparent->tqparent;
+ x->parent->parent->color = Node::Red;
+ x = x->parent->parent;
} else {
- if (x == x->tqparent->left) {
- x = x->tqparent;
+ if (x == x->parent->left) {
+ x = x->parent;
rotateRight( x, root );
}
- x->tqparent->color = Node::Black;
- x->tqparent->tqparent->color = Node::Red;
- rotateLeft( x->tqparent->tqparent, root );
+ x->parent->color = Node::Black;
+ x->parent->parent->color = Node::Red;
+ rotateLeft( x->parent->parent, root );
}
}
}
@@ -128,7 +128,7 @@ NodePtr TQMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,
{
NodePtr y = z;
NodePtr x;
- NodePtr x_tqparent;
+ NodePtr x_parent;
if (y->left == 0) {
x = y->right;
} else {
@@ -143,109 +143,109 @@ NodePtr TQMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,
}
}
if (y != z) {
- z->left->tqparent = y;
+ z->left->parent = y;
y->left = z->left;
if (y != z->right) {
- x_tqparent = y->tqparent;
+ x_parent = y->parent;
if (x)
- x->tqparent = y->tqparent;
- y->tqparent->left = x;
+ x->parent = y->parent;
+ y->parent->left = x;
y->right = z->right;
- z->right->tqparent = y;
+ z->right->parent = y;
} else {
- x_tqparent = y;
+ x_parent = y;
}
if (root == z)
root = y;
- else if (z->tqparent->left == z)
- z->tqparent->left = y;
+ else if (z->parent->left == z)
+ z->parent->left = y;
else
- z->tqparent->right = y;
- y->tqparent = z->tqparent;
+ 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_tqparent = y->tqparent;
+ x_parent = y->parent;
if (x)
- x->tqparent = y->tqparent;
+ x->parent = y->parent;
if (root == z)
root = x;
- else if (z->tqparent->left == z)
- z->tqparent->left = x;
+ else if (z->parent->left == z)
+ z->parent->left = x;
else
- z->tqparent->right = x;
+ z->parent->right = x;
if ( leftmost == z ) {
if (z->right == 0)
- leftmost = z->tqparent;
+ leftmost = z->parent;
else
leftmost = x->minimum();
}
if (rightmost == z) {
if (z->left == 0)
- rightmost = z->tqparent;
+ rightmost = z->parent;
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 (x == x_parent->left) {
+ NodePtr w = x_parent->right;
if (w->color == Node::Red) {
w->color = Node::Black;
- x_tqparent->color = Node::Red;
- rotateLeft(x_tqparent, root);
- w = x_tqparent->right;
+ 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_tqparent;
- x_tqparent = x_tqparent->tqparent;
+ 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_tqparent->right;
+ w = x_parent->right;
}
- w->color = x_tqparent->color;
- x_tqparent->color = Node::Black;
+ w->color = x_parent->color;
+ x_parent->color = Node::Black;
if (w->right)
w->right->color = Node::Black;
- rotateLeft(x_tqparent, root);
+ rotateLeft(x_parent, root);
break;
}
} else {
- NodePtr w = x_tqparent->left;
+ NodePtr w = x_parent->left;
if (w->color == Node::Red) {
w->color = Node::Black;
- x_tqparent->color = Node::Red;
- rotateRight(x_tqparent, root);
- w = x_tqparent->left;
+ 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_tqparent;
- x_tqparent = x_tqparent->tqparent;
+ 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_tqparent->left;
+ w = x_parent->left;
}
- w->color = x_tqparent->color;
- x_tqparent->color = Node::Black;
+ w->color = x_parent->color;
+ x_parent->color = Node::Black;
if (w->left)
w->left->color = Node::Black;
- rotateRight(x_tqparent, root);
+ rotateRight(x_parent, root);
break;
}
}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-06 03:35:03 +0000