Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qmap.cpp

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
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
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)
49y->left->parent = x;
50 y->parent = x->parent;
51 if (x == root)
52root = y;
53 else if (x == x->parent->left)
54x->parent->left = y;
55 else
56x->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)
67y->right->parent = x;
68 y->parent = x->parent;
69 if (x == root)
70root = y;
71 else if (x == x->parent->right)
72x->parent->right = y;
73 else
74x->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 ) {
84if ( x->parent == x->parent->parent->left ) {
85 NodePtr y = x->parent->parent->right;
86 if (y && y->color == Node::Red) {
87x->parent->color = Node::Black;
88y->color = Node::Black;
89x->parent->parent->color = Node::Red;
90x = x->parent->parent;
91 } else {
92if (x == x->parent->right) {
93 x = x->parent;
94 rotateLeft( x, root );
95}
96x->parent->color = Node::Black;
97x->parent->parent->color = Node::Red;
98rotateRight (x->parent->parent, root );
99 }
100} else {
101 NodePtr y = x->parent->parent->left;
102 if ( y && y->color == Node::Red ) {
103x->parent->color = Node::Black;
104y->color = Node::Black;
105x->parent->parent->color = Node::Red;
106x = x->parent->parent;
107 } else {
108if (x == x->parent->left) {
109 x = x->parent;
110 rotateRight( x, root );
111}
112x->parent->color = Node::Black;
113x->parent->parent->color = Node::Red;
114rotateLeft( 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) {
130x = y->right;
131 } else {
132if (y->right == 0)
133 x = y->left;
134else
135 {
136y = y->right;
137while (y->left != 0)
138 y = y->left;
139x = y->right;
140 }
141 }
142 if (y != z) {
143z->left->parent = y;
144y->left = z->left;
145if (y != z->right) {
146 x_parent = y->parent;
147 if (x)
148x->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}
155if (root == z)
156 root = y;
157else if (z->parent->left == z)
158 z->parent->left = y;
159else
160 z->parent->right = y;
161y->parent = z->parent;
162// Swap the colors
163Node::Color c = y->color;
164y->color = z->color;
165z->color = c;
166y = z;
167 } else {
168x_parent = y->parent;
169if (x)
170 x->parent = y->parent;
171if (root == z)
172 root = x;
173else if (z->parent->left == z)
174 z->parent->left = x;
175else
176 z->parent->right = x;
177if ( leftmost == z ) {
178 if (z->right == 0)
179leftmost = z->parent;
180 else
181leftmost = x->minimum();
182}
183if (rightmost == z) {
184 if (z->left == 0)
185rightmost = z->parent;
186 else
187rightmost = x->maximum();
188}
189 }
190 if (y->color != Node::Red) {
191while (x != root && (x == 0 || x->color == Node::Black)) {
192 if (x == x_parent->left) {
193NodePtr w = x_parent->right;
194if (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}
200if ((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) {
207if (w->left)
208 w->left->color = Node::Black;
209w->color = Node::Red;
210rotateRight(w, root);
211w = x_parent->right;
212 }
213 w->color = x_parent->color;
214 x_parent->color = Node::Black;
215 if (w->right)
216w->right->color = Node::Black;
217 rotateLeft(x_parent, root);
218 break;
219}
220 } else {
221NodePtr w = x_parent->left;
222if (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}
228if ((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) {
235if (w->right)
236 w->right->color = Node::Black;
237w->color = Node::Red;
238rotateLeft(w, root);
239w = x_parent->left;
240 }
241 w->color = x_parent->color;
242 x_parent->color = Node::Black;
243 if (w->left)
244w->left->color = Node::Black;
245 rotateRight(x_parent, root);
246 break;
247}
248 }
249}
250if (x)
251 x->color = Node::Black;
252 }
253 return y;
254}
255

Archive Download this file

Revision: 1322