williamr@2: /* williamr@2: * williamr@2: * Copyright (c) 1994 williamr@2: * Hewlett-Packard Company williamr@2: * williamr@2: * Copyright (c) 1996,1997 williamr@2: * Silicon Graphics Computer Systems, Inc. williamr@2: * williamr@2: * Copyright (c) 1997 williamr@2: * Moscow Center for SPARC Technology williamr@2: * williamr@2: * Copyright (c) 1999 williamr@2: * Boris Fomitchev williamr@2: * williamr@2: * This material is provided "as is", with absolutely no warranty expressed williamr@2: * or implied. Any use is at your own risk. williamr@2: * williamr@2: * Permission to use or copy this software for any purpose is hereby granted williamr@2: * without fee, provided the above notices are retained on all copies. williamr@2: * Permission to modify the code and to distribute modified code is granted, williamr@2: * provided the above notices are retained, and a notice that the code was williamr@2: * modified is included with the above copyright notice. williamr@2: * williamr@2: */ williamr@2: williamr@2: /* NOTE: This is an internal header file, included by other STL headers. williamr@2: * You should not attempt to use it directly. williamr@2: */ williamr@2: williamr@2: #ifndef _STLP_INTERNAL_TREE_H williamr@2: #define _STLP_INTERNAL_TREE_H williamr@2: williamr@2: /* williamr@2: williamr@2: Red-black tree class, designed for use in implementing STL williamr@2: associative containers (set, multiset, map, and multimap). The williamr@2: insertion and deletion algorithms are based on those in Cormen, williamr@2: Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), williamr@2: except that williamr@2: williamr@2: (1) the header cell is maintained with links not only to the root williamr@2: but also to the leftmost node of the tree, to enable constant time williamr@2: begin(), and to the rightmost node of the tree, to enable linear time williamr@2: performance when used with the generic set algorithms (set_union, williamr@2: etc.); williamr@2: williamr@2: (2) when a node being deleted has two children its successor node is williamr@2: relinked into its place, rather than copied, so that the only williamr@2: iterators invalidated are those referring to the deleted node. williamr@2: williamr@2: */ williamr@2: williamr@2: # ifndef _STLP_INTERNAL_ALGOBASE_H williamr@2: # include williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_INTERNAL_ALLOC_H williamr@2: # include williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_INTERNAL_ITERATOR_H williamr@2: # include williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_INTERNAL_CONSTRUCT_H williamr@2: # include williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_INTERNAL_FUNCTION_H williamr@2: # include williamr@2: # endif williamr@2: williamr@2: #if defined ( _STLP_DEBUG) williamr@2: # define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree) williamr@2: #endif williamr@2: williamr@2: _STLP_BEGIN_NAMESPACE williamr@2: williamr@2: typedef bool _Rb_tree_Color_type; williamr@2: //const _Rb_tree_Color_type _S_rb_tree_red = false; williamr@2: //const _Rb_tree_Color_type _S_rb_tree_black = true; williamr@2: williamr@2: #define _S_rb_tree_red false williamr@2: #define _S_rb_tree_black true williamr@2: williamr@2: struct _Rb_tree_node_base williamr@2: { williamr@2: typedef _Rb_tree_Color_type _Color_type; williamr@2: typedef _Rb_tree_node_base* _Base_ptr; williamr@2: williamr@2: _Color_type _M_color; williamr@2: _Base_ptr _M_parent; williamr@2: _Base_ptr _M_left; williamr@2: _Base_ptr _M_right; williamr@2: williamr@2: static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x) williamr@2: { williamr@2: while (__x->_M_left != 0) __x = __x->_M_left; williamr@2: return __x; williamr@2: } williamr@2: williamr@2: static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x) williamr@2: { williamr@2: while (__x->_M_right != 0) __x = __x->_M_right; williamr@2: return __x; williamr@2: } williamr@2: }; williamr@2: williamr@2: template struct _Rb_tree_node : public _Rb_tree_node_base williamr@2: { williamr@2: _Value _M_value_field; williamr@2: __TRIVIAL_STUFF(_Rb_tree_node) williamr@2: }; williamr@2: williamr@2: struct _Rb_tree_base_iterator; williamr@2: williamr@2: template class _Rb_global { williamr@2: public: williamr@2: typedef _Rb_tree_node_base* _Base_ptr; williamr@2: // those used to be global functions williamr@2: static void _STLP_CALL _Rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root); williamr@2: static _Rb_tree_node_base* _STLP_CALL _Rebalance_for_erase(_Rb_tree_node_base* __z, williamr@2: _Rb_tree_node_base*& __root, williamr@2: _Rb_tree_node_base*& __leftmost, williamr@2: _Rb_tree_node_base*& __rightmost); williamr@2: // those are from _Rb_tree_base_iterator - moved here to reduce code bloat williamr@2: // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator williamr@2: static _Rb_tree_node_base* _STLP_CALL _M_increment(_Rb_tree_node_base*); williamr@2: static _Rb_tree_node_base* _STLP_CALL _M_decrement(_Rb_tree_node_base*); williamr@2: static void _STLP_CALL _Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root); williamr@2: static void _STLP_CALL _Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root); williamr@2: }; williamr@2: williamr@2: # if defined (_STLP_USE_TEMPLATE_EXPORT) williamr@2: _STLP_EXPORT_TEMPLATE_CLASS _Rb_global; williamr@2: # endif williamr@2: williamr@2: typedef _Rb_global _Rb_global_inst; williamr@2: williamr@2: struct _Rb_tree_base_iterator williamr@2: { williamr@2: typedef _Rb_tree_node_base* _Base_ptr; williamr@2: typedef bidirectional_iterator_tag iterator_category; williamr@2: typedef ptrdiff_t difference_type; williamr@2: _Base_ptr _M_node; williamr@2: bool operator==(const _Rb_tree_base_iterator& __y) const { williamr@2: return _M_node == __y._M_node; williamr@2: } williamr@2: bool operator!=(const _Rb_tree_base_iterator& __y) const { williamr@2: return _M_node != __y._M_node; williamr@2: } williamr@2: }; williamr@2: williamr@2: williamr@2: template struct _Rb_tree_iterator : public _Rb_tree_base_iterator williamr@2: { williamr@2: typedef _Value value_type; williamr@2: typedef typename _Traits::reference reference; williamr@2: typedef typename _Traits::pointer pointer; williamr@2: typedef _Rb_tree_iterator<_Value, _Traits> _Self; williamr@2: typedef _Rb_tree_node<_Value>* _Link_type; williamr@2: williamr@2: _Rb_tree_iterator() { _M_node = 0; } williamr@2: _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } williamr@2: _Rb_tree_iterator(const _Rb_tree_iterator<_Value, williamr@2: _Nonconst_traits<_Value> >& __it) { _M_node = __it._M_node; } williamr@2: williamr@2: reference operator*() const { williamr@2: return _Link_type(_M_node)->_M_value_field; williamr@2: } williamr@2: williamr@2: _STLP_DEFINE_ARROW_OPERATOR williamr@2: williamr@2: _Self& operator++() { _M_node = _Rb_global_inst::_M_increment(_M_node); return *this; } williamr@2: _Self operator++(int) { williamr@2: _Self __tmp = *this; williamr@2: _M_node = _Rb_global_inst::_M_increment(_M_node); williamr@2: return __tmp; williamr@2: } williamr@2: williamr@2: _Self& operator--() { _M_node = _Rb_global_inst::_M_decrement(_M_node); return *this; } williamr@2: _Self operator--(int) { williamr@2: _Self __tmp = *this; williamr@2: _M_node = _Rb_global_inst::_M_decrement(_M_node); williamr@2: return __tmp; williamr@2: } williamr@2: }; williamr@2: williamr@2: # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES williamr@2: template inline _Value* value_type(const _Rb_tree_iterator<_Value, _Traits>&) { return (_Value*)0; } williamr@2: inline bidirectional_iterator_tag iterator_category(const _Rb_tree_base_iterator&) { return bidirectional_iterator_tag(); } williamr@2: inline ptrdiff_t* distance_type(const _Rb_tree_base_iterator&) { return (ptrdiff_t*) 0; } williamr@2: #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ williamr@2: williamr@2: // Base class to help EH williamr@2: williamr@2: template struct _Rb_tree_base williamr@2: { williamr@2: typedef _Rb_tree_node<_Tp> _Node; williamr@2: _STLP_FORCE_ALLOCATORS(_Tp, _Alloc) williamr@2: typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; williamr@2: williamr@2: _Rb_tree_base(const allocator_type& __a) : williamr@2: _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), (_Node*)0) { williamr@2: _M_header._M_data = _M_header.allocate(1); williamr@2: // WRITELOG("Rb_tree_base\n"); williamr@2: } williamr@2: ~_Rb_tree_base() { williamr@2: // WRITELOG("~Rb_tree_base\n"); williamr@2: _M_header.deallocate(_M_header._M_data,1); williamr@2: } williamr@2: allocator_type get_allocator() const { williamr@2: return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp); williamr@2: } williamr@2: protected: williamr@2: typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type; williamr@2: _STLP_alloc_proxy<_Node*, _Node, _M_node_allocator_type> _M_header; williamr@2: }; williamr@2: williamr@2: williamr@2: template class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> { williamr@2: typedef _Rb_tree_base<_Value, _Alloc> _Base; williamr@2: protected: williamr@2: typedef _Rb_tree_node_base* _Base_ptr; williamr@2: typedef _Rb_tree_node<_Value> _Node; williamr@2: typedef _Rb_tree_Color_type _Color_type; williamr@2: public: williamr@2: typedef _Key key_type; williamr@2: typedef _Value value_type; williamr@2: typedef value_type* pointer; williamr@2: typedef const value_type* const_pointer; williamr@2: typedef value_type& reference; williamr@2: typedef const value_type& const_reference; williamr@2: typedef _Rb_tree_node<_Value>* _Link_type; williamr@2: typedef size_t size_type; williamr@2: typedef ptrdiff_t difference_type; williamr@2: typedef bidirectional_iterator_tag _Iterator_category; williamr@2: typedef typename _Base::allocator_type allocator_type; williamr@2: williamr@2: protected: williamr@2: williamr@2: _Link_type _M_create_node(const value_type& __x) williamr@2: { williamr@2: _Link_type __tmp = this->_M_header.allocate(1); williamr@2: _STLP_TRY { williamr@2: _Construct(&__tmp->_M_value_field, __x); williamr@2: } williamr@2: _STLP_UNWIND(this->_M_header.deallocate(__tmp,1)); williamr@2: return __tmp; williamr@2: } williamr@2: williamr@2: _Link_type _M_clone_node(_Link_type __x) williamr@2: { williamr@2: _Link_type __tmp = _M_create_node(__x->_M_value_field); williamr@2: __tmp->_M_color = __x->_M_color; williamr@2: __tmp->_M_left = 0; williamr@2: __tmp->_M_right = 0; williamr@2: return __tmp; williamr@2: } williamr@2: williamr@2: protected: williamr@2: size_type _M_node_count; // keeps track of size of tree williamr@2: _Compare _M_key_compare; williamr@2: williamr@2: _Link_type& _M_root() const williamr@2: { return (_Link_type&) this->_M_header._M_data->_M_parent; } williamr@2: _Link_type& _M_leftmost() const williamr@2: { return (_Link_type&) this->_M_header._M_data->_M_left; } williamr@2: _Link_type& _M_rightmost() const williamr@2: { return (_Link_type&) this->_M_header._M_data->_M_right; } williamr@2: williamr@2: static _Link_type& _STLP_CALL _S_left(_Link_type __x) williamr@2: { return (_Link_type&)(__x->_M_left); } williamr@2: static _Link_type& _STLP_CALL _S_right(_Link_type __x) williamr@2: { return (_Link_type&)(__x->_M_right); } williamr@2: static _Link_type& _STLP_CALL _S_parent(_Link_type __x) williamr@2: { return (_Link_type&)(__x->_M_parent); } williamr@2: static reference _STLP_CALL _S_value(_Link_type __x) williamr@2: { return __x->_M_value_field; } williamr@2: static const _Key& _STLP_CALL _S_key(_Link_type __x) williamr@2: { return _KeyOfValue()(_S_value(__x)); } williamr@2: static _Color_type& _STLP_CALL _S_color(_Link_type __x) williamr@2: { return (_Color_type&)(__x->_M_color); } williamr@2: williamr@2: static _Link_type& _STLP_CALL _S_left(_Base_ptr __x) williamr@2: { return (_Link_type&)(__x->_M_left); } williamr@2: static _Link_type& _STLP_CALL _S_right(_Base_ptr __x) williamr@2: { return (_Link_type&)(__x->_M_right); } williamr@2: static _Link_type& _STLP_CALL _S_parent(_Base_ptr __x) williamr@2: { return (_Link_type&)(__x->_M_parent); } williamr@2: static reference _STLP_CALL _S_value(_Base_ptr __x) williamr@2: { return ((_Link_type)__x)->_M_value_field; } williamr@2: static const _Key& _STLP_CALL _S_key(_Base_ptr __x) williamr@2: { return _KeyOfValue()(_S_value(_Link_type(__x)));} williamr@2: static _Color_type& _STLP_CALL _S_color(_Base_ptr __x) williamr@2: { return (_Color_type&)(_Link_type(__x)->_M_color); } williamr@2: williamr@2: static _Link_type _STLP_CALL _S_minimum(_Link_type __x) williamr@2: { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } williamr@2: williamr@2: static _Link_type _STLP_CALL _S_maximum(_Link_type __x) williamr@2: { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); } williamr@2: williamr@2: public: williamr@2: typedef _Rb_tree_iterator > iterator; williamr@2: typedef _Rb_tree_iterator > const_iterator; williamr@2: _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; williamr@2: williamr@2: private: williamr@2: iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v, _Base_ptr __w = 0); williamr@2: _Link_type _M_copy(_Link_type __x, _Link_type __p); williamr@2: void _M_erase(_Link_type __x); williamr@2: williamr@2: public: williamr@2: // allocation/deallocation williamr@2: _Rb_tree() williamr@2: : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare()) williamr@2: { _M_empty_initialize(); williamr@2: } williamr@2: williamr@2: _Rb_tree(const _Compare& __comp) williamr@2: : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp) williamr@2: { _M_empty_initialize(); } williamr@2: williamr@2: _Rb_tree(const _Compare& __comp, const allocator_type& __a) williamr@2: : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp) williamr@2: { _M_empty_initialize(); } williamr@2: williamr@2: _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) williamr@2: : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()), williamr@2: _M_node_count(0), _M_key_compare(__x._M_key_compare) williamr@2: { williamr@2: if (__x._M_root() == 0) williamr@2: _M_empty_initialize(); williamr@2: else { williamr@2: _S_color(this->_M_header._M_data) = _S_rb_tree_red; williamr@2: _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data); williamr@2: _M_leftmost() = _S_minimum(_M_root()); williamr@2: _M_rightmost() = _S_maximum(_M_root()); williamr@2: } williamr@2: _M_node_count = __x._M_node_count; williamr@2: } williamr@2: ~_Rb_tree() { clear(); } williamr@2: _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x); williamr@2: williamr@2: private: williamr@2: void _M_empty_initialize() { williamr@2: _S_color(this->_M_header._M_data) = _S_rb_tree_red; // used to distinguish header from williamr@2: // __root, in iterator.operator++ williamr@2: _M_root() = 0; williamr@2: _M_leftmost() = this->_M_header._M_data; williamr@2: _M_rightmost() = this->_M_header._M_data; williamr@2: } williamr@2: williamr@2: public: williamr@2: // accessors: williamr@2: _Compare key_comp() const { return _M_key_compare; } williamr@2: williamr@2: iterator begin() { return iterator(_M_leftmost()); } williamr@2: const_iterator begin() const { return const_iterator(_M_leftmost()); } williamr@2: iterator end() { return iterator(this->_M_header._M_data); } williamr@2: const_iterator end() const { return const_iterator(this->_M_header._M_data); } williamr@2: williamr@2: reverse_iterator rbegin() { return reverse_iterator(end()); } williamr@2: const_reverse_iterator rbegin() const { williamr@2: return const_reverse_iterator(end()); williamr@2: } williamr@2: reverse_iterator rend() { return reverse_iterator(begin()); } williamr@2: const_reverse_iterator rend() const { williamr@2: return const_reverse_iterator(begin()); williamr@2: } williamr@2: bool empty() const { return _M_node_count == 0; } williamr@2: size_type size() const { return _M_node_count; } williamr@2: size_type max_size() const { return size_type(-1); } williamr@2: williamr@2: void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) { williamr@2: _STLP_STD::swap(this->_M_header, __t._M_header); williamr@2: _STLP_STD::swap(_M_node_count, __t._M_node_count); williamr@2: _STLP_STD::swap(_M_key_compare, __t._M_key_compare); williamr@2: } williamr@2: williamr@2: public: williamr@2: // insert/erase williamr@2: pair insert_unique(const value_type& __x); williamr@2: iterator insert_equal(const value_type& __x); williamr@2: williamr@2: iterator insert_unique(iterator __position, const value_type& __x); williamr@2: iterator insert_equal(iterator __position, const value_type& __x); williamr@2: williamr@2: #ifdef _STLP_MEMBER_TEMPLATES williamr@2: template void insert_equal(_II __first, _II __last) { williamr@2: for ( ; __first != __last; ++__first) williamr@2: insert_equal(*__first); williamr@2: } williamr@2: template void insert_unique(_II __first, _II __last) { williamr@2: for ( ; __first != __last; ++__first) williamr@2: insert_unique(*__first); williamr@2: } williamr@2: #else /* _STLP_MEMBER_TEMPLATES */ williamr@2: void insert_unique(const_iterator __first, const_iterator __last) { williamr@2: for ( ; __first != __last; ++__first) williamr@2: insert_unique(*__first); williamr@2: } williamr@2: void insert_unique(const value_type* __first, const value_type* __last) { williamr@2: for ( ; __first != __last; ++__first) williamr@2: insert_unique(*__first); williamr@2: } williamr@2: void insert_equal(const_iterator __first, const_iterator __last) { williamr@2: for ( ; __first != __last; ++__first) williamr@2: insert_equal(*__first); williamr@2: } williamr@2: void insert_equal(const value_type* __first, const value_type* __last) { williamr@2: for ( ; __first != __last; ++__first) williamr@2: insert_equal(*__first); williamr@2: } williamr@2: #endif /* _STLP_MEMBER_TEMPLATES */ williamr@2: williamr@2: void erase(iterator __position) { williamr@2: _Link_type __y = williamr@2: (_Link_type) _Rb_global_inst::_Rebalance_for_erase(__position._M_node, williamr@2: this->_M_header._M_data->_M_parent, williamr@2: this->_M_header._M_data->_M_left, williamr@2: this->_M_header._M_data->_M_right); williamr@2: _STLP_STD::_Destroy(&__y->_M_value_field); williamr@2: this->_M_header.deallocate(__y,1); williamr@2: --_M_node_count; williamr@2: } williamr@2: williamr@2: size_type erase(const key_type& __x) { williamr@2: pair __p = equal_range(__x); williamr@2: size_type __n = distance(__p.first, __p.second); williamr@2: erase(__p.first, __p.second); williamr@2: return __n; williamr@2: } williamr@2: williamr@2: void erase(iterator __first, iterator __last) { williamr@2: if (__first == begin() && __last == end()) williamr@2: clear(); williamr@2: else williamr@2: while (__first != __last) erase(__first++); williamr@2: } williamr@2: williamr@2: void erase(const key_type* __first, const key_type* __last) { williamr@2: while (__first != __last) erase(*__first++); williamr@2: } williamr@2: williamr@2: void clear() { williamr@2: if (_M_node_count != 0) { williamr@2: _M_erase(_M_root()); williamr@2: _M_leftmost() = this->_M_header._M_data; williamr@2: _M_root() = 0; williamr@2: _M_rightmost() = this->_M_header._M_data; williamr@2: _M_node_count = 0; williamr@2: } williamr@2: } williamr@2: williamr@2: public: williamr@2: // set operations: williamr@2: # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !defined(__MRC__) && !(defined(__SC__) && !defined(__DMC__)) williamr@2: template iterator find(const _KT& __x) { return iterator(_M_find(__x)); } williamr@2: template const_iterator find(const _KT& __x) const { return const_iterator(_M_find(__x)); } williamr@2: private: williamr@2: template _Rb_tree_node<_Value>* _M_find(const _KT& __k) const williamr@2: # else williamr@2: iterator find(const key_type& __x) { return iterator(_M_find(__x)); } williamr@2: const_iterator find(const key_type& __x) const { return const_iterator(_M_find(__x)); } williamr@2: private: williamr@2: _Rb_tree_node<_Value>* _M_find(const key_type& __k) const williamr@2: # endif williamr@2: { williamr@2: _Link_type __y = this->_M_header._M_data; // Last node which is not less than __k. williamr@2: _Link_type __x = _M_root(); // Current node. williamr@2: williamr@2: while (__x != 0) williamr@2: if (!_M_key_compare(_S_key(__x), __k)) williamr@2: __y = __x, __x = _S_left(__x); williamr@2: else williamr@2: __x = _S_right(__x); williamr@2: if (__y == this->_M_header._M_data || _M_key_compare(__k, _S_key(__y))) williamr@2: __y = this->_M_header._M_data; williamr@2: return __y; williamr@2: } williamr@2: williamr@2: _Link_type _M_lower_bound(const key_type& __k) const { williamr@2: _Link_type __y = this->_M_header._M_data; /* Last node which is not less than __k. */ williamr@2: _Link_type __x = _M_root(); /* Current node. */ williamr@2: williamr@2: while (__x != 0) williamr@2: if (!_M_key_compare(_S_key(__x), __k)) williamr@2: __y = __x, __x = _S_left(__x); williamr@2: else williamr@2: __x = _S_right(__x); williamr@2: williamr@2: return __y; williamr@2: } williamr@2: williamr@2: _Link_type _M_upper_bound(const key_type& __k) const { williamr@2: _Link_type __y = this->_M_header._M_data; /* Last node which is greater than __k. */ williamr@2: _Link_type __x = _M_root(); /* Current node. */ williamr@2: williamr@2: while (__x != 0) williamr@2: if (_M_key_compare(__k, _S_key(__x))) williamr@2: __y = __x, __x = _S_left(__x); williamr@2: else williamr@2: __x = _S_right(__x); williamr@2: williamr@2: return __y; williamr@2: } williamr@2: williamr@2: public: williamr@2: size_type count(const key_type& __x) const; williamr@2: iterator lower_bound(const key_type& __x) { return iterator(_M_lower_bound(__x)); } williamr@2: const_iterator lower_bound(const key_type& __x) const { return const_iterator(_M_lower_bound(__x)); } williamr@2: iterator upper_bound(const key_type& __x) { return iterator(_M_upper_bound(__x)); } williamr@2: const_iterator upper_bound(const key_type& __x) const { return const_iterator(_M_upper_bound(__x)); } williamr@2: pair equal_range(const key_type& __x) { williamr@2: return pair(lower_bound(__x), upper_bound(__x)); williamr@2: } williamr@2: pair equal_range(const key_type& __x) const { williamr@2: return pair(lower_bound(__x), williamr@2: upper_bound(__x)); williamr@2: } williamr@2: williamr@2: public: williamr@2: // Debugging. williamr@2: bool __rb_verify() const; williamr@2: }; williamr@2: williamr@2: template inline bool _STLP_CALL williamr@2: operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, williamr@2: const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) williamr@2: { williamr@2: return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin()); williamr@2: } williamr@2: williamr@2: template inline bool _STLP_CALL williamr@2: operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, williamr@2: const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) williamr@2: { williamr@2: return lexicographical_compare(__x.begin(), __x.end(), williamr@2: __y.begin(), __y.end()); williamr@2: } williamr@2: williamr@2: #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE williamr@2: williamr@2: template inline bool _STLP_CALL williamr@2: operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, williamr@2: const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { williamr@2: return !(__x == __y); williamr@2: } williamr@2: williamr@2: template inline bool _STLP_CALL williamr@2: operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, williamr@2: const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { williamr@2: return __y < __x; williamr@2: } williamr@2: williamr@2: template inline bool _STLP_CALL williamr@2: operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, williamr@2: const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { williamr@2: return !(__y < __x); williamr@2: } williamr@2: williamr@2: template inline bool _STLP_CALL williamr@2: operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, williamr@2: const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { williamr@2: return !(__x < __y); williamr@2: } williamr@2: williamr@2: #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */ williamr@2: williamr@2: #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER williamr@2: williamr@2: template inline void _STLP_CALL williamr@2: swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, williamr@2: _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) williamr@2: { williamr@2: __x.swap(__y); williamr@2: } williamr@2: williamr@2: #endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */ williamr@2: williamr@2: _STLP_END_NAMESPACE williamr@2: williamr@2: # if !defined (_STLP_LINK_TIME_INSTANTIATION) williamr@2: # include williamr@2: # endif williamr@2: williamr@2: # undef _Rb_tree williamr@2: williamr@2: #if defined (_STLP_DEBUG) williamr@2: # include williamr@2: #endif williamr@2: williamr@2: _STLP_BEGIN_NAMESPACE williamr@2: // Class rb_tree is not part of the C++ standard. It is provided for williamr@2: // compatibility with the HP STL. williamr@2: williamr@2: template struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> { williamr@2: typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base; williamr@2: typedef typename _Base::allocator_type allocator_type; williamr@2: williamr@2: rb_tree() williamr@2: : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(_Compare(), allocator_type()) {} williamr@2: rb_tree(const _Compare& __comp, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(__comp, __a) {} williamr@2: ~rb_tree() {} williamr@2: }; williamr@2: _STLP_END_NAMESPACE williamr@2: williamr@2: #endif /* _STLP_INTERNAL_TREE_H */ williamr@2: williamr@2: // Local Variables: williamr@2: // mode:C++ williamr@2: // End: