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_node_count(0)
00405 {
00406 this->_M_header._M_color = _S_red;
00407 this->_M_header._M_parent = 0;
00408 this->_M_header._M_left = &this->_M_header;
00409 this->_M_header._M_right = &this->_M_header;
00410 }
00411 };
00412
00413
00414
00415 template<typename _Key_compare>
00416 struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
00417 {
00418 _Key_compare _M_key_compare;
00419 _Rb_tree_node_base _M_header;
00420 size_type _M_node_count;
00421
00422 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00423 const _Key_compare& __comp = _Key_compare())
00424 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
00425 {
00426 this->_M_header._M_color = _S_red;
00427 this->_M_header._M_parent = 0;
00428 this->_M_header._M_left = &this->_M_header;
00429 this->_M_header._M_right = &this->_M_header;
00430 }
00431 };
00432
00433 _Rb_tree_impl<_Compare> _M_impl;
00434
00435 protected:
00436 _Base_ptr&
00437 _M_root()
00438 { return this->_M_impl._M_header._M_parent; }
00439
00440 _Const_Base_ptr
00441 _M_root() const
00442 { return this->_M_impl._M_header._M_parent; }
00443
00444 _Base_ptr&
00445 _M_leftmost()
00446 { return this->_M_impl._M_header._M_left; }
00447
00448 _Const_Base_ptr
00449 _M_leftmost() const
00450 { return this->_M_impl._M_header._M_left; }
00451
00452 _Base_ptr&
00453 _M_rightmost()
00454 { return this->_M_impl._M_header._M_right; }
00455
00456 _Const_Base_ptr
00457 _M_rightmost() const
00458 { return this->_M_impl._M_header._M_right; }
00459
00460 _Link_type
00461 _M_begin()
00462 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00463
00464 _Const_Link_type
00465 _M_begin() const
00466 {
00467 return static_cast<_Const_Link_type>
00468 (this->_M_impl._M_header._M_parent);
00469 }
00470
00471 _Link_type
00472 _M_end()
00473 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00474
00475 _Const_Link_type
00476 _M_end() const
00477 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00478
00479 static const_reference
00480 _S_value(_Const_Link_type __x)
00481 { return __x->_M_value_field; }
00482
00483 static const _Key&
00484 _S_key(_Const_Link_type __x)
00485 { return _KeyOfValue()(_S_value(__x)); }
00486
00487 static _Link_type
00488 _S_left(_Base_ptr __x)
00489 { return static_cast<_Link_type>(__x->_M_left); }
00490
00491 static _Const_Link_type
00492 _S_left(_Const_Base_ptr __x)
00493 { return static_cast<_Const_Link_type>(__x->_M_left); }
00494
00495 static _Link_type
00496 _S_right(_Base_ptr __x)
00497 { return static_cast<_Link_type>(__x->_M_right); }
00498
00499 static _Const_Link_type
00500 _S_right(_Const_Base_ptr __x)
00501 { return static_cast<_Const_Link_type>(__x->_M_right); }
00502
00503 static const_reference
00504 _S_value(_Const_Base_ptr __x)
00505 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00506
00507 static const _Key&
00508 _S_key(_Const_Base_ptr __x)
00509 { return _KeyOfValue()(_S_value(__x)); }
00510
00511 static _Base_ptr
00512 _S_minimum(_Base_ptr __x)
00513 { return _Rb_tree_node_base::_S_minimum(__x); }
00514
00515 static _Const_Base_ptr
00516 _S_minimum(_Const_Base_ptr __x)
00517 { return _Rb_tree_node_base::_S_minimum(__x); }
00518
00519 static _Base_ptr
00520 _S_maximum(_Base_ptr __x)
00521 { return _Rb_tree_node_base::_S_maximum(__x); }
00522
00523 static _Const_Base_ptr
00524 _S_maximum(_Const_Base_ptr __x)
00525 { return _Rb_tree_node_base::_S_maximum(__x); }
00526
00527 public:
00528 typedef _Rb_tree_iterator<value_type> iterator;
00529 typedef _Rb_tree_const_iterator<value_type> const_iterator;
00530
00531 typedef std::reverse_iterator<iterator> reverse_iterator;
00532 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00533
00534 private:
00535 iterator
00536 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00537
00538 _Link_type
00539 _M_copy(_Const_Link_type __x, _Link_type __p);
00540
00541 void
00542 _M_erase(_Link_type __x);
00543
00544 public:
00545
00546 _Rb_tree()
00547 { }
00548
00549 _Rb_tree(const _Compare& __comp)
00550 : _M_impl(allocator_type(), __comp)
00551 { }
00552
00553 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
00554 : _M_impl(__a, __comp)
00555 { }
00556
00557 _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00558 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
00559 {
00560 if (__x._M_root() != 0)
00561 {
00562 _M_root() = _M_copy(__x._M_begin(), _M_end());
00563 _M_leftmost() = _S_minimum(_M_root());
00564 _M_rightmost() = _S_maximum(_M_root());
00565 _M_impl._M_node_count = __x._M_impl._M_node_count;
00566 }
00567 }
00568
00569 ~_Rb_tree()
00570 { _M_erase(_M_begin()); }
00571
00572 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00573 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
00574
00575
00576 _Compare
00577 key_comp() const
00578 { return _M_impl._M_key_compare; }
00579
00580 iterator
00581 begin()
00582 { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
00583
00584 const_iterator
00585 begin() const
00586 {
00587 return static_cast<_Const_Link_type>
00588 (this->_M_impl._M_header._M_left);
00589 }
00590
00591 iterator
00592 end()
00593 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00594
00595 const_iterator
00596 end() const
00597 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00598
00599 reverse_iterator
00600 rbegin()
00601 { return reverse_iterator(end()); }
00602
00603 const_reverse_iterator
00604 rbegin() const
00605 { return const_reverse_iterator(end()); }
00606
00607 reverse_iterator
00608 rend()
00609 { return reverse_iterator(begin()); }
00610
00611 const_reverse_iterator
00612 rend() const
00613 { return const_reverse_iterator(begin()); }
00614
00615 bool
00616 empty() const
00617 { return _M_impl._M_node_count == 0; }
00618
00619 size_type
00620 size() const
00621 { return _M_impl._M_node_count; }
00622
00623 size_type
00624 max_size() const
00625 { return size_type(-1); }
00626
00627 void
00628 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
00629
00630
00631 pair<iterator,bool>
00632 insert_unique(const value_type& __x);
00633
00634 iterator
00635 insert_equal(const value_type& __x);
00636
00637 iterator
00638 insert_unique(iterator __position, const value_type& __x);
00639
00640 iterator
00641 insert_equal(iterator __position, const value_type& __x);
00642
00643 template<typename _InputIterator>
00644 void
00645 insert_unique(_InputIterator __first, _InputIterator __last);
00646
00647 template<typename _InputIterator>
00648 void
00649 insert_equal(_InputIterator __first, _InputIterator __last);
00650
00651 void
00652 erase(iterator __position);
00653
00654 size_type
00655 erase(const key_type& __x);
00656
00657 void
00658 erase(iterator __first, iterator __last);
00659
00660 void
00661 erase(const key_type* __first, const key_type* __last);
00662
00663 void
00664 clear()
00665 {
00666 _M_erase(_M_begin());
00667 _M_leftmost() = _M_end();
00668 _M_root() = 0;
00669 _M_rightmost() = _M_end();
00670 _M_impl._M_node_count = 0;
00671 }
00672
00673
00674 iterator
00675 find(const key_type& __x);
00676
00677 const_iterator
00678 find(const key_type& __x) const;
00679
00680 size_type
00681 count(const key_type& __x) const;
00682
00683 iterator
00684 lower_bound(const key_type& __x);
00685
00686 const_iterator
00687 lower_bound(const key_type& __x) const;
00688
00689 iterator
00690 upper_bound(const key_type& __x);
00691
00692 const_iterator
00693 upper_bound(const key_type& __x) const;
00694
00695 pair<iterator,iterator>
00696 equal_range(const key_type& __x);
00697
00698 pair<const_iterator, const_iterator>
00699 equal_range(const key_type& __x) const;
00700
00701
00702 bool
00703 __rb_verify() const;
00704 };
00705
00706 template<typename _Key, typename _Val, typename _KeyOfValue,
00707 typename _Compare, typename _Alloc>
00708 inline bool
00709 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00710 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00711 {
00712 return __x.size() == __y.size()
00713 && std::equal(__x.begin(), __x.end(), __y.begin());
00714 }
00715
00716 template<typename _Key, typename _Val, typename _KeyOfValue,
00717 typename _Compare, typename _Alloc>
00718 inline bool
00719 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00720 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00721 {
00722 return std::lexicographical_compare(__x.begin(), __x.end(),
00723 __y.begin(), __y.end());
00724 }
00725
00726 template<typename _Key, typename _Val, typename _KeyOfValue,
00727 typename _Compare, typename _Alloc>
00728 inline bool
00729 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00730 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00731 { return !(__x == __y); }
00732
00733 template<typename _Key, typename _Val, typename _KeyOfValue,
00734 typename _Compare, typename _Alloc>
00735 inline bool
00736 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00737 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00738 { return __y < __x; }
00739
00740 template<typename _Key, typename _Val, typename _KeyOfValue,
00741 typename _Compare, typename _Alloc>
00742 inline bool
00743 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00744 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00745 { return !(__y < __x); }
00746
00747 template<typename _Key, typename _Val, typename _KeyOfValue,
00748 typename _Compare, typename _Alloc>
00749 inline bool
00750 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00751 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00752 { return !(__x < __y); }
00753
00754 template<typename _Key, typename _Val, typename _KeyOfValue,
00755 typename _Compare, typename _Alloc>
00756 inline void
00757 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00758 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00759 { __x.swap(__y); }
00760
00761 template<typename _Key, typename _Val, typename _KeyOfValue,
00762 typename _Compare, typename _Alloc>
00763 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00764 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00765 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00766 {
00767 if (this != &__x)
00768 {
00769
00770 clear();
00771 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00772 if (__x._M_root() != 0)
00773 {
00774 _M_root() = _M_copy(__x._M_begin(), _M_end());
00775 _M_leftmost() = _S_minimum(_M_root());
00776 _M_rightmost() = _S_maximum(_M_root());
00777 _M_impl._M_node_count = __x._M_impl._M_node_count;
00778 }
00779 }
00780 return *this;
00781 }
00782
00783 template<typename _Key, typename _Val, typename _KeyOfValue,
00784 typename _Compare, typename _Alloc>
00785 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00786 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00787 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00788 {
00789 _Link_type __z = _M_create_node(__v);
00790 bool __insert_left;
00791
00792 __insert_left = (__x != 0 || __p == _M_end()
00793 || _M_impl._M_key_compare(_KeyOfValue()(__v),
00794 _S_key(__p)));
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 if (__position._M_node == _M_end()
00898 || __position._M_node == _M_rightmost())
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
00908 {
00909 iterator __after = __position;
00910 ++__after;
00911 if (_M_impl._M_key_compare(_S_key(__position._M_node),
00912 _KeyOfValue()(__v))
00913 && _M_impl._M_key_compare(_KeyOfValue()(__v),
00914 _S_key(__after._M_node)))
00915 {
00916 if (_S_right(__position._M_node) == 0)
00917 return _M_insert(0, __position._M_node, __v);
00918 else
00919 return _M_insert(__after._M_node, __after._M_node, __v);
00920
00921 }
00922 else
00923 return insert_unique(__v).first;
00924 }
00925 }
00926
00927 template<typename _Key, typename _Val, typename _KeyOfValue,
00928 typename _Compare, typename _Alloc>
00929 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00930 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00931 insert_equal(iterator __position, const _Val& __v)
00932 {
00933 if (__position._M_node == _M_end()
00934 || __position._M_node == _M_rightmost())
00935 {
00936 if (size() > 0
00937 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
00938 _S_key(_M_rightmost())))
00939 return _M_insert(0, _M_rightmost(), __v);
00940 else
00941 return insert_equal(__v);
00942 }
00943 else
00944 {
00945 iterator __after = __position;
00946 ++__after;
00947 if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
00948 _S_key(__position._M_node))
00949 && !_M_impl._M_key_compare(_S_key(__after._M_node),
00950 _KeyOfValue()(__v)))
00951 {
00952 if (_S_right(__position._M_node) == 0)
00953 return _M_insert(0, __position._M_node, __v);
00954 else
00955 return _M_insert(__after._M_node, __after._M_node, __v);
00956
00957 }
00958 else
00959 return insert_equal(__v);
00960 }
00961 }
00962
00963 template<typename _Key, typename _Val, typename _KoV,
00964 typename _Cmp, typename _Alloc>
00965 template<class _II>
00966 void
00967 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
00968 insert_equal(_II __first, _II __last)
00969 {
00970 for (; __first != __last; ++__first)
00971 insert_equal(end(), *__first);
00972 }
00973
00974 template<typename _Key, typename _Val, typename _KoV,
00975 typename _Cmp, typename _Alloc>
00976 template<class _II>
00977 void
00978 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
00979 insert_unique(_II __first, _II __last)
00980 {
00981 for (; __first != __last; ++__first)
00982 insert_unique(end(), *__first);
00983 }
00984
00985 template<typename _Key, typename _Val, typename _KeyOfValue,
00986 typename _Compare, typename _Alloc>
00987 inline void
00988 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00989 erase(iterator __position)
00990 {
00991 _Link_type __y =
00992 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
00993 (__position._M_node,
00994 this->_M_impl._M_header));
00995 destroy_node(__y);
00996 --_M_impl._M_node_count;
00997 }
00998
00999 template<typename _Key, typename _Val, typename _KeyOfValue,
01000 typename _Compare, typename _Alloc>
01001 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01002 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01003 erase(const _Key& __x)
01004 {
01005 pair<iterator,iterator> __p = equal_range(__x);
01006 size_type __n = std::distance(__p.first, __p.second);
01007 erase(__p.first, __p.second);
01008 return __n;
01009 }
01010
01011 template<typename _Key, typename _Val, typename _KoV,
01012 typename _Compare, typename _Alloc>
01013 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01014 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01015 _M_copy(_Const_Link_type __x, _Link_type __p)
01016 {
01017
01018 _Link_type __top = _M_clone_node(__x);
01019 __top->_M_parent = __p;
01020
01021 try
01022 {
01023 if (__x->_M_right)
01024 __top->_M_right = _M_copy(_S_right(__x), __top);
01025 __p = __top;
01026 __x = _S_left(__x);
01027
01028 while (__x != 0)
01029 {
01030 _Link_type __y = _M_clone_node(__x);
01031 __p->_M_left = __y;
01032 __y->_M_parent = __p;
01033 if (__x->_M_right)
01034 __y->_M_right = _M_copy(_S_right(__x), __y);
01035 __p = __y;
01036 __x = _S_left(__x);
01037 }
01038 }
01039 catch(...)
01040 {
01041 _M_erase(__top);
01042 __throw_exception_again;
01043 }
01044 return __top;
01045 }
01046
01047 template<typename _Key, typename _Val, typename _KeyOfValue,
01048 typename _Compare, typename _Alloc>
01049 void
01050 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01051 _M_erase(_Link_type __x)
01052 {
01053
01054 while (__x != 0)
01055 {
01056 _M_erase(_S_right(__x));
01057 _Link_type __y = _S_left(__x);
01058 destroy_node(__x);
01059 __x = __y;
01060 }
01061 }
01062
01063 template<typename _Key, typename _Val, typename _KeyOfValue,
01064 typename _Compare, typename _Alloc>
01065 void
01066 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01067 erase(iterator __first, iterator __last)
01068 {
01069 if (__first == begin() && __last == end())
01070 clear();
01071 else
01072 while (__first != __last)
01073 erase(__first++);
01074 }
01075
01076 template<typename _Key, typename _Val, typename _KeyOfValue,
01077 typename _Compare, typename _Alloc>
01078 void
01079 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01080 erase(const _Key* __first, const _Key* __last)
01081 {
01082 while (__first != __last)
01083 erase(*__first++);
01084 }
01085
01086 template<typename _Key, typename _Val, typename _KeyOfValue,
01087 typename _Compare, typename _Alloc>
01088 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01089 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01090 find(const _Key& __k)
01091 {
01092 _Link_type __x = _M_begin();
01093 _Link_type __y = _M_end();
01094
01095 while (__x != 0)
01096 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01097 __y = __x, __x = _S_left(__x);
01098 else
01099 __x = _S_right(__x);
01100
01101 iterator __j = iterator(__y);
01102 return (__j == end()
01103 || _M_impl._M_key_compare(__k,
01104 _S_key(__j._M_node))) ? end() : __j;
01105 }
01106
01107 template<typename _Key, typename _Val, typename _KeyOfValue,
01108 typename _Compare, typename _Alloc>
01109 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01110 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01111 find(const _Key& __k) const
01112 {
01113 _Const_Link_type __x = _M_begin();
01114 _Const_Link_type __y = _M_end();
01115
01116 while (__x != 0)
01117 {
01118 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01119 __y = __x, __x = _S_left(__x);
01120 else
01121 __x = _S_right(__x);
01122 }
01123 const_iterator __j = const_iterator(__y);
01124 return (__j == end()
01125 || _M_impl._M_key_compare(__k,
01126 _S_key(__j._M_node))) ? end() : __j;
01127 }
01128
01129 template<typename _Key, typename _Val, typename _KeyOfValue,
01130 typename _Compare, typename _Alloc>
01131 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01132 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01133 count(const _Key& __k) const
01134 {
01135 pair<const_iterator, const_iterator> __p = equal_range(__k);
01136 const size_type __n = std::distance(__p.first, __p.second);
01137 return __n;
01138 }
01139
01140 template<typename _Key, typename _Val, typename _KeyOfValue,
01141 typename _Compare, typename _Alloc>
01142 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01143 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01144 lower_bound(const _Key& __k)
01145 {
01146 _Link_type __x = _M_begin();
01147 _Link_type __y = _M_end();
01148
01149 while (__x != 0)
01150 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01151 __y = __x, __x = _S_left(__x);
01152 else
01153 __x = _S_right(__x);
01154
01155 return iterator(__y);
01156 }
01157
01158 template<typename _Key, typename _Val, typename _KeyOfValue,
01159 typename _Compare, typename _Alloc>
01160 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01161 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01162 lower_bound(const _Key& __k) const
01163 {
01164 _Const_Link_type __x = _M_begin();
01165 _Const_Link_type __y = _M_end();
01166
01167 while (__x != 0)
01168 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01169 __y = __x, __x = _S_left(__x);
01170 else
01171 __x = _S_right(__x);
01172
01173 return const_iterator(__y);
01174 }
01175
01176 template<typename _Key, typename _Val, typename _KeyOfValue,
01177 typename _Compare, typename _Alloc>
01178 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01179 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01180 upper_bound(const _Key& __k)
01181 {
01182 _Link_type __x = _M_begin();
01183 _Link_type __y = _M_end();
01184
01185 while (__x != 0)
01186 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01187 __y = __x, __x = _S_left(__x);
01188 else
01189 __x = _S_right(__x);
01190
01191 return iterator(__y);
01192 }
01193
01194 template<typename _Key, typename _Val, typename _KeyOfValue,
01195 typename _Compare, typename _Alloc>
01196 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01197 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01198 upper_bound(const _Key& __k) const
01199 {
01200 _Const_Link_type __x = _M_begin();
01201 _Const_Link_type __y = _M_end();
01202
01203 while (__x != 0)
01204 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01205 __y = __x, __x = _S_left(__x);
01206 else
01207 __x = _S_right(__x);
01208
01209 return const_iterator(__y);
01210 }
01211
01212 template<typename _Key, typename _Val, typename _KeyOfValue,
01213 typename _Compare, typename _Alloc>
01214 inline
01215 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01216 _Compare, _Alloc>::iterator,
01217 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
01218 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01219 equal_range(const _Key& __k)
01220 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
01221
01222 template<typename _Key, typename _Val, typename _KoV,
01223 typename _Compare, typename _Alloc>
01224 inline
01225 pair<typename _Rb_tree<_Key, _Val, _KoV,
01226 _Compare, _Alloc>::const_iterator,
01227 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01228 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01229 equal_range(const _Key& __k) const
01230 { return pair<const_iterator, const_iterator>(lower_bound(__k),
01231 upper_bound(__k)); }
01232
01233 unsigned int
01234 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01235 const _Rb_tree_node_base* __root);
01236
01237 template<typename _Key, typename _Val, typename _KeyOfValue,
01238 typename _Compare, typename _Alloc>
01239 bool
01240 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01241 {
01242 if (_M_impl._M_node_count == 0 || begin() == end())
01243 return _M_impl._M_node_count == 0 && begin() == end()
01244 && this->_M_impl._M_header._M_left == _M_end()
01245 && this->_M_impl._M_header._M_right == _M_end();
01246
01247 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01248 for (const_iterator __it = begin(); __it != end(); ++__it)
01249 {
01250 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01251 _Const_Link_type __L = _S_left(__x);
01252 _Const_Link_type __R = _S_right(__x);
01253
01254 if (__x->_M_color == _S_red)
01255 if ((__L && __L->_M_color == _S_red)
01256 || (__R && __R->_M_color == _S_red))
01257 return false;
01258
01259 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01260 return false;
01261 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01262 return false;
01263
01264 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01265 return false;
01266 }
01267
01268 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01269 return false;
01270 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01271 return false;
01272 return true;
01273 }
01274 }
01275
01276 #endif