name.cpp
Go to the documentation of this file.
00001 /*************************************************************************** 00002 file : $URL: http://svn.code.sf.net/p/frepple/code/trunk/src/utils/name.cpp $ 00003 version : $LastChangedRevision: 1713 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2012-07-18 11:46:01 +0200 (Wed, 18 Jul 2012) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007-2012 by Johan De Taeye, frePPLe bvba * 00010 * * 00011 * This library is free software; you can redistribute it and/or modify it * 00012 * under the terms of the GNU Affero General Public License as published * 00013 * by the Free Software Foundation; either version 3 of the License, or * 00014 * (at your option) any later version. * 00015 * * 00016 * This library is distributed in the hope that it will be useful, * 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 00019 * GNU Affero General Public License for more details. * 00020 * * 00021 * You should have received a copy of the GNU Affero General Public * 00022 * License along with this program. * 00023 * If not, see <http://www.gnu.org/licenses/>. * 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 // Tree is already empty 00038 if (empty()) return; 00039 00040 // Locking the tree is not required: the delete method locks 00041 // the tree during the deletion. 00042 //ScopeMutexLock l(treeaccess); 00043 00044 // Erase all elements 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); // The destructor calls the erase method 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 // Lock the tree 00061 ScopeMutexLock l(treeaccess); 00062 00063 // Use the hint to create the proper starting point in the tree 00064 int comp; 00065 TreeNode* y; 00066 if (!hint) 00067 { 00068 // Effectively no hint given 00069 hint = header.parent; 00070 y = &header; 00071 } 00072 else 00073 { 00074 // Check if the hint is a good starting point to descend 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 // Move the hint up to the parent node 00081 // If I'm left child of my parent && new node needs right insert 00082 // or I'm right child of my parent && new node needs left insert 00083 hint = hint->parent; 00084 else 00085 break; 00086 } 00087 y = hint->parent; 00088 } 00089 00090 // Step down the tree till we found a proper empty leaf node in the tree 00091 for (; hint; hint = comp<0 ? hint->left : hint->right) 00092 { 00093 y = hint; 00094 // Exit the function if the key is already found 00095 comp = z->nm.compare(hint->nm); 00096 if (!comp) return hint; 00097 } 00098 00099 if (y == &header || z->nm < y->nm) 00100 { 00101 // Inserting as a new left child 00102 y->left = z; // also makes leftmost() = z when y == header 00103 if (y == &header) 00104 { 00105 // Inserting a first element in the list 00106 header.parent = z; 00107 header.right = z; 00108 } 00109 // maintain leftmost() pointing to min node 00110 else if (y == header.left) header.left = z; 00111 } 00112 else 00113 { 00114 // Inserting as a new right child 00115 y->right = z; 00116 // Maintain rightmost() pointing to max node. 00117 if (y == header.right) header.right = z; 00118 } 00119 00120 // Set parent and child pointers of the new node 00121 z->parent = y; 00122 z->left = NULL; 00123 z->right = NULL; 00124 00125 // Increase the node count 00126 ++count; 00127 00128 // Rebalance the tree 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 // A colorless node was never inserted in the tree, and shouldn't be 00192 // removed from it either... 00193 if (!z || z->color == none) return; 00194 00195 // Lock the tree 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) // z has at most one non-null child. y == z. 00203 x = y->right; // x might be null. 00204 else if (y->right == NULL) // z has exactly one non-null child. y == z. 00205 x = y->left; // x is not null. 00206 else 00207 { 00208 // z has two non-null children. Set y to 00209 y = y->right; // z's successor. x might be null. 00210 while (y->left != NULL) y = y->left; 00211 x = y->right; 00212 } 00213 if (y != z) 00214 { 00215 // relink y in place of z. y is z's successor 00216 z->left->parent = y; 00217 y->left = z->left; 00218 if (y != z->right) 00219 { 00220 x_parent = y->parent; 00221 if (x) x->parent = y->parent; 00222 y->parent->left = x; // y must be a child of left 00223 y->right = z->right; 00224 z->right->parent = y; 00225 } 00226 else 00227 x_parent = y; 00228 if (header.parent == z) header.parent = y; 00229 else if (z->parent->left == z) z->parent->left = y; 00230 else z->parent->right = y; 00231 y->parent = z->parent; 00232 std::swap(y->color, z->color); 00233 y = z; 00234 // y now points to node to be actually deleted 00235 } 00236 else 00237 { 00238 // y == z 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) // z->left must be null also 00247 header.left = z->parent; 00248 // makes leftmost == header if z == root 00249 else 00250 header.left = minimum(x); 00251 } 00252 if (header.right == z) 00253 { 00254 if (z->left == NULL) // z->right must be null also 00255 header.right = z->parent; 00256 // makes rightmost == header if z == root 00257 else // x == z->left 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 // same as above, with right <-> left. 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 // x was the root 00345 header.parent = y; 00346 else if (x == x->parent->left) 00347 // x was on the left of its parent 00348 x->parent->left = y; 00349 else 00350 // x was on the right of its parent 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 // x was the root 00366 header.parent = y; 00367 else if (x == x->parent->right) 00368 // x was on the right of its parent 00369 x->parent->right = y; 00370 else 00371 // x was on the left of its parent 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 // Checks for an empty tree 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 // Nodes must have a color 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 // A red node can have only NULL and black children 00406 throw LogicException("Wrong color on node"); 00407 00408 if (L && x->nm<L->nm) 00409 // Left child isn't smaller 00410 throw LogicException("Wrong sorting on left node"); 00411 00412 if (R && R->nm<x->nm) 00413 // Right child isn't bigger 00414 throw LogicException("Wrong sorting on right node"); 00415 00416 if (!L && !R && countBlackNodes(x) != len) 00417 // All leaf nodes have the same number of black nodes on their path 00418 // to the root 00419 throw LogicException("Unbalanced count of black nodes"); 00420 } 00421 00422 // Check whether the header has a good pointer to the leftmost element 00423 if (header.left != minimum(header.parent)) 00424 throw LogicException("Incorrect tree minimum"); 00425 00426 // Check whether the header has a good pointer to the rightmost element 00427 if (header.right != maximum(header.parent)) 00428 throw LogicException("Incorrect tree maximum"); 00429 00430 // Check whether the measured node count match the expectation? 00431 if (counter != size()) 00432 throw LogicException("Incorrect tree size"); 00433 00434 // If we reach this point, then this tree is healthy 00435 } 00436 00437 } // end namespace 00438 } // end namespace