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