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() {}
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