00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 #ifndef __SGI_STL_INTERNAL_TREE_H
00063 #define __SGI_STL_INTERNAL_TREE_H
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
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)
00340 __x = __y->_M_right;
00341 else
00342 if (__y->_M_right == 0)
00343 __x = __y->_M_left;
00344 else {
00345 __y = __y->_M_right;
00346 while (__y->_M_left != 0)
00347 __y = __y->_M_left;
00348 __x = __y->_M_right;
00349 }
00350 if (__y != __z) {
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;
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
00372 }
00373 else {
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)
00385 __leftmost = __z->_M_parent;
00386
00387 else
00388 __leftmost = _Rb_tree_node_base::_S_minimum(__x);
00389 if (__rightmost == __z)
00390 if (__z->_M_left == 0)
00391 __rightmost = __z->_M_parent;
00392
00393 else
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 {
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
00463
00464
00465
00466
00467
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
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;
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
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;
00671
00672 _M_root() = 0;
00673 _M_leftmost() = _M_header;
00674 _M_rightmost() = _M_header;
00675 }
00676
00677 public:
00678
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
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
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
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
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;
00849
00850 if (__y == _M_header) {
00851 _M_root() = __z;
00852 _M_rightmost() = __z;
00853 }
00854 else if (__y == _M_leftmost())
00855 _M_leftmost() = __z;
00856 }
00857 else {
00858 __z = _M_create_node(__v);
00859 _S_right(__y) = __z;
00860 if (__y == _M_rightmost())
00861 _M_rightmost() = __z;
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) {
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
00926 else
00927 return insert_unique(__v).first;
00928 } else if (__position._M_node == _M_header) {
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
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) {
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
00959 else
00960 return insert_equal(__v);
00961 } else if (__position._M_node == _M_header) {
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
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
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
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;
01093 _Link_type __x = _M_root();
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;
01112 _Link_type __x = _M_root();
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;
01144 _Link_type __x = _M_root();
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;
01162 _Link_type __x = _M_root();
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;
01180 _Link_type __x = _M_root();
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;
01198 _Link_type __x = _M_root();
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
01284
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 }
01301
01302 #endif
01303
01304
01305
01306