-rw-r--r-- | qmake/tools/qmap.cpp | 254 |
1 files changed, 254 insertions, 0 deletions
diff --git a/qmake/tools/qmap.cpp b/qmake/tools/qmap.cpp new file mode 100644 index 0000000..3f73f81 --- a/dev/null +++ b/qmake/tools/qmap.cpp | |||
@@ -0,0 +1,254 @@ | |||
1 | /**************************************************************************** | ||
2 | ** $Id$ | ||
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 | } | ||