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

Documentation generated for frePPLe by  doxygen