source: trunk/src/tools/qmap.cpp@ 94

Last change on this file since 94 was 2, checked in by dmik, 20 years ago

Imported xplatform parts of the official release 3.3.1 from Trolltech
  • Property svn:keywords set to Id
File size: 6.5 KB
Line 
1/****************************************************************************
2** $Id: qmap.cpp 2 2005-11-16 15:49:26Z dmik $
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
40typedef QMapNodeBase* NodePtr;
41typedef QMapNodeBase Node;
42
43
44void 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
62void 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
80void 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
122NodePtr 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}
Note: See TracBrowser for help on using the repository browser.