Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 12 years 8 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)␊
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}␊
255

Archive Download this file

Revision: 1322