lib/3rdparty/stlport/stlport/stl/_tree.h

   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: