home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _tree.h < prev    next >
C/C++ Source or Header  |  2002-02-02  |  22KB  |  623 lines
  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_H
  70. #  include <stl/_function_base.h> 
  71. # endif
  72.  
  73. #if defined ( _STLP_DEBUG)
  74. #  define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree)
  75. #endif
  76.  
  77. _STLP_BEGIN_NAMESPACE
  78.  
  79. typedef bool _Rb_tree_Color_type;
  80. //const _Rb_tree_Color_type _S_rb_tree_red = false;
  81. //const _Rb_tree_Color_type _S_rb_tree_black = true;
  82.  
  83. #define _S_rb_tree_red false
  84. #define _S_rb_tree_black true
  85.  
  86. struct _Rb_tree_node_base
  87. {
  88.   typedef _Rb_tree_Color_type _Color_type;
  89.   typedef _Rb_tree_node_base* _Base_ptr;
  90.  
  91.   _Color_type _M_color; 
  92.   _Base_ptr _M_parent;
  93.   _Base_ptr _M_left;
  94.   _Base_ptr _M_right;
  95.  
  96.   static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
  97.   {
  98.     while (__x->_M_left != 0) __x = __x->_M_left;
  99.     return __x;
  100.   }
  101.  
  102.   static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
  103.   {
  104.     while (__x->_M_right != 0) __x = __x->_M_right;
  105.     return __x;
  106.   }
  107. };
  108.  
  109. template <class _Value> struct _Rb_tree_node : public _Rb_tree_node_base
  110. {
  111.   _Value _M_value_field;
  112.   __TRIVIAL_STUFF(_Rb_tree_node)
  113. };
  114.  
  115. struct _Rb_tree_base_iterator;
  116.  
  117. template <class _Dummy> class _Rb_global {
  118. public:
  119.   typedef _Rb_tree_node_base* _Base_ptr;
  120.   // those used to be global functions 
  121.   static void _STLP_CALL _Rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
  122.   static _Rb_tree_node_base* _STLP_CALL _Rebalance_for_erase(_Rb_tree_node_base* __z,
  123.                                                              _Rb_tree_node_base*& __root,
  124.                                                              _Rb_tree_node_base*& __leftmost,
  125.                                                              _Rb_tree_node_base*& __rightmost);
  126.   // those are from _Rb_tree_base_iterator - moved here to reduce code bloat
  127.   // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator
  128.   static _Rb_tree_node_base*  _STLP_CALL _M_increment(_Rb_tree_node_base*);
  129.   static _Rb_tree_node_base*  _STLP_CALL _M_decrement(_Rb_tree_node_base*);
  130.   static void _STLP_CALL _Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
  131.   static void _STLP_CALL _Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root); 
  132. };
  133.  
  134. # if defined (_STLP_USE_TEMPLATE_EXPORT) 
  135. _STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>;
  136. # endif
  137.  
  138. typedef _Rb_global<bool> _Rb_global_inst;
  139.  
  140. struct _Rb_tree_base_iterator
  141. {
  142.   typedef _Rb_tree_node_base*        _Base_ptr;
  143.   typedef bidirectional_iterator_tag iterator_category;
  144.   typedef ptrdiff_t                  difference_type;
  145.   _Base_ptr _M_node;
  146.   bool operator==(const _Rb_tree_base_iterator& __y) const {
  147.     return _M_node == __y._M_node;
  148.   }
  149.   bool operator!=(const _Rb_tree_base_iterator& __y) const {
  150.     return _M_node != __y._M_node;
  151.   }
  152. };
  153.  
  154.  
  155. template <class _Value, class _Traits> struct _Rb_tree_iterator : public _Rb_tree_base_iterator
  156. {
  157.   typedef _Value value_type;
  158.   typedef typename _Traits::reference  reference;
  159.   typedef typename _Traits::pointer    pointer;
  160.   typedef _Rb_tree_iterator<_Value, _Traits> _Self;
  161.   typedef _Rb_tree_node<_Value>* _Link_type;
  162.  
  163.   _Rb_tree_iterator() { _M_node = 0; }
  164.   _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
  165.   _Rb_tree_iterator(const _Rb_tree_iterator<_Value, 
  166.                     _Nonconst_traits<_Value> >& __it) { _M_node = __it._M_node; }
  167.  
  168.   reference operator*() const { 
  169.     return _Link_type(_M_node)->_M_value_field; 
  170.   }
  171.   
  172.   _STLP_DEFINE_ARROW_OPERATOR
  173.  
  174.   _Self& operator++() { _M_node = _Rb_global_inst::_M_increment(_M_node); return *this; }
  175.   _Self operator++(int) {
  176.     _Self __tmp = *this;
  177.     _M_node = _Rb_global_inst::_M_increment(_M_node);
  178.     return __tmp;
  179.   }
  180.     
  181.   _Self& operator--() { _M_node = _Rb_global_inst::_M_decrement(_M_node); return *this; }
  182.   _Self operator--(int) {
  183.     _Self __tmp = *this;
  184.     _M_node = _Rb_global_inst::_M_decrement(_M_node);
  185.     return __tmp;
  186.   }
  187. };
  188.  
  189. # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
  190. template <class _Value, class _Traits> inline _Value* value_type(const _Rb_tree_iterator<_Value, _Traits>&) { return (_Value*)0; }
  191. inline bidirectional_iterator_tag iterator_category(const _Rb_tree_base_iterator&) { return bidirectional_iterator_tag(); }
  192. inline ptrdiff_t* distance_type(const _Rb_tree_base_iterator&) { return (ptrdiff_t*) 0; }
  193. #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
  194.  
  195. // Base class to help EH
  196.  
  197. template <class _Tp, class _Alloc> struct _Rb_tree_base
  198. {
  199.   typedef _Rb_tree_node<_Tp> _Node;
  200.   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  201.   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  202.  
  203.   _Rb_tree_base(const allocator_type& __a) : 
  204.     _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), (_Node*)0) { 
  205.       _M_header._M_data = _M_header.allocate(1); 
  206.   }
  207.   ~_Rb_tree_base() { 
  208.     _M_header.deallocate(_M_header._M_data,1); 
  209.   }
  210.   allocator_type get_allocator() const { 
  211.     return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp); 
  212.   }
  213. protected:
  214.   typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type;
  215.   _STLP_alloc_proxy<_Node*, _Node, _M_node_allocator_type> _M_header;
  216. };
  217.  
  218.  
  219. template <class _Key, class _Value, class _KeyOfValue, class _Compare,
  220.           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
  221.   typedef _Rb_tree_base<_Value, _Alloc> _Base;
  222. protected:
  223.   typedef _Rb_tree_node_base* _Base_ptr;
  224.   typedef _Rb_tree_node<_Value> _Node;
  225.   typedef _Rb_tree_Color_type _Color_type;
  226. public:
  227.   typedef _Key key_type;
  228.   typedef _Value value_type;
  229.   typedef value_type* pointer;
  230.   typedef const value_type* const_pointer;
  231.   typedef value_type& reference;
  232.   typedef const value_type& const_reference;
  233.   typedef _Rb_tree_node<_Value>* _Link_type;
  234.   typedef size_t size_type;
  235.   typedef ptrdiff_t difference_type;
  236.   typedef bidirectional_iterator_tag _Iterator_category;
  237.   typedef typename _Base::allocator_type allocator_type;
  238.   
  239. protected:
  240.  
  241.   _Link_type _M_create_node(const value_type& __x)
  242.   {
  243.     _Link_type __tmp = this->_M_header.allocate(1);
  244.     _STLP_TRY {
  245.       _Construct(&__tmp->_M_value_field, __x);
  246.     }
  247.     _STLP_UNWIND(this->_M_header.deallocate(__tmp,1));
  248.     return __tmp;
  249.   }
  250.  
  251.   _Link_type _M_clone_node(_Link_type __x)
  252.   {
  253.     _Link_type __tmp = _M_create_node(__x->_M_value_field);
  254.     __tmp->_M_color = __x->_M_color;
  255.     __tmp->_M_left = 0;
  256.     __tmp->_M_right = 0;
  257.     return __tmp;
  258.   }
  259.  
  260. protected:
  261.   size_type _M_node_count; // keeps track of size of tree
  262.   _Compare _M_key_compare;
  263.  
  264.   _Link_type& _M_root() const 
  265.     { return (_Link_type&) this->_M_header._M_data->_M_parent; }
  266.   _Link_type& _M_leftmost() const 
  267.     { return (_Link_type&) this->_M_header._M_data->_M_left; }
  268.   _Link_type& _M_rightmost() const 
  269.     { return (_Link_type&) this->_M_header._M_data->_M_right; }
  270.  
  271.   static _Link_type& _STLP_CALL _S_left(_Link_type __x)
  272.     { return (_Link_type&)(__x->_M_left); }
  273.   static _Link_type& _STLP_CALL _S_right(_Link_type __x)
  274.     { return (_Link_type&)(__x->_M_right); }
  275.   static _Link_type& _STLP_CALL _S_parent(_Link_type __x)
  276.     { return (_Link_type&)(__x->_M_parent); }
  277.   static reference  _STLP_CALL _S_value(_Link_type __x)
  278.     { return __x->_M_value_field; }
  279.   static const _Key& _STLP_CALL _S_key(_Link_type __x)
  280.     { return _KeyOfValue()(_S_value(__x)); }
  281.   static _Color_type& _STLP_CALL _S_color(_Link_type __x)
  282.     { return (_Color_type&)(__x->_M_color); }
  283.  
  284.   static _Link_type& _STLP_CALL _S_left(_Base_ptr __x)
  285.     { return (_Link_type&)(__x->_M_left); }
  286.   static _Link_type& _STLP_CALL _S_right(_Base_ptr __x)
  287.     { return (_Link_type&)(__x->_M_right); }
  288.   static _Link_type& _STLP_CALL _S_parent(_Base_ptr __x)
  289.     { return (_Link_type&)(__x->_M_parent); }
  290.   static reference  _STLP_CALL _S_value(_Base_ptr __x)
  291.     { return ((_Link_type)__x)->_M_value_field; }
  292.   static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
  293.     { return _KeyOfValue()(_S_value(_Link_type(__x)));} 
  294.   static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
  295.     { return (_Color_type&)(_Link_type(__x)->_M_color); }
  296.  
  297.   static _Link_type  _STLP_CALL _S_minimum(_Link_type __x) 
  298.     { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
  299.  
  300.   static _Link_type  _STLP_CALL _S_maximum(_Link_type __x)
  301.     { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
  302.  
  303. public:
  304.   typedef _Rb_tree_iterator<value_type, _Nonconst_traits<value_type> > iterator;
  305.   typedef _Rb_tree_iterator<value_type, _Const_traits<value_type> > const_iterator;
  306.   _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
  307.  
  308. private:
  309.   iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v, _Base_ptr __w = 0);
  310.   _Link_type _M_copy(_Link_type __x, _Link_type __p);
  311.   void _M_erase(_Link_type __x);
  312.  
  313. public:
  314.                                 // allocation/deallocation
  315.   _Rb_tree()
  316.     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
  317.     { _M_empty_initialize(); }
  318.  
  319.   _Rb_tree(const _Compare& __comp)
  320.     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 
  321.     { _M_empty_initialize(); }
  322.  
  323.   _Rb_tree(const _Compare& __comp, const allocator_type& __a)
  324.     : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp) 
  325.     { _M_empty_initialize(); }
  326.  
  327.   _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) 
  328.     : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
  329.       _M_node_count(0), _M_key_compare(__x._M_key_compare)
  330.   { 
  331.     if (__x._M_root() == 0)
  332.       _M_empty_initialize();
  333.     else {
  334.       _S_color(this->_M_header._M_data) = _S_rb_tree_red;
  335.       _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);
  336.       _M_leftmost() = _S_minimum(_M_root());
  337.       _M_rightmost() = _S_maximum(_M_root());
  338.     }
  339.     _M_node_count = __x._M_node_count;
  340.   }
  341.   ~_Rb_tree() { clear(); }
  342.   _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);
  343.  
  344. private:
  345.   void _M_empty_initialize() {
  346.     _S_color(this->_M_header._M_data) = _S_rb_tree_red; // used to distinguish header from 
  347.                                           // __root, in iterator.operator++
  348.     _M_root() = 0;
  349.     _M_leftmost() = this->_M_header._M_data;
  350.     _M_rightmost() = this->_M_header._M_data;
  351.   }
  352.  
  353. public:    
  354.                                 // accessors:
  355.   _Compare key_comp() const { return _M_key_compare; }
  356.  
  357.   iterator begin() { return iterator(_M_leftmost()); }
  358.   const_iterator begin() const { return const_iterator(_M_leftmost()); }
  359.   iterator end() { return iterator(this->_M_header._M_data); }
  360.   const_iterator end() const { return const_iterator(this->_M_header._M_data); }
  361.  
  362.   reverse_iterator rbegin() { return reverse_iterator(end()); }
  363.   const_reverse_iterator rbegin() const { 
  364.     return const_reverse_iterator(end()); 
  365.   }
  366.   reverse_iterator rend() { return reverse_iterator(begin()); }
  367.   const_reverse_iterator rend() const { 
  368.     return const_reverse_iterator(begin());
  369.   } 
  370.   bool empty() const { return _M_node_count == 0; }
  371.   size_type size() const { return _M_node_count; }
  372.   size_type max_size() const { return size_type(-1); }
  373.  
  374.   void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
  375.     _STLP_STD::swap(this->_M_header, __t._M_header);
  376.     _STLP_STD::swap(_M_node_count, __t._M_node_count);
  377.     _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
  378.   }
  379.     
  380. public:
  381.                                 // insert/erase
  382.   pair<iterator,bool> insert_unique(const value_type& __x);
  383.   iterator insert_equal(const value_type& __x);
  384.  
  385.   iterator insert_unique(iterator __position, const value_type& __x);
  386.   iterator insert_equal(iterator __position, const value_type& __x);
  387.  
  388. #ifdef _STLP_MEMBER_TEMPLATES  
  389.   template<class _II> void insert_equal(_II __first, _II __last) {
  390.     for ( ; __first != __last; ++__first)
  391.       insert_equal(*__first);
  392.   }
  393.   template<class _II> void insert_unique(_II __first, _II __last) {
  394.     for ( ; __first != __last; ++__first)
  395.       insert_unique(*__first);
  396.   }
  397. #else /* _STLP_MEMBER_TEMPLATES */
  398.   void insert_unique(const_iterator __first, const_iterator __last) {
  399.     for ( ; __first != __last; ++__first)
  400.       insert_unique(*__first);
  401.   }
  402.   void insert_unique(const value_type* __first, const value_type* __last) {
  403.     for ( ; __first != __last; ++__first)
  404.       insert_unique(*__first);
  405.   }
  406.   void insert_equal(const_iterator __first, const_iterator __last) {
  407.     for ( ; __first != __last; ++__first)
  408.       insert_equal(*__first);
  409.   }
  410.   void insert_equal(const value_type* __first, const value_type* __last) {
  411.     for ( ; __first != __last; ++__first)
  412.       insert_equal(*__first);
  413.   }
  414. #endif /* _STLP_MEMBER_TEMPLATES */
  415.  
  416.   void erase(iterator __position) {
  417.     _Link_type __y = 
  418.       (_Link_type) _Rb_global_inst::_Rebalance_for_erase(__position._M_node,
  419.                              this->_M_header._M_data->_M_parent,
  420.                              this->_M_header._M_data->_M_left,
  421.                              this->_M_header._M_data->_M_right);
  422.     _Destroy(&__y->_M_value_field);
  423.     this->_M_header.deallocate(__y,1);
  424.     --_M_node_count;
  425.   }
  426.   
  427.   size_type erase(const key_type& __x) {
  428.     pair<iterator,iterator> __p = equal_range(__x);
  429.     size_type __n = distance(__p.first, __p.second);
  430.     erase(__p.first, __p.second);
  431.     return __n;
  432.   }
  433.   
  434.   void erase(iterator __first, iterator __last) {
  435.     if (__first == begin() && __last == end())
  436.       clear();
  437.     else
  438.       while (__first != __last) erase(__first++);
  439.   }
  440.  
  441.   void erase(const key_type* __first, const key_type* __last) {
  442.     while (__first != __last) erase(*__first++);
  443.   }
  444.  
  445.   void clear() {
  446.     if (_M_node_count != 0) {
  447.       _M_erase(_M_root());
  448.       _M_leftmost() = this->_M_header._M_data;
  449.       _M_root() = 0;
  450.       _M_rightmost() = this->_M_header._M_data;
  451.       _M_node_count = 0;
  452.     }
  453.   }      
  454.  
  455. public:
  456.                                 // set operations:
  457. # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !defined(__MRC__) && !defined(__SC__)
  458.   template <class _KT> iterator find(const _KT& __x) { return iterator(_M_find(__x)); }
  459.   template <class _KT> const_iterator find(const _KT& __x) const { return const_iterator(_M_find(__x)); }
  460. private:
  461.   template <class _KT> _Rb_tree_node<_Value>* _M_find(const _KT& __k) const
  462. # else
  463.   iterator find(const key_type& __x) { return iterator(_M_find(__x)); }
  464.   const_iterator find(const key_type& __x) const { return const_iterator(_M_find(__x)); }
  465. private:
  466.   _Rb_tree_node<_Value>* _M_find(const key_type& __k) const
  467. # endif
  468.   {
  469.     _Link_type __y = this->_M_header._M_data;      // Last node which is not less than __k. 
  470.     _Link_type __x = _M_root();      // Current node. 
  471.     
  472.     while (__x != 0) 
  473.       if (!_M_key_compare(_S_key(__x), __k))
  474.     __y = __x, __x = _S_left(__x);
  475.       else
  476.     __x = _S_right(__x);
  477.     if (__y == this->_M_header._M_data || _M_key_compare(__k, _S_key(__y)))
  478.       __y = this->_M_header._M_data;
  479.     return __y;
  480.   }
  481.   
  482.   _Link_type _M_lower_bound(const key_type& __k) const {
  483.     _Link_type __y = this->_M_header._M_data; /* Last node which is not less than __k. */
  484.     _Link_type __x = _M_root(); /* Current node. */
  485.     
  486.     while (__x != 0) 
  487.       if (!_M_key_compare(_S_key(__x), __k))
  488.     __y = __x, __x = _S_left(__x);
  489.       else
  490.     __x = _S_right(__x);
  491.     
  492.     return __y;
  493.   }
  494.  
  495.   _Link_type _M_upper_bound(const key_type& __k) const {
  496.     _Link_type __y = this->_M_header._M_data; /* Last node which is greater than __k. */
  497.     _Link_type __x = _M_root(); /* Current node. */
  498.     
  499.     while (__x != 0) 
  500.       if (_M_key_compare(__k, _S_key(__x)))
  501.     __y = __x, __x = _S_left(__x);
  502.       else
  503.     __x = _S_right(__x);
  504.     
  505.     return __y;
  506.   }
  507.   
  508. public:  
  509.   size_type count(const key_type& __x) const;
  510.   iterator lower_bound(const key_type& __x) { return iterator(_M_lower_bound(__x)); }
  511.   const_iterator lower_bound(const key_type& __x) const { return const_iterator(_M_lower_bound(__x)); }
  512.   iterator upper_bound(const key_type& __x) { return iterator(_M_upper_bound(__x)); }
  513.   const_iterator upper_bound(const key_type& __x) const { return const_iterator(_M_upper_bound(__x)); }
  514.   pair<iterator,iterator> equal_range(const key_type& __x) {
  515.     return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x));
  516.   }
  517.   pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
  518.     return pair<const_iterator,const_iterator>(lower_bound(__x),
  519.                            upper_bound(__x));
  520.   }
  521.  
  522. public:
  523.                                 // Debugging.
  524.   bool __rb_verify() const;
  525. };
  526.  
  527. template <class _Key, class _Value, class _KeyOfValue, 
  528.           class _Compare, class _Alloc> inline bool _STLP_CALL 
  529. operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  530.            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
  531. {
  532.   return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin());
  533. }
  534.  
  535. template <class _Key, class _Value, class _KeyOfValue, 
  536.           class _Compare, class _Alloc> inline bool _STLP_CALL 
  537. operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  538.           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
  539. {
  540.   return lexicographical_compare(__x.begin(), __x.end(), 
  541.                                  __y.begin(), __y.end());
  542. }
  543.  
  544. #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
  545.  
  546. template <class _Key, class _Value, class _KeyOfValue, 
  547.           class _Compare, class _Alloc> inline bool _STLP_CALL 
  548. operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  549.            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  550.   return !(__x == __y);
  551. }
  552.  
  553. template <class _Key, class _Value, class _KeyOfValue, 
  554.           class _Compare, class _Alloc> inline bool _STLP_CALL 
  555. operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  556.           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  557.   return __y < __x;
  558. }
  559.  
  560. template <class _Key, class _Value, class _KeyOfValue, 
  561.           class _Compare, class _Alloc> inline bool _STLP_CALL 
  562. operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  563.            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  564.   return !(__y < __x);
  565. }
  566.  
  567. template <class _Key, class _Value, class _KeyOfValue, 
  568.           class _Compare, class _Alloc> inline bool _STLP_CALL 
  569. operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  570.            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  571.   return !(__x < __y);
  572. }
  573.  
  574. #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
  575.  
  576. #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
  577.  
  578. template <class _Key, class _Value, class _KeyOfValue, 
  579.           class _Compare, class _Alloc> inline void _STLP_CALL 
  580. swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
  581.      _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
  582. {
  583.   __x.swap(__y);
  584. }
  585.  
  586. #endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
  587.          
  588. _STLP_END_NAMESPACE
  589.  
  590. # if !defined (_STLP_LINK_TIME_INSTANTIATION)
  591. #  include <stl/_tree.c> 
  592. # endif
  593.  
  594. # undef _Rb_tree
  595.  
  596. #if defined (_STLP_DEBUG)
  597. # include <stl/debug/_tree.h> 
  598. #endif
  599.  
  600. _STLP_BEGIN_NAMESPACE
  601. // Class rb_tree is not part of the C++ standard.  It is provided for
  602. // compatibility with the HP STL.
  603.  
  604. template <class _Key, class _Value, class _KeyOfValue, class _Compare,
  605.           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> {
  606.   typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
  607.   typedef typename _Base::allocator_type allocator_type;
  608.  
  609.   rb_tree()
  610.      : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(_Compare(), allocator_type()) {}
  611.   rb_tree(const _Compare& __comp,
  612.           const allocator_type& __a = allocator_type())
  613.     : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(__comp, __a) {} 
  614.   ~rb_tree() {}
  615. };
  616. _STLP_END_NAMESPACE
  617.  
  618. #endif /* _STLP_INTERNAL_TREE_H */
  619.  
  620. // Local Variables:
  621. // mode:C++
  622. // End:
  623.