URL https://opencores.org/ocsvn/scarts/scarts/trunk

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [src/] [tree.cc] - Blame information for rev 18

Details | Compare with Previous | View Log


// RB tree utilities implementation -*- C++ -*-
 
// Copyright (C) 2003 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.
 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
 
// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.
 
// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.
 
/*
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 */
 
#include <bits/stl_tree.h>
 
namespace std
{
  _Rb_tree_node_base*
  _Rb_tree_increment(_Rb_tree_node_base* __x)
  {
    if (__x->_M_right != 0)
      {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
          __x = __x->_M_left;
      }
    else
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_right)
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        if (__x->_M_right != __y)
          __x = __y;
      }
    return __x;
  }
 
  const _Rb_tree_node_base*
  _Rb_tree_increment(const _Rb_tree_node_base* __x)
  {
    return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
  }
 
  _Rb_tree_node_base*
  _Rb_tree_decrement(_Rb_tree_node_base* __x)
  {
    if (__x->_M_color == _S_red
        && __x->_M_parent->_M_parent == __x)
      __x = __x->_M_right;
    else if (__x->_M_left != 0)
      {
        _Rb_tree_node_base* __y = __x->_M_left;
        while (__y->_M_right != 0)
          __y = __y->_M_right;
        __x = __y;
      }
    else
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_left)
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        __x = __y;
      }
    return __x;
  }
 
  const _Rb_tree_node_base*
  _Rb_tree_decrement(const _Rb_tree_node_base* __x)
  {
    return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
  }
 
  void
  _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
                       _Rb_tree_node_base*& __root)
  {
    _Rb_tree_node_base* const __y = __x->_M_right;
 
    __x->_M_right = __y->_M_left;
    if (__y->_M_left !=0)
      __y->_M_left->_M_parent = __x;
    __y->_M_parent = __x->_M_parent;
 
    if (__x == __root)
      __root = __y;
    else if (__x == __x->_M_parent->_M_left)
      __x->_M_parent->_M_left = __y;
    else
      __x->_M_parent->_M_right = __y;
    __y->_M_left = __x;
    __x->_M_parent = __y;
  }
 
  void
  _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
                        _Rb_tree_node_base*& __root)
  {
    _Rb_tree_node_base* const __y = __x->_M_left;
 
    __x->_M_left = __y->_M_right;
    if (__y->_M_right != 0)
      __y->_M_right->_M_parent = __x;
    __y->_M_parent = __x->_M_parent;
 
    if (__x == __root)
      __root = __y;
    else if (__x == __x->_M_parent->_M_right)
      __x->_M_parent->_M_right = __y;
    else
      __x->_M_parent->_M_left = __y;
    __y->_M_right = __x;
    __x->_M_parent = __y;
  }
 
  void
  _Rb_tree_insert_and_rebalance(const bool          __insert_left,
                                _Rb_tree_node_base* __x,
                                _Rb_tree_node_base* __p,
                                _Rb_tree_node_base& __header)
  {
    _Rb_tree_node_base *& __root = __header._M_parent;
 
    // Initialize fields in new node to insert.
    __x->_M_parent = __p;
    __x->_M_left = 0;
    __x->_M_right = 0;
    __x->_M_color = _S_red;
 
    // Insert.
    // Make new node child of parent and maintain root, leftmost and
    // rightmost nodes.
    // N.B. First node is always inserted left.
    if (__insert_left)
      {
        __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
 
        if (__p == &__header)
        {
            __header._M_parent = __x;
            __header._M_right = __x;
        }
        else if (__p == __header._M_left)
          __header._M_left = __x; // maintain leftmost pointing to min node
      }
    else
      {
        __p->_M_right = __x;
 
        if (__p == __header._M_right)
          __header._M_right = __x; // maintain rightmost pointing to max node
      }
    // Rebalance.
    while (__x != __root
           && __x->_M_parent->_M_color == _S_red)
      {
        _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
 
        if (__x->_M_parent == __xpp->_M_left)
          {
            _Rb_tree_node_base* const __y = __xpp->_M_right;
            if (__y && __y->_M_color == _S_red)
              {
                __x->_M_parent->_M_color = _S_black;
                __y->_M_color = _S_black;
                __xpp->_M_color = _S_red;
                __x = __xpp;
              }
            else
              {
                if (__x == __x->_M_parent->_M_right)
                  {
                    __x = __x->_M_parent;
                    _Rb_tree_rotate_left(__x, __root);
                  }
                __x->_M_parent->_M_color = _S_black;
                __xpp->_M_color = _S_red;
                _Rb_tree_rotate_right(__xpp, __root);
              }
          }
        else
          {
            _Rb_tree_node_base* const __y = __xpp->_M_left;
            if (__y && __y->_M_color == _S_red)
              {
                __x->_M_parent->_M_color = _S_black;
                __y->_M_color = _S_black;
                __xpp->_M_color = _S_red;
                __x = __xpp;
              }
            else
              {
                if (__x == __x->_M_parent->_M_left)
                  {
                    __x = __x->_M_parent;
                    _Rb_tree_rotate_right(__x, __root);
                  }
                __x->_M_parent->_M_color = _S_black;
                __xpp->_M_color = _S_red;
                _Rb_tree_rotate_left(__xpp, __root);
              }
          }
      }
    __root->_M_color = _S_black;
  }
 
  _Rb_tree_node_base*
  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
                               _Rb_tree_node_base& __header)
  {
    _Rb_tree_node_base *& __root = __header._M_parent;
    _Rb_tree_node_base *& __leftmost = __header._M_left;
    _Rb_tree_node_base *& __rightmost = __header._M_right;
    _Rb_tree_node_base* __y = __z;
    _Rb_tree_node_base* __x = 0;
    _Rb_tree_node_base* __x_parent = 0;
 
    if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
      __x = __y->_M_right;     // __x might be null.
    else
      if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
        __x = __y->_M_left;    // __x is not null.
      else
        {
          // __z has two non-null children.  Set __y to
          __y = __y->_M_right;   //   __z's successor.  __x might be null.
          while (__y->_M_left != 0)
            __y = __y->_M_left;
          __x = __y->_M_right;
        }
    if (__y != __z)
      {
        // relink y in place of z.  y is z's successor
        __z->_M_left->_M_parent = __y;
        __y->_M_left = __z->_M_left;
        if (__y != __z->_M_right)
          {
            __x_parent = __y->_M_parent;
            if (__x) __x->_M_parent = __y->_M_parent;
            __y->_M_parent->_M_left = __x;   // __y must be a child of _M_left
            __y->_M_right = __z->_M_right;
            __z->_M_right->_M_parent = __y;
          }
        else
          __x_parent = __y;
        if (__root == __z)
          __root = __y;
        else if (__z->_M_parent->_M_left == __z)
          __z->_M_parent->_M_left = __y;
        else
          __z->_M_parent->_M_right = __y;
        __y->_M_parent = __z->_M_parent;
        std::swap(__y->_M_color, __z->_M_color);
        __y = __z;
        // __y now points to node to be actually deleted
      }
    else
      {                        // __y == __z
        __x_parent = __y->_M_parent;
        if (__x)
          __x->_M_parent = __y->_M_parent;
        if (__root == __z)
          __root = __x;
        else
          if (__z->_M_parent->_M_left == __z)
            __z->_M_parent->_M_left = __x;
          else
            __z->_M_parent->_M_right = __x;
        if (__leftmost == __z)
          if (__z->_M_right == 0)        // __z->_M_left must be null also
            __leftmost = __z->_M_parent;
        // makes __leftmost == _M_header if __z == __root
          else
            __leftmost = _Rb_tree_node_base::_S_minimum(__x);
        if (__rightmost == __z)
          if (__z->_M_left == 0)         // __z->_M_right must be null also
            __rightmost = __z->_M_parent;
        // makes __rightmost == _M_header if __z == __root
          else                      // __x == __z->_M_left
            __rightmost = _Rb_tree_node_base::_S_maximum(__x);
      }
    if (__y->_M_color != _S_red)
      {
        while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
          if (__x == __x_parent->_M_left)
            {
              _Rb_tree_node_base* __w = __x_parent->_M_right;
              if (__w->_M_color == _S_red)
                {
                  __w->_M_color = _S_black;
                  __x_parent->_M_color = _S_red;
                  _Rb_tree_rotate_left(__x_parent, __root);
                  __w = __x_parent->_M_right;
                }
              if ((__w->_M_left == 0 ||
                   __w->_M_left->_M_color == _S_black) &&
                  (__w->_M_right == 0 ||
                   __w->_M_right->_M_color == _S_black))
                {
                  __w->_M_color = _S_red;
                  __x = __x_parent;
                  __x_parent = __x_parent->_M_parent;
                }
              else
                {
                  if (__w->_M_right == 0
                      || __w->_M_right->_M_color == _S_black)
                    {
                      __w->_M_left->_M_color = _S_black;
                      __w->_M_color = _S_red;
                      _Rb_tree_rotate_right(__w, __root);
                      __w = __x_parent->_M_right;
                    }
                  __w->_M_color = __x_parent->_M_color;
                  __x_parent->_M_color = _S_black;
                  if (__w->_M_right)
                    __w->_M_right->_M_color = _S_black;
                  _Rb_tree_rotate_left(__x_parent, __root);
                  break;
                }
            }
          else
            {
              // same as above, with _M_right <-> _M_left.
              _Rb_tree_node_base* __w = __x_parent->_M_left;
              if (__w->_M_color == _S_red)
                {
                  __w->_M_color = _S_black;
                  __x_parent->_M_color = _S_red;
                  _Rb_tree_rotate_right(__x_parent, __root);
                  __w = __x_parent->_M_left;
                }
              if ((__w->_M_right == 0 ||
                   __w->_M_right->_M_color == _S_black) &&
                  (__w->_M_left == 0 ||
                   __w->_M_left->_M_color == _S_black))
                {
                  __w->_M_color = _S_red;
                  __x = __x_parent;
                  __x_parent = __x_parent->_M_parent;
                }
              else
                {
                  if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black)
                    {
                      __w->_M_right->_M_color = _S_black;
                      __w->_M_color = _S_red;
                      _Rb_tree_rotate_left(__w, __root);
                      __w = __x_parent->_M_left;
                    }
                  __w->_M_color = __x_parent->_M_color;
                  __x_parent->_M_color = _S_black;
                  if (__w->_M_left)
                    __w->_M_left->_M_color = _S_black;
                  _Rb_tree_rotate_right(__x_parent, __root);
                  break;
                }
            }
        if (__x) __x->_M_color = _S_black;
      }
    return __y;
  }
 
  unsigned int
  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
                       const _Rb_tree_node_base* __root)
  {
    if (__node == 0)
      return 0;
    unsigned int __sum = 0;
    do
      {
        if (__node->_M_color == _S_black)
          ++__sum;
        if (__node == __root)
          break;
        __node = __node->_M_parent;
      }
    while (1);
    return __sum;
  }
} // namespace std 

