name.cpp
Go to the documentation of this file.
00001 /*************************************************************************** 00002 file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/trunk/src/utils/name.cpp $ 00003 version : $LastChangedRevision: 1505 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2011-08-26 18:55:08 +0200 (Fri, 26 Aug 2011) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007-2011 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 Lesser General Public License as published * 00013 * by the Free Software Foundation; either version 2.1 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 GNU Lesser * 00019 * General Public License for more details. * 00020 * * 00021 * You should have received a copy of the GNU Lesser General Public * 00022 * License along with this library; if not, write to the Free Software * 00023 * Foundation Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,* 00024 * USA * 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 // Tree is already empty 00039 if (empty()) return; 00040 00041 // Locking the tree is not required: the delete method locks 00042 // the tree during the deletion. 00043 //ScopeMutexLock l(treeaccess); 00044 00045 // Erase all elements 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); // The destructor calls the erase method 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 // Lock the tree 00062 ScopeMutexLock l(treeaccess); 00063 00064 // Use the hint to create the proper starting point in the tree 00065 int comp; 00066 TreeNode* y; 00067 if (!hint) 00068 { 00069 // Effectively no hint given 00070 hint = header.parent; 00071 y = &header; 00072 } 00073 else 00074 { 00075 // Check if the hint is a good starting point to descend 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 // Move the hint up to the parent node 00082 // If I'm left child of my parent && new node needs right insert 00083 // or I'm right child of my parent && new node needs left insert 00084 hint = hint->parent; 00085 else 00086 break; 00087 } 00088 y = hint->parent; 00089 } 00090 00091 // Step down the tree till we found a proper empty leaf node in the tree 00092 for (; hint; hint = comp<0 ? hint->left : hint->right) 00093 { 00094 y = hint; 00095 // Exit the function if the key is already found 00096 comp = z->nm.compare(hint->nm); 00097 if (!comp) return hint; 00098 } 00099 00100 if (y == &header || z->nm < y->nm) 00101 { 00102 // Inserting as a new left child 00103 y->left = z; // also makes leftmost() = z when y == header 00104 if (y == &header) 00105 { 00106 // Inserting a first element in the list 00107 header.parent = z; 00108 header.right = z; 00109 } 00110 // maintain leftmost() pointing to min node 00111 else if (y == header.left) header.left = z; 00112 } 00113 else 00114 { 00115 // Inserting as a new right child 00116 y->right = z; 00117 // Maintain rightmost() pointing to max node. 00118 if (y == header.right) header.right = z; 00119 } 00120 00121 // Set parent and child pointers of the new node 00122 z->parent = y; 00123 z->left = NULL; 00124 z->right = NULL; 00125 00126 // Increase the node count 00127 ++count; 00128 00129 // Rebalance the tree 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 // A colorless node was never inserted in the tree, and shouldn't be 00193 // removed from it either... 00194 if (!z || z->color == none) return; 00195 00196 // Lock the tree 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) // z has at most one non-null child. y == z. 00204 x = y->right; // x might be null. 00205 else 00206 if (y->right == NULL) // z has exactly one non-null child. y == z. 00207 x = y->left; // x is not null. 00208 else 00209 { 00210 // z has two non-null children. Set y to 00211 y = y->right; // z's successor. x might be null. 00212 while (y->left != NULL) y = y->left; 00213 x = y->right; 00214 } 00215 if (y != z) 00216 { 00217 // relink y in place of z. y is z's successor 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; // y must be a child of left 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 // y now points to node to be actually deleted 00237 } 00238 else 00239 { // y == z 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) // z->left must be null also 00248 header.left = z->parent; 00249 // makes leftmost == header if z == root 00250 else 00251 header.left = minimum(x); 00252 } 00253 if (header.right == z) 00254 { 00255 if (z->left == NULL) // z->right must be null also 00256 header.right = z->parent; 00257 // makes rightmost == header if z == root 00258 else // x == z->left 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 // same as above, with right <-> left. 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 // x was the root 00346 header.parent = y; 00347 else if (x == x->parent->left) 00348 // x was on the left of its parent 00349 x->parent->left = y; 00350 else 00351 // x was on the right of its parent 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 // x was the root 00367 header.parent = y; 00368 else if (x == x->parent->right) 00369 // x was on the right of its parent 00370 x->parent->right = y; 00371 else 00372 // x was on the left of its parent 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 // Checks for an empty tree 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 // Nodes must have a color 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 // A red node can have only NULL and black children 00407 throw LogicException("Wrong color on node"); 00408 00409 if (L && x->nm<L->nm) 00410 // Left child isn't smaller 00411 throw LogicException("Wrong sorting on left node"); 00412 00413 if (R && R->nm<x->nm) 00414 // Right child isn't bigger 00415 throw LogicException("Wrong sorting on right node"); 00416 00417 if (!L && !R && countBlackNodes(x) != len) 00418 // All leaf nodes have the same number of black nodes on their path 00419 // to the root 00420 throw LogicException("Unbalanced count of black nodes"); 00421 } 00422 00423 // Check whether the header has a good pointer to the leftmost element 00424 if (header.left != minimum(header.parent)) 00425 throw LogicException("Incorrect tree minimum"); 00426 00427 // Check whether the header has a good pointer to the rightmost element 00428 if (header.right != maximum(header.parent)) 00429 throw LogicException("Incorrect tree maximum"); 00430 00431 // Check whether the measured node count match the expectation? 00432 if (counter != size()) 00433 throw LogicException("Incorrect tree size"); 00434 00435 // If we reach this point, then this tree is healthy 00436 } 00437 00438 } // end namespace 00439 } // end namespace