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

Generated on Wed Sep 8 10:19:53 2004 for libstdc++-v3 Source by doxygen 1.3.8