1.1 --- a/epoc32/include/stdapis/stlport/stl/_tree.h Tue Nov 24 13:55:44 2009 +0000
1.2 +++ b/epoc32/include/stdapis/stlport/stl/_tree.h Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -1,1 +1,625 @@
1.4 -_tree.h
1.5 +/*
1.6 + *
1.7 + * Copyright (c) 1994
1.8 + * Hewlett-Packard Company
1.9 + *
1.10 + * Copyright (c) 1996,1997
1.11 + * Silicon Graphics Computer Systems, Inc.
1.12 + *
1.13 + * Copyright (c) 1997
1.14 + * Moscow Center for SPARC Technology
1.15 + *
1.16 + * Copyright (c) 1999
1.17 + * Boris Fomitchev
1.18 + *
1.19 + * This material is provided "as is", with absolutely no warranty expressed
1.20 + * or implied. Any use is at your own risk.
1.21 + *
1.22 + * Permission to use or copy this software for any purpose is hereby granted
1.23 + * without fee, provided the above notices are retained on all copies.
1.24 + * Permission to modify the code and to distribute modified code is granted,
1.25 + * provided the above notices are retained, and a notice that the code was
1.26 + * modified is included with the above copyright notice.
1.27 + *
1.28 + */
1.29 +
1.30 +/* NOTE: This is an internal header file, included by other STL headers.
1.31 + * You should not attempt to use it directly.
1.32 + */
1.33 +
1.34 +#ifndef _STLP_INTERNAL_TREE_H
1.35 +#define _STLP_INTERNAL_TREE_H
1.36 +
1.37 +/*
1.38 +
1.39 +Red-black tree class, designed for use in implementing STL
1.40 +associative containers (set, multiset, map, and multimap). The
1.41 +insertion and deletion algorithms are based on those in Cormen,
1.42 +Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
1.43 +except that
1.44 +
1.45 +(1) the header cell is maintained with links not only to the root
1.46 +but also to the leftmost node of the tree, to enable constant time
1.47 +begin(), and to the rightmost node of the tree, to enable linear time
1.48 +performance when used with the generic set algorithms (set_union,
1.49 +etc.);
1.50 +
1.51 +(2) when a node being deleted has two children its successor node is
1.52 +relinked into its place, rather than copied, so that the only
1.53 +iterators invalidated are those referring to the deleted node.
1.54 +
1.55 +*/
1.56 +
1.57 +# ifndef _STLP_INTERNAL_ALGOBASE_H
1.58 +# include <stl/_algobase.h>
1.59 +# endif
1.60 +
1.61 +# ifndef _STLP_INTERNAL_ALLOC_H
1.62 +# include <stl/_alloc.h>
1.63 +# endif
1.64 +
1.65 +# ifndef _STLP_INTERNAL_ITERATOR_H
1.66 +# include <stl/_iterator.h>
1.67 +# endif
1.68 +
1.69 +# ifndef _STLP_INTERNAL_CONSTRUCT_H
1.70 +# include <stl/_construct.h>
1.71 +# endif
1.72 +
1.73 +# ifndef _STLP_INTERNAL_FUNCTION_H
1.74 +# include <stl/_function_base.h>
1.75 +# endif
1.76 +
1.77 +#if defined ( _STLP_DEBUG)
1.78 +# define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree)
1.79 +#endif
1.80 +
1.81 +_STLP_BEGIN_NAMESPACE
1.82 +
1.83 +typedef bool _Rb_tree_Color_type;
1.84 +//const _Rb_tree_Color_type _S_rb_tree_red = false;
1.85 +//const _Rb_tree_Color_type _S_rb_tree_black = true;
1.86 +
1.87 +#define _S_rb_tree_red false
1.88 +#define _S_rb_tree_black true
1.89 +
1.90 +struct _Rb_tree_node_base
1.91 +{
1.92 + typedef _Rb_tree_Color_type _Color_type;
1.93 + typedef _Rb_tree_node_base* _Base_ptr;
1.94 +
1.95 + _Color_type _M_color;
1.96 + _Base_ptr _M_parent;
1.97 + _Base_ptr _M_left;
1.98 + _Base_ptr _M_right;
1.99 +
1.100 + static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
1.101 + {
1.102 + while (__x->_M_left != 0) __x = __x->_M_left;
1.103 + return __x;
1.104 + }
1.105 +
1.106 + static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
1.107 + {
1.108 + while (__x->_M_right != 0) __x = __x->_M_right;
1.109 + return __x;
1.110 + }
1.111 +};
1.112 +
1.113 +template <class _Value> struct _Rb_tree_node : public _Rb_tree_node_base
1.114 +{
1.115 + _Value _M_value_field;
1.116 + __TRIVIAL_STUFF(_Rb_tree_node)
1.117 +};
1.118 +
1.119 +struct _Rb_tree_base_iterator;
1.120 +
1.121 +template <class _Dummy> class _Rb_global {
1.122 +public:
1.123 + typedef _Rb_tree_node_base* _Base_ptr;
1.124 + // those used to be global functions
1.125 + static void _STLP_CALL _Rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
1.126 + static _Rb_tree_node_base* _STLP_CALL _Rebalance_for_erase(_Rb_tree_node_base* __z,
1.127 + _Rb_tree_node_base*& __root,
1.128 + _Rb_tree_node_base*& __leftmost,
1.129 + _Rb_tree_node_base*& __rightmost);
1.130 + // those are from _Rb_tree_base_iterator - moved here to reduce code bloat
1.131 + // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator
1.132 + static _Rb_tree_node_base* _STLP_CALL _M_increment(_Rb_tree_node_base*);
1.133 + static _Rb_tree_node_base* _STLP_CALL _M_decrement(_Rb_tree_node_base*);
1.134 + static void _STLP_CALL _Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
1.135 + static void _STLP_CALL _Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
1.136 +};
1.137 +
1.138 +# if defined (_STLP_USE_TEMPLATE_EXPORT)
1.139 +_STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>;
1.140 +# endif
1.141 +
1.142 +typedef _Rb_global<bool> _Rb_global_inst;
1.143 +
1.144 +struct _Rb_tree_base_iterator
1.145 +{
1.146 + typedef _Rb_tree_node_base* _Base_ptr;
1.147 + typedef bidirectional_iterator_tag iterator_category;
1.148 + typedef ptrdiff_t difference_type;
1.149 + _Base_ptr _M_node;
1.150 + bool operator==(const _Rb_tree_base_iterator& __y) const {
1.151 + return _M_node == __y._M_node;
1.152 + }
1.153 + bool operator!=(const _Rb_tree_base_iterator& __y) const {
1.154 + return _M_node != __y._M_node;
1.155 + }
1.156 +};
1.157 +
1.158 +
1.159 +template <class _Value, class _Traits> struct _Rb_tree_iterator : public _Rb_tree_base_iterator
1.160 +{
1.161 + typedef _Value value_type;
1.162 + typedef typename _Traits::reference reference;
1.163 + typedef typename _Traits::pointer pointer;
1.164 + typedef _Rb_tree_iterator<_Value, _Traits> _Self;
1.165 + typedef _Rb_tree_node<_Value>* _Link_type;
1.166 +
1.167 + _Rb_tree_iterator() { _M_node = 0; }
1.168 + _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
1.169 + _Rb_tree_iterator(const _Rb_tree_iterator<_Value,
1.170 + _Nonconst_traits<_Value> >& __it) { _M_node = __it._M_node; }
1.171 +
1.172 + reference operator*() const {
1.173 + return _Link_type(_M_node)->_M_value_field;
1.174 + }
1.175 +
1.176 + _STLP_DEFINE_ARROW_OPERATOR
1.177 +
1.178 + _Self& operator++() { _M_node = _Rb_global_inst::_M_increment(_M_node); return *this; }
1.179 + _Self operator++(int) {
1.180 + _Self __tmp = *this;
1.181 + _M_node = _Rb_global_inst::_M_increment(_M_node);
1.182 + return __tmp;
1.183 + }
1.184 +
1.185 + _Self& operator--() { _M_node = _Rb_global_inst::_M_decrement(_M_node); return *this; }
1.186 + _Self operator--(int) {
1.187 + _Self __tmp = *this;
1.188 + _M_node = _Rb_global_inst::_M_decrement(_M_node);
1.189 + return __tmp;
1.190 + }
1.191 +};
1.192 +
1.193 +# ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
1.194 +template <class _Value, class _Traits> inline _Value* value_type(const _Rb_tree_iterator<_Value, _Traits>&) { return (_Value*)0; }
1.195 +inline bidirectional_iterator_tag iterator_category(const _Rb_tree_base_iterator&) { return bidirectional_iterator_tag(); }
1.196 +inline ptrdiff_t* distance_type(const _Rb_tree_base_iterator&) { return (ptrdiff_t*) 0; }
1.197 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.198 +
1.199 +// Base class to help EH
1.200 +
1.201 +template <class _Tp, class _Alloc> struct _Rb_tree_base
1.202 +{
1.203 + typedef _Rb_tree_node<_Tp> _Node;
1.204 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.205 + typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
1.206 +
1.207 + _Rb_tree_base(const allocator_type& __a) :
1.208 + _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), (_Node*)0) {
1.209 + _M_header._M_data = _M_header.allocate(1);
1.210 + // WRITELOG("Rb_tree_base\n");
1.211 + }
1.212 + ~_Rb_tree_base() {
1.213 + // WRITELOG("~Rb_tree_base\n");
1.214 + _M_header.deallocate(_M_header._M_data,1);
1.215 + }
1.216 + allocator_type get_allocator() const {
1.217 + return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp);
1.218 + }
1.219 +protected:
1.220 + typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type;
1.221 + _STLP_alloc_proxy<_Node*, _Node, _M_node_allocator_type> _M_header;
1.222 +};
1.223 +
1.224 +
1.225 +template <class _Key, class _Value, class _KeyOfValue, class _Compare,
1.226 + _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
1.227 + typedef _Rb_tree_base<_Value, _Alloc> _Base;
1.228 +protected:
1.229 + typedef _Rb_tree_node_base* _Base_ptr;
1.230 + typedef _Rb_tree_node<_Value> _Node;
1.231 + typedef _Rb_tree_Color_type _Color_type;
1.232 +public:
1.233 + typedef _Key key_type;
1.234 + typedef _Value value_type;
1.235 + typedef value_type* pointer;
1.236 + typedef const value_type* const_pointer;
1.237 + typedef value_type& reference;
1.238 + typedef const value_type& const_reference;
1.239 + typedef _Rb_tree_node<_Value>* _Link_type;
1.240 + typedef size_t size_type;
1.241 + typedef ptrdiff_t difference_type;
1.242 + typedef bidirectional_iterator_tag _Iterator_category;
1.243 + typedef typename _Base::allocator_type allocator_type;
1.244 +
1.245 +protected:
1.246 +
1.247 + _Link_type _M_create_node(const value_type& __x)
1.248 + {
1.249 + _Link_type __tmp = this->_M_header.allocate(1);
1.250 + _STLP_TRY {
1.251 + _Construct(&__tmp->_M_value_field, __x);
1.252 + }
1.253 + _STLP_UNWIND(this->_M_header.deallocate(__tmp,1));
1.254 + return __tmp;
1.255 + }
1.256 +
1.257 + _Link_type _M_clone_node(_Link_type __x)
1.258 + {
1.259 + _Link_type __tmp = _M_create_node(__x->_M_value_field);
1.260 + __tmp->_M_color = __x->_M_color;
1.261 + __tmp->_M_left = 0;
1.262 + __tmp->_M_right = 0;
1.263 + return __tmp;
1.264 + }
1.265 +
1.266 +protected:
1.267 + size_type _M_node_count; // keeps track of size of tree
1.268 + _Compare _M_key_compare;
1.269 +
1.270 + _Link_type& _M_root() const
1.271 + { return (_Link_type&) this->_M_header._M_data->_M_parent; }
1.272 + _Link_type& _M_leftmost() const
1.273 + { return (_Link_type&) this->_M_header._M_data->_M_left; }
1.274 + _Link_type& _M_rightmost() const
1.275 + { return (_Link_type&) this->_M_header._M_data->_M_right; }
1.276 +
1.277 + static _Link_type& _STLP_CALL _S_left(_Link_type __x)
1.278 + { return (_Link_type&)(__x->_M_left); }
1.279 + static _Link_type& _STLP_CALL _S_right(_Link_type __x)
1.280 + { return (_Link_type&)(__x->_M_right); }
1.281 + static _Link_type& _STLP_CALL _S_parent(_Link_type __x)
1.282 + { return (_Link_type&)(__x->_M_parent); }
1.283 + static reference _STLP_CALL _S_value(_Link_type __x)
1.284 + { return __x->_M_value_field; }
1.285 + static const _Key& _STLP_CALL _S_key(_Link_type __x)
1.286 + { return _KeyOfValue()(_S_value(__x)); }
1.287 + static _Color_type& _STLP_CALL _S_color(_Link_type __x)
1.288 + { return (_Color_type&)(__x->_M_color); }
1.289 +
1.290 + static _Link_type& _STLP_CALL _S_left(_Base_ptr __x)
1.291 + { return (_Link_type&)(__x->_M_left); }
1.292 + static _Link_type& _STLP_CALL _S_right(_Base_ptr __x)
1.293 + { return (_Link_type&)(__x->_M_right); }
1.294 + static _Link_type& _STLP_CALL _S_parent(_Base_ptr __x)
1.295 + { return (_Link_type&)(__x->_M_parent); }
1.296 + static reference _STLP_CALL _S_value(_Base_ptr __x)
1.297 + { return ((_Link_type)__x)->_M_value_field; }
1.298 + static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
1.299 + { return _KeyOfValue()(_S_value(_Link_type(__x)));}
1.300 + static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
1.301 + { return (_Color_type&)(_Link_type(__x)->_M_color); }
1.302 +
1.303 + static _Link_type _STLP_CALL _S_minimum(_Link_type __x)
1.304 + { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); }
1.305 +
1.306 + static _Link_type _STLP_CALL _S_maximum(_Link_type __x)
1.307 + { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
1.308 +
1.309 +public:
1.310 + typedef _Rb_tree_iterator<value_type, _Nonconst_traits<value_type> > iterator;
1.311 + typedef _Rb_tree_iterator<value_type, _Const_traits<value_type> > const_iterator;
1.312 + _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
1.313 +
1.314 +private:
1.315 + iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v, _Base_ptr __w = 0);
1.316 + _Link_type _M_copy(_Link_type __x, _Link_type __p);
1.317 + void _M_erase(_Link_type __x);
1.318 +
1.319 +public:
1.320 + // allocation/deallocation
1.321 + _Rb_tree()
1.322 + : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
1.323 + { _M_empty_initialize();
1.324 + }
1.325 +
1.326 + _Rb_tree(const _Compare& __comp)
1.327 + : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
1.328 + { _M_empty_initialize(); }
1.329 +
1.330 + _Rb_tree(const _Compare& __comp, const allocator_type& __a)
1.331 + : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp)
1.332 + { _M_empty_initialize(); }
1.333 +
1.334 + _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
1.335 + : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
1.336 + _M_node_count(0), _M_key_compare(__x._M_key_compare)
1.337 + {
1.338 + if (__x._M_root() == 0)
1.339 + _M_empty_initialize();
1.340 + else {
1.341 + _S_color(this->_M_header._M_data) = _S_rb_tree_red;
1.342 + _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);
1.343 + _M_leftmost() = _S_minimum(_M_root());
1.344 + _M_rightmost() = _S_maximum(_M_root());
1.345 + }
1.346 + _M_node_count = __x._M_node_count;
1.347 + }
1.348 + ~_Rb_tree() { clear(); }
1.349 + _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);
1.350 +
1.351 +private:
1.352 + void _M_empty_initialize() {
1.353 + _S_color(this->_M_header._M_data) = _S_rb_tree_red; // used to distinguish header from
1.354 + // __root, in iterator.operator++
1.355 + _M_root() = 0;
1.356 + _M_leftmost() = this->_M_header._M_data;
1.357 + _M_rightmost() = this->_M_header._M_data;
1.358 + }
1.359 +
1.360 +public:
1.361 + // accessors:
1.362 + _Compare key_comp() const { return _M_key_compare; }
1.363 +
1.364 + iterator begin() { return iterator(_M_leftmost()); }
1.365 + const_iterator begin() const { return const_iterator(_M_leftmost()); }
1.366 + iterator end() { return iterator(this->_M_header._M_data); }
1.367 + const_iterator end() const { return const_iterator(this->_M_header._M_data); }
1.368 +
1.369 + reverse_iterator rbegin() { return reverse_iterator(end()); }
1.370 + const_reverse_iterator rbegin() const {
1.371 + return const_reverse_iterator(end());
1.372 + }
1.373 + reverse_iterator rend() { return reverse_iterator(begin()); }
1.374 + const_reverse_iterator rend() const {
1.375 + return const_reverse_iterator(begin());
1.376 + }
1.377 + bool empty() const { return _M_node_count == 0; }
1.378 + size_type size() const { return _M_node_count; }
1.379 + size_type max_size() const { return size_type(-1); }
1.380 +
1.381 + void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
1.382 + _STLP_STD::swap(this->_M_header, __t._M_header);
1.383 + _STLP_STD::swap(_M_node_count, __t._M_node_count);
1.384 + _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
1.385 + }
1.386 +
1.387 +public:
1.388 + // insert/erase
1.389 + pair<iterator,bool> insert_unique(const value_type& __x);
1.390 + iterator insert_equal(const value_type& __x);
1.391 +
1.392 + iterator insert_unique(iterator __position, const value_type& __x);
1.393 + iterator insert_equal(iterator __position, const value_type& __x);
1.394 +
1.395 +#ifdef _STLP_MEMBER_TEMPLATES
1.396 + template<class _II> void insert_equal(_II __first, _II __last) {
1.397 + for ( ; __first != __last; ++__first)
1.398 + insert_equal(*__first);
1.399 + }
1.400 + template<class _II> void insert_unique(_II __first, _II __last) {
1.401 + for ( ; __first != __last; ++__first)
1.402 + insert_unique(*__first);
1.403 + }
1.404 +#else /* _STLP_MEMBER_TEMPLATES */
1.405 + void insert_unique(const_iterator __first, const_iterator __last) {
1.406 + for ( ; __first != __last; ++__first)
1.407 + insert_unique(*__first);
1.408 + }
1.409 + void insert_unique(const value_type* __first, const value_type* __last) {
1.410 + for ( ; __first != __last; ++__first)
1.411 + insert_unique(*__first);
1.412 + }
1.413 + void insert_equal(const_iterator __first, const_iterator __last) {
1.414 + for ( ; __first != __last; ++__first)
1.415 + insert_equal(*__first);
1.416 + }
1.417 + void insert_equal(const value_type* __first, const value_type* __last) {
1.418 + for ( ; __first != __last; ++__first)
1.419 + insert_equal(*__first);
1.420 + }
1.421 +#endif /* _STLP_MEMBER_TEMPLATES */
1.422 +
1.423 + void erase(iterator __position) {
1.424 + _Link_type __y =
1.425 + (_Link_type) _Rb_global_inst::_Rebalance_for_erase(__position._M_node,
1.426 + this->_M_header._M_data->_M_parent,
1.427 + this->_M_header._M_data->_M_left,
1.428 + this->_M_header._M_data->_M_right);
1.429 + _STLP_STD::_Destroy(&__y->_M_value_field);
1.430 + this->_M_header.deallocate(__y,1);
1.431 + --_M_node_count;
1.432 + }
1.433 +
1.434 + size_type erase(const key_type& __x) {
1.435 + pair<iterator,iterator> __p = equal_range(__x);
1.436 + size_type __n = distance(__p.first, __p.second);
1.437 + erase(__p.first, __p.second);
1.438 + return __n;
1.439 + }
1.440 +
1.441 + void erase(iterator __first, iterator __last) {
1.442 + if (__first == begin() && __last == end())
1.443 + clear();
1.444 + else
1.445 + while (__first != __last) erase(__first++);
1.446 + }
1.447 +
1.448 + void erase(const key_type* __first, const key_type* __last) {
1.449 + while (__first != __last) erase(*__first++);
1.450 + }
1.451 +
1.452 + void clear() {
1.453 + if (_M_node_count != 0) {
1.454 + _M_erase(_M_root());
1.455 + _M_leftmost() = this->_M_header._M_data;
1.456 + _M_root() = 0;
1.457 + _M_rightmost() = this->_M_header._M_data;
1.458 + _M_node_count = 0;
1.459 + }
1.460 + }
1.461 +
1.462 +public:
1.463 + // set operations:
1.464 +# if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !defined(__MRC__) && !(defined(__SC__) && !defined(__DMC__))
1.465 + template <class _KT> iterator find(const _KT& __x) { return iterator(_M_find(__x)); }
1.466 + template <class _KT> const_iterator find(const _KT& __x) const { return const_iterator(_M_find(__x)); }
1.467 +private:
1.468 + template <class _KT> _Rb_tree_node<_Value>* _M_find(const _KT& __k) const
1.469 +# else
1.470 + iterator find(const key_type& __x) { return iterator(_M_find(__x)); }
1.471 + const_iterator find(const key_type& __x) const { return const_iterator(_M_find(__x)); }
1.472 +private:
1.473 + _Rb_tree_node<_Value>* _M_find(const key_type& __k) const
1.474 +# endif
1.475 + {
1.476 + _Link_type __y = this->_M_header._M_data; // Last node which is not less than __k.
1.477 + _Link_type __x = _M_root(); // Current node.
1.478 +
1.479 + while (__x != 0)
1.480 + if (!_M_key_compare(_S_key(__x), __k))
1.481 + __y = __x, __x = _S_left(__x);
1.482 + else
1.483 + __x = _S_right(__x);
1.484 + if (__y == this->_M_header._M_data || _M_key_compare(__k, _S_key(__y)))
1.485 + __y = this->_M_header._M_data;
1.486 + return __y;
1.487 + }
1.488 +
1.489 + _Link_type _M_lower_bound(const key_type& __k) const {
1.490 + _Link_type __y = this->_M_header._M_data; /* Last node which is not less than __k. */
1.491 + _Link_type __x = _M_root(); /* Current node. */
1.492 +
1.493 + while (__x != 0)
1.494 + if (!_M_key_compare(_S_key(__x), __k))
1.495 + __y = __x, __x = _S_left(__x);
1.496 + else
1.497 + __x = _S_right(__x);
1.498 +
1.499 + return __y;
1.500 + }
1.501 +
1.502 + _Link_type _M_upper_bound(const key_type& __k) const {
1.503 + _Link_type __y = this->_M_header._M_data; /* Last node which is greater than __k. */
1.504 + _Link_type __x = _M_root(); /* Current node. */
1.505 +
1.506 + while (__x != 0)
1.507 + if (_M_key_compare(__k, _S_key(__x)))
1.508 + __y = __x, __x = _S_left(__x);
1.509 + else
1.510 + __x = _S_right(__x);
1.511 +
1.512 + return __y;
1.513 + }
1.514 +
1.515 +public:
1.516 + size_type count(const key_type& __x) const;
1.517 + iterator lower_bound(const key_type& __x) { return iterator(_M_lower_bound(__x)); }
1.518 + const_iterator lower_bound(const key_type& __x) const { return const_iterator(_M_lower_bound(__x)); }
1.519 + iterator upper_bound(const key_type& __x) { return iterator(_M_upper_bound(__x)); }
1.520 + const_iterator upper_bound(const key_type& __x) const { return const_iterator(_M_upper_bound(__x)); }
1.521 + pair<iterator,iterator> equal_range(const key_type& __x) {
1.522 + return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x));
1.523 + }
1.524 + pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
1.525 + return pair<const_iterator,const_iterator>(lower_bound(__x),
1.526 + upper_bound(__x));
1.527 + }
1.528 +
1.529 +public:
1.530 + // Debugging.
1.531 + bool __rb_verify() const;
1.532 +};
1.533 +
1.534 +template <class _Key, class _Value, class _KeyOfValue,
1.535 + class _Compare, class _Alloc> inline bool _STLP_CALL
1.536 +operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
1.537 + const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
1.538 +{
1.539 + return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin());
1.540 +}
1.541 +
1.542 +template <class _Key, class _Value, class _KeyOfValue,
1.543 + class _Compare, class _Alloc> inline bool _STLP_CALL
1.544 +operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
1.545 + const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
1.546 +{
1.547 + return lexicographical_compare(__x.begin(), __x.end(),
1.548 + __y.begin(), __y.end());
1.549 +}
1.550 +
1.551 +#ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
1.552 +
1.553 +template <class _Key, class _Value, class _KeyOfValue,
1.554 + class _Compare, class _Alloc> inline bool _STLP_CALL
1.555 +operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
1.556 + const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
1.557 + return !(__x == __y);
1.558 +}
1.559 +
1.560 +template <class _Key, class _Value, class _KeyOfValue,
1.561 + class _Compare, class _Alloc> inline bool _STLP_CALL
1.562 +operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
1.563 + const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
1.564 + return __y < __x;
1.565 +}
1.566 +
1.567 +template <class _Key, class _Value, class _KeyOfValue,
1.568 + class _Compare, class _Alloc> inline bool _STLP_CALL
1.569 +operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
1.570 + const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
1.571 + return !(__y < __x);
1.572 +}
1.573 +
1.574 +template <class _Key, class _Value, class _KeyOfValue,
1.575 + class _Compare, class _Alloc> inline bool _STLP_CALL
1.576 +operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
1.577 + const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
1.578 + return !(__x < __y);
1.579 +}
1.580 +
1.581 +#endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
1.582 +
1.583 +#ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
1.584 +
1.585 +template <class _Key, class _Value, class _KeyOfValue,
1.586 + class _Compare, class _Alloc> inline void _STLP_CALL
1.587 +swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
1.588 + _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
1.589 +{
1.590 + __x.swap(__y);
1.591 +}
1.592 +
1.593 +#endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
1.594 +
1.595 +_STLP_END_NAMESPACE
1.596 +
1.597 +# if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.598 +# include <stl/_tree.c>
1.599 +# endif
1.600 +
1.601 +# undef _Rb_tree
1.602 +
1.603 +#if defined (_STLP_DEBUG)
1.604 +# include <stl/debug/_tree.h>
1.605 +#endif
1.606 +
1.607 +_STLP_BEGIN_NAMESPACE
1.608 +// Class rb_tree is not part of the C++ standard. It is provided for
1.609 +// compatibility with the HP STL.
1.610 +
1.611 +template <class _Key, class _Value, class _KeyOfValue, class _Compare,
1.612 + _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> {
1.613 + typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
1.614 + typedef typename _Base::allocator_type allocator_type;
1.615 +
1.616 + rb_tree()
1.617 + : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(_Compare(), allocator_type()) {}
1.618 + rb_tree(const _Compare& __comp,
1.619 + const allocator_type& __a = allocator_type())
1.620 + : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(__comp, __a) {}
1.621 + ~rb_tree() {}
1.622 +};
1.623 +_STLP_END_NAMESPACE
1.624 +
1.625 +#endif /* _STLP_INTERNAL_TREE_H */
1.626 +
1.627 +// Local Variables:
1.628 +// mode:C++
1.629 +// End: