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