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
00063 #ifndef __GLIBCPP_INTERNAL_TREE_H
00064 #define __GLIBCPP_INTERNAL_TREE_H
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
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() { _M_node = 0; }
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)
00370 __x = __y->_M_right;
00371 else
00372 if (__y->_M_right == 0)
00373 __x = __y->_M_left;
00374 else
00375 {
00376
00377 __y = __y->_M_right;
00378 while (__y->_M_left != 0)
00379 __y = __y->_M_left;
00380 __x = __y->_M_right;
00381 }
00382 if (__y != __z)
00383 {
00384
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;
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
00407 }
00408 else
00409 {
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)
00422 __leftmost = __z->_M_parent;
00423
00424 else
00425 __leftmost = _Rb_tree_node_base::_S_minimum(__x);
00426 if (__rightmost == __z)
00427 if (__z->_M_left == 0)
00428 __rightmost = __z->_M_parent;
00429
00430 else
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
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
00516
00517
00518
00519
00520
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
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;
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
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;
00757
00758 _M_root() = 0;
00759 _M_leftmost() = _M_header;
00760 _M_rightmost() = _M_header;
00761 }
00762
00763 public:
00764
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
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
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
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
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;
00987
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;
00995 }
00996 else
00997 {
00998 __z = _M_create_node(__v);
00999 _S_right(__y) = __z;
01000
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
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
01070 else
01071 return insert_unique(__v).first;
01072 }
01073 else if (__position._M_node == _M_header)
01074 {
01075
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
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
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
01112 else
01113 return insert_equal(__v);
01114 }
01115 else if (__position._M_node == _M_header)
01116 {
01117
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
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
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
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;
01268 _Link_type __x = _M_root();
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;
01288 _Link_type __x = _M_root();
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;
01320 _Link_type __x = _M_root();
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;
01338 _Link_type __x = _M_root();
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;
01356 _Link_type __x = _M_root();
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;
01374 _Link_type __x = _M_root();
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 }
01461
01462 #endif