Copyright (C) 2000-2012 |
Whole document tree stl_tree.hGo to the documentation of this file.00001 // RB tree implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001 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 /* NOTE: This is an internal header file, included by other STL headers. 00059 * You should not attempt to use it directly. 00060 */ 00061 00062 #ifndef __SGI_STL_INTERNAL_TREE_H 00063 #define __SGI_STL_INTERNAL_TREE_H 00064 00065 /* 00066 00067 Red-black tree class, designed for use in implementing STL 00068 associative containers (set, multiset, map, and multimap). The 00069 insertion and deletion algorithms are based on those in Cormen, 00070 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), 00071 except that 00072 00073 (1) the header cell is maintained with links not only to the root 00074 but also to the leftmost node of the tree, to enable constant time 00075 begin(), and to the rightmost node of the tree, to enable linear time 00076 performance when used with the generic set algorithms (set_union, 00077 etc.); 00078 00079 (2) when a node being deleted has two children its successor node is 00080 relinked into its place, rather than copied, so that the only 00081 iterators invalidated are those referring to the deleted node. 00082 00083 */ 00084 00085 #include <bits/stl_algobase.h> 00086 #include <bits/stl_alloc.h> 00087 #include <bits/stl_construct.h> 00088 #include <bits/stl_function.h> 00089 00090 namespace std 00091 { 00092 00093 typedef bool _Rb_tree_Color_type; 00094 const _Rb_tree_Color_type _S_rb_tree_red = false; 00095 const _Rb_tree_Color_type _S_rb_tree_black = true; 00096 00097 struct _Rb_tree_node_base 00098 { 00099 typedef _Rb_tree_Color_type _Color_type; 00100 typedef _Rb_tree_node_base* _Base_ptr; 00101 00102 _Color_type _M_color; 00103 _Base_ptr _M_parent; 00104 _Base_ptr _M_left; 00105 _Base_ptr _M_right; 00106 00107 static _Base_ptr _S_minimum(_Base_ptr __x) 00108 { 00109 while (__x->_M_left != 0) __x = __x->_M_left; 00110 return __x; 00111 } 00112 00113 static _Base_ptr _S_maximum(_Base_ptr __x) 00114 { 00115 while (__x->_M_right != 0) __x = __x->_M_right; 00116 return __x; 00117 } 00118 }; 00119 00120 template <class _Value> 00121 struct _Rb_tree_node : public _Rb_tree_node_base 00122 { 00123 typedef _Rb_tree_node<_Value>* _Link_type; 00124 _Value _M_value_field; 00125 }; 00126 00127 00128 struct _Rb_tree_base_iterator 00129 { 00130 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 00131 typedef bidirectional_iterator_tag iterator_category; 00132 typedef ptrdiff_t difference_type; 00133 _Base_ptr _M_node; 00134 00135 void _M_increment() 00136 { 00137 if (_M_node->_M_right != 0) { 00138 _M_node = _M_node->_M_right; 00139 while (_M_node->_M_left != 0) 00140 _M_node = _M_node->_M_left; 00141 } 00142 else { 00143 _Base_ptr __y = _M_node->_M_parent; 00144 while (_M_node == __y->_M_right) { 00145 _M_node = __y; 00146 __y = __y->_M_parent; 00147 } 00148 if (_M_node->_M_right != __y) 00149 _M_node = __y; 00150 } 00151 } 00152 00153 void _M_decrement() 00154 { 00155 if (_M_node->_M_color == _S_rb_tree_red && 00156 _M_node->_M_parent->_M_parent == _M_node) 00157 _M_node = _M_node->_M_right; 00158 else if (_M_node->_M_left != 0) { 00159 _Base_ptr __y = _M_node->_M_left; 00160 while (__y->_M_right != 0) 00161 __y = __y->_M_right; 00162 _M_node = __y; 00163 } 00164 else { 00165 _Base_ptr __y = _M_node->_M_parent; 00166 while (_M_node == __y->_M_left) { 00167 _M_node = __y; 00168 __y = __y->_M_parent; 00169 } 00170 _M_node = __y; 00171 } 00172 } 00173 }; 00174 00175 template <class _Value, class _Ref, class _Ptr> 00176 struct _Rb_tree_iterator : public _Rb_tree_base_iterator 00177 { 00178 typedef _Value value_type; 00179 typedef _Ref reference; 00180 typedef _Ptr pointer; 00181 typedef _Rb_tree_iterator<_Value, _Value&, _Value*> 00182 iterator; 00183 typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*> 00184 const_iterator; 00185 typedef _Rb_tree_iterator<_Value, _Ref, _Ptr> 00186 _Self; 00187 typedef _Rb_tree_node<_Value>* _Link_type; 00188 00189 _Rb_tree_iterator() {} 00190 _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } 00191 _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; } 00192 00193 reference operator*() const { return _Link_type(_M_node)->_M_value_field; } 00194 pointer operator->() const { return &(operator*()); } 00195 00196 _Self& operator++() { _M_increment(); return *this; } 00197 _Self operator++(int) { 00198 _Self __tmp = *this; 00199 _M_increment(); 00200 return __tmp; 00201 } 00202 00203 _Self& operator--() { _M_decrement(); return *this; } 00204 _Self operator--(int) { 00205 _Self __tmp = *this; 00206 _M_decrement(); 00207 return __tmp; 00208 } 00209 }; 00210 00211 template <class _Value, class _Ref, class _Ptr> 00212 inline bool operator==(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x, 00213 const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) { 00214 return __x._M_node == __y._M_node; 00215 } 00216 00217 template <class _Value> 00218 inline bool operator==(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x, 00219 const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) { 00220 return __x._M_node == __y._M_node; 00221 } 00222 00223 template <class _Value> 00224 inline bool operator==(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x, 00225 const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) { 00226 return __x._M_node == __y._M_node; 00227 } 00228 00229 template <class _Value, class _Ref, class _Ptr> 00230 inline bool operator!=(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x, 00231 const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) { 00232 return __x._M_node != __y._M_node; 00233 } 00234 00235 template <class _Value> 00236 inline bool operator!=(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x, 00237 const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) { 00238 return __x._M_node != __y._M_node; 00239 } 00240 00241 template <class _Value> 00242 inline bool operator!=(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x, 00243 const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) { 00244 return __x._M_node != __y._M_node; 00245 } 00246 00247 inline void 00248 _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) 00249 { 00250 _Rb_tree_node_base* __y = __x->_M_right; 00251 __x->_M_right = __y->_M_left; 00252 if (__y->_M_left !=0) 00253 __y->_M_left->_M_parent = __x; 00254 __y->_M_parent = __x->_M_parent; 00255 00256 if (__x == __root) 00257 __root = __y; 00258 else if (__x == __x->_M_parent->_M_left) 00259 __x->_M_parent->_M_left = __y; 00260 else 00261 __x->_M_parent->_M_right = __y; 00262 __y->_M_left = __x; 00263 __x->_M_parent = __y; 00264 } 00265 00266 inline void 00267 _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) 00268 { 00269 _Rb_tree_node_base* __y = __x->_M_left; 00270 __x->_M_left = __y->_M_right; 00271 if (__y->_M_right != 0) 00272 __y->_M_right->_M_parent = __x; 00273 __y->_M_parent = __x->_M_parent; 00274 00275 if (__x == __root) 00276 __root = __y; 00277 else if (__x == __x->_M_parent->_M_right) 00278 __x->_M_parent->_M_right = __y; 00279 else 00280 __x->_M_parent->_M_left = __y; 00281 __y->_M_right = __x; 00282 __x->_M_parent = __y; 00283 } 00284 00285 inline void 00286 _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) 00287 { 00288 __x->_M_color = _S_rb_tree_red; 00289 while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) { 00290 if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) { 00291 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; 00292 if (__y && __y->_M_color == _S_rb_tree_red) { 00293 __x->_M_parent->_M_color = _S_rb_tree_black; 00294 __y->_M_color = _S_rb_tree_black; 00295 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 00296 __x = __x->_M_parent->_M_parent; 00297 } 00298 else { 00299 if (__x == __x->_M_parent->_M_right) { 00300 __x = __x->_M_parent; 00301 _Rb_tree_rotate_left(__x, __root); 00302 } 00303 __x->_M_parent->_M_color = _S_rb_tree_black; 00304 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 00305 _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root); 00306 } 00307 } 00308 else { 00309 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; 00310 if (__y && __y->_M_color == _S_rb_tree_red) { 00311 __x->_M_parent->_M_color = _S_rb_tree_black; 00312 __y->_M_color = _S_rb_tree_black; 00313 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 00314 __x = __x->_M_parent->_M_parent; 00315 } 00316 else { 00317 if (__x == __x->_M_parent->_M_left) { 00318 __x = __x->_M_parent; 00319 _Rb_tree_rotate_right(__x, __root); 00320 } 00321 __x->_M_parent->_M_color = _S_rb_tree_black; 00322 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 00323 _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root); 00324 } 00325 } 00326 } 00327 __root->_M_color = _S_rb_tree_black; 00328 } 00329 00330 inline _Rb_tree_node_base* 00331 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z, 00332 _Rb_tree_node_base*& __root, 00333 _Rb_tree_node_base*& __leftmost, 00334 _Rb_tree_node_base*& __rightmost) 00335 { 00336 _Rb_tree_node_base* __y = __z; 00337 _Rb_tree_node_base* __x = 0; 00338 _Rb_tree_node_base* __x_parent = 0; 00339 if (__y->_M_left == 0) // __z has at most one non-null child. y == z. 00340 __x = __y->_M_right; // __x might be null. 00341 else 00342 if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. 00343 __x = __y->_M_left; // __x is not null. 00344 else { // __z has two non-null children. Set __y to 00345 __y = __y->_M_right; // __z's successor. __x might be null. 00346 while (__y->_M_left != 0) 00347 __y = __y->_M_left; 00348 __x = __y->_M_right; 00349 } 00350 if (__y != __z) { // relink y in place of z. y is z's successor 00351 __z->_M_left->_M_parent = __y; 00352 __y->_M_left = __z->_M_left; 00353 if (__y != __z->_M_right) { 00354 __x_parent = __y->_M_parent; 00355 if (__x) __x->_M_parent = __y->_M_parent; 00356 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left 00357 __y->_M_right = __z->_M_right; 00358 __z->_M_right->_M_parent = __y; 00359 } 00360 else 00361 __x_parent = __y; 00362 if (__root == __z) 00363 __root = __y; 00364 else if (__z->_M_parent->_M_left == __z) 00365 __z->_M_parent->_M_left = __y; 00366 else 00367 __z->_M_parent->_M_right = __y; 00368 __y->_M_parent = __z->_M_parent; 00369 std::swap(__y->_M_color, __z->_M_color); 00370 __y = __z; 00371 // __y now points to node to be actually deleted 00372 } 00373 else { // __y == __z 00374 __x_parent = __y->_M_parent; 00375 if (__x) __x->_M_parent = __y->_M_parent; 00376 if (__root == __z) 00377 __root = __x; 00378 else 00379 if (__z->_M_parent->_M_left == __z) 00380 __z->_M_parent->_M_left = __x; 00381 else 00382 __z->_M_parent->_M_right = __x; 00383 if (__leftmost == __z) 00384 if (__z->_M_right == 0) // __z->_M_left must be null also 00385 __leftmost = __z->_M_parent; 00386 // makes __leftmost == _M_header if __z == __root 00387 else 00388 __leftmost = _Rb_tree_node_base::_S_minimum(__x); 00389 if (__rightmost == __z) 00390 if (__z->_M_left == 0) // __z->_M_right must be null also 00391 __rightmost = __z->_M_parent; 00392 // makes __rightmost == _M_header if __z == __root 00393 else // __x == __z->_M_left 00394 __rightmost = _Rb_tree_node_base::_S_maximum(__x); 00395 } 00396 if (__y->_M_color != _S_rb_tree_red) { 00397 while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black)) 00398 if (__x == __x_parent->_M_left) { 00399 _Rb_tree_node_base* __w = __x_parent->_M_right; 00400 if (__w->_M_color == _S_rb_tree_red) { 00401 __w->_M_color = _S_rb_tree_black; 00402 __x_parent->_M_color = _S_rb_tree_red; 00403 _Rb_tree_rotate_left(__x_parent, __root); 00404 __w = __x_parent->_M_right; 00405 } 00406 if ((__w->_M_left == 0 || 00407 __w->_M_left->_M_color == _S_rb_tree_black) && 00408 (__w->_M_right == 0 || 00409 __w->_M_right->_M_color == _S_rb_tree_black)) { 00410 __w->_M_color = _S_rb_tree_red; 00411 __x = __x_parent; 00412 __x_parent = __x_parent->_M_parent; 00413 } else { 00414 if (__w->_M_right == 0 || 00415 __w->_M_right->_M_color == _S_rb_tree_black) { 00416 if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; 00417 __w->_M_color = _S_rb_tree_red; 00418 _Rb_tree_rotate_right(__w, __root); 00419 __w = __x_parent->_M_right; 00420 } 00421 __w->_M_color = __x_parent->_M_color; 00422 __x_parent->_M_color = _S_rb_tree_black; 00423 if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; 00424 _Rb_tree_rotate_left(__x_parent, __root); 00425 break; 00426 } 00427 } else { // same as above, with _M_right <-> _M_left. 00428 _Rb_tree_node_base* __w = __x_parent->_M_left; 00429 if (__w->_M_color == _S_rb_tree_red) { 00430 __w->_M_color = _S_rb_tree_black; 00431 __x_parent->_M_color = _S_rb_tree_red; 00432 _Rb_tree_rotate_right(__x_parent, __root); 00433 __w = __x_parent->_M_left; 00434 } 00435 if ((__w->_M_right == 0 || 00436 __w->_M_right->_M_color == _S_rb_tree_black) && 00437 (__w->_M_left == 0 || 00438 __w->_M_left->_M_color == _S_rb_tree_black)) { 00439 __w->_M_color = _S_rb_tree_red; 00440 __x = __x_parent; 00441 __x_parent = __x_parent->_M_parent; 00442 } else { 00443 if (__w->_M_left == 0 || 00444 __w->_M_left->_M_color == _S_rb_tree_black) { 00445 if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; 00446 __w->_M_color = _S_rb_tree_red; 00447 _Rb_tree_rotate_left(__w, __root); 00448 __w = __x_parent->_M_left; 00449 } 00450 __w->_M_color = __x_parent->_M_color; 00451 __x_parent->_M_color = _S_rb_tree_black; 00452 if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; 00453 _Rb_tree_rotate_right(__x_parent, __root); 00454 break; 00455 } 00456 } 00457 if (__x) __x->_M_color = _S_rb_tree_black; 00458 } 00459 return __y; 00460 } 00461 00462 // Base class to encapsulate the differences between old SGI-style 00463 // allocators and standard-conforming allocators. In order to avoid 00464 // having an empty base class, we arbitrarily move one of rb_tree's 00465 // data members into the base class. 00466 00467 // _Base for general standard-conforming allocators. 00468 template <class _Tp, class _Alloc, bool _S_instanceless> 00469 class _Rb_tree_alloc_base { 00470 public: 00471 typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; 00472 allocator_type get_allocator() const { return _M_node_allocator; } 00473 00474 _Rb_tree_alloc_base(const allocator_type& __a) 00475 : _M_node_allocator(__a), _M_header(0) {} 00476 00477 protected: 00478 typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type 00479 _M_node_allocator; 00480 _Rb_tree_node<_Tp>* _M_header; 00481 00482 _Rb_tree_node<_Tp>* _M_get_node() 00483 { return _M_node_allocator.allocate(1); } 00484 void _M_put_node(_Rb_tree_node<_Tp>* __p) 00485 { _M_node_allocator.deallocate(__p, 1); } 00486 }; 00487 00488 // Specialization for instanceless allocators. 00489 template <class _Tp, class _Alloc> 00490 class _Rb_tree_alloc_base<_Tp, _Alloc, true> { 00491 public: 00492 typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; 00493 allocator_type get_allocator() const { return allocator_type(); } 00494 00495 _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {} 00496 00497 protected: 00498 _Rb_tree_node<_Tp>* _M_header; 00499 00500 typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type 00501 _Alloc_type; 00502 00503 _Rb_tree_node<_Tp>* _M_get_node() 00504 { return _Alloc_type::allocate(1); } 00505 void _M_put_node(_Rb_tree_node<_Tp>* __p) 00506 { _Alloc_type::deallocate(__p, 1); } 00507 }; 00508 00509 template <class _Tp, class _Alloc> 00510 struct _Rb_tree_base 00511 : public _Rb_tree_alloc_base<_Tp, _Alloc, 00512 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00513 { 00514 typedef _Rb_tree_alloc_base<_Tp, _Alloc, 00515 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00516 _Base; 00517 typedef typename _Base::allocator_type allocator_type; 00518 00519 _Rb_tree_base(const allocator_type& __a) 00520 : _Base(__a) { _M_header = _M_get_node(); } 00521 ~_Rb_tree_base() { _M_put_node(_M_header); } 00522 00523 }; 00524 00525 00526 template <class _Key, class _Value, class _KeyOfValue, class _Compare, 00527 class _Alloc = allocator<_Value> > 00528 class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> { 00529 typedef _Rb_tree_base<_Value, _Alloc> _Base; 00530 protected: 00531 typedef _Rb_tree_node_base* _Base_ptr; 00532 typedef _Rb_tree_node<_Value> _Rb_tree_node; 00533 typedef _Rb_tree_Color_type _Color_type; 00534 public: 00535 typedef _Key key_type; 00536 typedef _Value value_type; 00537 typedef value_type* pointer; 00538 typedef const value_type* const_pointer; 00539 typedef value_type& reference; 00540 typedef const value_type& const_reference; 00541 typedef _Rb_tree_node* _Link_type; 00542 typedef size_t size_type; 00543 typedef ptrdiff_t difference_type; 00544 00545 typedef typename _Base::allocator_type allocator_type; 00546 allocator_type get_allocator() const { return _Base::get_allocator(); } 00547 00548 protected: 00549 using _Base::_M_get_node; 00550 using _Base::_M_put_node; 00551 using _Base::_M_header; 00552 00553 protected: 00554 00555 _Link_type _M_create_node(const value_type& __x) 00556 { 00557 _Link_type __tmp = _M_get_node(); 00558 __STL_TRY { 00559 construct(&__tmp->_M_value_field, __x); 00560 } 00561 __STL_UNWIND(_M_put_node(__tmp)); 00562 return __tmp; 00563 } 00564 00565 _Link_type _M_clone_node(_Link_type __x) 00566 { 00567 _Link_type __tmp = _M_create_node(__x->_M_value_field); 00568 __tmp->_M_color = __x->_M_color; 00569 __tmp->_M_left = 0; 00570 __tmp->_M_right = 0; 00571 return __tmp; 00572 } 00573 00574 void destroy_node(_Link_type __p) 00575 { 00576 destroy(&__p->_M_value_field); 00577 _M_put_node(__p); 00578 } 00579 00580 protected: 00581 size_type _M_node_count; // keeps track of size of tree 00582 _Compare _M_key_compare; 00583 00584 _Link_type& _M_root() const 00585 { return (_Link_type&) _M_header->_M_parent; } 00586 _Link_type& _M_leftmost() const 00587 { return (_Link_type&) _M_header->_M_left; } 00588 _Link_type& _M_rightmost() const 00589 { return (_Link_type&) _M_header->_M_right; } 00590 00591 static _Link_type& _S_left(_Link_type __x) 00592 { return (_Link_type&)(__x->_M_left); } 00593 static _Link_type& _S_right(_Link_type __x) 00594 { return (_Link_type&)(__x->_M_right); } 00595 static _Link_type& _S_parent(_Link_type __x) 00596 { return (_Link_type&)(__x->_M_parent); } 00597 static reference _S_value(_Link_type __x) 00598 { return __x->_M_value_field; } 00599 static const _Key& _S_key(_Link_type __x) 00600 { return _KeyOfValue()(_S_value(__x)); } 00601 static _Color_type& _S_color(_Link_type __x) 00602 { return (_Color_type&)(__x->_M_color); } 00603 00604 static _Link_type& _S_left(_Base_ptr __x) 00605 { return (_Link_type&)(__x->_M_left); } 00606 static _Link_type& _S_right(_Base_ptr __x) 00607 { return (_Link_type&)(__x->_M_right); } 00608 static _Link_type& _S_parent(_Base_ptr __x) 00609 { return (_Link_type&)(__x->_M_parent); } 00610 static reference _S_value(_Base_ptr __x) 00611 { return ((_Link_type)__x)->_M_value_field; } 00612 static const _Key& _S_key(_Base_ptr __x) 00613 { return _KeyOfValue()(_S_value(_Link_type(__x)));} 00614 static _Color_type& _S_color(_Base_ptr __x) 00615 { return (_Color_type&)(_Link_type(__x)->_M_color); } 00616 00617 static _Link_type _S_minimum(_Link_type __x) 00618 { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } 00619 00620 static _Link_type _S_maximum(_Link_type __x) 00621 { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); } 00622 00623 public: 00624 typedef _Rb_tree_iterator<value_type, reference, pointer> iterator; 00625 typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> 00626 const_iterator; 00627 00628 typedef reverse_iterator<const_iterator> const_reverse_iterator; 00629 typedef reverse_iterator<iterator> reverse_iterator; 00630 00631 private: 00632 iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 00633 _Link_type _M_copy(_Link_type __x, _Link_type __p); 00634 void _M_erase(_Link_type __x); 00635 00636 public: 00637 // allocation/deallocation 00638 _Rb_tree() 00639 : _Base(allocator_type()), _M_node_count(0), _M_key_compare() 00640 { _M_empty_initialize(); } 00641 00642 _Rb_tree(const _Compare& __comp) 00643 : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 00644 { _M_empty_initialize(); } 00645 00646 _Rb_tree(const _Compare& __comp, const allocator_type& __a) 00647 : _Base(__a), _M_node_count(0), _M_key_compare(__comp) 00648 { _M_empty_initialize(); } 00649 00650 _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) 00651 : _Base(__x.get_allocator()), 00652 _M_node_count(0), _M_key_compare(__x._M_key_compare) 00653 { 00654 if (__x._M_root() == 0) 00655 _M_empty_initialize(); 00656 else { 00657 _S_color(_M_header) = _S_rb_tree_red; 00658 _M_root() = _M_copy(__x._M_root(), _M_header); 00659 _M_leftmost() = _S_minimum(_M_root()); 00660 _M_rightmost() = _S_maximum(_M_root()); 00661 } 00662 _M_node_count = __x._M_node_count; 00663 } 00664 ~_Rb_tree() { clear(); } 00665 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& 00666 operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x); 00667 00668 private: 00669 void _M_empty_initialize() { 00670 _S_color(_M_header) = _S_rb_tree_red; // used to distinguish header from 00671 // __root, in iterator.operator++ 00672 _M_root() = 0; 00673 _M_leftmost() = _M_header; 00674 _M_rightmost() = _M_header; 00675 } 00676 00677 public: 00678 // accessors: 00679 _Compare key_comp() const { return _M_key_compare; } 00680 iterator begin() { return _M_leftmost(); } 00681 const_iterator begin() const { return _M_leftmost(); } 00682 iterator end() { return _M_header; } 00683 const_iterator end() const { return _M_header; } 00684 reverse_iterator rbegin() { return reverse_iterator(end()); } 00685 const_reverse_iterator rbegin() const { 00686 return const_reverse_iterator(end()); 00687 } 00688 reverse_iterator rend() { return reverse_iterator(begin()); } 00689 const_reverse_iterator rend() const { 00690 return const_reverse_iterator(begin()); 00691 } 00692 bool empty() const { return _M_node_count == 0; } 00693 size_type size() const { return _M_node_count; } 00694 size_type max_size() const { return size_type(-1); } 00695 00696 void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) { 00697 std::swap(_M_header, __t._M_header); 00698 std::swap(_M_node_count, __t._M_node_count); 00699 std::swap(_M_key_compare, __t._M_key_compare); 00700 } 00701 00702 public: 00703 // insert/erase 00704 pair<iterator,bool> insert_unique(const value_type& __x); 00705 iterator insert_equal(const value_type& __x); 00706 00707 iterator insert_unique(iterator __position, const value_type& __x); 00708 iterator insert_equal(iterator __position, const value_type& __x); 00709 00710 template <class _InputIterator> 00711 void insert_unique(_InputIterator __first, _InputIterator __last); 00712 template <class _InputIterator> 00713 void insert_equal(_InputIterator __first, _InputIterator __last); 00714 00715 void erase(iterator __position); 00716 size_type erase(const key_type& __x); 00717 void erase(iterator __first, iterator __last); 00718 void erase(const key_type* __first, const key_type* __last); 00719 void clear() { 00720 if (_M_node_count != 0) { 00721 _M_erase(_M_root()); 00722 _M_leftmost() = _M_header; 00723 _M_root() = 0; 00724 _M_rightmost() = _M_header; 00725 _M_node_count = 0; 00726 } 00727 } 00728 00729 public: 00730 // set operations: 00731 iterator find(const key_type& __x); 00732 const_iterator find(const key_type& __x) const; 00733 size_type count(const key_type& __x) const; 00734 iterator lower_bound(const key_type& __x); 00735 const_iterator lower_bound(const key_type& __x) const; 00736 iterator upper_bound(const key_type& __x); 00737 const_iterator upper_bound(const key_type& __x) const; 00738 pair<iterator,iterator> equal_range(const key_type& __x); 00739 pair<const_iterator, const_iterator> equal_range(const key_type& __x) const; 00740 00741 public: 00742 // Debugging. 00743 bool __rb_verify() const; 00744 }; 00745 00746 template <class _Key, class _Value, class _KeyOfValue, 00747 class _Compare, class _Alloc> 00748 inline bool 00749 operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 00750 const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) 00751 { 00752 return __x.size() == __y.size() && 00753 equal(__x.begin(), __x.end(), __y.begin()); 00754 } 00755 00756 template <class _Key, class _Value, class _KeyOfValue, 00757 class _Compare, class _Alloc> 00758 inline bool 00759 operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 00760 const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) 00761 { 00762 return lexicographical_compare(__x.begin(), __x.end(), 00763 __y.begin(), __y.end()); 00764 } 00765 00766 template <class _Key, class _Value, class _KeyOfValue, 00767 class _Compare, class _Alloc> 00768 inline bool 00769 operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 00770 const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { 00771 return !(__x == __y); 00772 } 00773 00774 template <class _Key, class _Value, class _KeyOfValue, 00775 class _Compare, class _Alloc> 00776 inline bool 00777 operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 00778 const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { 00779 return __y < __x; 00780 } 00781 00782 template <class _Key, class _Value, class _KeyOfValue, 00783 class _Compare, class _Alloc> 00784 inline bool 00785 operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 00786 const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { 00787 return !(__y < __x); 00788 } 00789 00790 template <class _Key, class _Value, class _KeyOfValue, 00791 class _Compare, class _Alloc> 00792 inline bool 00793 operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 00794 const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { 00795 return !(__x < __y); 00796 } 00797 00798 00799 template <class _Key, class _Value, class _KeyOfValue, 00800 class _Compare, class _Alloc> 00801 inline void 00802 swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 00803 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) 00804 { 00805 __x.swap(__y); 00806 } 00807 00808 00809 template <class _Key, class _Value, class _KeyOfValue, 00810 class _Compare, class _Alloc> 00811 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& 00812 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 00813 ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) 00814 { 00815 if (this != &__x) { 00816 // Note that _Key may be a constant type. 00817 clear(); 00818 _M_node_count = 0; 00819 _M_key_compare = __x._M_key_compare; 00820 if (__x._M_root() == 0) { 00821 _M_root() = 0; 00822 _M_leftmost() = _M_header; 00823 _M_rightmost() = _M_header; 00824 } 00825 else { 00826 _M_root() = _M_copy(__x._M_root(), _M_header); 00827 _M_leftmost() = _S_minimum(_M_root()); 00828 _M_rightmost() = _S_maximum(_M_root()); 00829 _M_node_count = __x._M_node_count; 00830 } 00831 } 00832 return *this; 00833 } 00834 00835 template <class _Key, class _Value, class _KeyOfValue, 00836 class _Compare, class _Alloc> 00837 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 00838 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 00839 ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v) 00840 { 00841 _Link_type __x = (_Link_type) __x_; 00842 _Link_type __y = (_Link_type) __y_; 00843 _Link_type __z; 00844 00845 if (__y == _M_header || __x != 0 || 00846 _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) { 00847 __z = _M_create_node(__v); 00848 _S_left(__y) = __z; // also makes _M_leftmost() = __z 00849 // when __y == _M_header 00850 if (__y == _M_header) { 00851 _M_root() = __z; 00852 _M_rightmost() = __z; 00853 } 00854 else if (__y == _M_leftmost()) 00855 _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node 00856 } 00857 else { 00858 __z = _M_create_node(__v); 00859 _S_right(__y) = __z; 00860 if (__y == _M_rightmost()) 00861 _M_rightmost() = __z; // maintain _M_rightmost() pointing to max node 00862 } 00863 _S_parent(__z) = __y; 00864 _S_left(__z) = 0; 00865 _S_right(__z) = 0; 00866 _Rb_tree_rebalance(__z, _M_header->_M_parent); 00867 ++_M_node_count; 00868 return iterator(__z); 00869 } 00870 00871 template <class _Key, class _Value, class _KeyOfValue, 00872 class _Compare, class _Alloc> 00873 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 00874 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 00875 ::insert_equal(const _Value& __v) 00876 { 00877 _Link_type __y = _M_header; 00878 _Link_type __x = _M_root(); 00879 while (__x != 0) { 00880 __y = __x; 00881 __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 00882 _S_left(__x) : _S_right(__x); 00883 } 00884 return _M_insert(__x, __y, __v); 00885 } 00886 00887 00888 template <class _Key, class _Value, class _KeyOfValue, 00889 class _Compare, class _Alloc> 00890 pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator, 00891 bool> 00892 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 00893 ::insert_unique(const _Value& __v) 00894 { 00895 _Link_type __y = _M_header; 00896 _Link_type __x = _M_root(); 00897 bool __comp = true; 00898 while (__x != 0) { 00899 __y = __x; 00900 __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 00901 __x = __comp ? _S_left(__x) : _S_right(__x); 00902 } 00903 iterator __j = iterator(__y); 00904 if (__comp) 00905 if (__j == begin()) 00906 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 00907 else 00908 --__j; 00909 if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 00910 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 00911 return pair<iterator,bool>(__j, false); 00912 } 00913 00914 00915 template <class _Key, class _Val, class _KeyOfValue, 00916 class _Compare, class _Alloc> 00917 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 00918 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc> 00919 ::insert_unique(iterator __position, const _Val& __v) 00920 { 00921 if (__position._M_node == _M_header->_M_left) { // begin() 00922 if (size() > 0 && 00923 _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) 00924 return _M_insert(__position._M_node, __position._M_node, __v); 00925 // first argument just needs to be non-null 00926 else 00927 return insert_unique(__v).first; 00928 } else if (__position._M_node == _M_header) { // end() 00929 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) 00930 return _M_insert(0, _M_rightmost(), __v); 00931 else 00932 return insert_unique(__v).first; 00933 } else { 00934 iterator __before = __position; 00935 --__before; 00936 if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) 00937 && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) { 00938 if (_S_right(__before._M_node) == 0) 00939 return _M_insert(0, __before._M_node, __v); 00940 else 00941 return _M_insert(__position._M_node, __position._M_node, __v); 00942 // first argument just needs to be non-null 00943 } else 00944 return insert_unique(__v).first; 00945 } 00946 } 00947 00948 template <class _Key, class _Val, class _KeyOfValue, 00949 class _Compare, class _Alloc> 00950 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 00951 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc> 00952 ::insert_equal(iterator __position, const _Val& __v) 00953 { 00954 if (__position._M_node == _M_header->_M_left) { // begin() 00955 if (size() > 0 && 00956 !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) 00957 return _M_insert(__position._M_node, __position._M_node, __v); 00958 // first argument just needs to be non-null 00959 else 00960 return insert_equal(__v); 00961 } else if (__position._M_node == _M_header) {// end() 00962 if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) 00963 return _M_insert(0, _M_rightmost(), __v); 00964 else 00965 return insert_equal(__v); 00966 } else { 00967 iterator __before = __position; 00968 --__before; 00969 if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node)) 00970 && !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) { 00971 if (_S_right(__before._M_node) == 0) 00972 return _M_insert(0, __before._M_node, __v); 00973 else 00974 return _M_insert(__position._M_node, __position._M_node, __v); 00975 // first argument just needs to be non-null 00976 } else 00977 return insert_equal(__v); 00978 } 00979 } 00980 00981 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc> 00982 template<class _II> 00983 void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc> 00984 ::insert_equal(_II __first, _II __last) 00985 { 00986 for ( ; __first != __last; ++__first) 00987 insert_equal(*__first); 00988 } 00989 00990 template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc> 00991 template<class _II> 00992 void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc> 00993 ::insert_unique(_II __first, _II __last) { 00994 for ( ; __first != __last; ++__first) 00995 insert_unique(*__first); 00996 } 00997 00998 template <class _Key, class _Value, class _KeyOfValue, 00999 class _Compare, class _Alloc> 01000 inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01001 ::erase(iterator __position) 01002 { 01003 _Link_type __y = 01004 (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node, 01005 _M_header->_M_parent, 01006 _M_header->_M_left, 01007 _M_header->_M_right); 01008 destroy_node(__y); 01009 --_M_node_count; 01010 } 01011 01012 template <class _Key, class _Value, class _KeyOfValue, 01013 class _Compare, class _Alloc> 01014 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type 01015 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) 01016 { 01017 pair<iterator,iterator> __p = equal_range(__x); 01018 size_type __n = 0; 01019 distance(__p.first, __p.second, __n); 01020 erase(__p.first, __p.second); 01021 return __n; 01022 } 01023 01024 template <class _Key, class _Val, class _KoV, class _Compare, class _Alloc> 01025 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01026 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc> 01027 ::_M_copy(_Link_type __x, _Link_type __p) 01028 { 01029 // structural copy. __x and __p must be non-null. 01030 _Link_type __top = _M_clone_node(__x); 01031 __top->_M_parent = __p; 01032 01033 __STL_TRY { 01034 if (__x->_M_right) 01035 __top->_M_right = _M_copy(_S_right(__x), __top); 01036 __p = __top; 01037 __x = _S_left(__x); 01038 01039 while (__x != 0) { 01040 _Link_type __y = _M_clone_node(__x); 01041 __p->_M_left = __y; 01042 __y->_M_parent = __p; 01043 if (__x->_M_right) 01044 __y->_M_right = _M_copy(_S_right(__x), __y); 01045 __p = __y; 01046 __x = _S_left(__x); 01047 } 01048 } 01049 __STL_UNWIND(_M_erase(__top)); 01050 01051 return __top; 01052 } 01053 01054 template <class _Key, class _Value, class _KeyOfValue, 01055 class _Compare, class _Alloc> 01056 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01057 ::_M_erase(_Link_type __x) 01058 { 01059 // erase without rebalancing 01060 while (__x != 0) { 01061 _M_erase(_S_right(__x)); 01062 _Link_type __y = _S_left(__x); 01063 destroy_node(__x); 01064 __x = __y; 01065 } 01066 } 01067 01068 template <class _Key, class _Value, class _KeyOfValue, 01069 class _Compare, class _Alloc> 01070 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01071 ::erase(iterator __first, iterator __last) 01072 { 01073 if (__first == begin() && __last == end()) 01074 clear(); 01075 else 01076 while (__first != __last) erase(__first++); 01077 } 01078 01079 template <class _Key, class _Value, class _KeyOfValue, 01080 class _Compare, class _Alloc> 01081 void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01082 ::erase(const _Key* __first, const _Key* __last) 01083 { 01084 while (__first != __last) erase(*__first++); 01085 } 01086 01087 template <class _Key, class _Value, class _KeyOfValue, 01088 class _Compare, class _Alloc> 01089 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 01090 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) 01091 { 01092 _Link_type __y = _M_header; // Last node which is not less than __k. 01093 _Link_type __x = _M_root(); // Current node. 01094 01095 while (__x != 0) 01096 if (!_M_key_compare(_S_key(__x), __k)) 01097 __y = __x, __x = _S_left(__x); 01098 else 01099 __x = _S_right(__x); 01100 01101 iterator __j = iterator(__y); 01102 return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? 01103 end() : __j; 01104 } 01105 01106 template <class _Key, class _Value, class _KeyOfValue, 01107 class _Compare, class _Alloc> 01108 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator 01109 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const 01110 { 01111 _Link_type __y = _M_header; /* Last node which is not less than __k. */ 01112 _Link_type __x = _M_root(); /* Current node. */ 01113 01114 while (__x != 0) { 01115 if (!_M_key_compare(_S_key(__x), __k)) 01116 __y = __x, __x = _S_left(__x); 01117 else 01118 __x = _S_right(__x); 01119 } 01120 const_iterator __j = const_iterator(__y); 01121 return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? 01122 end() : __j; 01123 } 01124 01125 template <class _Key, class _Value, class _KeyOfValue, 01126 class _Compare, class _Alloc> 01127 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type 01128 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01129 ::count(const _Key& __k) const 01130 { 01131 pair<const_iterator, const_iterator> __p = equal_range(__k); 01132 size_type __n = 0; 01133 distance(__p.first, __p.second, __n); 01134 return __n; 01135 } 01136 01137 template <class _Key, class _Value, class _KeyOfValue, 01138 class _Compare, class _Alloc> 01139 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 01140 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01141 ::lower_bound(const _Key& __k) 01142 { 01143 _Link_type __y = _M_header; /* Last node which is not less than __k. */ 01144 _Link_type __x = _M_root(); /* Current node. */ 01145 01146 while (__x != 0) 01147 if (!_M_key_compare(_S_key(__x), __k)) 01148 __y = __x, __x = _S_left(__x); 01149 else 01150 __x = _S_right(__x); 01151 01152 return iterator(__y); 01153 } 01154 01155 template <class _Key, class _Value, class _KeyOfValue, 01156 class _Compare, class _Alloc> 01157 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator 01158 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01159 ::lower_bound(const _Key& __k) const 01160 { 01161 _Link_type __y = _M_header; /* Last node which is not less than __k. */ 01162 _Link_type __x = _M_root(); /* Current node. */ 01163 01164 while (__x != 0) 01165 if (!_M_key_compare(_S_key(__x), __k)) 01166 __y = __x, __x = _S_left(__x); 01167 else 01168 __x = _S_right(__x); 01169 01170 return const_iterator(__y); 01171 } 01172 01173 template <class _Key, class _Value, class _KeyOfValue, 01174 class _Compare, class _Alloc> 01175 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 01176 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01177 ::upper_bound(const _Key& __k) 01178 { 01179 _Link_type __y = _M_header; /* Last node which is greater than __k. */ 01180 _Link_type __x = _M_root(); /* Current node. */ 01181 01182 while (__x != 0) 01183 if (_M_key_compare(__k, _S_key(__x))) 01184 __y = __x, __x = _S_left(__x); 01185 else 01186 __x = _S_right(__x); 01187 01188 return iterator(__y); 01189 } 01190 01191 template <class _Key, class _Value, class _KeyOfValue, 01192 class _Compare, class _Alloc> 01193 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator 01194 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01195 ::upper_bound(const _Key& __k) const 01196 { 01197 _Link_type __y = _M_header; /* Last node which is greater than __k. */ 01198 _Link_type __x = _M_root(); /* Current node. */ 01199 01200 while (__x != 0) 01201 if (_M_key_compare(__k, _S_key(__x))) 01202 __y = __x, __x = _S_left(__x); 01203 else 01204 __x = _S_right(__x); 01205 01206 return const_iterator(__y); 01207 } 01208 01209 template <class _Key, class _Value, class _KeyOfValue, 01210 class _Compare, class _Alloc> 01211 inline 01212 pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator, 01213 typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator> 01214 _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 01215 ::equal_range(const _Key& __k) 01216 { 01217 return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); 01218 } 01219 01220 template <class _Key, class _Value, class _KoV, class _Compare, class _Alloc> 01221 inline 01222 pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator, 01223 typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator> 01224 _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc> 01225 ::equal_range(const _Key& __k) const 01226 { 01227 return pair<const_iterator,const_iterator>(lower_bound(__k), 01228 upper_bound(__k)); 01229 } 01230 01231 inline int 01232 __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) 01233 { 01234 if (__node == 0) 01235 return 0; 01236 int __sum = 0; 01237 do { 01238 if (__node->_M_color == _S_rb_tree_black) 01239 ++__sum; 01240 if (__node == __root) 01241 break; 01242 __node = __node->_M_parent; 01243 } while (1); 01244 return __sum; 01245 } 01246 01247 template <class _Key, class _Value, class _KeyOfValue, 01248 class _Compare, class _Alloc> 01249 bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 01250 { 01251 if (_M_node_count == 0 || begin() == end()) 01252 return _M_node_count == 0 && begin() == end() && 01253 _M_header->_M_left == _M_header && _M_header->_M_right == _M_header; 01254 01255 int __len = __black_count(_M_leftmost(), _M_root()); 01256 for (const_iterator __it = begin(); __it != end(); ++__it) { 01257 _Link_type __x = (_Link_type) __it._M_node; 01258 _Link_type __L = _S_left(__x); 01259 _Link_type __R = _S_right(__x); 01260 01261 if (__x->_M_color == _S_rb_tree_red) 01262 if ((__L && __L->_M_color == _S_rb_tree_red) || 01263 (__R && __R->_M_color == _S_rb_tree_red)) 01264 return false; 01265 01266 if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) 01267 return false; 01268 if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) 01269 return false; 01270 01271 if (!__L && !__R && __black_count(__x, _M_root()) != __len) 01272 return false; 01273 } 01274 01275 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 01276 return false; 01277 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 01278 return false; 01279 01280 return true; 01281 } 01282 01283 // Class rb_tree is not part of the C++ standard. It is provided for 01284 // compatibility with the HP STL. 01285 01286 template <class _Key, class _Value, class _KeyOfValue, class _Compare, 01287 class _Alloc = allocator<_Value> > 01288 struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> 01289 { 01290 typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base; 01291 typedef typename _Base::allocator_type allocator_type; 01292 01293 rb_tree(const _Compare& __comp = _Compare(), 01294 const allocator_type& __a = allocator_type()) 01295 : _Base(__comp, __a) {} 01296 01297 ~rb_tree() {} 01298 }; 01299 01300 } // namespace std 01301 01302 #endif /* __SGI_STL_INTERNAL_TREE_H */ 01303 01304 // Local Variables: 01305 // mode:C++ 01306 // End: Generated on Mon Apr 8 03:11:45 2002 for libstdc++-v3 Source by 1.2.15 |