Browse

Tools

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [src/] [tree.cc] - Blame information for rev 18

Line No.	Rev	Author	Line
1	18	jlechner	`// RB tree utilities implementation -- C++ --`
2
3			`// Copyright (C) 2003 Free Software Foundation, Inc.`
4			`//`
5			`// This file is part of the GNU ISO C++ Library. This library is free`
6			`// software; you can redistribute it and/or modify it under the`
7			`// terms of the GNU General Public License as published by the`
8			`// Free Software Foundation; either version 2, or (at your option)`
9			`// any later version.`
10
11			`// This library is distributed in the hope that it will be useful,`
12			`// but WITHOUT ANY WARRANTY; without even the implied warranty of`
13			`// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the`
14			`// GNU General Public License for more details.`
15
16			`// You should have received a copy of the GNU General Public License along`
17			`// with this library; see the file COPYING. If not, write to the Free`
18			`// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,`
19			`// USA.`
20
21			`// As a special exception, you may use this file as part of a free software`
22			`// library without restriction. Specifically, if other files instantiate`
23			`// templates or use macros or inline functions from this file, or you compile`
24			`// this file and link it with other files to produce an executable, this`
25			`// file does not by itself cause the resulting executable to be covered by`
26			`// the GNU General Public License. This exception does not however`
27			`// invalidate any other reasons why the executable file might be covered by`
28			`// the GNU General Public License.`
29
30			`/*`
31			`*`
32			`* Copyright (c) 1996,1997`
33			`* Silicon Graphics Computer Systems, Inc.`
34			`*`
35			`* Permission to use, copy, modify, distribute and sell this software`
36			`* and its documentation for any purpose is hereby granted without fee,`
37			`* provided that the above copyright notice appear in all copies and`
38			`* that both that copyright notice and this permission notice appear`
39			`* in supporting documentation. Silicon Graphics makes no`
40			`* representations about the suitability of this software for any`
41			`* purpose. It is provided "as is" without express or implied warranty.`
42			`*`
43			`*`
44			`* Copyright (c) 1994`
45			`* Hewlett-Packard Company`
46			`*`
47			`* Permission to use, copy, modify, distribute and sell this software`
48			`* and its documentation for any purpose is hereby granted without fee,`
49			`* provided that the above copyright notice appear in all copies and`
50			`* that both that copyright notice and this permission notice appear`
51			`* in supporting documentation. Hewlett-Packard Company makes no`
52			`* representations about the suitability of this software for any`
53			`* purpose. It is provided "as is" without express or implied warranty.`
54			`*`
55			`*`
56			`*/`
57
58			`#include <bits/stl_tree.h>`
59
60			`namespace std`
61			`{`
62			`_Rb_tree_node_base*`
63			`_Rb_tree_increment(_Rb_tree_node_base* __x)`
64			`{`
65			`if (__x->_M_right != 0)`
66			`{`
67			`__x = __x->_M_right;`
68			`while (__x->_M_left != 0)`
69			`__x = __x->_M_left;`
70			`}`
71			`else`
72			`{`
73			`_Rb_tree_node_base* __y = __x->_M_parent;`
74			`while (__x == __y->_M_right)`
75			`{`
76			`__x = __y;`
77			`__y = __y->_M_parent;`
78			`}`
79			`if (__x->_M_right != __y)`
80			`__x = __y;`
81			`}`
82			`return __x;`
83			`}`
84
85			`const _Rb_tree_node_base*`
86			`_Rb_tree_increment(const _Rb_tree_node_base* __x)`
87			`{`
88			`return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));`
89			`}`
90
91			`_Rb_tree_node_base*`
92			`_Rb_tree_decrement(_Rb_tree_node_base* __x)`
93			`{`
94			`if (__x->_M_color == _S_red`
95			`&& __x->_M_parent->_M_parent == __x)`
96			`__x = __x->_M_right;`
97			`else if (__x->_M_left != 0)`
98			`{`
99			`_Rb_tree_node_base* __y = __x->_M_left;`
100			`while (__y->_M_right != 0)`
101			`__y = __y->_M_right;`
102			`__x = __y;`
103			`}`
104			`else`
105			`{`
106			`_Rb_tree_node_base* __y = __x->_M_parent;`
107			`while (__x == __y->_M_left)`
108			`{`
109			`__x = __y;`
110			`__y = __y->_M_parent;`
111			`}`
112			`__x = __y;`
113			`}`
114			`return __x;`
115			`}`
116
117			`const _Rb_tree_node_base*`
118			`_Rb_tree_decrement(const _Rb_tree_node_base* __x)`
119			`{`
120			`return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));`
121			`}`
122
123			`void`
124			`_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,`
125			`_Rb_tree_node_base*& __root)`
126			`{`
127			`_Rb_tree_node_base* const __y = __x->_M_right;`
128
129			`__x->_M_right = __y->_M_left;`
130			`if (__y->_M_left !=0)`
131			`__y->_M_left->_M_parent = __x;`
132			`__y->_M_parent = __x->_M_parent;`
133
134			`if (__x == __root)`
135			`__root = __y;`
136			`else if (__x == __x->_M_parent->_M_left)`
137			`__x->_M_parent->_M_left = __y;`
138			`else`
139			`__x->_M_parent->_M_right = __y;`
140			`__y->_M_left = __x;`
141			`__x->_M_parent = __y;`
142			`}`
143
144			`void`
145			`_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,`
146			`_Rb_tree_node_base*& __root)`
147			`{`
148			`_Rb_tree_node_base* const __y = __x->_M_left;`
149
150			`__x->_M_left = __y->_M_right;`
151			`if (__y->_M_right != 0)`
152			`__y->_M_right->_M_parent = __x;`
153			`__y->_M_parent = __x->_M_parent;`
154
155			`if (__x == __root)`
156			`__root = __y;`
157			`else if (__x == __x->_M_parent->_M_right)`
158			`__x->_M_parent->_M_right = __y;`
159			`else`
160			`__x->_M_parent->_M_left = __y;`
161			`__y->_M_right = __x;`
162			`__x->_M_parent = __y;`
163			`}`
164
165			`void`
166			`_Rb_tree_insert_and_rebalance(const bool __insert_left,`
167			`_Rb_tree_node_base* __x,`
168			`_Rb_tree_node_base* __p,`
169			`_Rb_tree_node_base& __header)`
170			`{`
171			`_Rb_tree_node_base *& __root = __header._M_parent;`
172
173			`// Initialize fields in new node to insert.`
174			`__x->_M_parent = __p;`
175			`__x->_M_left = 0;`
176			`__x->_M_right = 0;`
177			`__x->_M_color = _S_red;`
178
179			`// Insert.`
180			`// Make new node child of parent and maintain root, leftmost and`
181			`// rightmost nodes.`
182			`// N.B. First node is always inserted left.`
183			`if (__insert_left)`
184			`{`
185			`__p->_M_left = __x; // also makes leftmost = __x when __p == &__header`
186
187			`if (__p == &__header)`
188			`{`
189			`__header._M_parent = __x;`
190			`__header._M_right = __x;`
191			`}`
192			`else if (__p == __header._M_left)`
193			`__header._M_left = __x; // maintain leftmost pointing to min node`
194			`}`
195			`else`
196			`{`
197			`__p->_M_right = __x;`
198
199			`if (__p == __header._M_right)`
200			`__header._M_right = __x; // maintain rightmost pointing to max node`
201			`}`
202			`// Rebalance.`
203			`while (__x != __root`
204			`&& __x->_M_parent->_M_color == _S_red)`
205			`{`
206			`_Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;`
207
208			`if (__x->_M_parent == __xpp->_M_left)`
209			`{`
210			`_Rb_tree_node_base* const __y = __xpp->_M_right;`
211			`if (__y && __y->_M_color == _S_red)`
212			`{`
213			`__x->_M_parent->_M_color = _S_black;`
214			`__y->_M_color = _S_black;`
215			`__xpp->_M_color = _S_red;`
216			`__x = __xpp;`
217			`}`
218			`else`
219			`{`
220			`if (__x == __x->_M_parent->_M_right)`
221			`{`
222			`__x = __x->_M_parent;`
223			`_Rb_tree_rotate_left(__x, __root);`
224			`}`
225			`__x->_M_parent->_M_color = _S_black;`
226			`__xpp->_M_color = _S_red;`
227			`_Rb_tree_rotate_right(__xpp, __root);`
228			`}`
229			`}`
230			`else`
231			`{`
232			`_Rb_tree_node_base* const __y = __xpp->_M_left;`
233			`if (__y && __y->_M_color == _S_red)`
234			`{`
235			`__x->_M_parent->_M_color = _S_black;`
236			`__y->_M_color = _S_black;`
237			`__xpp->_M_color = _S_red;`
238			`__x = __xpp;`
239			`}`
240			`else`
241			`{`
242			`if (__x == __x->_M_parent->_M_left)`
243			`{`
244			`__x = __x->_M_parent;`
245			`_Rb_tree_rotate_right(__x, __root);`
246			`}`
247			`__x->_M_parent->_M_color = _S_black;`
248			`__xpp->_M_color = _S_red;`
249			`_Rb_tree_rotate_left(__xpp, __root);`
250			`}`
251			`}`
252			`}`
253			`__root->_M_color = _S_black;`
254			`}`
255
256			`_Rb_tree_node_base*`
257			`_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,`
258			`_Rb_tree_node_base& __header)`
259			`{`
260			`_Rb_tree_node_base *& __root = __header._M_parent;`
261			`_Rb_tree_node_base *& __leftmost = __header._M_left;`
262			`_Rb_tree_node_base *& __rightmost = __header._M_right;`
263			`_Rb_tree_node_base* __y = __z;`
264			`_Rb_tree_node_base* __x = 0;`
265			`_Rb_tree_node_base* __x_parent = 0;`
266
267			`if (__y->_M_left == 0) // __z has at most one non-null child. y == z.`
268			`__x = __y->_M_right; // __x might be null.`
269			`else`
270			`if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.`
271			`__x = __y->_M_left; // __x is not null.`
272			`else`
273			`{`
274			`// __z has two non-null children. Set __y to`
275			`__y = __y->_M_right; // __z's successor. __x might be null.`
276			`while (__y->_M_left != 0)`
277			`__y = __y->_M_left;`
278			`__x = __y->_M_right;`
279			`}`
280			`if (__y != __z)`
281			`{`
282			`// relink y in place of z. y is z's successor`
283			`__z->_M_left->_M_parent = __y;`
284			`__y->_M_left = __z->_M_left;`
285			`if (__y != __z->_M_right)`
286			`{`
287			`__x_parent = __y->_M_parent;`
288			`if (__x) __x->_M_parent = __y->_M_parent;`
289			`__y->_M_parent->_M_left = __x; // __y must be a child of _M_left`
290			`__y->_M_right = __z->_M_right;`
291			`__z->_M_right->_M_parent = __y;`
292			`}`
293			`else`
294			`__x_parent = __y;`
295			`if (__root == __z)`
296			`__root = __y;`
297			`else if (__z->_M_parent->_M_left == __z)`
298			`__z->_M_parent->_M_left = __y;`
299			`else`
300			`__z->_M_parent->_M_right = __y;`
301			`__y->_M_parent = __z->_M_parent;`
302			`std::swap(__y->_M_color, __z->_M_color);`
303			`__y = __z;`
304			`// __y now points to node to be actually deleted`
305			`}`
306			`else`
307			`{ // __y == __z`
308			`__x_parent = __y->_M_parent;`
309			`if (__x)`
310			`__x->_M_parent = __y->_M_parent;`
311			`if (__root == __z)`
312			`__root = __x;`
313			`else`
314			`if (__z->_M_parent->_M_left == __z)`
315			`__z->_M_parent->_M_left = __x;`
316			`else`
317			`__z->_M_parent->_M_right = __x;`
318			`if (__leftmost == __z)`
319			`if (__z->_M_right == 0) // __z->_M_left must be null also`
320			`__leftmost = __z->_M_parent;`
321			`// makes __leftmost == _M_header if __z == __root`
322			`else`
323			`__leftmost = _Rb_tree_node_base::_S_minimum(__x);`
324			`if (__rightmost == __z)`
325			`if (__z->_M_left == 0) // __z->_M_right must be null also`
326			`__rightmost = __z->_M_parent;`
327			`// makes __rightmost == _M_header if __z == __root`
328			`else // __x == __z->_M_left`
329			`__rightmost = _Rb_tree_node_base::_S_maximum(__x);`
330			`}`
331			`if (__y->_M_color != _S_red)`
332			`{`
333			`while (__x != __root && (__x == 0 \|\| __x->_M_color == _S_black))`
334			`if (__x == __x_parent->_M_left)`
335			`{`
336			`_Rb_tree_node_base* __w = __x_parent->_M_right;`
337			`if (__w->_M_color == _S_red)`
338			`{`
339			`__w->_M_color = _S_black;`
340			`__x_parent->_M_color = _S_red;`
341			`_Rb_tree_rotate_left(__x_parent, __root);`
342			`__w = __x_parent->_M_right;`
343			`}`
344			`if ((__w->_M_left == 0 \|\|`
345			`__w->_M_left->_M_color == _S_black) &&`
346			`(__w->_M_right == 0 \|\|`
347			`__w->_M_right->_M_color == _S_black))`
348			`{`
349			`__w->_M_color = _S_red;`
350			`__x = __x_parent;`
351			`__x_parent = __x_parent->_M_parent;`
352			`}`
353			`else`
354			`{`
355			`if (__w->_M_right == 0`
356			`\|\| __w->_M_right->_M_color == _S_black)`
357			`{`
358			`__w->_M_left->_M_color = _S_black;`
359			`__w->_M_color = _S_red;`
360			`_Rb_tree_rotate_right(__w, __root);`
361			`__w = __x_parent->_M_right;`
362			`}`
363			`__w->_M_color = __x_parent->_M_color;`
364			`__x_parent->_M_color = _S_black;`
365			`if (__w->_M_right)`
366			`__w->_M_right->_M_color = _S_black;`
367			`_Rb_tree_rotate_left(__x_parent, __root);`
368			`break;`
369			`}`
370			`}`
371			`else`
372			`{`
373			`// same as above, with _M_right <-> _M_left.`
374			`_Rb_tree_node_base* __w = __x_parent->_M_left;`
375			`if (__w->_M_color == _S_red)`
376			`{`
377			`__w->_M_color = _S_black;`
378			`__x_parent->_M_color = _S_red;`
379			`_Rb_tree_rotate_right(__x_parent, __root);`
380			`__w = __x_parent->_M_left;`
381			`}`
382			`if ((__w->_M_right == 0 \|\|`
383			`__w->_M_right->_M_color == _S_black) &&`
384			`(__w->_M_left == 0 \|\|`
385			`__w->_M_left->_M_color == _S_black))`
386			`{`
387			`__w->_M_color = _S_red;`
388			`__x = __x_parent;`
389			`__x_parent = __x_parent->_M_parent;`
390			`}`
391			`else`
392			`{`
393			`if (__w->_M_left == 0 \|\| __w->_M_left->_M_color == _S_black)`
394			`{`
395			`__w->_M_right->_M_color = _S_black;`
396			`__w->_M_color = _S_red;`
397			`_Rb_tree_rotate_left(__w, __root);`
398			`__w = __x_parent->_M_left;`
399			`}`
400			`__w->_M_color = __x_parent->_M_color;`
401			`__x_parent->_M_color = _S_black;`
402			`if (__w->_M_left)`
403			`__w->_M_left->_M_color = _S_black;`
404			`_Rb_tree_rotate_right(__x_parent, __root);`
405			`break;`
406			`}`
407			`}`
408			`if (__x) __x->_M_color = _S_black;`
409			`}`
410			`return __y;`
411			`}`
412
413			`unsigned int`
414			`_Rb_tree_black_count(const _Rb_tree_node_base* __node,`
415			`const _Rb_tree_node_base* __root)`
416			`{`
417			`if (__node == 0)`
418			`return 0;`
419			`unsigned int __sum = 0;`
420			`do`
421			`{`
422			`if (__node->_M_color == _S_black)`
423			`++__sum;`
424			`if (__node == __root)`
425			`break;`
426			`__node = __node->_M_parent;`
427			`}`
428			`while (1);`
429			`return __sum;`
430			`}`
431			`} // namespace std`