Sierra Toolkit Version of the Day
Mapv.cpp
00001 
00010 // ---------------------------------------------------------------------
00011 // Author:     H. Carter Edwards
00012 //
00013 // Purpose:    Associative container for allocated data objects
00014 // ---------------------------------------------------------------------
00015 // Acknowledgements:
00016 //
00017 //   Most all of the algorithms in this class were obtained from
00018 // the Hewlett-Packard source for the Standard Template Library,
00019 // thus the inclusion of Hewlett-Packard's copyright notice.
00020 // Some minor modifications were obtained from Silicon Graphics'
00021 // Standard Template Library source.
00022 // ---------------------------------------------------------------------
00023 /*
00024  * Copyright (c) 1996,1997
00025  * Silicon Graphics Computer Systems, Inc.
00026  *
00027  * Permission to use, copy, modify, distribute and sell this software
00028  * and its documentation for any purpose is hereby granted without fee,
00029  * provided that the above copyright notice appear in all copies and
00030  * that both that copyright notice and this permission notice appear
00031  * in supporting documentation.  Silicon Graphics makes no
00032  * representations about the suitability of this software for any
00033  * purpose.  It is provided "as is" without express or implied warranty.
00034  *
00035  *
00036  * Copyright (c) 1994
00037  * Hewlett-Packard Company
00038  *
00039  * Permission to use, copy, modify, distribute and sell this software
00040  * and its documentation for any purpose is hereby granted without fee,
00041  * provided that the above copyright notice appear in all copies and
00042  * that both that copyright notice and this permission notice appear
00043  * in supporting documentation.  Hewlett-Packard Company makes no
00044  * representations about the suitability of this software for any
00045  * purpose.  It is provided "as is" without express or implied warranty.
00046  *
00047  */
00048 /*
00049 Red-black tree class, designed for use in implementing STL
00050 associative containers (set, multiset, map, and multimap). The
00051 insertion and deletion algorithms are based on those in Cormen,
00052 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
00053 except that
00054 
00055 (1) the header cell is maintained with links not only to the root
00056 but also to the leftmost node of the tree, to enable constant time
00057 begin(), and to the rightmost node of the tree, to enable linear time
00058 performance when used with the generic set algorithms (set_union,
00059 etc.);
00060 
00061 (2) when a node being deleted has two children its successor node is
00062 relinked into its place, rather than copied, so that the only
00063 iterators invalidated are those referring to the deleted node.
00064 */
00065 // ---------------------------------------------------------------------
00066 
00067 // The header
00068 
00069 #include <stk_util/diag/Mapv.hpp>
00070 
00071 #include <stdexcept>
00072 #if defined(SIERRA_IA64_OPTIMIZER_WARN)
00073 #include <stk_util/diag/Env.hpp>
00074 #endif
00075 #include <string>
00076 
00077 namespace sierra {
00078 
00079 // ---------------------------------------------------------------------
00080 
00081 inline
00082 MapvNodeBase * MapvBase::minimum( MapvNodeBase * x )
00083   { while ( x->left ) x = x->left ; return x ; }
00084 
00085 inline
00086 MapvNodeBase * MapvBase::maximum( MapvNodeBase * x )
00087   { while ( x->right ) x = x->right ; return x ; }
00088 
00089 // ---------------------------------------------------------------------
00090 
00091 inline void MapvBase::rotate_left( MapvNodeBase * x )
00092 {
00093   MapvNodeBase * y = x->right ;
00094 
00095   x->right = y->left ;
00096   if ( y->left ) y->left->parent = x ;
00097   y->parent = x->parent ;
00098 
00099   if      ( x == nRoot() )         root(y);
00100   else if ( x == x->parent->left ) x->parent->left  = y ;
00101   else                             x->parent->right = y ;
00102 
00103   y->left   = x ;
00104   x->parent = y ;
00105 }
00106 
00107 inline void MapvBase::rotate_right( MapvNodeBase * x )
00108 {
00109   MapvNodeBase * y = x->left ;
00110 
00111   x->left = y->right ;
00112   if ( y->right ) y->right->parent = x;
00113   y->parent = x->parent ;
00114 
00115   if      ( x == nRoot() )          root(y);
00116   else if ( x == x->parent->right ) x->parent->right = y ;
00117   else                              x->parent->left  = y ;
00118 
00119   y->right  = x;
00120   x->parent = y;
00121 }
00122 
00123 // ---------------------------------------------------------------------
00124 
00125 void MapvBase::insert( MapvNodeBase * y , MapvNodeBase * z , bool z_lt_y )
00126 {
00127   z->remove_from_container();
00128 
00129   if ( y == nEnd() ) { // First node inserted
00130     root(z);
00131     leftmost(z);
00132     rightmost(z);
00133     z->parent = header() ; // header is 'super-root'
00134   }
00135   else {
00136     if ( z_lt_y ) {
00137       y->left = z ;
00138       // maintain leftmost() pointing to minimum node
00139       if ( y == leftmost() ) leftmost(z);
00140     }
00141     else {
00142       y->right = z;
00143       // maintain rightmost() pointing to maximum node
00144       if ( y == rightmost() ) rightmost(z);
00145     }
00146     z->parent = y ;
00147   }
00148   z->left  = 0 ;
00149   z->right = 0 ;
00150   z->color = red ;
00151   ++Count ;
00152 
00153   // -------------------------------------------------------------------
00154   // Rebalance, 'y' and 'z' are reused as a local variable
00155 
00156   while ( z != nRoot() && z->parent->color == red ) {
00157     if ( z->parent == z->parent->parent->left ) {
00158       y = z->parent->parent->right ;
00159       if ( y && y->color == red ) {
00160   z->parent->color         = black;
00161   y->color                 = black;
00162   z->parent->parent->color = red;
00163   z = z->parent->parent ;
00164       }
00165       else {
00166   if ( z == z->parent->right ) {
00167       z = z->parent ;
00168       rotate_left(z);
00169   }
00170   z->parent->color         = black;
00171   z->parent->parent->color = red;
00172   rotate_right( z->parent->parent );
00173       }
00174     }
00175     else {
00176       y = z->parent->parent->left ;
00177       if ( y && y->color == red ) {
00178   z->parent->color         = black;
00179   y->color                 = black;
00180   z->parent->parent->color = red;
00181   z = z->parent->parent ;
00182       }
00183       else {
00184   if ( z == z->parent->left ) {
00185       z = z->parent ;
00186       rotate_right(z);
00187   }
00188   z->parent->color         = black;
00189   z->parent->parent->color = red;
00190   rotate_left(z->parent->parent);
00191       }
00192     }
00193   }
00194   nRoot()->color = black;
00195 }
00196 
00197 // ---------------------------------------------------------------------
00198 
00199 void MapvBase::remove( MapvNodeBase * node )
00200 {
00201   static const char method_name[] = "MapvBase::remove" ;
00202 
00203   if ( container(node) != this ) {
00204     std::string msg(method_name);
00205     msg.append(" given object not in this container");
00206     throw std::invalid_argument( msg );
00207   }
00208 
00209   if ( 1 == Count ) { // The last node ?
00210 
00211     if ( node != leftmost() || node != rightmost() || node != nRoot() ) {
00212       std::string msg(method_name);
00213       msg.append(" internal data structure corrupted" );
00214       throw std::runtime_error( msg );
00215     }
00216 
00217     leftmost( nREnd() );
00218     rightmost( nEnd() );
00219     root(0);
00220     Count = 0 ;
00221     header()->color = red ;
00222     node->left = node->right = node->parent = 0 ; node->color = 0 ;
00223     return ;
00224   }
00225 
00226   MapvNodeBase * z = node ;
00227   MapvNodeBase * y = node ;
00228   MapvNodeBase * x = 0 ;
00229   MapvNodeBase * x_parent = 0 ;
00230 
00231   // Ready to remove
00232 
00233   if ( y->left == 0 ) {       // z has at most one non-null child. y == z
00234     x = y->right ;            // x might be null
00235   }
00236   else if ( y->right == 0 ) { // z has exactly one non-null child. y == z
00237     x = y->left ;             // z is not null
00238   }
00239   else {                      // z has two non-null children.
00240      y = y->right ;           // Set y to z's successor.
00241      while ( y->left ) y = y->left ;
00242      x = y->right ;           // x might be null
00243   }
00244 
00245   if ( y != z ) { // relink y in place of z. y is z's successor
00246     z->left->parent = y ;
00247     y->left = z->left ;
00248     if ( y != z->right ) {
00249       x_parent = y->parent ;
00250       if ( x ) x->parent = x_parent ;
00251       y->parent->left = x;   // y must be a left child
00252       y->right = z->right;
00253       z->right->parent = y;
00254     } else {
00255       x_parent = y;  // needed in case x == 0
00256     }
00257     if ( nRoot() == z) {
00258       root(y);
00259     }
00260     else if ( z->parent->left == z) {
00261       z->parent->left = y;
00262     }
00263     else {
00264       z->parent->right = y;
00265     }
00266     y->parent = z->parent;
00267     { int c = y->color; y->color = z->color; z->color = c ; }
00268     y = z;
00269     // y points to node to be actually deleted
00270   }
00271   else {  // y == z
00272     x_parent = y->parent ;
00273     if ( x ) x->parent = x_parent ; // possibly x == 0
00274     if ( nRoot() == z) {
00275       root(x);
00276     }
00277     else if ( z->parent->left == z ) {
00278       z->parent->left = x;
00279     }
00280     else {
00281       z->parent->right = x;
00282     }
00283     if ( leftmost() == z )  {
00284       if ( z->right == 0 ) { // z->left must be null also
00285   // makes leftmost() == nEnd() if z == nRoot()
00286   leftmost( z->parent );
00287       }
00288       else {
00289   leftmost( minimum(x) );
00290       }
00291     }
00292     if ( rightmost() == z )  {
00293       if ( z->left == 0 ) { // z->right must be null also
00294   // makes rightmost() == nEnd() if z == nRoot()
00295   rightmost( z->parent );
00296       }
00297       else { // x == z->left
00298   rightmost( maximum(x) );
00299       }
00300     }
00301   }
00302   if ( y->color != red ) {
00303     while ( x != nRoot() && ( x == 0 || x->color == black ) ) {
00304       if ( x == x_parent->left ) {
00305   MapvNodeBase * w = x_parent->right ;
00306   if ( w->color == red ) {
00307     w->color        = black;
00308     x_parent->color = red;
00309     rotate_left(x_parent);
00310     w = x_parent->right ;
00311   }
00312   if ((w->left  == 0 || w->left->color  == black) &&
00313       (w->right == 0 || w->right->color == black)) {
00314     w->color = red ;
00315     x = x_parent ;
00316     x_parent = x_parent->parent ;
00317   }
00318   else {
00319     if (w->right == 0 || w->right->color == black) {
00320         if ( w->left ) w->left->color = black;
00321         w->color = red;
00322         rotate_right(w);
00323         w = x_parent->right ;
00324     }
00325     w->color = x_parent->color ;
00326     x_parent->color = black;
00327     if ( w->right ) w->right->color = black;
00328     rotate_left(x_parent);
00329     break;
00330   }
00331       }
00332       else {  // same as then clause with "right" and "left" exchanged
00333   MapvNodeBase * w = x_parent->left ;
00334   if ( w->color == red ) {
00335     w->color = black;
00336     x_parent->color = red;
00337     rotate_right(x_parent);
00338     w = x_parent->left ;
00339   }
00340   if ((w->right == 0 || w->right->color == black) &&
00341       (w->left  == 0 || w->left->color  == black)) {
00342     w->color = red;
00343     x = x_parent ;
00344     x_parent = x_parent->parent ;
00345   }
00346   else {
00347     if ( w->left == 0 || w->left->color == black ) {
00348       if ( w->right ) w->right->color = black;
00349       w->color = red;
00350       rotate_left(w);
00351       w = x_parent->left ;
00352     }
00353     w->color = x_parent->color ;
00354     x_parent->color = black;
00355     if ( w->left ) w->left->color = black;
00356     rotate_right(x_parent);
00357     break;
00358   }
00359       }
00360     }
00361     if ( x ) x->color = black;
00362   }
00363 
00364   y->left = y->right = y->parent = 0 ; y->color = 0 ;
00365 
00366   --Count ; // Decrement the tree's count
00367 }
00368 
00369 // ---------------------------------------------------------------------
00370 // A reverse communicating method for deleting all entries
00371 
00372 MapvNodeBase * MapvBase::unbalancing_removal( MapvNodeBase ** n )
00373 {
00374   MapvNodeBase * t = *n ;
00375 
00376   while ( t != header() && t->parent ) {
00377     if      ( t->left  ) { t = t->left ; }
00378     else if ( t->right ) { t = t->right ; }
00379     else { // Move to parent and remove this leaf
00380       *n = t->parent ; t->parent = 0 ;
00381       if ( (*n)->left == t ) (*n)->left  = 0 ;
00382       else                   (*n)->right = 0 ;
00383     }
00384   }
00385 
00386   if ( t == header() ) {
00387 
00388     header()->parent = 0 ;
00389     header()->left   = 0 ;
00390     header()->right  = 0 ;
00391     header()->color  = red ;  /* Color the header node red */
00392 
00393     Count = 0 ;
00394 
00395     left_end.parent = 0 ;
00396     left_end.left   = 0 ;
00397     left_end.right  = 0 ;
00398     left_end.color  = black ;
00399 
00400     right_end.parent = 0 ;
00401     right_end.left   = 0 ;
00402     right_end.right  = 0 ;
00403     right_end.color  = black ;
00404 
00405     leftmost(  header()->left  = nREnd() ); // left end of the tree
00406     rightmost( header()->right = nEnd() );  // right end of the tree
00407 
00408     t = 0 ;
00409   }
00410 
00411   return t ;
00412 }
00413 
00414 // ---------------------------------------------------------------------
00415 void MapvBase::WarnOptimize()
00416 {
00417 #if defined(SIERRA_IA64_OPTIMIZER_WARN) && defined(NDEBUG)
00418     static bool warn_once=true;
00419     int my_proc=Env::parallel_rank();
00420 
00421     if ( warn_once && my_proc==0){
00422         warn_once = false;
00423         std::cerr << "Optimizing previous versions of the intel compiler "
00424                   << "caused errors in Mapv.\n"
00425                   << "Results may be suspect.\n";
00426     }
00427 #endif
00428 }
00429 
00430 // ---------------------------------------------------------------------
00431 // Virtual destructor
00432 
00433 MapvBase::~MapvBase()
00434 {
00435   if ( Count || nRoot() != 0 ) {
00436     std::string msg("MapvBase destructor, container is not empty");
00437     throw std::logic_error( msg );
00438   }
00439 }
00440 
00441 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines