1 /****************************************************************************

     2 ** 

     3 **

     4 ** Implementation of QMap

     5 **

     6 ** Created : 990406

     7 **

     8 ** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.

     9 **

    10 ** This file is part of the tools module of the Qt GUI Toolkit.

    11 **

    12 ** This file may be distributed under the terms of the Q Public License

    13 ** as defined by Trolltech AS of Norway and appearing in the file

    14 ** LICENSE.QPL included in the packaging of this file.

    15 **

    16 ** This file may be distributed and/or modified under the terms of the

    17 ** GNU General Public License version 2 as published by the Free Software

    18 ** Foundation and appearing in the file LICENSE.GPL included in the

    19 ** packaging of this file.

    20 **

    21 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition

    22 ** licenses may use this file in accordance with the Qt Commercial License

    23 ** Agreement provided with the Software.

    24 **

    25 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE

    26 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

    27 **

    28 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for

    29 **   information about Qt Commercial License Agreements.

    30 ** See http://www.trolltech.com/qpl/ for QPL licensing information.

    31 ** See http://www.trolltech.com/gpl/ for GPL licensing information.

    32 **

    33 ** Contact info@trolltech.com if any conditions of this licensing are

    34 ** not clear to you.

    35 **

    36 **********************************************************************/

    37 

    38 #include "qmap.h"

    39 

    40 typedef QMapNodeBase* NodePtr;

    41 typedef QMapNodeBase Node;

    42 

    43 

    44 void QMapPrivateBase::rotateLeft( NodePtr x, NodePtr& root)

    45 {

    46     NodePtr y = x->right;

    47     x->right = y->left;

    48     if (y->left !=0)

    49 	y->left->parent = x;

    50     y->parent = x->parent;

    51     if (x == root)

    52 	root = y;

    53     else if (x == x->parent->left)

    54 	x->parent->left = y;

    55     else

    56 	x->parent->right = y;

    57     y->left = x;

    58     x->parent = y;

    59 }

    60 

    61 

    62 void QMapPrivateBase::rotateRight( NodePtr x, NodePtr& root )

    63 {

    64     NodePtr y = x->left;

    65     x->left = y->right;

    66     if (y->right != 0)

    67 	y->right->parent = x;

    68     y->parent = x->parent;

    69     if (x == root)

    70 	root = y;

    71     else if (x == x->parent->right)

    72 	x->parent->right = y;

    73     else

    74 	x->parent->left = y;

    75     y->right = x;

    76     x->parent = y;

    77 }

    78 

    79 

    80 void QMapPrivateBase::rebalance( NodePtr x, NodePtr& root)

    81 {

    82     x->color = Node::Red;

    83     while ( x != root && x->parent->color == Node::Red ) {

    84 	if ( x->parent == x->parent->parent->left ) {

    85 	    NodePtr y = x->parent->parent->right;

    86 	    if (y && y->color == Node::Red) {

    87 		x->parent->color = Node::Black;

    88 		y->color = Node::Black;

    89 		x->parent->parent->color = Node::Red;

    90 		x = x->parent->parent;

    91 	    } else {

    92 		if (x == x->parent->right) {

    93 		    x = x->parent;

    94 		    rotateLeft( x, root );

    95 		}

    96 		x->parent->color = Node::Black;

    97 		x->parent->parent->color = Node::Red;

    98 		rotateRight (x->parent->parent, root );

    99 	    }

   100 	} else {

   101 	    NodePtr y = x->parent->parent->left;

   102 	    if ( y && y->color == Node::Red ) {

   103 		x->parent->color = Node::Black;

   104 		y->color = Node::Black;

   105 		x->parent->parent->color = Node::Red;

   106 		x = x->parent->parent;

   107 	    } else {

   108 		if (x == x->parent->left) { 

   109 		    x = x->parent;

   110 		    rotateRight( x, root );

   111 		}

   112 		x->parent->color = Node::Black;

   113 		x->parent->parent->color = Node::Red;

   114 		rotateLeft( x->parent->parent, root );

   115 	    }

   116 	}

   117     }

   118     root->color = Node::Black;

   119 }

   120 

   121 

   122 NodePtr QMapPrivateBase::removeAndRebalance( NodePtr z, NodePtr& root,

   123 					     NodePtr& leftmost,

   124 					     NodePtr& rightmost )

   125 {

   126     NodePtr y = z;

   127     NodePtr x;

   128     NodePtr x_parent;

   129     if (y->left == 0) {

   130 	x = y->right;

   131     } else {

   132 	if (y->right == 0)

   133 	    x = y->left;

   134 	else

   135 	    {

   136 		y = y->right;

   137 		while (y->left != 0)

   138 		    y = y->left;

   139 		x = y->right;

   140 	    }

   141     }

   142     if (y != z) {

   143 	z->left->parent = y; 

   144 	y->left = z->left;

   145 	if (y != z->right) {

   146 	    x_parent = y->parent;

   147 	    if (x)

   148 		x->parent = y->parent;

   149 	    y->parent->left = x;

   150 	    y->right = z->right;

   151 	    z->right->parent = y;

   152 	} else {

   153 	    x_parent = y;  

   154 	}

   155 	if (root == z)

   156 	    root = y;

   157 	else if (z->parent->left == z)

   158 	    z->parent->left = y;

   159 	else 

   160 	    z->parent->right = y;

   161 	y->parent = z->parent;

   162 	// Swap the colors

   163 	Node::Color c = y->color;

   164 	y->color = z->color;

   165 	z->color = c;

   166 	y = z;

   167     } else {       

   168 	x_parent = y->parent;

   169 	if (x)

   170 	    x->parent = y->parent;   

   171 	if (root == z)

   172 	    root = x;

   173 	else if (z->parent->left == z)

   174 	    z->parent->left = x;

   175 	else

   176 	    z->parent->right = x;

   177 	if ( leftmost == z ) {

   178 	    if (z->right == 0)

   179 		leftmost = z->parent;

   180 	    else

   181 		leftmost = x->minimum();

   182 	}

   183 	if (rightmost == z) {

   184 	    if (z->left == 0)

   185 		rightmost = z->parent;  

   186 	    else

   187 		rightmost = x->maximum();

   188 	}

   189     }

   190     if (y->color != Node::Red) { 

   191 	while (x != root && (x == 0 || x->color == Node::Black)) {

   192 	    if (x == x_parent->left) {

   193 		NodePtr w = x_parent->right;

   194 		if (w->color == Node::Red) {

   195 		    w->color = Node::Black;

   196 		    x_parent->color = Node::Red;

   197 		    rotateLeft(x_parent, root);

   198 		    w = x_parent->right;

   199 		}

   200 		if ((w->left == 0 || w->left->color == Node::Black) &&

   201 		    (w->right == 0 || w->right->color == Node::Black)) {

   202 		    w->color = Node::Red;

   203 		    x = x_parent;

   204 		    x_parent = x_parent->parent;

   205 		} else {

   206 		    if (w->right == 0 || w->right->color == Node::Black) {

   207 			if (w->left)

   208 			    w->left->color = Node::Black;

   209 			w->color = Node::Red;

   210 			rotateRight(w, root);

   211 			w = x_parent->right;

   212 		    }

   213 		    w->color = x_parent->color;

   214 		    x_parent->color = Node::Black;

   215 		    if (w->right)

   216 			w->right->color = Node::Black;

   217 		    rotateLeft(x_parent, root);

   218 		    break;

   219 		}

   220 	    } else {

   221 		NodePtr w = x_parent->left;

   222 		if (w->color == Node::Red) {

   223 		    w->color = Node::Black;

   224 		    x_parent->color = Node::Red;

   225 		    rotateRight(x_parent, root);

   226 		    w = x_parent->left;

   227 		}

   228 		if ((w->right == 0 || w->right->color == Node::Black) &&

   229 		    (w->left == 0 || w->left->color == Node::Black)) {

   230 		    w->color = Node::Red;

   231 		    x = x_parent;

   232 		    x_parent = x_parent->parent;

   233 		} else {

   234 		    if (w->left == 0 || w->left->color == Node::Black) {

   235 			if (w->right) 

   236 			    w->right->color = Node::Black;

   237 			w->color = Node::Red;

   238 			rotateLeft(w, root);

   239 			w = x_parent->left;

   240 		    }

   241 		    w->color = x_parent->color;

   242 		    x_parent->color = Node::Black;

   243 		    if (w->left)

   244 			w->left->color = Node::Black;

   245 		    rotateRight(x_parent, root);

   246 		    break;

   247 		}

   248 	    }

   249 	}

   250 	if (x)

   251 	    x->color = Node::Black;

   252     }

   253     return y;

   254 }