1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 18 * Permission to use or copy this software for any purpose is hereby granted 19 * without fee, provided the above notices are retained on all copies. 20 * Permission to modify the code and to distribute modified code is granted, 21 * provided the above notices are retained, and a notice that the code was 22 * modified is included with the above copyright notice. 23 * 24 */ 25 26 /* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _STLP_INTERNAL_TREE_H 31 #define _STLP_INTERNAL_TREE_H 32 33 /* 34 35 Red-black tree class, designed for use in implementing STL 36 associative containers (set, multiset, map, and multimap). The 37 insertion and deletion algorithms are based on those in Cormen, 38 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), 39 except that 40 41 (1) the header cell is maintained with links not only to the root 42 but also to the leftmost node of the tree, to enable constant time 43 begin(), and to the rightmost node of the tree, to enable linear time 44 performance when used with the generic set algorithms (set_union, 45 etc.); 46 47 (2) when a node being deleted has two children its successor node is 48 relinked into its place, rather than copied, so that the only 49 iterators invalidated are those referring to the deleted node. 50 51 */ 52 53 #ifndef _STLP_INTERNAL_ALGOBASE_H 54 # include <stl/_algobase.h> 55 #endif 56 57 #ifndef _STLP_INTERNAL_ALLOC_H 58 # include <stl/_alloc.h> 59 #endif 60 61 #ifndef _STLP_INTERNAL_ITERATOR_H 62 # include <stl/_iterator.h> 63 #endif 64 65 #ifndef _STLP_INTERNAL_CONSTRUCT_H 66 # include <stl/_construct.h> 67 #endif 68 69 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H 70 # include <stl/_function_base.h> 71 #endif 72 73 _STLP_BEGIN_NAMESPACE 74 75 _STLP_MOVE_TO_PRIV_NAMESPACE 76 77 typedef bool _Rb_tree_Color_type; 78 //const _Rb_tree_Color_type _S_rb_tree_red = false; 79 //const _Rb_tree_Color_type _S_rb_tree_black = true; 80 81 #define _S_rb_tree_red false 82 #define _S_rb_tree_black true 83 84 struct _Rb_tree_node_base { 85 typedef _Rb_tree_Color_type _Color_type; 86 typedef _Rb_tree_node_base* _Base_ptr; 87 88 _Color_type _M_color; 89 _Base_ptr _M_parent; 90 _Base_ptr _M_left; 91 _Base_ptr _M_right; 92 93 static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) { 94 while (__x->_M_left != 0) __x = __x->_M_left; 95 return __x; 96 } 97 98 static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) { 99 while (__x->_M_right != 0) __x = __x->_M_right; 100 return __x; 101 } 102 }; 103 104 template <class _Value> 105 struct _Rb_tree_node : public _Rb_tree_node_base { 106 _Value _M_value_field; 107 __TRIVIAL_STUFF(_Rb_tree_node) 108 }; 109 110 struct _Rb_tree_base_iterator; 111 112 template <class _Dummy> 113 class _Rb_global { 114 public: 115 typedef _Rb_tree_node_base* _Base_ptr; 116 // those used to be global functions 117 static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr& __root); 118 static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, 119 _Base_ptr& __root, 120 _Base_ptr& __leftmost, 121 _Base_ptr& __rightmost); 122 // those are from _Rb_tree_base_iterator - moved here to reduce code bloat 123 // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator 124 static _Base_ptr _STLP_CALL _M_increment (_Base_ptr); 125 static _Base_ptr _STLP_CALL _M_decrement (_Base_ptr); 126 static void _STLP_CALL _Rotate_left (_Base_ptr __x, _Base_ptr& __root); 127 static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr& __root); 128 }; 129 130 # if defined (_STLP_USE_TEMPLATE_EXPORT) 131 _STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>; 132 # endif 133 134 typedef _Rb_global<bool> _Rb_global_inst; 135 136 struct _Rb_tree_base_iterator { 137 typedef _Rb_tree_node_base* _Base_ptr; 138 typedef bidirectional_iterator_tag iterator_category; 139 typedef ptrdiff_t difference_type; 140 _Base_ptr _M_node; 141 _Rb_tree_base_iterator() : _M_node(0) {} 142 _Rb_tree_base_iterator(_Base_ptr __x) : _M_node(__x) {} 143 }; 144 145 template <class _Value, class _Traits> 146 struct _Rb_tree_iterator : public _Rb_tree_base_iterator { 147 typedef _Value value_type; 148 typedef typename _Traits::reference reference; 149 typedef typename _Traits::pointer pointer; 150 typedef _Rb_tree_iterator<_Value, _Traits> _Self; 151 typedef _Rb_tree_node_base* _Base_ptr; 152 typedef _Rb_tree_node<_Value>* _Link_type; 153 154 typedef typename _Traits::_NonConstTraits _NonConstTraits; 155 typedef _Rb_tree_iterator<_Value, _NonConstTraits> iterator; 156 typedef typename _Traits::_ConstTraits _ConstTraits; 157 typedef _Rb_tree_iterator<_Value, _ConstTraits> const_iterator; 158 159 _Rb_tree_iterator() {} 160 #if !defined (_STLP_DEBUG) 161 /* In STL debug mode we need this constructor implicit for the pointer 162 * specialization implementation. 163 */ 164 explicit 165 #endif 166 _Rb_tree_iterator(_Base_ptr __x) : _Rb_tree_base_iterator(__x) {} 167 //copy constructor for iterator and constructor from iterator for const_iterator 168 _Rb_tree_iterator(const iterator& __it) : _Rb_tree_base_iterator(__it._M_node) {} 169 170 reference operator*() const { 171 return __STATIC_CAST(_Link_type, _M_node)->_M_value_field; 172 } 173 174 _STLP_DEFINE_ARROW_OPERATOR 175 176 _Self& operator++() { 177 _M_node = _Rb_global_inst::_M_increment(_M_node); 178 return *this; 179 } 180 _Self operator++(int) { 181 _Self __tmp = *this; 182 ++(*this); 183 return __tmp; 184 } 185 186 _Self& operator--() { 187 _M_node = _Rb_global_inst::_M_decrement(_M_node); 188 return *this; 189 } 190 _Self operator--(int) { 191 _Self __tmp = *this; 192 --(*this); 193 return __tmp; 194 } 195 196 bool operator == (const_iterator __rhs) const { 197 return _M_node == __rhs._M_node; 198 } 199 bool operator != (const_iterator __rhs) const { 200 return _M_node != __rhs._M_node; 201 } 202 }; 203 204 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 205 _STLP_MOVE_TO_STD_NAMESPACE 206 template <class _Value, class _Traits> 207 struct __type_traits<_STLP_PRIV _Rb_tree_iterator<_Value, _Traits> > { 208 typedef __false_type has_trivial_default_constructor; 209 typedef __true_type has_trivial_copy_constructor; 210 typedef __true_type has_trivial_assignment_operator; 211 typedef __true_type has_trivial_destructor; 212 typedef __false_type is_POD_type; 213 }; 214 _STLP_MOVE_TO_PRIV_NAMESPACE 215 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 216 217 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES) 218 _STLP_MOVE_TO_STD_NAMESPACE 219 template <class _Value, class _Traits> 220 inline _Value* value_type(const _STLP_PRIV _Rb_tree_iterator<_Value, _Traits>&) 221 { return (_Value*)0; } 222 inline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _Rb_tree_base_iterator&) 223 { return bidirectional_iterator_tag(); } 224 inline ptrdiff_t* distance_type(const _STLP_PRIV _Rb_tree_base_iterator&) 225 { return (ptrdiff_t*) 0; } 226 _STLP_MOVE_TO_PRIV_NAMESPACE 227 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 228 229 // Base class to help EH 230 231 template <class _Tp, class _Alloc> 232 class _Rb_tree_base { 233 public: 234 typedef _Rb_tree_node_base _Node_base; 235 typedef _Rb_tree_node<_Tp> _Node; 236 _STLP_FORCE_ALLOCATORS(_Tp, _Alloc) 237 typedef _Alloc allocator_type; 238 private: 239 typedef _Rb_tree_base<_Tp, _Alloc> _Self; 240 typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type; 241 typedef _STLP_alloc_proxy<_Node_base, _Node, _M_node_allocator_type> _AllocProxy; 242 243 public: 244 allocator_type get_allocator() const { 245 return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp); 246 } 247 248 protected: 249 _Rb_tree_base(const allocator_type& __a) : 250 _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Node_base() ) { 251 _M_empty_initialize(); 252 } 253 254 #if !defined (_STLP_NO_MOVE_SEMANTIC) 255 _Rb_tree_base(__move_source<_Self> src) : 256 _M_header(__move_source<_AllocProxy>(src.get()._M_header)) { 257 _M_rebind(&src.get()._M_header._M_data); 258 src.get()._M_empty_initialize(); 259 } 260 #endif 261 262 void _M_empty_initialize() { 263 _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from 264 // __root, in iterator.operator++ 265 _M_header._M_data._M_parent = 0; 266 _M_header._M_data._M_left = &_M_header._M_data; 267 _M_header._M_data._M_right = &_M_header._M_data; 268 } 269 270 void _M_rebind(_Node_base *__static_node) { 271 if (_M_header._M_data._M_parent != 0) { 272 _M_header._M_data._M_parent->_M_parent = &_M_header._M_data; 273 } 274 if (_M_header._M_data._M_right == __static_node) { 275 _M_header._M_data._M_right = &_M_header._M_data; 276 } 277 if (_M_header._M_data._M_left == __static_node) { 278 _M_header._M_data._M_left = &_M_header._M_data; 279 } 280 } 281 282 _AllocProxy _M_header; 283 }; 284 285 #if defined (_STLP_DEBUG) 286 # define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree) 287 #endif 288 289 template <class _Key, class _Compare, 290 class _Value, class _KeyOfValue, class _Traits, 291 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 292 class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> { 293 typedef _Rb_tree_base<_Value, _Alloc> _Base; 294 typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self; 295 protected: 296 typedef _Rb_tree_node_base * _Base_ptr; 297 typedef _Rb_tree_node<_Value> _Node; 298 typedef _Node* _Link_type; 299 typedef _Rb_tree_Color_type _Color_type; 300 public: 301 typedef _Key key_type; 302 typedef _Value value_type; 303 typedef typename _Traits::pointer pointer; 304 typedef const value_type* const_pointer; 305 typedef typename _Traits::reference reference; 306 typedef const value_type& const_reference; 307 typedef size_t size_type; 308 typedef ptrdiff_t difference_type; 309 typedef bidirectional_iterator_tag _Iterator_category; 310 typedef typename _Base::allocator_type allocator_type; 311 312 protected: 313 314 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 315 _Base_ptr _M_create_node(const value_type& __x) { 316 _Link_type __tmp = this->_M_header.allocate(1); 317 _STLP_TRY { 318 _Copy_Construct(&__tmp->_M_value_field, __x); 319 } 320 _STLP_UNWIND(this->_M_header.deallocate(__tmp,1)) 321 _S_left(__tmp) = 0; 322 _S_right(__tmp) = 0; 323 return __tmp; 324 } 325 326 _Base_ptr _M_clone_node(_Base_ptr __x) { 327 _Base_ptr __tmp = _M_create_node(_S_value(__x)); 328 _S_color(__tmp) = _S_color(__x); 329 return __tmp; 330 } 331 332 size_type _M_node_count; // keeps track of size of tree 333 _Compare _M_key_compare; 334 335 _Base_ptr _M_root() const 336 { return this->_M_header._M_data._M_parent; } 337 _Base_ptr _M_leftmost() const 338 { return this->_M_header._M_data._M_left; } 339 _Base_ptr _M_rightmost() const 340 { return this->_M_header._M_data._M_right; } 341 342 _Base_ptr& _M_root() 343 { return this->_M_header._M_data._M_parent; } 344 _Base_ptr& _M_leftmost() 345 { return this->_M_header._M_data._M_left; } 346 _Base_ptr& _M_rightmost() 347 { return this->_M_header._M_data._M_right; } 348 349 static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x) 350 { return __x->_M_left; } 351 static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x) 352 { return __x->_M_right; } 353 static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x) 354 { return __x->_M_parent; } 355 static value_type& _STLP_CALL _S_value(_Base_ptr __x) 356 { return __STATIC_CAST(_Link_type, __x)->_M_value_field; } 357 static const _Key& _STLP_CALL _S_key(_Base_ptr __x) 358 { return _KeyOfValue()(_S_value(__x));} 359 static _Color_type& _STLP_CALL _S_color(_Base_ptr __x) 360 { return (_Color_type&)(__x->_M_color); } 361 362 static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) 363 { return _Rb_tree_node_base::_S_minimum(__x); } 364 365 static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) 366 { return _Rb_tree_node_base::_S_maximum(__x); } 367 368 public: 369 typedef typename _Traits::_NonConstTraits _NonConstTraits; 370 typedef typename _Traits::_ConstTraits _ConstTraits; 371 typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator; 372 typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator; 373 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; 374 375 private: 376 iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0); 377 _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p); 378 void _M_erase(_Base_ptr __x); 379 380 public: 381 // allocation/deallocation 382 _Rb_tree() 383 : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare()) 384 {} 385 386 _Rb_tree(const _Compare& __comp) 387 : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 388 {} 389 390 _Rb_tree(const _Compare& __comp, const allocator_type& __a) 391 : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp) 392 {} 393 394 _Rb_tree(const _Self& __x) 395 : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()), 396 _M_node_count(0), _M_key_compare(__x._M_key_compare) { 397 if (__x._M_root() != 0) { 398 _S_color(&this->_M_header._M_data) = _S_rb_tree_red; 399 _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data); 400 _M_leftmost() = _S_minimum(_M_root()); 401 _M_rightmost() = _S_maximum(_M_root()); 402 } 403 _M_node_count = __x._M_node_count; 404 } 405 406 #if !defined (_STLP_NO_MOVE_SEMANTIC) 407 _Rb_tree(__move_source<_Self> src) 408 : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())), 409 _M_node_count(src.get()._M_node_count), 410 _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) 411 { src.get()._M_node_count = 0; } 412 #endif 413 414 ~_Rb_tree() { clear(); } 415 _Self& operator=(const _Self& __x); 416 417 public: 418 // accessors: 419 _Compare key_comp() const { return _M_key_compare; } 420 421 iterator begin() { return iterator(_M_leftmost()); } 422 const_iterator begin() const { return const_iterator(_M_leftmost()); } 423 iterator end() { return iterator(&this->_M_header._M_data); } 424 const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); } 425 426 reverse_iterator rbegin() { return reverse_iterator(end()); } 427 const_reverse_iterator rbegin() const 428 { return const_reverse_iterator(end()); } 429 reverse_iterator rend() { return reverse_iterator(begin()); } 430 const_reverse_iterator rend() const 431 { return const_reverse_iterator(begin()); } 432 bool empty() const { return _M_node_count == 0; } 433 size_type size() const { return _M_node_count; } 434 size_type max_size() const { return size_type(-1); } 435 436 void swap(_Self& __t) { 437 if (__t.empty()) { 438 if (this->empty()) return; 439 __t._M_header.swap(this->_M_header); 440 __t._M_rebind(&this->_M_header._M_data); 441 this->_M_empty_initialize(); 442 } 443 else if (this->empty()) { 444 __t.swap(*this); 445 return; 446 } 447 else { 448 this->_M_header.swap(__t._M_header); 449 this->_M_rebind(&__t._M_header._M_data); 450 __t._M_rebind(&this->_M_header._M_data); 451 } 452 _STLP_STD::swap(_M_node_count, __t._M_node_count); 453 _STLP_STD::swap(_M_key_compare, __t._M_key_compare); 454 } 455 456 public: 457 // insert/erase 458 pair<iterator,bool> insert_unique(const value_type& __x); 459 iterator insert_equal(const value_type& __x); 460 461 iterator insert_unique(iterator __pos, const value_type& __x); 462 iterator insert_equal(iterator __pos, const value_type& __x); 463 464 #if defined (_STLP_MEMBER_TEMPLATES) 465 template<class _II> void insert_equal(_II __first, _II __last) { 466 for ( ; __first != __last; ++__first) 467 insert_equal(*__first); 468 } 469 template<class _II> void insert_unique(_II __first, _II __last) { 470 for ( ; __first != __last; ++__first) 471 insert_unique(*__first); 472 } 473 #else 474 void insert_unique(const_iterator __first, const_iterator __last) { 475 for ( ; __first != __last; ++__first) 476 insert_unique(*__first); 477 } 478 void insert_unique(const value_type* __first, const value_type* __last) { 479 for ( ; __first != __last; ++__first) 480 insert_unique(*__first); 481 } 482 void insert_equal(const_iterator __first, const_iterator __last) { 483 for ( ; __first != __last; ++__first) 484 insert_equal(*__first); 485 } 486 void insert_equal(const value_type* __first, const value_type* __last) { 487 for ( ; __first != __last; ++__first) 488 insert_equal(*__first); 489 } 490 #endif 491 492 void erase(iterator __pos) { 493 _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node, 494 this->_M_header._M_data._M_parent, 495 this->_M_header._M_data._M_left, 496 this->_M_header._M_data._M_right); 497 _STLP_STD::_Destroy(&_S_value(__x)); 498 this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1); 499 --_M_node_count; 500 } 501 502 size_type erase(const key_type& __x) { 503 pair<iterator,iterator> __p = equal_range(__x); 504 size_type __n = _STLP_STD::distance(__p.first, __p.second); 505 erase(__p.first, __p.second); 506 return __n; 507 } 508 509 size_type erase_unique(const key_type& __x) { 510 iterator __i = find(__x); 511 if (__i._M_node != &this->_M_header._M_data) { 512 erase(__i); 513 return 1; 514 } 515 return 0; 516 } 517 518 void erase(iterator __first, iterator __last) { 519 if (__first._M_node == this->_M_header._M_data._M_left && // begin() 520 __last._M_node == &this->_M_header._M_data) // end() 521 clear(); 522 else 523 while (__first != __last) erase(__first++); 524 } 525 526 void erase(const key_type* __first, const key_type* __last) { 527 while (__first != __last) erase(*__first++); 528 } 529 530 void clear() { 531 if (_M_node_count != 0) { 532 _M_erase(_M_root()); 533 _M_leftmost() = &this->_M_header._M_data; 534 _M_root() = 0; 535 _M_rightmost() = &this->_M_header._M_data; 536 _M_node_count = 0; 537 } 538 } 539 540 public: 541 // set operations: 542 _STLP_TEMPLATE_FOR_CONT_EXT 543 iterator find(const _KT& __k) { return iterator(_M_find(__k)); } 544 _STLP_TEMPLATE_FOR_CONT_EXT 545 const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); } 546 private: 547 _STLP_TEMPLATE_FOR_CONT_EXT 548 _Base_ptr _M_find(const _KT& __k) const { 549 _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k. 550 _Base_ptr __x = _M_root(); // Current node. 551 552 while (__x != 0) 553 if (!_M_key_compare(_S_key(__x), __k)) 554 __y = __x, __x = _S_left(__x); 555 else 556 __x = _S_right(__x); 557 558 if (__y != &this->_M_header._M_data) { 559 if (_M_key_compare(__k, _S_key(__y))) { 560 __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); 561 } 562 } 563 return __y; 564 } 565 566 _STLP_TEMPLATE_FOR_CONT_EXT 567 _Base_ptr _M_lower_bound(const _KT& __k) const { 568 _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */ 569 _Base_ptr __x = _M_root(); /* Current node. */ 570 571 while (__x != 0) 572 if (!_M_key_compare(_S_key(__x), __k)) 573 __y = __x, __x = _S_left(__x); 574 else 575 __x = _S_right(__x); 576 577 return __y; 578 } 579 580 _STLP_TEMPLATE_FOR_CONT_EXT 581 _Base_ptr _M_upper_bound(const _KT& __k) const { 582 _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */ 583 _Base_ptr __x = _M_root(); /* Current node. */ 584 585 while (__x != 0) 586 if (_M_key_compare(__k, _S_key(__x))) 587 __y = __x, __x = _S_left(__x); 588 else 589 __x = _S_right(__x); 590 591 return __y; 592 } 593 594 public: 595 _STLP_TEMPLATE_FOR_CONT_EXT 596 size_type count(const _KT& __x) const { 597 pair<const_iterator, const_iterator> __p = equal_range(__x); 598 return _STLP_STD::distance(__p.first, __p.second); 599 } 600 _STLP_TEMPLATE_FOR_CONT_EXT 601 iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); } 602 _STLP_TEMPLATE_FOR_CONT_EXT 603 const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); } 604 _STLP_TEMPLATE_FOR_CONT_EXT 605 iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); } 606 _STLP_TEMPLATE_FOR_CONT_EXT 607 const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); } 608 _STLP_TEMPLATE_FOR_CONT_EXT 609 pair<iterator,iterator> equal_range(const _KT& __x) 610 { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); } 611 _STLP_TEMPLATE_FOR_CONT_EXT 612 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const 613 { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); } 614 _STLP_TEMPLATE_FOR_CONT_EXT 615 pair<iterator,iterator> equal_range_unique(const _KT& __x) { 616 pair<iterator, iterator> __p; 617 __p.second = lower_bound(__x); 618 if (__p.second._M_node != &this->_M_header._M_data && 619 !_M_key_compare(__x, _S_key(__p.second._M_node))) { 620 __p.first = __p.second++; 621 } 622 else { 623 __p.first = __p.second; 624 } 625 return __p; 626 } 627 _STLP_TEMPLATE_FOR_CONT_EXT 628 pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const { 629 pair<const_iterator, const_iterator> __p; 630 __p.second = lower_bound(__x); 631 if (__p.second._M_node != &this->_M_header._M_data && 632 !_M_key_compare(__x, _S_key(__p.second._M_node))) { 633 __p.first = __p.second++; 634 } 635 else { 636 __p.first = __p.second; 637 } 638 return __p; 639 } 640 641 #if defined (_STLP_DEBUG) 642 public: 643 // Debugging. 644 bool __rb_verify() const; 645 #endif //_STLP_DEBUG 646 }; 647 648 #if defined (_STLP_DEBUG) 649 # undef _Rb_tree 650 #endif 651 652 _STLP_MOVE_TO_STD_NAMESPACE 653 654 _STLP_END_NAMESPACE 655 656 #if !defined (_STLP_LINK_TIME_INSTANTIATION) 657 # include <stl/_tree.c> 658 #endif 659 660 #if defined (_STLP_DEBUG) 661 # include <stl/debug/_tree.h> 662 #endif 663 664 _STLP_BEGIN_NAMESPACE 665 666 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc> 667 #define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> 668 #include <stl/_relops_cont.h> 669 #undef _STLP_TEMPLATE_CONTAINER 670 #undef _STLP_TEMPLATE_HEADER 671 672 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 673 template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc> 674 struct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> > 675 : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {}; 676 #endif 677 678 _STLP_END_NAMESPACE 679 680 #endif /* _STLP_INTERNAL_TREE_H */ 681 682 // Local Variables: 683 // mode:C++ 684 // End: 685
