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 bool __insert_left = (__x != 0 || __p == _M_end()
00790 || _M_impl._M_key_compare(_KeyOfValue()(__v),
00791 _S_key(__p)));
00792
00793 _Link_type __z = _M_create_node(__v);
00794
00795 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
00796 this->_M_impl._M_header);
00797 ++_M_impl._M_node_count;
00798 return iterator(__z);
00799 }
00800
00801 template<typename _Key, typename _Val, typename _KeyOfValue,
00802 typename _Compare, typename _Alloc>
00803 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00804 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00805 insert_equal(const _Val& __v)
00806 {
00807 _Link_type __x = _M_begin();
00808 _Link_type __y = _M_end();
00809 while (__x != 0)
00810 {
00811 __y = __x;
00812 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
00813 _S_left(__x) : _S_right(__x);
00814 }
00815 return _M_insert(__x, __y, __v);
00816 }
00817
00818 template<typename _Key, typename _Val, typename _KeyOfValue,
00819 typename _Compare, typename _Alloc>
00820 void
00821 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00822 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
00823 {
00824 if (_M_root() == 0)
00825 {
00826 if (__t._M_root() != 0)
00827 {
00828 _M_root() = __t._M_root();
00829 _M_leftmost() = __t._M_leftmost();
00830 _M_rightmost() = __t._M_rightmost();
00831 _M_root()->_M_parent = _M_end();
00832
00833 __t._M_root() = 0;
00834 __t._M_leftmost() = __t._M_end();
00835 __t._M_rightmost() = __t._M_end();
00836 }
00837 }
00838 else if (__t._M_root() == 0)
00839 {
00840 __t._M_root() = _M_root();
00841 __t._M_leftmost() = _M_leftmost();
00842 __t._M_rightmost() = _M_rightmost();
00843 __t._M_root()->_M_parent = __t._M_end();
00844
00845 _M_root() = 0;
00846 _M_leftmost() = _M_end();
00847 _M_rightmost() = _M_end();
00848 }
00849 else
00850 {
00851 std::swap(_M_root(),__t._M_root());
00852 std::swap(_M_leftmost(),__t._M_leftmost());
00853 std::swap(_M_rightmost(),__t._M_rightmost());
00854
00855 _M_root()->_M_parent = _M_end();
00856 __t._M_root()->_M_parent = __t._M_end();
00857 }
00858
00859 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
00860 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
00861 }
00862
00863 template<typename _Key, typename _Val, typename _KeyOfValue,
00864 typename _Compare, typename _Alloc>
00865 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
00866 _Compare, _Alloc>::iterator, bool>
00867 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00868 insert_unique(const _Val& __v)
00869 {
00870 _Link_type __x = _M_begin();
00871 _Link_type __y = _M_end();
00872 bool __comp = true;
00873 while (__x != 0)
00874 {
00875 __y = __x;
00876 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
00877 __x = __comp ? _S_left(__x) : _S_right(__x);
00878 }
00879 iterator __j = iterator(__y);
00880 if (__comp)
00881 if (__j == begin())
00882 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
00883 else
00884 --__j;
00885 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
00886 return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
00887 return pair<iterator, bool>(__j, false);
00888 }
00889
00890 template<typename _Key, typename _Val, typename _KeyOfValue,
00891 typename _Compare, typename _Alloc>
00892 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00893 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00894 insert_unique(iterator __position, const _Val& __v)
00895 {
00896
00897 if (__position._M_node == _M_end())
00898 {
00899 if (size() > 0
00900 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
00901 _KeyOfValue()(__v)))
00902 return _M_insert(0, _M_rightmost(), __v);
00903 else
00904 return insert_unique(__v).first;
00905 }
00906 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00907 _S_key(__position._M_node)))
00908 {
00909
00910 iterator __before = __position;
00911 if (__position._M_node == _M_leftmost())
00912 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
00913 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
00914 _KeyOfValue()(__v)))
00915 {
00916 if (_S_right(__before._M_node) == 0)
00917 return _M_insert(0, __before._M_node, __v);
00918 else
00919 return _M_insert(__position._M_node,
00920 __position._M_node, __v);
00921 }
00922 else
00923 return insert_unique(__v).first;
00924 }
00925 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
00926 _KeyOfValue()(__v)))
00927 {
00928
00929 iterator __after = __position;
00930 if (__position._M_node == _M_rightmost())
00931 return _M_insert(0, _M_rightmost(), __v);
00932 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00933 _S_key((++__after)._M_node)))
00934 {
00935 if (_S_right(__position._M_node) == 0)
00936 return _M_insert(0, __position._M_node, __v);
00937 else
00938 return _M_insert(__after._M_node, __after._M_node, __v);
00939 }
00940 else
00941 return insert_unique(__v).first;
00942 }
00943 else
00944 return __position;
00945 }
00946
00947 template<typename _Key, typename _Val, typename _KeyOfValue,
00948 typename _Compare, typename _Alloc>
00949 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00950 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00951 insert_equal(iterator __position, const _Val& __v)
00952 {
00953
00954 if (__position._M_node == _M_end())
00955 {
00956 if (size() > 0
00957 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
00958 _S_key(_M_rightmost())))
00959 return _M_insert(0, _M_rightmost(), __v);
00960 else
00961 return insert_equal(__v);
00962 }
00963 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
00964 _KeyOfValue()(__v)))
00965 {
00966
00967 iterator __before = __position;
00968 if (__position._M_node == _M_leftmost())
00969 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
00970 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
00971 _S_key((--__before)._M_node)))
00972 {
00973 if (_S_right(__before._M_node) == 0)
00974 return _M_insert(0, __before._M_node, __v);
00975 else
00976 return _M_insert(__position._M_node,
00977 __position._M_node, __v);
00978 }
00979 else
00980 return insert_equal(__v);
00981 }
00982 else
00983 {
00984
00985 iterator __after = __position;
00986 if (__position._M_node == _M_rightmost())
00987 return _M_insert(0, _M_rightmost(), __v);
00988 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
00989 _KeyOfValue()(__v)))
00990 {
00991 if (_S_right(__position._M_node) == 0)
00992 return _M_insert(0, __position._M_node, __v);
00993 else
00994 return _M_insert(__after._M_node, __after._M_node, __v);
00995 }
00996 else
00997 return insert_equal(__v);
00998 }
00999 }
01000
01001 template<typename _Key, typename _Val, typename _KoV,
01002 typename _Cmp, typename _Alloc>
01003 template<class _II>
01004 void
01005 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01006 insert_equal(_II __first, _II __last)
01007 {
01008 for (; __first != __last; ++__first)
01009 insert_equal(end(), *__first);
01010 }
01011
01012 template<typename _Key, typename _Val, typename _KoV,
01013 typename _Cmp, typename _Alloc>
01014 template<class _II>
01015 void
01016 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01017 insert_unique(_II __first, _II __last)
01018 {
01019 for (; __first != __last; ++__first)
01020 insert_unique(end(), *__first);
01021 }
01022
01023 template<typename _Key, typename _Val, typename _KeyOfValue,
01024 typename _Compare, typename _Alloc>
01025 inline void
01026 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01027 erase(iterator __position)
01028 {
01029 _Link_type __y =
01030 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01031 (__position._M_node,
01032 this->_M_impl._M_header));
01033 destroy_node(__y);
01034 --_M_impl._M_node_count;
01035 }
01036
01037 template<typename _Key, typename _Val, typename _KeyOfValue,
01038 typename _Compare, typename _Alloc>
01039 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01040 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01041 erase(const _Key& __x)
01042 {
01043 pair<iterator,iterator> __p = equal_range(__x);
01044 size_type __n = std::distance(__p.first, __p.second);
01045 erase(__p.first, __p.second);
01046 return __n;
01047 }
01048
01049 template<typename _Key, typename _Val, typename _KoV,
01050 typename _Compare, typename _Alloc>
01051 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01052 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01053 _M_copy(_Const_Link_type __x, _Link_type __p)
01054 {
01055
01056 _Link_type __top = _M_clone_node(__x);
01057 __top->_M_parent = __p;
01058
01059 try
01060 {
01061 if (__x->_M_right)
01062 __top->_M_right = _M_copy(_S_right(__x), __top);
01063 __p = __top;
01064 __x = _S_left(__x);
01065
01066 while (__x != 0)
01067 {
01068 _Link_type __y = _M_clone_node(__x);
01069 __p->_M_left = __y;
01070 __y->_M_parent = __p;
01071 if (__x->_M_right)
01072 __y->_M_right = _M_copy(_S_right(__x), __y);
01073 __p = __y;
01074 __x = _S_left(__x);
01075 }
01076 }
01077 catch(...)
01078 {
01079 _M_erase(__top);
01080 __throw_exception_again;
01081 }
01082 return __top;
01083 }
01084
01085 template<typename _Key, typename _Val, typename _KeyOfValue,
01086 typename _Compare, typename _Alloc>
01087 void
01088 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01089 _M_erase(_Link_type __x)
01090 {
01091
01092 while (__x != 0)
01093 {
01094 _M_erase(_S_right(__x));
01095 _Link_type __y = _S_left(__x);
01096 destroy_node(__x);
01097 __x = __y;
01098 }
01099 }
01100
01101 template<typename _Key, typename _Val, typename _KeyOfValue,
01102 typename _Compare, typename _Alloc>
01103 void
01104 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01105 erase(iterator __first, iterator __last)
01106 {
01107 if (__first == begin() && __last == end())
01108 clear();
01109 else
01110 while (__first != __last)
01111 erase(__first++);
01112 }
01113
01114 template<typename _Key, typename _Val, typename _KeyOfValue,
01115 typename _Compare, typename _Alloc>
01116 void
01117 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01118 erase(const _Key* __first, const _Key* __last)
01119 {
01120 while (__first != __last)
01121 erase(*__first++);
01122 }
01123
01124 template<typename _Key, typename _Val, typename _KeyOfValue,
01125 typename _Compare, typename _Alloc>
01126 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01127 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01128 find(const _Key& __k)
01129 {
01130 _Link_type __x = _M_begin();
01131 _Link_type __y = _M_end();
01132
01133 while (__x != 0)
01134 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01135 __y = __x, __x = _S_left(__x);
01136 else
01137 __x = _S_right(__x);
01138
01139 iterator __j = iterator(__y);
01140 return (__j == end()
01141 || _M_impl._M_key_compare(__k,
01142 _S_key(__j._M_node))) ? end() : __j;
01143 }
01144
01145 template<typename _Key, typename _Val, typename _KeyOfValue,
01146 typename _Compare, typename _Alloc>
01147 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01148 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01149 find(const _Key& __k) const
01150 {
01151 _Const_Link_type __x = _M_begin();
01152 _Const_Link_type __y = _M_end();
01153
01154 while (__x != 0)
01155 {
01156 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01157 __y = __x, __x = _S_left(__x);
01158 else
01159 __x = _S_right(__x);
01160 }
01161 const_iterator __j = const_iterator(__y);
01162 return (__j == end()
01163 || _M_impl._M_key_compare(__k,
01164 _S_key(__j._M_node))) ? end() : __j;
01165 }
01166
01167 template<typename _Key, typename _Val, typename _KeyOfValue,
01168 typename _Compare, typename _Alloc>
01169 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01170 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01171 count(const _Key& __k) const
01172 {
01173 pair<const_iterator, const_iterator> __p = equal_range(__k);
01174 const size_type __n = std::distance(__p.first, __p.second);
01175 return __n;
01176 }
01177
01178 template<typename _Key, typename _Val, typename _KeyOfValue,
01179 typename _Compare, typename _Alloc>
01180 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01181 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01182 lower_bound(const _Key& __k)
01183 {
01184 _Link_type __x = _M_begin();
01185 _Link_type __y = _M_end();
01186
01187 while (__x != 0)
01188 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01189 __y = __x, __x = _S_left(__x);
01190 else
01191 __x = _S_right(__x);
01192
01193 return iterator(__y);
01194 }
01195
01196 template<typename _Key, typename _Val, typename _KeyOfValue,
01197 typename _Compare, typename _Alloc>
01198 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01199 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01200 lower_bound(const _Key& __k) const
01201 {
01202 _Const_Link_type __x = _M_begin();
01203 _Const_Link_type __y = _M_end();
01204
01205 while (__x != 0)
01206 if (!_M_impl._M_key_compare(_S_key(__x), __k))
01207 __y = __x, __x = _S_left(__x);
01208 else
01209 __x = _S_right(__x);
01210
01211 return const_iterator(__y);
01212 }
01213
01214 template<typename _Key, typename _Val, typename _KeyOfValue,
01215 typename _Compare, typename _Alloc>
01216 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01217 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01218 upper_bound(const _Key& __k)
01219 {
01220 _Link_type __x = _M_begin();
01221 _Link_type __y = _M_end();
01222
01223 while (__x != 0)
01224 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01225 __y = __x, __x = _S_left(__x);
01226 else
01227 __x = _S_right(__x);
01228
01229 return iterator(__y);
01230 }
01231
01232 template<typename _Key, typename _Val, typename _KeyOfValue,
01233 typename _Compare, typename _Alloc>
01234 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01235 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01236 upper_bound(const _Key& __k) const
01237 {
01238 _Const_Link_type __x = _M_begin();
01239 _Const_Link_type __y = _M_end();
01240
01241 while (__x != 0)
01242 if (_M_impl._M_key_compare(__k, _S_key(__x)))
01243 __y = __x, __x = _S_left(__x);
01244 else
01245 __x = _S_right(__x);
01246
01247 return const_iterator(__y);
01248 }
01249
01250 template<typename _Key, typename _Val, typename _KeyOfValue,
01251 typename _Compare, typename _Alloc>
01252 inline
01253 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01254 _Compare, _Alloc>::iterator,
01255 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
01256 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01257 equal_range(const _Key& __k)
01258 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
01259
01260 template<typename _Key, typename _Val, typename _KoV,
01261 typename _Compare, typename _Alloc>
01262 inline
01263 pair<typename _Rb_tree<_Key, _Val, _KoV,
01264 _Compare, _Alloc>::const_iterator,
01265 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01266 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01267 equal_range(const _Key& __k) const
01268 { return pair<const_iterator, const_iterator>(lower_bound(__k),
01269 upper_bound(__k)); }
01270
01271 unsigned int
01272 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01273 const _Rb_tree_node_base* __root);
01274
01275 template<typename _Key, typename _Val, typename _KeyOfValue,
01276 typename _Compare, typename _Alloc>
01277 bool
01278 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01279 {
01280 if (_M_impl._M_node_count == 0 || begin() == end())
01281 return _M_impl._M_node_count == 0 && begin() == end()
01282 && this->_M_impl._M_header._M_left == _M_end()
01283 && this->_M_impl._M_header._M_right == _M_end();
01284
01285 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01286 for (const_iterator __it = begin(); __it != end(); ++__it)
01287 {
01288 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01289 _Const_Link_type __L = _S_left(__x);
01290 _Const_Link_type __R = _S_right(__x);
01291
01292 if (__x->_M_color == _S_red)
01293 if ((__L && __L->_M_color == _S_red)
01294 || (__R && __R->_M_color == _S_red))
01295 return false;
01296
01297 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01298 return false;
01299 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01300 return false;
01301
01302 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01303 return false;
01304 }
01305
01306 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01307 return false;
01308 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01309 return false;
01310 return true;
01311 }
01312 }
01313
01314 #endif