stl_tree.h

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

Generated on Wed Aug 4 21:43:21 2004 for libstdc++-v3 Source by doxygen 1.3.8