epoc32/include/stdapis/stlport/stl/_tree.h
branchSymbian2
changeset 2 2fe1408b6811
parent 0 061f57f2323e
     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: