# tree.cc

    00001 // RB tree utilities implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2003 Free Software Foundation, Inc.
    00004 //
    00005 // This file is part of the GNU ISO C++ Library.  This library is free
    00006 // software; you can redistribute it and/or modify it under the
    00007 // terms of the GNU General Public License as published by the
    00008 // Free Software Foundation; either version 2, or (at your option)
    00009 // any later version.
    00010
    00011 // This library is distributed in the hope that it will be useful,
    00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00014 // GNU General Public License for more details.
    00015
    00016 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /*
    00031  *
    00032  * Copyright (c) 1996,1997
    00033  * Silicon Graphics Computer Systems, Inc.
    00034  *
    00035  * Permission to use, copy, modify, distribute and sell this software
    00036  * and its documentation for any purpose is hereby granted without fee,
    00037  * provided that the above copyright notice appear in all copies and
    00038  * that both that copyright notice and this permission notice appear
    00039  * in supporting documentation.  Silicon Graphics makes no
    00040  * representations about the suitability of this software for any
    00041  * purpose.  It is provided "as is" without express or implied warranty.
    00042  *
    00043  *
    00044  * Copyright (c) 1994
    00045  * Hewlett-Packard Company
    00046  *
    00047  * Permission to use, copy, modify, distribute and sell this software
    00048  * and its documentation for any purpose is hereby granted without fee,
    00049  * provided that the above copyright notice appear in all copies and
    00050  * that both that copyright notice and this permission notice appear
    00051  * in supporting documentation.  Hewlett-Packard Company makes no
    00052  * representations about the suitability of this software for any
    00053  * purpose.  It is provided "as is" without express or implied warranty.
    00054  *
    00055  *
    00056  */
    00057
    00058 #include <bits/stl_tree.h>
    00059
    00060 namespace std
    00061 {
    00062   _Rb_tree_node_base*
    00063   _Rb_tree_increment(_Rb_tree_node_base* __x)
    00064   {
    00065     if (__x->_M_right != 0)
    00066       {
    00067         __x = __x->_M_right;
    00068         while (__x->_M_left != 0)
    00069           __x = __x->_M_left;
    00070       }
    00071     else
    00072       {
    00073         _Rb_tree_node_base* __y = __x->_M_parent;
    00074         while (__x == __y->_M_right)
    00075           {
    00076             __x = __y;
    00077             __y = __y->_M_parent;
    00078           }
    00079         if (__x->_M_right != __y)
    00080           __x = __y;
    00081       }
    00082     return __x;
    00083   }
    00084
    00085   const _Rb_tree_node_base*
    00086   _Rb_tree_increment(const _Rb_tree_node_base* __x)
    00087   {
    00088     return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
    00089   }
    00090
    00091   _Rb_tree_node_base*
    00092   _Rb_tree_decrement(_Rb_tree_node_base* __x)
    00093   {
    00094     if (__x->_M_color == _S_red
    00095         && __x->_M_parent->_M_parent == __x)
    00096       __x = __x->_M_right;
    00097     else if (__x->_M_left != 0)
    00098       {
    00099         _Rb_tree_node_base* __y = __x->_M_left;
    00100         while (__y->_M_right != 0)
    00101           __y = __y->_M_right;
    00102         __x = __y;
    00103       }
    00104     else
    00105       {
    00106         _Rb_tree_node_base* __y = __x->_M_parent;
    00107         while (__x == __y->_M_left)
    00108           {
    00109             __x = __y;
    00110             __y = __y->_M_parent;
    00111           }
    00112         __x = __y;
    00113       }
    00114     return __x;
    00115   }
    00116
    00117   const _Rb_tree_node_base*
    00118   _Rb_tree_decrement(const _Rb_tree_node_base* __x)
    00119   {
    00120     return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
    00121   }
    00122
    00123   void
    00124   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
    00125                _Rb_tree_node_base*& __root)
    00126   {
    00127     _Rb_tree_node_base* const __y = __x->_M_right;
    00128
    00129     __x->_M_right = __y->_M_left;
    00130     if (__y->_M_left !=0)
    00131       __y->_M_left->_M_parent = __x;
    00132     __y->_M_parent = __x->_M_parent;
    00133
    00134     if (__x == __root)
    00135       __root = __y;
    00136     else if (__x == __x->_M_parent->_M_left)
    00137       __x->_M_parent->_M_left = __y;
    00138     else
    00139       __x->_M_parent->_M_right = __y;
    00140     __y->_M_left = __x;
    00141     __x->_M_parent = __y;
    00142   }
    00143
    00144   void
    00145   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
    00146             _Rb_tree_node_base*& __root)
    00147   {
    00148     _Rb_tree_node_base* const __y = __x->_M_left;
    00149
    00150     __x->_M_left = __y->_M_right;
    00151     if (__y->_M_right != 0)
    00152       __y->_M_right->_M_parent = __x;
    00153     __y->_M_parent = __x->_M_parent;
    00154
    00155     if (__x == __root)
    00156       __root = __y;
    00157     else if (__x == __x->_M_parent->_M_right)
    00158       __x->_M_parent->_M_right = __y;
    00159     else
    00160       __x->_M_parent->_M_left = __y;
    00161     __y->_M_right = __x;
    00162     __x->_M_parent = __y;
    00163   }
    00164
    00165   void
    00166   _Rb_tree_insert_and_rebalance(const bool          __insert_left,
    00167                                 _Rb_tree_node_base* __x,
    00168                                 _Rb_tree_node_base* __p,
    00169                                 _Rb_tree_node_base& __header)
    00170   {
    00171     _Rb_tree_node_base *& __root = __header._M_parent;
    00172
    00173     // Initialize fields in new node to insert.
    00174     __x->_M_parent = __p;
    00175     __x->_M_left = 0;
    00176     __x->_M_right = 0;
    00177     __x->_M_color = _S_red;
    00178
    00179     // Insert.
    00180     // Make new node child of parent and maintain root, leftmost and
    00181     // rightmost nodes.
    00182     // N.B. First node is always inserted left.
    00183     if (__insert_left)
    00184       {
    00185         __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
    00186
    00187         if (__p == &__header)
    00188         {
    00189             __header._M_parent = __x;
    00190             __header._M_right = __x;
    00191         }
    00192         else if (__p == __header._M_left)
    00193           __header._M_left = __x; // maintain leftmost pointing to min node
    00194       }
    00195     else
    00196       {
    00197         __p->_M_right = __x;
    00198
    00199         if (__p == __header._M_right)
    00200           __header._M_right = __x; // maintain rightmost pointing to max node
    00201       }
    00202     // Rebalance.
    00203     while (__x != __root
    00204        && __x->_M_parent->_M_color == _S_red)
    00205       {
    00206     _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
    00207
    00208     if (__x->_M_parent == __xpp->_M_left)
    00209       {
    00210         _Rb_tree_node_base* const __y = __xpp->_M_right;
    00211         if (__y && __y->_M_color == _S_red)
    00212           {
    00213         __x->_M_parent->_M_color = _S_black;
    00214         __y->_M_color = _S_black;
    00215         __xpp->_M_color = _S_red;
    00216         __x = __xpp;
    00217           }
    00218         else
    00219           {
    00220         if (__x == __x->_M_parent->_M_right)
    00221           {
    00222             __x = __x->_M_parent;
    00223             _Rb_tree_rotate_left(__x, __root);
    00224           }
    00225         __x->_M_parent->_M_color = _S_black;
    00226         __xpp->_M_color = _S_red;
    00227         _Rb_tree_rotate_right(__xpp, __root);
    00228           }
    00229       }
    00230     else
    00231       {
    00232         _Rb_tree_node_base* const __y = __xpp->_M_left;
    00233         if (__y && __y->_M_color == _S_red)
    00234           {
    00235         __x->_M_parent->_M_color = _S_black;
    00236         __y->_M_color = _S_black;
    00237         __xpp->_M_color = _S_red;
    00238         __x = __xpp;
    00239           }
    00240         else
    00241           {
    00242         if (__x == __x->_M_parent->_M_left)
    00243           {
    00244             __x = __x->_M_parent;
    00245             _Rb_tree_rotate_right(__x, __root);
    00246           }
    00247         __x->_M_parent->_M_color = _S_black;
    00248         __xpp->_M_color = _S_red;
    00249         _Rb_tree_rotate_left(__xpp, __root);
    00250           }
    00251       }
    00252       }
    00253     __root->_M_color = _S_black;
    00254   }
    00255
    00256   _Rb_tree_node_base*
    00257   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
    00258                    _Rb_tree_node_base& __header)
    00259   {
    00260     _Rb_tree_node_base *& __root = __header._M_parent;
    00261     _Rb_tree_node_base *& __leftmost = __header._M_left;
    00262     _Rb_tree_node_base *& __rightmost = __header._M_right;
    00263     _Rb_tree_node_base* __y = __z;
    00264     _Rb_tree_node_base* __x = 0;
    00265     _Rb_tree_node_base* __x_parent = 0;
    00266
    00267     if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
    00268       __x = __y->_M_right;     // __x might be null.
    00269     else
    00270       if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
    00271     __x = __y->_M_left;    // __x is not null.
    00272       else
    00273     {
    00274       // __z has two non-null children.  Set __y to
    00275       __y = __y->_M_right;   //   __z's successor.  __x might be null.
    00276       while (__y->_M_left != 0)
    00277         __y = __y->_M_left;
    00278       __x = __y->_M_right;
    00279     }
    00280     if (__y != __z)
    00281       {
    00282     // relink y in place of z.  y is z's successor
    00283     __z->_M_left->_M_parent = __y;
    00284     __y->_M_left = __z->_M_left;
    00285     if (__y != __z->_M_right)
    00286       {
    00287         __x_parent = __y->_M_parent;
    00288         if (__x) __x->_M_parent = __y->_M_parent;
    00289         __y->_M_parent->_M_left = __x;   // __y must be a child of _M_left
    00290         __y->_M_right = __z->_M_right;
    00291         __z->_M_right->_M_parent = __y;
    00292       }
    00293     else
    00294       __x_parent = __y;
    00295     if (__root == __z)
    00296       __root = __y;
    00297     else if (__z->_M_parent->_M_left == __z)
    00298       __z->_M_parent->_M_left = __y;
    00299     else
    00300       __z->_M_parent->_M_right = __y;
    00301     __y->_M_parent = __z->_M_parent;
    00302     std::swap(__y->_M_color, __z->_M_color);
    00303     __y = __z;
    00304     // __y now points to node to be actually deleted
    00305       }
    00306     else
    00307       {                        // __y == __z
    00308     __x_parent = __y->_M_parent;
    00309     if (__x)
    00310       __x->_M_parent = __y->_M_parent;
    00311     if (__root == __z)
    00312       __root = __x;
    00313     else
    00314       if (__z->_M_parent->_M_left == __z)
    00315         __z->_M_parent->_M_left = __x;
    00316       else
    00317         __z->_M_parent->_M_right = __x;
    00318     if (__leftmost == __z)
    00319       if (__z->_M_right == 0)        // __z->_M_left must be null also
    00320         __leftmost = __z->_M_parent;
    00321     // makes __leftmost == _M_header if __z == __root
    00322       else
    00323         __leftmost = _Rb_tree_node_base::_S_minimum(__x);
    00324     if (__rightmost == __z)
    00325       if (__z->_M_left == 0)         // __z->_M_right must be null also
    00326         __rightmost = __z->_M_parent;
    00327     // makes __rightmost == _M_header if __z == __root
    00328       else                      // __x == __z->_M_left
    00329         __rightmost = _Rb_tree_node_base::_S_maximum(__x);
    00330       }
    00331     if (__y->_M_color != _S_red)
    00332       {
    00333     while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
    00334       if (__x == __x_parent->_M_left)
    00335         {
    00336           _Rb_tree_node_base* __w = __x_parent->_M_right;
    00337           if (__w->_M_color == _S_red)
    00338         {
    00339           __w->_M_color = _S_black;
    00340           __x_parent->_M_color = _S_red;
    00341           _Rb_tree_rotate_left(__x_parent, __root);
    00342           __w = __x_parent->_M_right;
    00343         }
    00344           if ((__w->_M_left == 0 ||
    00345            __w->_M_left->_M_color == _S_black) &&
    00346           (__w->_M_right == 0 ||
    00347            __w->_M_right->_M_color == _S_black))
    00348         {
    00349           __w->_M_color = _S_red;
    00350           __x = __x_parent;
    00351           __x_parent = __x_parent->_M_parent;
    00352         }
    00353           else
    00354         {
    00355           if (__w->_M_right == 0
    00356               || __w->_M_right->_M_color == _S_black)
    00357             {
    00358               __w->_M_left->_M_color = _S_black;
    00359               __w->_M_color = _S_red;
    00360               _Rb_tree_rotate_right(__w, __root);
    00361               __w = __x_parent->_M_right;
    00362             }
    00363           __w->_M_color = __x_parent->_M_color;
    00364           __x_parent->_M_color = _S_black;
    00365           if (__w->_M_right)
    00366             __w->_M_right->_M_color = _S_black;
    00367           _Rb_tree_rotate_left(__x_parent, __root);
    00368           break;
    00369         }
    00370         }
    00371       else
    00372         {
    00373           // same as above, with _M_right <-> _M_left.
    00374           _Rb_tree_node_base* __w = __x_parent->_M_left;
    00375           if (__w->_M_color == _S_red)
    00376         {
    00377           __w->_M_color = _S_black;
    00378           __x_parent->_M_color = _S_red;
    00379           _Rb_tree_rotate_right(__x_parent, __root);
    00380           __w = __x_parent->_M_left;
    00381         }
    00382           if ((__w->_M_right == 0 ||
    00383            __w->_M_right->_M_color == _S_black) &&
    00384           (__w->_M_left == 0 ||
    00385            __w->_M_left->_M_color == _S_black))
    00386         {
    00387           __w->_M_color = _S_red;
    00388           __x = __x_parent;
    00389           __x_parent = __x_parent->_M_parent;
    00390         }
    00391           else
    00392         {
    00393           if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black)
    00394             {
    00395               __w->_M_right->_M_color = _S_black;
    00396               __w->_M_color = _S_red;
    00397               _Rb_tree_rotate_left(__w, __root);
    00398               __w = __x_parent->_M_left;
    00399             }
    00400           __w->_M_color = __x_parent->_M_color;
    00401           __x_parent->_M_color = _S_black;
    00402           if (__w->_M_left)
    00403             __w->_M_left->_M_color = _S_black;
    00404           _Rb_tree_rotate_right(__x_parent, __root);
    00405           break;
    00406         }
    00407         }
    00408     if (__x) __x->_M_color = _S_black;
    00409       }
    00410     return __y;
    00411   }
    00412
    00413   unsigned int
    00414   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
    00415                        const _Rb_tree_node_base* __root)
    00416   {
    00417     if (__node == 0)
    00418       return 0;
    00419     unsigned int __sum = 0;
    00420     do
    00421       {
    00422     if (__node->_M_color == _S_black)
    00423       ++__sum;
    00424     if (__node == __root)
    00425       break;
    00426     __node = __node->_M_parent;
    00427       }
    00428     while (1);
    00429     return __sum;
    00430   }
    00431 } // namespace std