Split out qt3 and tqt3 files

1 files changed, 243 insertions, 0 deletions

diff --git a/qtinterface/interface_qt3/tqmap.cpp b/qtinterface/interface_qt3/tqmap.cpp
new file mode 100644
index 0000000..8ab4436
--- /dev/null
+++ b/qtinterface/interface_qt3/tqmap.cpp
@@ -0,0 +1,243 @@
+/*
+
+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