name.cpp
Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/tags/0.9.1/src/utils/name.cpp $
00003   version : $LastChangedRevision: 1656 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2012-03-27 19:05:34 +0200 (Tue, 27 Mar 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 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 if (y->right == NULL) // z has exactly one non-null child. y == z.
00206     x = y->left;    // x is not null.
00207   else
00208   {
00209     // z has two non-null children.  Set y to
00210     y = y->right;   //   z's successor.  x might be null.
00211     while (y->left != NULL) y = y->left;
00212     x = y->right;
00213   }
00214   if (y != z)
00215   {
00216     // relink y in place of z.  y is z's successor
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;   // y must be a child of left
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     // y now points to node to be actually deleted
00236   }
00237   else
00238   {
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

Documentation generated for frePPLe by  doxygen