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

Documentation generated for frePPLe by  doxygen