test: epoc32/include/stdapis/stlport/stl/

     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  */

    26 /* NOTE: This is an internal header file, included by other STL headers.

    27  *   You should not attempt to use it directly.

    28  */

    30 #ifndef _STLP_INTERNAL_TREE_H

    31 #define _STLP_INTERNAL_TREE_H

    33 /*

    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

    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.);

    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.

    51 */

    53 # ifndef _STLP_INTERNAL_ALGOBASE_H

    54 #  include <stl/_algobase.h>

    55 # endif

    57 # ifndef _STLP_INTERNAL_ALLOC_H

    58 #  include <stl/_alloc.h>

    59 # endif

    61 # ifndef _STLP_INTERNAL_ITERATOR_H

    62 #  include <stl/_iterator.h>

    63 # endif

    65 # ifndef _STLP_INTERNAL_CONSTRUCT_H

    66 #  include <stl/_construct.h>

    67 # endif

    69 # ifndef _STLP_INTERNAL_FUNCTION_H

    70 #  include <stl/_function_base.h>

    71 # endif

    73 #if defined ( _STLP_DEBUG)

    74 #  define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree)

    75 #endif

    77 _STLP_BEGIN_NAMESPACE

    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;

    83 #define _S_rb_tree_red false

    84 #define _S_rb_tree_black true

    86 struct _Rb_tree_node_base

    87 {

    88   typedef _Rb_tree_Color_type _Color_type;

    89   typedef _Rb_tree_node_base* _Base_ptr;

    91   _Color_type _M_color;

    92   _Base_ptr _M_parent;

    93   _Base_ptr _M_left;

    94   _Base_ptr _M_right;

    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   }

   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 };

   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 };

   115 struct _Rb_tree_base_iterator;

   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 };

   134 # if defined (_STLP_USE_TEMPLATE_EXPORT)

   135 _STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>;

   136 # endif

   138 typedef _Rb_global<bool> _Rb_global_inst;

   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 };

   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;

   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; }

   168   reference operator*() const {

   169     return _Link_type(_M_node)->_M_value_field;

   170   }

   172   _STLP_DEFINE_ARROW_OPERATOR

   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   }

   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 };

   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 */

   195 // Base class to help EH

   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;

   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     //    WRITELOG("Rb_tree_base\n");

   207   }

   208   ~_Rb_tree_base() {

   209     //    WRITELOG("~Rb_tree_base\n");

   210     _M_header.deallocate(_M_header._M_data,1);

   211   }

   212   allocator_type get_allocator() const {

   213     return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp);

   214   }

   215 protected:

   216   typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type;

   217   _STLP_alloc_proxy<_Node*, _Node, _M_node_allocator_type> _M_header;

   218 };

   221 template <class _Key, class _Value, class _KeyOfValue, class _Compare,

   222           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {

   223   typedef _Rb_tree_base<_Value, _Alloc> _Base;

   224 protected:

   225   typedef _Rb_tree_node_base* _Base_ptr;

   226   typedef _Rb_tree_node<_Value> _Node;

   227   typedef _Rb_tree_Color_type _Color_type;

   228 public:

   229   typedef _Key key_type;

   230   typedef _Value value_type;

   231   typedef value_type* pointer;

   232   typedef const value_type* const_pointer;

   233   typedef value_type& reference;

   234   typedef const value_type& const_reference;

   235   typedef _Rb_tree_node<_Value>* _Link_type;

   236   typedef size_t size_type;

   237   typedef ptrdiff_t difference_type;

   238   typedef bidirectional_iterator_tag _Iterator_category;

   239   typedef typename _Base::allocator_type allocator_type;

   241 protected:

   243   _Link_type _M_create_node(const value_type& __x)

   244   {

   245     _Link_type __tmp = this->_M_header.allocate(1);

   246     _STLP_TRY {

   247       _Construct(&__tmp->_M_value_field, __x);

   248     }

   249     _STLP_UNWIND(this->_M_header.deallocate(__tmp,1));

   250     return __tmp;

   251   }

   253   _Link_type _M_clone_node(_Link_type __x)

   254   {

   255     _Link_type __tmp = _M_create_node(__x->_M_value_field);

   256     __tmp->_M_color = __x->_M_color;

   257     __tmp->_M_left = 0;

   258     __tmp->_M_right = 0;

   259     return __tmp;

   260   }

   262 protected:

   263   size_type _M_node_count; // keeps track of size of tree

   264   _Compare _M_key_compare;

   266   _Link_type& _M_root() const

   267     { return (_Link_type&) this->_M_header._M_data->_M_parent; }

   268   _Link_type& _M_leftmost() const

   269     { return (_Link_type&) this->_M_header._M_data->_M_left; }

   270   _Link_type& _M_rightmost() const

   271     { return (_Link_type&) this->_M_header._M_data->_M_right; }

   273   static _Link_type& _STLP_CALL _S_left(_Link_type __x)

   274     { return (_Link_type&)(__x->_M_left); }

   275   static _Link_type& _STLP_CALL _S_right(_Link_type __x)

   276     { return (_Link_type&)(__x->_M_right); }

   277   static _Link_type& _STLP_CALL _S_parent(_Link_type __x)

   278     { return (_Link_type&)(__x->_M_parent); }

   279   static reference  _STLP_CALL _S_value(_Link_type __x)

   280     { return __x->_M_value_field; }

   281   static const _Key& _STLP_CALL _S_key(_Link_type __x)

   282     { return _KeyOfValue()(_S_value(__x)); }

   283   static _Color_type& _STLP_CALL _S_color(_Link_type __x)

   284     { return (_Color_type&)(__x->_M_color); }

   286   static _Link_type& _STLP_CALL _S_left(_Base_ptr __x)

   287     { return (_Link_type&)(__x->_M_left); }

   288   static _Link_type& _STLP_CALL _S_right(_Base_ptr __x)

   289     { return (_Link_type&)(__x->_M_right); }

   290   static _Link_type& _STLP_CALL _S_parent(_Base_ptr __x)

   291     { return (_Link_type&)(__x->_M_parent); }

   292   static reference  _STLP_CALL _S_value(_Base_ptr __x)

   293     { return ((_Link_type)__x)->_M_value_field; }

   294   static const _Key& _STLP_CALL _S_key(_Base_ptr __x)

   295     { return _KeyOfValue()(_S_value(_Link_type(__x)));}

   296   static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)

   297     { return (_Color_type&)(_Link_type(__x)->_M_color); }

   299   static _Link_type  _STLP_CALL _S_minimum(_Link_type __x)

   300     { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }

   302   static _Link_type  _STLP_CALL _S_maximum(_Link_type __x)

   303     { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }

   305 public:

   306   typedef _Rb_tree_iterator<value_type, _Nonconst_traits<value_type> > iterator;

   307   typedef _Rb_tree_iterator<value_type, _Const_traits<value_type> > const_iterator;

   308   _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;

   310 private:

   311   iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v, _Base_ptr __w = 0);

   312   _Link_type _M_copy(_Link_type __x, _Link_type __p);

   313   void _M_erase(_Link_type __x);

   315 public:

   316                                 // allocation/deallocation

   317   _Rb_tree()

   318     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())

   319     { _M_empty_initialize();

   320     }

   322   _Rb_tree(const _Compare& __comp)

   323     : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp)

   324     { _M_empty_initialize(); }

   326   _Rb_tree(const _Compare& __comp, const allocator_type& __a)

   327     : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp)

   328     { _M_empty_initialize(); }

   330   _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)

   331     : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),

   332       _M_node_count(0), _M_key_compare(__x._M_key_compare)

   333   {

   334     if (__x._M_root() == 0)

   335       _M_empty_initialize();

   336     else {

   337       _S_color(this->_M_header._M_data) = _S_rb_tree_red;

   338       _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);

   339       _M_leftmost() = _S_minimum(_M_root());

   340       _M_rightmost() = _S_maximum(_M_root());

   341     }

   342     _M_node_count = __x._M_node_count;

   343   }

   344   ~_Rb_tree() { clear(); }

   345   _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);

   347 private:

   348   void _M_empty_initialize() {

   349     _S_color(this->_M_header._M_data) = _S_rb_tree_red; // used to distinguish header from

   350                                           // __root, in iterator.operator++

   351     _M_root() = 0;

   352     _M_leftmost() = this->_M_header._M_data;

   353     _M_rightmost() = this->_M_header._M_data;

   354   }

   356 public:

   357                                 // accessors:

   358   _Compare key_comp() const { return _M_key_compare; }

   360   iterator begin() { return iterator(_M_leftmost()); }

   361   const_iterator begin() const { return const_iterator(_M_leftmost()); }

   362   iterator end() { return iterator(this->_M_header._M_data); }

   363   const_iterator end() const { return const_iterator(this->_M_header._M_data); }

   365   reverse_iterator rbegin() { return reverse_iterator(end()); }

   366   const_reverse_iterator rbegin() const {

   367     return const_reverse_iterator(end());

   368   }

   369   reverse_iterator rend() { return reverse_iterator(begin()); }

   370   const_reverse_iterator rend() const {

   371     return const_reverse_iterator(begin());

   372   }

   373   bool empty() const { return _M_node_count == 0; }

   374   size_type size() const { return _M_node_count; }

   375   size_type max_size() const { return size_type(-1); }

   377   void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {

   378     _STLP_STD::swap(this->_M_header, __t._M_header);

   379     _STLP_STD::swap(_M_node_count, __t._M_node_count);

   380     _STLP_STD::swap(_M_key_compare, __t._M_key_compare);

   381   }

   383 public:

   384                                 // insert/erase

   385   pair<iterator,bool> insert_unique(const value_type& __x);

   386   iterator insert_equal(const value_type& __x);

   388   iterator insert_unique(iterator __position, const value_type& __x);

   389   iterator insert_equal(iterator __position, const value_type& __x);

   391 #ifdef _STLP_MEMBER_TEMPLATES

   392   template<class _II> void insert_equal(_II __first, _II __last) {

   393     for ( ; __first != __last; ++__first)

   394       insert_equal(*__first);

   395   }

   396   template<class _II> void insert_unique(_II __first, _II __last) {

   397     for ( ; __first != __last; ++__first)

   398       insert_unique(*__first);

   399   }

   400 #else /* _STLP_MEMBER_TEMPLATES */

   401   void insert_unique(const_iterator __first, const_iterator __last) {

   402     for ( ; __first != __last; ++__first)

   403       insert_unique(*__first);

   404   }

   405   void insert_unique(const value_type* __first, const value_type* __last) {

   406     for ( ; __first != __last; ++__first)

   407       insert_unique(*__first);

   408   }

   409   void insert_equal(const_iterator __first, const_iterator __last) {

   410     for ( ; __first != __last; ++__first)

   411       insert_equal(*__first);

   412   }

   413   void insert_equal(const value_type* __first, const value_type* __last) {

   414     for ( ; __first != __last; ++__first)

   415       insert_equal(*__first);

   416   }

   417 #endif /* _STLP_MEMBER_TEMPLATES */

   419   void erase(iterator __position) {

   420     _Link_type __y =

   421       (_Link_type) _Rb_global_inst::_Rebalance_for_erase(__position._M_node,

   422 							 this->_M_header._M_data->_M_parent,

   423 							 this->_M_header._M_data->_M_left,

   424 							 this->_M_header._M_data->_M_right);

   425     _STLP_STD::_Destroy(&__y->_M_value_field);

   426     this->_M_header.deallocate(__y,1);

   427     --_M_node_count;

   428   }

   430   size_type erase(const key_type& __x) {

   431     pair<iterator,iterator> __p = equal_range(__x);

   432     size_type __n = distance(__p.first, __p.second);

   433     erase(__p.first, __p.second);

   434     return __n;

   435   }

   437   void erase(iterator __first, iterator __last) {

   438     if (__first == begin() && __last == end())

   439       clear();

   440     else

   441       while (__first != __last) erase(__first++);

   442   }

   444   void erase(const key_type* __first, const key_type* __last) {

   445     while (__first != __last) erase(*__first++);

   446   }

   448   void clear() {

   449     if (_M_node_count != 0) {

   450       _M_erase(_M_root());

   451       _M_leftmost() = this->_M_header._M_data;

   452       _M_root() = 0;

   453       _M_rightmost() = this->_M_header._M_data;

   454       _M_node_count = 0;

   455     }

   456   }

   458 public:

   459                                 // set operations:

   460 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !defined(__MRC__) && !(defined(__SC__) && !defined(__DMC__))

   461   template <class _KT> iterator find(const _KT& __x) { return iterator(_M_find(__x)); }

   462   template <class _KT> const_iterator find(const _KT& __x) const { return const_iterator(_M_find(__x)); }

   463 private:

   464   template <class _KT> _Rb_tree_node<_Value>* _M_find(const _KT& __k) const

   465 # else

   466   iterator find(const key_type& __x) { return iterator(_M_find(__x)); }

   467   const_iterator find(const key_type& __x) const { return const_iterator(_M_find(__x)); }

   468 private:

   469   _Rb_tree_node<_Value>* _M_find(const key_type& __k) const

   470 # endif

   471   {

   472     _Link_type __y = this->_M_header._M_data;      // Last node which is not less than __k.

   473     _Link_type __x = _M_root();      // Current node.

   475     while (__x != 0)

   476       if (!_M_key_compare(_S_key(__x), __k))

   477 	__y = __x, __x = _S_left(__x);

   478       else

   479 	__x = _S_right(__x);

   480     if (__y == this->_M_header._M_data || _M_key_compare(__k, _S_key(__y)))

   481       __y = this->_M_header._M_data;

   482     return __y;

   483   }

   485   _Link_type _M_lower_bound(const key_type& __k) const {

   486     _Link_type __y = this->_M_header._M_data; /* Last node which is not less than __k. */

   487     _Link_type __x = _M_root(); /* Current node. */

   489     while (__x != 0)

   490       if (!_M_key_compare(_S_key(__x), __k))

   491 	__y = __x, __x = _S_left(__x);

   492       else

   493 	__x = _S_right(__x);

   495     return __y;

   496   }

   498   _Link_type _M_upper_bound(const key_type& __k) const {

   499     _Link_type __y = this->_M_header._M_data; /* Last node which is greater than __k. */

   500     _Link_type __x = _M_root(); /* Current node. */

   502     while (__x != 0)

   503       if (_M_key_compare(__k, _S_key(__x)))

   504 	__y = __x, __x = _S_left(__x);

   505       else

   506 	__x = _S_right(__x);

   508     return __y;

   509   }

   511 public:

   512   size_type count(const key_type& __x) const;

   513   iterator lower_bound(const key_type& __x) { return iterator(_M_lower_bound(__x)); }

   514   const_iterator lower_bound(const key_type& __x) const { return const_iterator(_M_lower_bound(__x)); }

   515   iterator upper_bound(const key_type& __x) { return iterator(_M_upper_bound(__x)); }

   516   const_iterator upper_bound(const key_type& __x) const { return const_iterator(_M_upper_bound(__x)); }

   517   pair<iterator,iterator> equal_range(const key_type& __x) {

   518     return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x));

   519   }

   520   pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {

   521     return pair<const_iterator,const_iterator>(lower_bound(__x),

   522 					       upper_bound(__x));

   523   }

   525 public:

   526                                 // Debugging.

   527   bool __rb_verify() const;

   528 };

   530 template <class _Key, class _Value, class _KeyOfValue,

   531           class _Compare, class _Alloc> inline bool _STLP_CALL

   532 operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,

   533            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)

   534 {

   535   return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin());

   536 }

   538 template <class _Key, class _Value, class _KeyOfValue,

   539           class _Compare, class _Alloc> inline bool _STLP_CALL

   540 operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,

   541           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)

   542 {

   543   return lexicographical_compare(__x.begin(), __x.end(),

   544                                  __y.begin(), __y.end());

   545 }

   547 #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE

   549 template <class _Key, class _Value, class _KeyOfValue,

   550           class _Compare, class _Alloc> inline bool _STLP_CALL

   551 operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,

   552            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {

   553   return !(__x == __y);

   554 }

   556 template <class _Key, class _Value, class _KeyOfValue,

   557           class _Compare, class _Alloc> inline bool _STLP_CALL

   558 operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,

   559           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {

   560   return __y < __x;

   561 }

   563 template <class _Key, class _Value, class _KeyOfValue,

   564           class _Compare, class _Alloc> inline bool _STLP_CALL

   565 operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,

   566            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {

   567   return !(__y < __x);

   568 }

   570 template <class _Key, class _Value, class _KeyOfValue,

   571           class _Compare, class _Alloc> inline bool _STLP_CALL

   572 operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,

   573            const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {

   574   return !(__x < __y);

   575 }

   577 #endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */

   579 #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER

   581 template <class _Key, class _Value, class _KeyOfValue,

   582           class _Compare, class _Alloc> inline void _STLP_CALL

   583 swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,

   584      _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)

   585 {

   586   __x.swap(__y);

   587 }

   589 #endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */

   591 _STLP_END_NAMESPACE

   593 # if !defined (_STLP_LINK_TIME_INSTANTIATION)

   594 #  include <stl/_tree.c>

   595 # endif

   597 # undef _Rb_tree

   599 #if defined (_STLP_DEBUG)

   600 # include <stl/debug/_tree.h>

   601 #endif

   603 _STLP_BEGIN_NAMESPACE

   604 // Class rb_tree is not part of the C++ standard.  It is provided for

   605 // compatibility with the HP STL.

   607 template <class _Key, class _Value, class _KeyOfValue, class _Compare,

   608           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> {

   609   typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;

   610   typedef typename _Base::allocator_type allocator_type;

   612   rb_tree()

   613      : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(_Compare(), allocator_type()) {}

   614   rb_tree(const _Compare& __comp,

   615           const allocator_type& __a = allocator_type())

   616     : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(__comp, __a) {}

   617   ~rb_tree() {}

   618 };

   619 _STLP_END_NAMESPACE

   621 #endif /* _STLP_INTERNAL_TREE_H */

   623 // Local Variables:

   624 // mode:C++

   625 // End:

author	William Roberts <williamr@symbian.org>
	Tue, 16 Mar 2010 16:12:26 +0000
branch	Symbian2
changeset 2	2fe1408b6811
parent 0	061f57f2323e
permissions	-rw-r--r--