include/c++/stl/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 typename _Alloc_traits<_Tp, _Alloc>::allocator_type 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   _Rb_tree_base(__move_source<_Self> src) :
 254     _M_header(__move_source<_AllocProxy>(src.get()._M_header)) {
 255     _M_rebind(&src.get()._M_header._M_data);
 256     src.get()._M_empty_initialize();
 257   }
 258   void _M_empty_initialize() {
 259     _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from
 260                                                  // __root, in iterator.operator++
 261     _M_header._M_data._M_parent = 0;
 262     _M_header._M_data._M_left = &_M_header._M_data;
 263     _M_header._M_data._M_right = &_M_header._M_data;
 264   }
 265
 266   void _M_rebind(_Node_base *__static_node) {
 267     if (_M_header._M_data._M_parent != 0) {
 268       _M_header._M_data._M_parent->_M_parent = &_M_header._M_data;
 269     }
 270     if (_M_header._M_data._M_right == __static_node) {
 271       _M_header._M_data._M_right = &_M_header._M_data;
 272     }
 273     if (_M_header._M_data._M_left == __static_node) {
 274       _M_header._M_data._M_left = &_M_header._M_data;
 275     }
 276   }
 277
 278   _AllocProxy _M_header;
 279 };
 280
 281 #if defined (_STLP_DEBUG)
 282 #  define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
 283 #endif
 284
 285 template <class _Key, class _Compare,
 286           class _Value, class _KeyOfValue, class _Traits,
 287           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
 288 class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
 289   typedef _Rb_tree_base<_Value, _Alloc> _Base;
 290   typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self;
 291 protected:
 292   typedef _Rb_tree_node_base * _Base_ptr;
 293   typedef _Rb_tree_node<_Value> _Node;
 294   typedef _Node* _Link_type;
 295   typedef _Rb_tree_Color_type _Color_type;
 296 public:
 297   typedef _Key key_type;
 298   typedef _Value value_type;
 299   typedef typename _Traits::pointer pointer;
 300   typedef const value_type* const_pointer;
 301   typedef typename _Traits::reference reference;
 302   typedef const value_type& const_reference;
 303   typedef size_t size_type;
 304   typedef ptrdiff_t difference_type;
 305   typedef bidirectional_iterator_tag _Iterator_category;
 306   typedef typename _Base::allocator_type allocator_type;
 307
 308 protected:
 309
 310   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 311   _Base_ptr _M_create_node(const value_type& __x) {
 312     _Link_type __tmp = this->_M_header.allocate(1);
 313     _STLP_TRY {
 314       _Copy_Construct(&__tmp->_M_value_field, __x);
 315     }
 316     _STLP_UNWIND(this->_M_header.deallocate(__tmp,1))
 317     _S_left(__tmp) = 0;
 318     _S_right(__tmp) = 0;
 319     return __tmp;
 320   }
 321
 322   _Base_ptr _M_clone_node(_Base_ptr __x) {
 323     _Base_ptr __tmp = _M_create_node(_S_value(__x));
 324     _S_color(__tmp) = _S_color(__x);
 325     return __tmp;
 326   }
 327
 328   size_type _M_node_count; // keeps track of size of tree
 329   _Compare _M_key_compare;
 330
 331   _Base_ptr _M_root() const
 332   { return this->_M_header._M_data._M_parent; }
 333   _Base_ptr _M_leftmost() const
 334   { return this->_M_header._M_data._M_left; }
 335   _Base_ptr _M_rightmost() const
 336   { return this->_M_header._M_data._M_right; }
 337
 338   _Base_ptr& _M_root()
 339   { return this->_M_header._M_data._M_parent; }
 340   _Base_ptr& _M_leftmost()
 341   { return this->_M_header._M_data._M_left; }
 342   _Base_ptr& _M_rightmost()
 343   { return this->_M_header._M_data._M_right; }
 344
 345   static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x)
 346   { return __x->_M_left; }
 347   static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x)
 348   { return __x->_M_right; }
 349   static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x)
 350   { return __x->_M_parent; }
 351   static value_type& _STLP_CALL _S_value(_Base_ptr __x)
 352   { return __STATIC_CAST(_Link_type, __x)->_M_value_field; }
 353   static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
 354   { return _KeyOfValue()(_S_value(__x));}
 355   static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
 356   { return (_Color_type&)(__x->_M_color); }
 357
 358   static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
 359   { return _Rb_tree_node_base::_S_minimum(__x); }
 360
 361   static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
 362   { return _Rb_tree_node_base::_S_maximum(__x); }
 363
 364 public:
 365   typedef typename _Traits::_NonConstTraits _NonConstTraits;
 366   typedef typename _Traits::_ConstTraits _ConstTraits;
 367   typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator;
 368   typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator;
 369   _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
 370
 371 private:
 372   iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0);
 373   _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p);
 374   void _M_erase(_Base_ptr __x);
 375
 376 public:
 377                                 // allocation/deallocation
 378   _Rb_tree()
 379     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
 380     {}
 381
 382   _Rb_tree(const _Compare& __comp)
 383     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
 384     {}
 385
 386   _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 387     : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp)
 388     {}
 389
 390   _Rb_tree(const _Self& __x)
 391     : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
 392       _M_node_count(0), _M_key_compare(__x._M_key_compare) {
 393     if (__x._M_root() != 0) {
 394       _S_color(&this->_M_header._M_data) = _S_rb_tree_red;
 395       _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
 396       _M_leftmost() = _S_minimum(_M_root());
 397       _M_rightmost() = _S_maximum(_M_root());
 398     }
 399     _M_node_count = __x._M_node_count;
 400   }
 401
 402   _Rb_tree(__move_source<_Self> src)
 403     : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())),
 404       _M_node_count(src.get()._M_node_count),
 405       _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) {
 406     src.get()._M_node_count = 0;
 407   }
 408
 409   ~_Rb_tree() { clear(); }
 410   _Self& operator=(const _Self& __x);
 411
 412 public:
 413                                 // accessors:
 414   _Compare key_comp() const { return _M_key_compare; }
 415
 416   iterator begin() { return iterator(_M_leftmost()); }
 417   const_iterator begin() const { return const_iterator(_M_leftmost()); }
 418   iterator end() { return iterator(&this->_M_header._M_data); }
 419   const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); }
 420
 421   reverse_iterator rbegin() { return reverse_iterator(end()); }
 422   const_reverse_iterator rbegin() const
 423   { return const_reverse_iterator(end()); }
 424   reverse_iterator rend() { return reverse_iterator(begin()); }
 425   const_reverse_iterator rend() const
 426   { return const_reverse_iterator(begin()); }
 427   bool empty() const { return _M_node_count == 0; }
 428   size_type size() const { return _M_node_count; }
 429   size_type max_size() const { return size_type(-1); }
 430
 431   void swap(_Self& __t) {
 432     if (__t.empty()) {
 433       if (this->empty()) return;
 434       __t._M_header.swap(this->_M_header);
 435       __t._M_rebind(&this->_M_header._M_data);
 436       this->_M_empty_initialize();
 437     }
 438     else if (this->empty()) {
 439       __t.swap(*this);
 440       return;
 441     }
 442     else {
 443       this->_M_header.swap(__t._M_header);
 444       this->_M_rebind(&__t._M_header._M_data);
 445       __t._M_rebind(&this->_M_header._M_data);
 446     }
 447     _STLP_STD::swap(_M_node_count, __t._M_node_count);
 448     _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
 449   }
 450
 451 public:
 452                                 // insert/erase
 453   pair<iterator,bool> insert_unique(const value_type& __x);
 454   iterator insert_equal(const value_type& __x);
 455
 456   iterator insert_unique(iterator __pos, const value_type& __x);
 457   iterator insert_equal(iterator __pos, const value_type& __x);
 458
 459 #if defined (_STLP_MEMBER_TEMPLATES)
 460   template<class _II> void insert_equal(_II __first, _II __last) {
 461     for ( ; __first != __last; ++__first)
 462       insert_equal(*__first);
 463   }
 464   template<class _II> void insert_unique(_II __first, _II __last) {
 465     for ( ; __first != __last; ++__first)
 466       insert_unique(*__first);
 467   }
 468 #else
 469   void insert_unique(const_iterator __first, const_iterator __last) {
 470     for ( ; __first != __last; ++__first)
 471       insert_unique(*__first);
 472   }
 473   void insert_unique(const value_type* __first, const value_type* __last) {
 474     for ( ; __first != __last; ++__first)
 475       insert_unique(*__first);
 476   }
 477   void insert_equal(const_iterator __first, const_iterator __last) {
 478     for ( ; __first != __last; ++__first)
 479       insert_equal(*__first);
 480   }
 481   void insert_equal(const value_type* __first, const value_type* __last) {
 482     for ( ; __first != __last; ++__first)
 483       insert_equal(*__first);
 484   }
 485 #endif
 486
 487   void erase(iterator __pos) {
 488     _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node,
 489                                                           this->_M_header._M_data._M_parent,
 490                                                           this->_M_header._M_data._M_left,
 491                                                           this->_M_header._M_data._M_right);
 492     _STLP_STD::_Destroy(&_S_value(__x));
 493     this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
 494     --_M_node_count;
 495   }
 496
 497   size_type erase(const key_type& __x) {
 498     pair<iterator,iterator> __p = equal_range(__x);
 499     size_type __n = distance(__p.first, __p.second);
 500     erase(__p.first, __p.second);
 501     return __n;
 502   }
 503
 504   size_type erase_unique(const key_type& __x) {
 505     iterator __i = find(__x);
 506     if (__i._M_node != &this->_M_header._M_data) {
 507       erase(__i);
 508       return 1;
 509     }
 510     return 0;
 511   }
 512
 513   void erase(iterator __first, iterator __last) {
 514     if (__first._M_node == this->_M_header._M_data._M_left && // begin()
 515         __last._M_node == &this->_M_header._M_data)           // end()
 516       clear();
 517     else
 518       while (__first != __last) erase(__first++);
 519   }
 520
 521   void erase(const key_type* __first, const key_type* __last) {
 522     while (__first != __last) erase(*__first++);
 523   }
 524
 525   void clear() {
 526     if (_M_node_count != 0) {
 527       _M_erase(_M_root());
 528       _M_leftmost() = &this->_M_header._M_data;
 529       _M_root() = 0;
 530       _M_rightmost() = &this->_M_header._M_data;
 531       _M_node_count = 0;
 532     }
 533   }
 534
 535 public:
 536                                 // set operations:
 537   _STLP_TEMPLATE_FOR_CONT_EXT
 538   iterator find(const _KT& __k) { return iterator(_M_find(__k)); }
 539   _STLP_TEMPLATE_FOR_CONT_EXT
 540   const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); }
 541 private:
 542   _STLP_TEMPLATE_FOR_CONT_EXT
 543   _Base_ptr _M_find(const _KT& __k) const {
 544     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);      // Last node which is not less than __k.
 545     _Base_ptr __x = _M_root();      // Current node.
 546
 547     while (__x != 0)
 548       if (!_M_key_compare(_S_key(__x), __k))
 549         __y = __x, __x = _S_left(__x);
 550       else
 551         __x = _S_right(__x);
 552
 553     if (__y != &this->_M_header._M_data) {
 554       if (_M_key_compare(__k, _S_key(__y))) {
 555         __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
 556       }
 557     }
 558     return __y;
 559   }
 560
 561   _STLP_TEMPLATE_FOR_CONT_EXT
 562   _Base_ptr _M_lower_bound(const _KT& __k) const {
 563     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
 564     _Base_ptr __x = _M_root(); /* Current node. */
 565
 566     while (__x != 0)
 567       if (!_M_key_compare(_S_key(__x), __k))
 568         __y = __x, __x = _S_left(__x);
 569       else
 570         __x = _S_right(__x);
 571
 572     return __y;
 573   }
 574
 575   _STLP_TEMPLATE_FOR_CONT_EXT
 576   _Base_ptr _M_upper_bound(const _KT& __k) const {
 577     _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
 578     _Base_ptr __x = _M_root(); /* Current node. */
 579
 580     while (__x != 0)
 581       if (_M_key_compare(__k, _S_key(__x)))
 582         __y = __x, __x = _S_left(__x);
 583       else
 584         __x = _S_right(__x);
 585
 586     return __y;
 587   }
 588
 589 public:
 590   _STLP_TEMPLATE_FOR_CONT_EXT
 591   size_type count(const _KT& __x) const {
 592     pair<const_iterator, const_iterator> __p = equal_range(__x);
 593     return distance(__p.first, __p.second);
 594   }
 595   _STLP_TEMPLATE_FOR_CONT_EXT
 596   iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); }
 597   _STLP_TEMPLATE_FOR_CONT_EXT
 598   const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); }
 599   _STLP_TEMPLATE_FOR_CONT_EXT
 600   iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); }
 601   _STLP_TEMPLATE_FOR_CONT_EXT
 602   const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); }
 603   _STLP_TEMPLATE_FOR_CONT_EXT
 604   pair<iterator,iterator> equal_range(const _KT& __x)
 605   { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); }
 606   _STLP_TEMPLATE_FOR_CONT_EXT
 607   pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
 608   { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); }
 609   _STLP_TEMPLATE_FOR_CONT_EXT
 610   pair<iterator,iterator> equal_range_unique(const _KT& __x) {
 611     pair<iterator, iterator> __p;
 612     __p.second = lower_bound(__x);
 613     if (__p.second._M_node != &this->_M_header._M_data &&
 614         !_M_key_compare(__x, _S_key(__p.second._M_node))) {
 615       __p.first = __p.second++;
 616     }
 617     else {
 618       __p.first = __p.second;
 619     }
 620     return __p;
 621   }
 622   _STLP_TEMPLATE_FOR_CONT_EXT
 623   pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const {
 624     pair<const_iterator, const_iterator> __p;
 625     __p.second = lower_bound(__x);
 626     if (__p.second._M_node != &this->_M_header._M_data &&
 627         !_M_key_compare(__x, _S_key(__p.second._M_node))) {
 628       __p.first = __p.second++;
 629     }
 630     else {
 631       __p.first = __p.second;
 632     }
 633     return __p;
 634   }
 635
 636 #if defined (_STLP_DEBUG)
 637 public:
 638   // Debugging.
 639   bool __rb_verify() const;
 640 #endif //_STLP_DEBUG
 641 };
 642
 643 #if defined (_STLP_DEBUG)
 644 #  undef _Rb_tree
 645 #endif
 646
 647 _STLP_MOVE_TO_STD_NAMESPACE
 648
 649 _STLP_END_NAMESPACE
 650
 651 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
 652 #  include <stl/_tree.c>
 653 #endif
 654
 655 #if defined (_STLP_DEBUG)
 656 #  include <stl/debug/_tree.h>
 657 #endif
 658
 659 _STLP_BEGIN_NAMESPACE
 660
 661 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
 662 #define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>
 663 #include <stl/_relops_cont.h>
 664 #undef _STLP_TEMPLATE_CONTAINER
 665 #undef _STLP_TEMPLATE_HEADER
 666
 667 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 668 template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
 669 struct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> >
 670   : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {};
 671 #endif
 672
 673 _STLP_END_NAMESPACE
 674
 675 #endif /* _STLP_INTERNAL_TREE_H */
 676
 677 // Local Variables:
 678 // mode:C++
 679 // End: