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 : _M_node() { }
00166
00167 explicit
00168 _Rb_tree_iterator(_Link_type __x)
00169 : _M_node(__x) { }
00170
00171 reference
00172 operator*() const
00173 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00174
00175 pointer
00176 operator->() const
00177 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00178
00179 _Self&
00180 operator++()
00181 {
00182 _M_node = _Rb_tree_increment(_M_node);
00183 return *this;
00184 }
00185
00186 _Self
00187 operator++(int)
00188 {
00189 _Self __tmp = *this;
00190 _M_node = _Rb_tree_increment(_M_node);
00191 return __tmp;
00192 }
00193
00194 _Self&
00195 operator--()
00196 {
00197 _M_node = _Rb_tree_decrement(_M_node);
00198 return *this;
00199 }
00200
00201 _Self
00202 operator--(int)
00203 {
00204 _Self __tmp = *this;
00205 _M_node = _Rb_tree_decrement(_M_node);
00206 return __tmp;
00207 }
00208
00209 bool
00210 operator==(const _Self& __x) const
00211 { return _M_node == __x._M_node; }
00212
00213 bool
00214 operator!=(const _Self& __x) const
00215 { return _M_node != __x._M_node; }
00216
00217 _Base_ptr _M_node;
00218 };
00219
00220 template<typename _Tp>
00221 struct _Rb_tree_const_iterator
00222 {
00223 typedef _Tp value_type;
00224 typedef const _Tp& reference;
00225 typedef const _Tp* pointer;
00226
00227 typedef _Rb_tree_iterator<_Tp> iterator;
00228
00229 typedef bidirectional_iterator_tag iterator_category;
00230 typedef ptrdiff_t difference_type;
00231
00232 typedef _Rb_tree_const_iterator<_Tp> _Self;
00233 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00234 typedef const _Rb_tree_node<_Tp>* _Link_type;
00235
00236 _Rb_tree_const_iterator()
00237 : _M_node() { }
00238
00239 explicit
00240 _Rb_tree_const_iterator(_Link_type __x)
00241 : _M_node(__x) { }
00242
00243 _Rb_tree_const_iterator(const iterator& __it)
00244 : _M_node(__it._M_node) { }
00245
00246 reference
00247 operator*() const
00248 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00249
00250 pointer
00251 operator->() const
00252 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00253
00254 _Self&
00255 operator++()
00256 {
00257 _M_node = _Rb_tree_increment(_M_node);
00258 return *this;
00259 }
00260
00261 _Self
00262 operator++(int)
00263 {
00264 _Self __tmp = *this;
00265 _M_node = _Rb_tree_increment(_M_node);
00266 return __tmp;
00267 }
00268
00269 _Self&
00270 operator--()
00271 {
00272 _M_node = _Rb_tree_decrement(_M_node);
00273 return *this;
00274 }
00275
00276 _Self
00277 operator--(int)
00278 {
00279 _Self __tmp = *this;
00280 _M_node = _Rb_tree_decrement(_M_node);
00281 return __tmp;
00282 }
00283
00284 bool
00285 operator==(const _Self& __x) const
00286 { return _M_node == __x._M_node; }
00287
00288 bool
00289 operator!=(const _Self& __x) const
00290 { return _M_node != __x._M_node; }
00291
00292 _Base_ptr _M_node;
00293 };
00294
00295 template<typename _Val>
00296 inline bool
00297 operator==(const _Rb_tree_iterator<_Val>& __x,
00298 const _Rb_tree_const_iterator<_Val>& __y)
00299 { return __x._M_node == __y._M_node; }
00300
00301 template<typename _Val>
00302 inline bool
00303 operator!=(const _Rb_tree_iterator<_Val>& __x,
00304 const _Rb_tree_const_iterator<_Val>& __y)
00305 { return __x._M_node != __y._M_node; }
00306
00307 void
00308 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
00309 _Rb_tree_node_base*& __root);
00310
00311 void
00312 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
00313 _Rb_tree_node_base*& __root);
00314
00315 void
00316 _Rb_tree_insert_and_rebalance(const bool __insert_left,
00317 _Rb_tree_node_base* __x,
00318 _Rb_tree_node_base* __p,
00319 _Rb_tree_node_base& __header);
00320
00321 _Rb_tree_node_base*
00322 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00323 _Rb_tree_node_base& __header);
00324
00325
00326 template<typename _Key, typename _Val, typename _KeyOfValue,
00327 typename _Compare, typename _Alloc = allocator<_Val> >
00328 class _Rb_tree
00329 {
00330 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
00331 _Node_allocator;
00332
00333 protected:
00334 typedef _Rb_tree_node_base* _Base_ptr;
00335 typedef const _Rb_tree_node_base* _Const_Base_ptr;
00336 typedef _Rb_tree_node<_Val> _Rb_tree_node;
00337
00338 public:
00339 typedef _Key key_type;
00340 typedef _Val value_type;
00341 typedef value_type* pointer;
00342 typedef const value_type* const_pointer;
00343 typedef value_type& reference;
00344 typedef const value_type& const_reference;
00345 typedef _Rb_tree_node* _Link_type;
00346 typedef const _Rb_tree_node* _Const_Link_type;
00347 typedef size_t size_type;
00348 typedef ptrdiff_t difference_type;
00349 typedef _Alloc allocator_type;
00350
00351 allocator_type
00352 get_allocator() const
00353 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00354
00355 protected:
00356 _Rb_tree_node*
00357 _M_get_node()
00358 { return _M_impl._Node_allocator::allocate(1); }
00359
00360 void
00361 _M_put_node(_Rb_tree_node* __p)
00362 { _M_impl._Node_allocator::deallocate(__p, 1); }
00363
00364 _Link_type
00365 _M_create_node(const value_type& __x)
00366 {
00367 _Link_type __tmp = _M_get_node();
00368 try
00369 { get_allocator().construct(&__tmp->_M_value_field, __x); }
00370 catch(...)
00371 {
00372 _M_put_node(__tmp);
00373 __throw_exception_again;
00374 }
00375 return __tmp;
00376 }
00377
00378 _Link_type
00379 _M_clone_node(_Const_Link_type __x)
00380 {
00381 _Link_type __tmp = _M_create_node(__x->_M_value_field);
00382 __tmp->_M_color = __x->_M_color;
00383 __tmp->_M_left = 0;
00384 __tmp->_M_right = 0;
00385 return __tmp;
00386 }
00387
00388 void
00389 destroy_node(_Link_type __p)
00390 {
00391 get_allocator().destroy(&__p->_M_value_field);
00392 _M_put_node(__p);
00393 }
00394
00395 protected:
00396 template<typename _Key_compare,
00397 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
00398 struct _Rb_tree_impl : public _Node_allocator
00399 {
00400 _Key_compare _M_key_compare;
00401 _Rb_tree_node_base _M_header;
00402 size_type _M_node_count;
00403
00404 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00405 const _Key_compare& __comp = _Key_compare())
00406 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
00407 _M_node_count(0)
00408 {
00409 this->_M_header._M_color = _S_red;
00410 this->_M_header._M_parent = 0;
00411 this->_M_header._M_left = &this->_M_header;
00412 this->_M_header._M_right = &this->_M_header;
00413 }
00414 };
00415
00416
00417
00418 template<typename _Key_compare>
00419 struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
00420 {
00421 _Key_compare _M_key_compare;
00422 _Rb_tree_node_base _M_header;
00423 size_type _M_node_count;
00424
00425 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00426 const _Key_compare& __comp = _Key_compare())
00427 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
00428 _M_node_count(0)
00429 {
00430 this->_M_header._M_color = _S_red;
00431 this->_M_header._M_parent = 0;
00432 this->_M_header._M_left = &this->_M_header;
00433 this->_M_header._M_right = &this->_M_header;
00434 }
00435 };
00436
00437 _Rb_tree_impl<_Compare> _M_impl;
00438
00439 protected:
00440 _Base_ptr&
00441 _M_root()
00442 { return this->_M_impl._M_header._M_parent; }
00443
00444 _Const_Base_ptr
00445 _M_root() const
00446 { return this->_M_impl._M_header._M_parent; }
00447
00448 _Base_ptr&
00449 _M_leftmost()
00450 { return this->_M_impl._M_header._M_left; }
00451
00452 _Const_Base_ptr
00453 _M_leftmost() const
00454 { return this->_M_impl._M_header._M_left; }
00455
00456 _Base_ptr&
00457 _M_rightmost()
00458 { return this->_M_impl._M_header._M_right; }
00459
00460 _Const_Base_ptr
00461 _M_rightmost() const
00462 { return this->_M_impl._M_header._M_right; }
00463
00464 _Link_type
00465 _M_begin()
00466 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00467
00468 _Const_Link_type
00469 _M_begin() const
00470 {
00471 return static_cast<_Const_Link_type>
00472 (this->_M_impl._M_header._M_parent);
00473 }
00474
00475 _Link_type
00476 _M_end()
00477 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00478
00479 _Const_Link_type
00480 _M_end() const
00481 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00482
00483 static const_reference
00484 _S_value(_Const_Link_type __x)
00485 { return __x->_M_value_field; }
00486
00487 static const _Key&
00488 _S_key(_Const_Link_type __x)
00489 { return _KeyOfValue()(_S_value(__x)); }
00490
00491 static _Link_type
00492 _S_left(_Base_ptr __x)
00493 { return static_cast<_Link_type>(__x->_M_left); }
00494
00495 static _Const_Link_type
00496 _S_left(_Const_Base_ptr __x)
00497 { return static_cast<_Const_Link_type>(__x->_M_left); }
00498
00499 static _Link_type
00500 _S_right(_Base_ptr __x)
00501 { return static_cast<_Link_type>(__x->_M_right); }
00502
00503 static _Const_Link_type
00504 _S_right(_Const_Base_ptr __x)
00505 { return static_cast<_Const_Link_type>(__x->_M_right); }
00506
00507 static const_reference
00508 _S_value(_Const_Base_ptr __x)
00509 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00510
00511 static const _Key&
00512 _S_key(_Const_Base_ptr __x)
00513 { return _KeyOfValue()(_S_value(__x)); }
00514
00515 static _Base_ptr
00516 _S_minimum(_Base_ptr __x)
00517 { return _Rb_tree_node_base::_S_minimum(__x); }
00518
00519 static _Const_Base_ptr
00520 _S_minimum(_Const_Base_ptr __x)
00521 { return _Rb_tree_node_base::_S_minimum(__x); }
00522
00523 static _Base_ptr
00524 _S_maximum(_Base_ptr __x)
00525 { return _Rb_tree_node_base::_S_maximum(__x); }
00526
00527 static _Const_Base_ptr
00528 _S_maximum(_Const_Base_ptr __x)
00529 { return _Rb_tree_node_base::_S_maximum(__x); }
00530
00531 public:
00532 typedef _Rb_tree_iterator<value_type> iterator;
00533 typedef _Rb_tree_const_iterator<value_type> const_iterator;
00534
00535 typedef std::reverse_iterator<iterator> reverse_iterator;
00536 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00537
00538 private:
00539 iterator
00540 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00541
00542 const_iterator
00543 _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
00544 const value_type& __v);
00545
00546 _Link_type
00547 _M_copy(_Const_Link_type __x, _Link_type __p);
00548
00549 void
00550 _M_erase(_Link_type __x);
00551
00552 public:
00553
00554 _Rb_tree()
00555 { }
00556
00557 _Rb_tree(const _Compare& __comp)
00558 : _M_impl(allocator_type(), __comp)
00559 { }
00560
00561 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
00562 : _M_impl(__a, __comp)
00563 { }
00564
00565 _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00566 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
00567 {
00568 if (__x._M_root() != 0)
00569 {
00570 _M_root() = _M_copy(__x._M_begin(), _M_end());
00571 _M_leftmost() = _S_minimum(_M_root());
00572 _M_rightmost() = _S_maximum(_M_root());
00573 _M_impl._M_node_count = __x._M_impl._M_node_count;
00574 }
00575 }
00576
00577 ~_Rb_tree()
00578 { _M_erase(_M_begin()); }
00579
00580 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00581 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
00582
00583
00584 _Compare
00585 key_comp() const
00586 { return _M_impl._M_key_compare; }
00587
00588 iterator
00589 begin()
00590 {
00591 return iterator(static_cast<_Link_type>
00592 (this->_M_impl._M_header._M_left));
00593 }
00594
00595 const_iterator
00596 begin() const
00597 {
00598 return const_iterator(static_cast<_Const_Link_type>
00599 (this->_M_impl._M_header._M_left));
00600 }
00601
00602 iterator
00603 end()
00604 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
00605
00606 const_iterator
00607 end() const
00608 {
00609 return const_iterator(static_cast<_Const_Link_type>
00610 (&this->_M_impl._M_header));
00611 }
00612
00613 reverse_iterator
00614 rbegin()
00615 { return reverse_iterator(end()); }
00616
00617 const_reverse_iterator
00618 rbegin() const
00619 { return const_reverse_iterator(end()); }
00620
00621 reverse_iterator
00622 rend()
00623 { return reverse_iterator(begin()); }
00624
00625 const_reverse_iterator
00626 rend() const
00627 { return const_reverse_iterator(begin()); }
00628
00629 bool
00630 empty() const
00631 { return _M_impl._M_node_count == 0; }
00632
00633 size_type
00634 size() const
00635 { return _M_impl._M_node_count; }
00636
00637 size_type
00638 max_size() const
00639 { return size_type(-1); }
00640
00641 void
00642 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
00643
00644
00645 pair<iterator,bool>
00646 insert_unique(const value_type& __x);
00647
00648 iterator
00649 insert_equal(const value_type& __x);
00650
00651 iterator
00652 insert_unique(iterator __position, const value_type& __x);
00653
00654 const_iterator
00655 insert_unique(const_iterator __position, const value_type& __x);
00656
00657 iterator
00658 insert_equal(iterator __position, const value_type& __x);
00659
00660 const_iterator
00661 insert_equal(const_iterator __position, const value_type& __x);
00662
00663 template<typename _InputIterator>
00664 void
00665 insert_unique(_InputIterator __first, _InputIterator __last);
00666
00667 template<typename _InputIterator>
00668 void
00669 insert_equal(_InputIterator __first, _InputIterator __last);
00670
00671 void
00672 erase(iterator __position);
00673
00674 void
00675 erase(const_iterator __position);
00676
00677 size_type
00678 erase(const key_type& __x);
00679
00680 void
00681 erase(iterator __first, iterator __last);
00682
00683 void
00684 erase(const_iterator __first, const_iterator __last);
00685
00686 void
00687 erase(const key_type* __first, const key_type* __last);
00688
00689 void
00690 clear()
00691 {
00692 _M_erase(_M_begin());
00693 _M_leftmost() = _M_end();
00694 _M_root() = 0;
00695 _M_rightmost() = _M_end();
00696 _M_impl._M_node_count = 0;
00697 }
00698
00699
00700 iterator
00701 find(const key_type& __x);
00702
00703 const_iterator
00704 find(const key_type& __x) const;
00705
00706 size_type
00707 count(const key_type& __x) const;
00708
00709 iterator
00710 lower_bound(const key_type& __x);
00711
00712 const_iterator
00713 lower_bound(const key_type& __x) const;
00714
00715 iterator
00716 upper_bound(const key_type& __x);
00717
00718 const_iterator
00719 upper_bound(const key_type& __x) const;
00720
00721 pair<iterator,iterator>
00722 equal_range(const key_type& __x);
00723
00724 pair<const_iterator, const_iterator>
00725 equal_range(const key_type& __x) const;
00726
00727
00728 bool
00729 __rb_verify() const;
00730 };
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 {
00738 return __x.size() == __y.size()
00739 && std::equal(__x.begin(), __x.end(), __y.begin());
00740 }
00741
00742 template<typename _Key, typename _Val, typename _KeyOfValue,
00743 typename _Compare, typename _Alloc>
00744 inline bool
00745 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00746 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00747 {
00748 return std::lexicographical_compare(__x.begin(), __x.end(),
00749 __y.begin(), __y.end());
00750 }
00751
00752 template<typename _Key, typename _Val, typename _KeyOfValue,
00753 typename _Compare, typename _Alloc>
00754 inline bool
00755 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00756 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00757 { return !(__x == __y); }
00758
00759 template<typename _Key, typename _Val, typename _KeyOfValue,
00760 typename _Compare, typename _Alloc>
00761 inline bool
00762 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00763 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00764 { return __y < __x; }
00765
00766 template<typename _Key, typename _Val, typename _KeyOfValue,
00767 typename _Compare, typename _Alloc>
00768 inline bool
00769 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00770 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00771 { return !(__y < __x); }
00772
00773 template<typename _Key, typename _Val, typename _KeyOfValue,
00774 typename _Compare, typename _Alloc>
00775 inline bool
00776 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00777 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00778 { return !(__x < __y); }
00779
00780 template<typename _Key, typename _Val, typename _KeyOfValue,
00781 typename _Compare, typename _Alloc>
00782 inline void
00783 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00784 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00785 { __x.swap(__y); }
00786
00787 template<typename _Key, typename _Val, typename _KeyOfValue,
00788 typename _Compare, typename _Alloc>
00789 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00790 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00791 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00792 {
00793 if (this != &__x)
00794 {
00795
00796 clear();
00797 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00798 if (__x._M_root() != 0)
00799 {
00800 _M_root() = _M_copy(__x._M_begin(), _M_end());
00801 _M_leftmost() = _S_minimum(_M_root());
00802 _M_rightmost() = _S_maximum(_M_root());
00803 _M_impl._M_node_count = __x._M_impl._M_node_count;
00804 }
00805 }
00806 return *this;
00807 }
00808
00809 template<typename _Key, typename _Val, typename _KeyOfValue,
00810 typename _Compare, typename _Alloc>
00811 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00812 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00813 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00814 {
00815 bool __insert_left = (__x != 0 || __p == _M_end()
00816 || _M_impl._M_key_compare(_KeyOfValue()(__v),
00817 _S_key(__p)));
00818
00819 _Link_type __z = _M_create_node(__v);
00820
00821 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
00822 this->_M_impl._M_header);
00823 ++_M_impl._M_node_count;
00824 return iterator(__z);
00825 }
00826
00827 template<typename _Key, typename _Val, typename _KeyOfValue,
00828 typename _Compare, typename _Alloc>
00829 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
00830 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00831 _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
00832 {
00833 bool __insert_left = (__x != 0 || __p == _M_end()
00834 || _M_impl._M_key_compare(_KeyOfValue()(__v),
00835 _S_key(__p)));
00836
00837 _Link_type __z = _M_create_node(__v);
00838
00839 _Rb_tree_insert_and_rebalance(__insert_left, __z,
00840 const_cast<_Base_ptr>(__p),
00841 this->_M_impl._M_header);
00842 ++_M_impl._M_node_count;
00843 return const_iterator(__z);
00844 }
00845
00846 template<typename _Key, typename _Val, typename _KeyOfValue,
00847 typename _Compare, typename _Alloc>
00848 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00849 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00850 insert_equal(const _Val& __v)
00851 {
00852 _Link_type __x = _M_begin();
00853 _Link_type __y = _M_end();
00854 while (__x != 0)
00855 {
00856 __y = __x;
00857 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
00858 _S_left(__x) : _S_right(__x);
00859 }
00860 return _M_insert(__x, __y, __v);
00861 }
00862
00863 template<typename _Key, typename _Val, typename _KeyOfValue,
00864 typename _Compare, typename _Alloc>
00865 void
00866 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00867 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
00868 {
00869 if (_M_root() == 0)
00870 {
00871 if (__t._M_root() != 0)
00872 {
00873 _M_root() = __t._M_root();
00874 _M_leftmost() = __t._M_leftmost();
00875 _M_rightmost() = __t._M_rightmost();
00876 _M_root()->_M_parent = _M_end();
00877
00878 __t._M_root() = 0;
00879 __t._M_leftmost() = __t._M_end();
00880 __t._M_rightmost() = __t._M_end();
00881 }
00882 }
00883 else if (__t._M_root() == 0)
00884 {
00885 __t._M_root() = _M_root();
00886 __t._M_leftmost() = _M_leftmost();
00887 __t._M_rightmost() = _M_rightmost();
00888 __t._M_root()->_M_parent = __t._M_end();
00889
00890 _M_root() = 0;
00891 _M_leftmost() = _M_end();
00892 _M_rightmost() = _M_end();
00893 }
00894 else
00895 {
00896 std::swap(_M_root(),__t._M_root());
00897 std::swap(_M_leftmost(),__t._M_leftmost());
00898 std::swap(_M_rightmost(),__t._M_rightmost());
00899
00900 _M_root()->_M_parent = _M_end();
00901 __t._M_root()->_M_parent = __t._M_end();
00902 }
00903
00904 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
00905 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
00906 }
00907
00908 template<typename _Key, typename _Val, typename _KeyOfValue,
00909 typename _Compare, typename _Alloc>
00910 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
00911 _Compare, _Alloc>::iterator, bool>
00912 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00913 insert_unique(const _Val& __v)
00914 {
00915 _Link_type __x = _M_begin();
00916 _Link_type __y = _M_end();
00917 bool __comp = true;
00918 while (__x != 0)
00919 {
00920 __y = __x;
00921 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
00922 __x = __comp ? _S_left(__x) : _S_right(__x);
00923 }
00924 iterator __j = iterator(__y);
00925 if (__comp)
00926 if (__j == begin())
00927 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
00928 else
00929 --__j;
00930 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
00931 return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
00932 return pair<iterator, bool>(__j, false);
00933 }
00934
00935 template<typename _Key, typename _Val, typename _KeyOfValue,
00936 typename _Compare, typename _Alloc>
00937 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00938 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00939 insert_unique(iterator __position, const _Val& __v)
00940 {
00941
00942 if (__position._M_node == _M_end())
00943 {
00944 if (size() > 0
00945 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
00946 _KeyOfValue()(__v)))
00947 return _M_insert(0, _M_rightmost(), __v);
00948 else
00949 return insert_unique(__v).first;
00950 }
00951 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00952 _S_key(__position._M_node)))
00953 {
00954
00955 iterator __before = __position;
00956 if (__position._M_node == _M_leftmost())
00957 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
00958 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
00959 _KeyOfValue()(__v)))
00960 {
00961 if (_S_right(__before._M_node) == 0)
00962 return _M_insert(0, __before._M_node, __v);
00963 else
00964 return _M_insert(__position._M_node,
00965 __position._M_node, __v);
00966 }
00967 else
00968 return insert_unique(__v).first;
00969 }
00970 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
00971 _KeyOfValue()(__v)))
00972 {
00973
00974 iterator __after = __position;
00975 if (__position._M_node == _M_rightmost())
00976 return _M_insert(0, _M_rightmost(), __v);
00977 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00978 _S_key((++__after)._M_node)))
00979 {
00980 if (_S_right(__position._M_node) == 0)
00981 return _M_insert(0, __position._M_node, __v);
00982 else
00983 return _M_insert(__after._M_node, __after._M_node, __v);
00984 }
00985 else
00986 return insert_unique(__v).first;
00987 }
00988 else
00989 return __position;
00990 }
00991
00992 template<typename _Key, typename _Val, typename _KeyOfValue,
00993 typename _Compare, typename _Alloc>
00994 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
00995 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00996 insert_unique(const_iterator __position, const _Val& __v)
00997 {
00998
00999 if (__position._M_node == _M_end())
01000 {
01001 if (size() > 0
01002 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
01003 _KeyOfValue()(__v)))
01004 return _M_insert(0, _M_rightmost(), __v);
01005 else
01006 return const_iterator(insert_unique(__v).first);
01007 }
01008 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01009 _S_key(__position._M_node)))
01010 {
01011
01012 const_iterator __before = __position;
01013 if (__position._M_node == _M_leftmost())
01014 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
01015 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
01016 _KeyOfValue()(__v)))
01017 {
01018 if (_S_right(__before._M_node) == 0)
01019 return _M_insert(0, __before._M_node, __v);
01020 else
01021 return _M_insert(__position._M_node,
01022 __position._M_node, __v);
01023 }
01024 else
01025 return const_iterator(insert_unique(__v).first);
01026 }
01027 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
01028 _KeyOfValue()(__v)))
01029 {
01030
01031 const_iterator __after = __position;
01032 if (__position._M_node == _M_rightmost())
01033 return _M_insert(0, _M_rightmost(), __v);
01034 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01035 _S_key((++__after)._M_node)))
01036 {
01037 if (_S_right(__position._M_node) == 0)
01038 return _M_insert(0, __position._M_node, __v);
01039 else
01040 return _M_insert(__after._M_node, __after._M_node, __v);
01041 }
01042 else
01043 return const_iterator(insert_unique(__v).first);
01044 }
01045 else
01046 return __position;
01047 }
01048
01049 template<typename _Key, typename _Val, typename _KeyOfValue,
01050 typename _Compare, typename _Alloc>
01051 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01052 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01053 insert_equal(iterator __position, const _Val& __v)
01054 {
01055
01056 if (__position._M_node == _M_end())
01057 {
01058 if (size() > 0
01059 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
01060 _S_key(_M_rightmost())))
01061 return _M_insert(0, _M_rightmost(), __v);
01062 else
01063 return insert_equal(__v);
01064 }
01065 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
01066 _KeyOfValue()(__v)))
01067 {
01068
01069 iterator __before = __position;
01070 if (__position._M_node == _M_leftmost())
01071 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
01072 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
01073 _S_key((--__before)._M_node)))
01074 {
01075 if (_S_right(__before._M_node) == 0)
01076 return _M_insert(0, __before._M_node, __v);
01077 else
01078 return _M_insert(__position._M_node,
01079 __position._M_node, __v);
01080 }
01081 else
01082 return insert_equal(__v);
01083 }
01084 else
01085 {
01086
01087 iterator __after = __position;
01088 if (__position._M_node == _M_rightmost())
01089 return _M_insert(0, _M_rightmost(), __v);
01090 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
01091 _KeyOfValue()(__v)))
01092 {
01093 if (_S_right(__position._M_node) == 0)
01094 return _M_insert(0, __position._M_node, __v);
01095 else
01096 return _M_insert(__after._M_node, __after._M_node, __v);
01097 }
01098 else
01099 return insert_equal(__v);
01100 }
01101 }
01102
01103 template<typename _Key, typename _Val, typename _KeyOfValue,
01104 typename _Compare, typename _Alloc>
01105 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01106 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01107 insert_equal(const_iterator __position, const _Val& __v)
01108 {
01109
01110 if (__position._M_node == _M_end())
01111 {
01112 if (size() > 0
01113 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
01114 _S_key(_M_rightmost())))
01115 return _M_insert(0, _M_rightmost(), __v);
01116 else
01117 return const_iterator(insert_equal(__v));
01118 }
01119 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
01120 _KeyOfValue()(__v)))
01121 {
01122
01123 const_iterator __before = __position;
01124 if (__position._M_node == _M_leftmost())
01125 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
01126 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
01127 _S_key((--__before)._M_node)))
01128 {
01129 if (_S_right(__before._M_node) == 0)
01130 return _M_insert(0, __before._M_node, __v);
01131 else
01132 return _M_insert(__position._M_node,
01133 __position._M_node, __v);
01134 }
01135 else
01136 return const_iterator(insert_equal(__v));
01137 }
01138 else
01139 {
01140
01141 const_iterator __after = __position;
01142 if (__position._M_node == _M_rightmost())
01143 return _M_insert(0, _M_rightmost(), __v);
01144 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
01145 _KeyOfValue()(__v)))
01146 {
01147 if (_S_right(__position._M_node) == 0)
01148 return _M_insert(0, __position._M_node, __v);
01149 else
01150 return _M_insert(__after._M_node, __after._M_node, __v);
01151 }
01152 else
01153 return const_iterator(insert_equal(__v));
01154 }
01155 }
01156
01157 template<typename _Key, typename _Val, typename _KoV,
01158 typename _Cmp, typename _Alloc>
01159 template<class _II>
01160 void
01161 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01162 insert_equal(_II __first, _II __last)
01163 {
01164 for (; __first != __last; ++__first)
01165 insert_equal(end(), *__first);
01166 }
01167
01168 template<typename _Key, typename _Val, typename _KoV,
01169 typename _Cmp, typename _Alloc>
01170 template<class _II>
01171 void
01172 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01173 insert_unique(_II __first, _II __last)
01174 {
01175 for (; __first != __last; ++__first)
01176 insert_unique(end(), *__first);
01177 }
01178
01179 template<typename _Key, typename _Val, typename _KeyOfValue,
01180 typename _Compare, typename _Alloc>
01181 inline void
01182 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01183 erase(iterator __position)
01184 {
01185 _Link_type __y =
01186 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01187 (__position._M_node,
01188 this->_M_impl._M_header));
01189 destroy_node(__y);
01190 --_M_impl._M_node_count;
01191 }
01192
01193 template<typename _Key, typename _Val, typename _KeyOfValue,
01194 typename _Compare, typename _Alloc>
01195 inline void
01196 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01197 erase(const_iterator __position)
01198 {
01199 _Link_type __y =
01200 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01201 (const_cast<_Base_ptr>(__position._M_node),
01202 this->_M_impl._M_header));
01203 destroy_node(__y);
01204 --_M_impl._M_node_count;
01205 }
01206
01207 template<typename _Key, typename _Val, typename _KeyOfValue,
01208 typename _Compare, typename _Alloc>
01209 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01210 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01211 erase(const _Key& __x)
01212 {
01213 pair<iterator,iterator> __p = equal_range(__x);
01214 size_type __n = std::distance(__p.first, __p.second);
01215 erase(__p.first, __p.second);
01216 return __n;
01217 }
01218
01219 template<typename _Key, typename _Val, typename _KoV,
01220 typename _Compare, typename _Alloc>
01221 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01222 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01223 _M_copy(_Const_Link_type __x, _Link_type __p)
01224 {
01225
01226 _Link_type __top = _M_clone_node(__x);
01227 __top->_M_parent = __p;
01228
01229 try
01230 {
01231 if (__x->_M_right)
01232 __top->_M_right = _M_copy(_S_right(__x), __top);
01233 __p = __top;
01234 __x = _S_left(__x);
01235
01236 while (__x != 0)
01237 {
01238 _Link_type __y = _M_clone_node(__x);
01239 __p->_M_left = __y;
01240 __y->_M_parent = __p;
01241 if (__x->_M_right)
01242 __y->_M_right = _M_copy(_S_right(__x), __y);
01243 __p = __y;
01244 __x = _S_left(__x);
01245 }
01246 }
01247 catch(...)
01248 {
01249 _M_erase(__top);
01250 __throw_exception_again;
01251 }
01252 return __top;
01253 }
01254
01255 template<typename _Key, typename _Val, typename _KeyOfValue,
01256 typename _Compare, typename _Alloc>
01257 void
01258 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01259 _M_erase(_Link_type __x)
01260 {
01261
01262 while (__x != 0)
01263 {
01264 _M_erase(_S_right(__x));
01265 _Link_type __y = _S_left(__x);
01266 destroy_node(__x);
01267 __x = __y;
01268 }
01269 }
01270
01271 template<typename _Key, typename _Val, typename _KeyOfValue,
01272 typename _Compare, typename _Alloc>
01273 void
01274 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01275 erase(iterator __first, iterator __last)
01276 {
01277 if (__first == begin() && __last == end())
01278 clear();
01279 else
01280 while (__first != __last)
01281 erase(__first++);
01282 }
01283
01284 template<typename _Key, typename _Val, typename _KeyOfValue,
01285 typename _Compare, typename _Alloc>
01286 void
01287 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01288 erase(const_iterator __first, const_iterator __last)
01289 {
01290 if (__first == begin() && __last == end())
01291 clear();
01292 else
01293 while (__first != __last)
01294 erase(__first++);
01295 }
01296
01297 template<typename _Key, typename _Val, typename _KeyOfValue,
01298 typename _Compare, typename _Alloc>
01299 void
01300 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01301 erase(const _Key* __first, const _Key* __last)
01302 {
01303 while (__first != __last)
01304 erase(*__first++);
01305 }
01306
01307 template<typename _Key, typename _Val, typename _KeyOfValue,
01308 typename _Compare, typename _Alloc>
01309 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01310 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01311 find(const _Key& __k)
01312 {
01313 _Link_type __x = _M_begin();
01314 _Link_type __y = _M_end();
01315
01316 while (__x != 0)
01317 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01318 __y = __x, __x = _S_left(__x);
01319 else
01320 __x = _S_right(__x);
01321
01322 iterator __j = iterator(__y);
01323 return (__j == end()
01324 || _M_impl._M_key_compare(__k,
01325 _S_key(__j._M_node))) ? end() : __j;
01326 }
01327
01328 template<typename _Key, typename _Val, typename _KeyOfValue,
01329 typename _Compare, typename _Alloc>
01330 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01331 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01332 find(const _Key& __k) const
01333 {
01334 _Const_Link_type __x = _M_begin();
01335 _Const_Link_type __y = _M_end();
01336
01337 while (__x != 0)
01338 {
01339 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01340 __y = __x, __x = _S_left(__x);
01341 else
01342 __x = _S_right(__x);
01343 }
01344 const_iterator __j = const_iterator(__y);
01345 return (__j == end()
01346 || _M_impl._M_key_compare(__k,
01347 _S_key(__j._M_node))) ? end() : __j;
01348 }
01349
01350 template<typename _Key, typename _Val, typename _KeyOfValue,
01351 typename _Compare, typename _Alloc>
01352 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01353 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01354 count(const _Key& __k) const
01355 {
01356 pair<const_iterator, const_iterator> __p = equal_range(__k);
01357 const size_type __n = std::distance(__p.first, __p.second);
01358 return __n;
01359 }
01360
01361 template<typename _Key, typename _Val, typename _KeyOfValue,
01362 typename _Compare, typename _Alloc>
01363 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01364 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01365 lower_bound(const _Key& __k)
01366 {
01367 _Link_type __x = _M_begin();
01368 _Link_type __y = _M_end();
01369
01370 while (__x != 0)
01371 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01372 __y = __x, __x = _S_left(__x);
01373 else
01374 __x = _S_right(__x);
01375
01376 return iterator(__y);
01377 }
01378
01379 template<typename _Key, typename _Val, typename _KeyOfValue,
01380 typename _Compare, typename _Alloc>
01381 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01382 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01383 lower_bound(const _Key& __k) const
01384 {
01385 _Const_Link_type __x = _M_begin();
01386 _Const_Link_type __y = _M_end();
01387
01388 while (__x != 0)
01389 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01390 __y = __x, __x = _S_left(__x);
01391 else
01392 __x = _S_right(__x);
01393
01394 return const_iterator(__y);
01395 }
01396
01397 template<typename _Key, typename _Val, typename _KeyOfValue,
01398 typename _Compare, typename _Alloc>
01399 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01400 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01401 upper_bound(const _Key& __k)
01402 {
01403 _Link_type __x = _M_begin();
01404 _Link_type __y = _M_end();
01405
01406 while (__x != 0)
01407 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01408 __y = __x, __x = _S_left(__x);
01409 else
01410 __x = _S_right(__x);
01411
01412 return iterator(__y);
01413 }
01414
01415 template<typename _Key, typename _Val, typename _KeyOfValue,
01416 typename _Compare, typename _Alloc>
01417 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01418 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01419 upper_bound(const _Key& __k) const
01420 {
01421 _Const_Link_type __x = _M_begin();
01422 _Const_Link_type __y = _M_end();
01423
01424 while (__x != 0)
01425 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01426 __y = __x, __x = _S_left(__x);
01427 else
01428 __x = _S_right(__x);
01429
01430 return const_iterator(__y);
01431 }
01432
01433 template<typename _Key, typename _Val, typename _KeyOfValue,
01434 typename _Compare, typename _Alloc>
01435 inline
01436 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01437 _Compare, _Alloc>::iterator,
01438 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
01439 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01440 equal_range(const _Key& __k)
01441 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
01442
01443 template<typename _Key, typename _Val, typename _KoV,
01444 typename _Compare, typename _Alloc>
01445 inline
01446 pair<typename _Rb_tree<_Key, _Val, _KoV,
01447 _Compare, _Alloc>::const_iterator,
01448 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01449 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01450 equal_range(const _Key& __k) const
01451 { return pair<const_iterator, const_iterator>(lower_bound(__k),
01452 upper_bound(__k)); }
01453
01454 unsigned int
01455 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01456 const _Rb_tree_node_base* __root);
01457
01458 template<typename _Key, typename _Val, typename _KeyOfValue,
01459 typename _Compare, typename _Alloc>
01460 bool
01461 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01462 {
01463 if (_M_impl._M_node_count == 0 || begin() == end())
01464 return _M_impl._M_node_count == 0 && begin() == end()
01465 && this->_M_impl._M_header._M_left == _M_end()
01466 && this->_M_impl._M_header._M_right == _M_end();
01467
01468 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01469 for (const_iterator __it = begin(); __it != end(); ++__it)
01470 {
01471 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01472 _Const_Link_type __L = _S_left(__x);
01473 _Const_Link_type __R = _S_right(__x);
01474
01475 if (__x->_M_color == _S_red)
01476 if ((__L && __L->_M_color == _S_red)
01477 || (__R && __R->_M_color == _S_red))
01478 return false;
01479
01480 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01481 return false;
01482 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01483 return false;
01484
01485 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01486 return false;
01487 }
01488
01489 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01490 return false;
01491 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01492 return false;
01493 return true;
01494 }
01495 }
01496
01497 #endif