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