name.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #define FREPPLE_CORE
00029 #include "frepple/utils.h"
00030
00031 namespace frepple
00032 {
00033 namespace utils
00034 {
00035
00036 DECLARE_EXPORT void Tree::clear()
00037 {
00038
00039 if (empty()) return;
00040
00041
00042
00043
00044
00045
00046 for (TreeNode* x = begin(); x != end(); x = begin())
00047 {
00048 Object *o = dynamic_cast<Object*>(x);
00049 if (o && o->getType().raiseEvent(o, SIG_REMOVE))
00050 delete(x);
00051 else
00052 throw DataException("Can't delete object");
00053 }
00054 }
00055
00056
00057 Tree::TreeNode* Tree::insert(TreeNode* z, TreeNode *hint)
00058 {
00059 if (!z) throw LogicException("Inserting null pointer in tree");
00060
00061
00062 ScopeMutexLock l(treeaccess);
00063
00064
00065 int comp;
00066 TreeNode* y;
00067 if (!hint)
00068 {
00069
00070 hint = header.parent;
00071 y = &header;
00072 }
00073 else
00074 {
00075
00076 while (hint->parent)
00077 {
00078 comp = z->nm.compare(hint->parent->nm);
00079 if ((comp>0 && hint == hint->parent->left)
00080 || (comp<0 && hint == hint->parent->right))
00081
00082
00083
00084 hint = hint->parent;
00085 else
00086 break;
00087 }
00088 y = hint->parent;
00089 }
00090
00091
00092 for (; hint; hint = comp<0 ? hint->left : hint->right)
00093 {
00094 y = hint;
00095
00096 comp = z->nm.compare(hint->nm);
00097 if (!comp) return hint;
00098 }
00099
00100 if (y == &header || z->nm < y->nm)
00101 {
00102
00103 y->left = z;
00104 if (y == &header)
00105 {
00106
00107 header.parent = z;
00108 header.right = z;
00109 }
00110
00111 else if (y == header.left) header.left = z;
00112 }
00113 else
00114 {
00115
00116 y->right = z;
00117
00118 if (y == header.right) header.right = z;
00119 }
00120
00121
00122 z->parent = y;
00123 z->left = NULL;
00124 z->right = NULL;
00125
00126
00127 ++count;
00128
00129
00130 rebalance(z);
00131 return z;
00132 }
00133
00134
00135 void Tree::rebalance(TreeNode* x)
00136 {
00137 x->color = red;
00138
00139 while (x != header.parent && x->parent->color == red)
00140 {
00141 if (x->parent == x->parent->parent->left)
00142 {
00143 TreeNode* y = x->parent->parent->right;
00144 if (y && y->color == red)
00145 {
00146 x->parent->color = black;
00147 y->color = black;
00148 x->parent->parent->color = red;
00149 x = x->parent->parent;
00150 }
00151 else
00152 {
00153 if (x == x->parent->right)
00154 {
00155 x = x->parent;
00156 rotateLeft(x);
00157 }
00158 x->parent->color = black;
00159 x->parent->parent->color = red;
00160 rotateRight(x->parent->parent);
00161 }
00162 }
00163 else
00164 {
00165 TreeNode* y = x->parent->parent->left;
00166 if (y && y->color == red)
00167 {
00168 x->parent->color = black;
00169 y->color = black;
00170 x->parent->parent->color = red;
00171 x = x->parent->parent;
00172 }
00173 else
00174 {
00175 if (x == x->parent->left)
00176 {
00177 x = x->parent;
00178 rotateRight(x);
00179 }
00180 x->parent->color = black;
00181 x->parent->parent->color = red;
00182 rotateLeft(x->parent->parent);
00183 }
00184 }
00185 }
00186 header.parent->color = black;
00187 }
00188
00189
00190 void Tree::erase(TreeNode* z)
00191 {
00192
00193
00194 if (!z || z->color == none) return;
00195
00196
00197 ScopeMutexLock l(treeaccess);
00198
00199 TreeNode* y = z;
00200 TreeNode* x = NULL;
00201 TreeNode* x_parent = NULL;
00202 --count;
00203 if (y->left == NULL)
00204 x = y->right;
00205 else
00206 if (y->right == NULL)
00207 x = y->left;
00208 else
00209 {
00210
00211 y = y->right;
00212 while (y->left != NULL) y = y->left;
00213 x = y->right;
00214 }
00215 if (y != z)
00216 {
00217
00218 z->left->parent = y;
00219 y->left = z->left;
00220 if (y != z->right)
00221 {
00222 x_parent = y->parent;
00223 if (x) x->parent = y->parent;
00224 y->parent->left = x;
00225 y->right = z->right;
00226 z->right->parent = y;
00227 }
00228 else
00229 x_parent = y;
00230 if (header.parent == z) header.parent = y;
00231 else if (z->parent->left == z) z->parent->left = y;
00232 else z->parent->right = y;
00233 y->parent = z->parent;
00234 std::swap(y->color, z->color);
00235 y = z;
00236
00237 }
00238 else
00239 {
00240 x_parent = y->parent;
00241 if (x) x->parent = y->parent;
00242 if (header.parent == z) header.parent = x;
00243 else if (z->parent->left == z) z->parent->left = x;
00244 else z->parent->right = x;
00245 if (header.left == z)
00246 {
00247 if (z->right == NULL)
00248 header.left = z->parent;
00249
00250 else
00251 header.left = minimum(x);
00252 }
00253 if (header.right == z)
00254 {
00255 if (z->left == NULL)
00256 header.right = z->parent;
00257
00258 else
00259 header.right = maximum(x);
00260 }
00261 }
00262 if (y->color != red)
00263 {
00264 while (x != header.parent && (x == NULL || x->color == black))
00265 if (x == x_parent->left)
00266 {
00267 TreeNode* w = x_parent->right;
00268 if (w->color == red)
00269 {
00270 w->color = black;
00271 x_parent->color = red;
00272 rotateLeft(x_parent);
00273 w = x_parent->right;
00274 }
00275 if ((w->left == NULL || w->left->color == black) &&
00276 (w->right == NULL || w->right->color == black))
00277 {
00278 w->color = red;
00279 x = x_parent;
00280 x_parent = x_parent->parent;
00281 }
00282 else
00283 {
00284 if (w->right == NULL || w->right->color == black)
00285 {
00286 w->left->color = black;
00287 w->color = red;
00288 rotateRight(w);
00289 w = x_parent->right;
00290 }
00291 w->color = x_parent->color;
00292 x_parent->color = black;
00293 if (w->right) w->right->color = black;
00294 rotateLeft(x_parent);
00295 break;
00296 }
00297 }
00298 else
00299 {
00300
00301 TreeNode* w = x_parent->left;
00302 if (w->color == red)
00303 {
00304 w->color = black;
00305 x_parent->color = red;
00306 rotateRight(x_parent);
00307 w = x_parent->left;
00308 }
00309 if ((w->right == NULL || w->right->color == black) &&
00310 (w->left == NULL || w->left->color == black))
00311 {
00312 w->color = red;
00313 x = x_parent;
00314 x_parent = x_parent->parent;
00315 }
00316 else
00317 {
00318 if (w->left == NULL || w->left->color == black)
00319 {
00320 w->right->color = black;
00321 w->color = red;
00322 rotateLeft(w);
00323 w = x_parent->left;
00324 }
00325 w->color = x_parent->color;
00326 x_parent->color = black;
00327 if (w->left) w->left->color = black;
00328 rotateRight(x_parent);
00329 break;
00330 }
00331 }
00332 if (x) x->color = black;
00333 }
00334 }
00335
00336
00337 void Tree::rotateLeft(TreeNode* x)
00338 {
00339 TreeNode* y = x->right;
00340 x->right = y->left;
00341 if (y->left != NULL) y->left->parent = x;
00342 y->parent = x->parent;
00343
00344 if (x == header.parent)
00345
00346 header.parent = y;
00347 else if (x == x->parent->left)
00348
00349 x->parent->left = y;
00350 else
00351
00352 x->parent->right = y;
00353 y->left = x;
00354 x->parent = y;
00355 }
00356
00357
00358 void Tree::rotateRight(TreeNode* x)
00359 {
00360 TreeNode* y = x->left;
00361 x->left = y->right;
00362 if (y->right != NULL) y->right->parent = x;
00363 y->parent = x->parent;
00364
00365 if (x == header.parent)
00366
00367 header.parent = y;
00368 else if (x == x->parent->right)
00369
00370 x->parent->right = y;
00371 else
00372
00373 x->parent->left = y;
00374 y->right = x;
00375 x->parent = y;
00376 }
00377
00378
00379 DECLARE_EXPORT void Tree::verify() const
00380 {
00381
00382 if (empty() || begin() == end())
00383 {
00384 bool ok = (empty() &&
00385 begin() == end() &&
00386 header.left == &header &&
00387 header.right == &header);
00388 if (!ok) throw LogicException("Invalid empty tree");
00389 return;
00390 }
00391
00392 unsigned int len = countBlackNodes(header.left);
00393 size_t counter = 0;
00394 for (TreeNode* x = begin(); x != end(); x = x->increment())
00395 {
00396 TreeNode* L = x->left;
00397 TreeNode* R = x->right;
00398 ++counter;
00399
00400 if (x->color == none)
00401
00402 throw LogicException("Colorless node included in a tree");
00403
00404 if (x->color == red)
00405 if ((L && L->color == red) || (R && R->color == red))
00406
00407 throw LogicException("Wrong color on node");
00408
00409 if (L && x->nm<L->nm)
00410
00411 throw LogicException("Wrong sorting on left node");
00412
00413 if (R && R->nm<x->nm)
00414
00415 throw LogicException("Wrong sorting on right node");
00416
00417 if (!L && !R && countBlackNodes(x) != len)
00418
00419
00420 throw LogicException("Unbalanced count of black nodes");
00421 }
00422
00423
00424 if (header.left != minimum(header.parent))
00425 throw LogicException("Incorrect tree minimum");
00426
00427
00428 if (header.right != maximum(header.parent))
00429 throw LogicException("Incorrect tree maximum");
00430
00431
00432 if (counter != size())
00433 throw LogicException("Incorrect tree size");
00434
00435
00436 }
00437
00438 }
00439 }