Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 10:26:02 

0001 // modified from  stl RBtree
0002 // https://gcc.gnu.org/onlinedocs/gcc-4.9.3/libstdc++/api/a01266.html
0003 // removed allocator
0004 // added CUDA annotations
0005 // added less and pair structs
0006 
0007 #ifndef VECCORE_RB_TREE_H
0008 #define VECCORE_RB_TREE_H
0009 #include <exception>
0010 #include <iostream>
0011 #include <cstddef>
0012 #include "VecGeom/base/Global.h"
0013 
0014 namespace vecgeom {
0015 VECGEOM_DEVICE_FORWARD_DECLARE(template <typename Type> class _Rb_tree;);
0016 
0017 inline namespace VECGEOM_IMPL_NAMESPACE {
0018 template <class T>
0019 struct less {
0020   VECCORE_ATT_HOST_DEVICE
0021   bool operator()(const T &x, const T &y) const { return x < y; }
0022   typedef T first_argument_type;
0023   typedef T second_argument_type;
0024   typedef bool result_type;
0025 };
0026 
0027 ///// re-implemeting std::pair struct to compile RBTree and map for CUDA
0028 
0029 template <class T1, class T2>
0030 struct pair {
0031   typedef T1 first_type;
0032   typedef T2 second_type;
0033 
0034   T1 first;
0035   T2 second;
0036 
0037   VECCORE_ATT_HOST_DEVICE
0038   pair() : first(), second() {}
0039 
0040   VECCORE_ATT_HOST_DEVICE
0041   pair(const pair &apair)
0042   {
0043     first  = apair.first;
0044     second = apair.second;
0045   };
0046   VECCORE_ATT_HOST_DEVICE
0047   pair(const T1 &x, const T2 &y)
0048   {
0049     first  = x;
0050     second = y;
0051   };
0052   VECCORE_ATT_HOST_DEVICE
0053   pair &operator=(const pair &p)
0054   {
0055     first  = p.first;
0056     second = p.second;
0057     return *this;
0058   };
0059 
0060   VECCORE_ATT_HOST_DEVICE
0061   friend bool operator<(const pair<T1, T2> &lhs, const pair<T1, T2> &rhs)
0062   {
0063     return lhs.first < rhs.first || (!(rhs.first < lhs.first) && lhs.second < rhs.second);
0064   };
0065 
0066   VECCORE_ATT_HOST_DEVICE
0067   void swap(pair &p)
0068   {
0069     T1 temp = p.first;
0070     first   = p.second;
0071     second  = temp;
0072   };
0073 };
0074 typedef bool _Rb_tree_Color_type;
0075 const _Rb_tree_Color_type _S_rb_tree_red   = false;
0076 const _Rb_tree_Color_type _S_rb_tree_black = true;
0077 
0078 struct _Rb_tree_node_base {
0079   typedef _Rb_tree_Color_type _Color_type;
0080   typedef _Rb_tree_node_base *_Base_ptr;
0081 
0082   _Color_type _M_color;
0083   _Base_ptr _M_parent;
0084   _Base_ptr _M_left;
0085   _Base_ptr _M_right;
0086 
0087   VECCORE_ATT_HOST_DEVICE
0088   static _Base_ptr _S_minimum(_Base_ptr __x)
0089   {
0090     while (__x->_M_left != 0)
0091       __x = __x->_M_left;
0092     return __x;
0093   }
0094 
0095   VECCORE_ATT_HOST_DEVICE
0096   static _Base_ptr _S_maximum(_Base_ptr __x)
0097   {
0098     while (__x->_M_right != 0)
0099       __x = __x->_M_right;
0100     return __x;
0101   }
0102 };
0103 
0104 template <class _Value>
0105 struct _Rb_tree_node : public _Rb_tree_node_base {
0106   typedef _Rb_tree_node<_Value> *_Link_type;
0107   _Value _M_value_field;
0108 
0109   VECCORE_ATT_HOST_DEVICE
0110   _Value get_value() { return _M_value_field; };
0111   VECCORE_ATT_HOST_DEVICE
0112   void set_value(_Value _new_value) { _M_value_field = _new_value; };
0113 };
0114 
0115 struct _Rb_tree_base_iterator {
0116   typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
0117   typedef ptrdiff_t difference_type;
0118   _Base_ptr _M_node;
0119 
0120   VECCORE_ATT_HOST_DEVICE
0121   void _M_increment()
0122   {
0123     if (_M_node->_M_right != 0) {
0124       _M_node = _M_node->_M_right;
0125       while (_M_node->_M_left != 0)
0126         _M_node = _M_node->_M_left;
0127     } else {
0128       _Base_ptr __y = _M_node->_M_parent;
0129       while (_M_node == __y->_M_right) {
0130         _M_node = __y;
0131         __y     = __y->_M_parent;
0132       }
0133       if (_M_node->_M_right != __y) _M_node = __y;
0134     }
0135   }
0136 
0137   VECCORE_ATT_HOST_DEVICE
0138   void _M_decrement()
0139   {
0140     if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node)
0141       _M_node = _M_node->_M_right;
0142     else if (_M_node->_M_left != 0) {
0143       _Base_ptr __y = _M_node->_M_left;
0144       while (__y->_M_right != 0)
0145         __y   = __y->_M_right;
0146       _M_node = __y;
0147     } else {
0148       _Base_ptr __y = _M_node->_M_parent;
0149       while (_M_node == __y->_M_left) {
0150         _M_node = __y;
0151         __y     = __y->_M_parent;
0152       }
0153       _M_node = __y;
0154     }
0155   }
0156 };
0157 
0158 template <class _Value, class _Ref, class _Ptr>
0159 struct _Rb_tree_iterator : public _Rb_tree_base_iterator {
0160   typedef _Value value_type;
0161   typedef _Ref reference;
0162   typedef _Ptr pointer;
0163   typedef _Rb_tree_iterator<_Value, _Value &, _Value *> iterator;
0164   typedef _Rb_tree_iterator<_Value, const _Value &, const _Value *> const_iterator;
0165   typedef _Rb_tree_iterator<_Value, _Ref, _Ptr> _Self;
0166   typedef _Rb_tree_node<_Value> *_Link_type;
0167 
0168   VECCORE_ATT_HOST_DEVICE
0169   _Rb_tree_iterator() {}
0170   VECCORE_ATT_HOST_DEVICE
0171   _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
0172   VECCORE_ATT_HOST_DEVICE
0173   _Rb_tree_iterator(const iterator &__it) { _M_node = __it._M_node; }
0174 
0175   VECCORE_ATT_HOST_DEVICE
0176   reference operator*() const { return _Link_type(_M_node)->_M_value_field; }
0177   VECCORE_ATT_HOST_DEVICE
0178   pointer operator->() const { return &(operator*()); }
0179 
0180   VECCORE_ATT_HOST_DEVICE
0181   _Self &operator++()
0182   {
0183     _M_increment();
0184     return *this;
0185   }
0186   VECCORE_ATT_HOST_DEVICE
0187   _Self operator++(int)
0188   {
0189     _Self __tmp = *this;
0190     _M_increment();
0191     return __tmp;
0192   }
0193 
0194   VECCORE_ATT_HOST_DEVICE
0195   _Self &operator--()
0196   {
0197     _M_decrement();
0198     return *this;
0199   }
0200   VECCORE_ATT_HOST_DEVICE
0201   _Self operator--(int)
0202   {
0203     _Self __tmp = *this;
0204     _M_decrement();
0205     return __tmp;
0206   }
0207 };
0208 
0209 VECCORE_ATT_HOST_DEVICE
0210 inline bool operator==(const _Rb_tree_base_iterator &__x, const _Rb_tree_base_iterator &__y)
0211 {
0212   return __x._M_node == __y._M_node;
0213 }
0214 
0215 VECCORE_ATT_HOST_DEVICE
0216 inline bool operator!=(const _Rb_tree_base_iterator &__x, const _Rb_tree_base_iterator &__y)
0217 {
0218   return __x._M_node != __y._M_node;
0219 }
0220 
0221 VECCORE_ATT_HOST_DEVICE
0222 inline _Rb_tree_base_iterator::difference_type *distance_type(const _Rb_tree_base_iterator &)
0223 {
0224   return (_Rb_tree_base_iterator::difference_type *)0;
0225 }
0226 
0227 template <class _Value, class _Ref, class _Ptr>
0228 VECCORE_ATT_HOST_DEVICE
0229 inline _Value *value_type(const _Rb_tree_iterator<_Value, _Ref, _Ptr> &)
0230 {
0231   return (_Value *)0;
0232 }
0233 
0234 VECCORE_ATT_HOST_DEVICE
0235 inline void _Rb_tree_rotate_left(_Rb_tree_node_base *__x, _Rb_tree_node_base *&__root)
0236 {
0237   _Rb_tree_node_base *__y                        = __x->_M_right;
0238   __x->_M_right                                  = __y->_M_left;
0239   if (__y->_M_left != 0) __y->_M_left->_M_parent = __x;
0240   __y->_M_parent                                 = __x->_M_parent;
0241 
0242   if (__x == __root)
0243     __root = __y;
0244   else if (__x == __x->_M_parent->_M_left)
0245     __x->_M_parent->_M_left = __y;
0246   else
0247     __x->_M_parent->_M_right = __y;
0248   __y->_M_left               = __x;
0249   __x->_M_parent             = __y;
0250 }
0251 
0252 VECCORE_ATT_HOST_DEVICE
0253 inline void _Rb_tree_rotate_right(_Rb_tree_node_base *__x, _Rb_tree_node_base *&__root)
0254 {
0255   _Rb_tree_node_base *__y                          = __x->_M_left;
0256   __x->_M_left                                     = __y->_M_right;
0257   if (__y->_M_right != 0) __y->_M_right->_M_parent = __x;
0258   __y->_M_parent                                   = __x->_M_parent;
0259 
0260   if (__x == __root)
0261     __root = __y;
0262   else if (__x == __x->_M_parent->_M_right)
0263     __x->_M_parent->_M_right = __y;
0264   else
0265     __x->_M_parent->_M_left = __y;
0266   __y->_M_right             = __x;
0267   __x->_M_parent            = __y;
0268 }
0269 
0270 VECCORE_ATT_HOST_DEVICE
0271 inline void _Rb_tree_rebalance(_Rb_tree_node_base *__x, _Rb_tree_node_base *&__root)
0272 {
0273   __x->_M_color = _S_rb_tree_red;
0274   while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
0275     if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
0276       _Rb_tree_node_base *__y = __x->_M_parent->_M_parent->_M_right;
0277       if (__y && __y->_M_color == _S_rb_tree_red) {
0278         __x->_M_parent->_M_color            = _S_rb_tree_black;
0279         __y->_M_color                       = _S_rb_tree_black;
0280         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
0281         __x                                 = __x->_M_parent->_M_parent;
0282       } else {
0283         if (__x == __x->_M_parent->_M_right) {
0284           __x = __x->_M_parent;
0285           _Rb_tree_rotate_left(__x, __root);
0286         }
0287         __x->_M_parent->_M_color            = _S_rb_tree_black;
0288         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
0289         _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
0290       }
0291     } else {
0292       _Rb_tree_node_base *__y = __x->_M_parent->_M_parent->_M_left;
0293       if (__y && __y->_M_color == _S_rb_tree_red) {
0294         __x->_M_parent->_M_color            = _S_rb_tree_black;
0295         __y->_M_color                       = _S_rb_tree_black;
0296         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
0297         __x                                 = __x->_M_parent->_M_parent;
0298       } else {
0299         if (__x == __x->_M_parent->_M_left) {
0300           __x = __x->_M_parent;
0301           _Rb_tree_rotate_right(__x, __root);
0302         }
0303         __x->_M_parent->_M_color            = _S_rb_tree_black;
0304         __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
0305         _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
0306       }
0307     }
0308   }
0309   __root->_M_color = _S_rb_tree_black;
0310 }
0311 
0312 VECCORE_ATT_HOST_DEVICE
0313 inline _Rb_tree_node_base *_Rb_tree_rebalance_for_erase(_Rb_tree_node_base *__z, _Rb_tree_node_base *&__root,
0314                                                         _Rb_tree_node_base *&__leftmost,
0315                                                         _Rb_tree_node_base *&__rightmost)
0316 {
0317   _Rb_tree_node_base *__y        = __z;
0318   _Rb_tree_node_base *__x        = 0;
0319   _Rb_tree_node_base *__x_parent = 0;
0320   if (__y->_M_left == 0)       // __z has at most one non-null child. y == z.
0321     __x = __y->_M_right;       // __x might be null.
0322   else if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
0323     __x = __y->_M_left;        // __x is not null.
0324   else {                       // __z has two non-null children.  Set __y to
0325     __y = __y->_M_right;       //   __z's successor.  __x might be null.
0326     while (__y->_M_left != 0)
0327       __y = __y->_M_left;
0328     __x   = __y->_M_right;
0329   }
0330   if (__y != __z) { // relink y in place of z.  y is z's successor
0331     __z->_M_left->_M_parent = __y;
0332     __y->_M_left            = __z->_M_left;
0333     if (__y != __z->_M_right) {
0334       __x_parent               = __y->_M_parent;
0335       if (__x) __x->_M_parent  = __y->_M_parent;
0336       __y->_M_parent->_M_left  = __x; // __y must be a child of _M_left
0337       __y->_M_right            = __z->_M_right;
0338       __z->_M_right->_M_parent = __y;
0339     } else
0340       __x_parent = __y;
0341     if (__root == __z)
0342       __root = __y;
0343     else if (__z->_M_parent->_M_left == __z)
0344       __z->_M_parent->_M_left = __y;
0345     else
0346       __z->_M_parent->_M_right = __y;
0347     __y->_M_parent             = __z->_M_parent;
0348     bool tmp_swap              = __y->_M_color;
0349     __y->_M_color              = __z->_M_color;
0350     __z->_M_color              = tmp_swap;
0351     //_Rb_tree_swap(__y->_M_color, __z->_M_color);
0352     __y = __z;
0353     // __y now points to node to be actually deleted
0354   } else { // __y == __z
0355     __x_parent              = __y->_M_parent;
0356     if (__x) __x->_M_parent = __y->_M_parent;
0357     if (__root == __z)
0358       __root = __x;
0359     else {
0360       if (__z->_M_parent->_M_left == __z)
0361         __z->_M_parent->_M_left = __x;
0362       else
0363         __z->_M_parent->_M_right = __x;
0364     }
0365     if (__leftmost == __z) {
0366       if (__z->_M_right == 0) // __z->_M_left must be null also
0367         __leftmost = __z->_M_parent;
0368       // makes __leftmost == _M_header if __z == __root
0369       else
0370         __leftmost = _Rb_tree_node_base::_S_minimum(__x);
0371     }
0372     if (__rightmost == __z) {
0373       if (__z->_M_left == 0) // __z->_M_right must be null also
0374         __rightmost = __z->_M_parent;
0375       // makes __rightmost == _M_header if __z == __root
0376       else // __x == __z->_M_left
0377         __rightmost = _Rb_tree_node_base::_S_maximum(__x);
0378     }
0379   }
0380   if (__y->_M_color != _S_rb_tree_red) {
0381     while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
0382       if (__x == __x_parent->_M_left) {
0383         _Rb_tree_node_base *__w = __x_parent->_M_right;
0384         if (__w->_M_color == _S_rb_tree_red) {
0385           __w->_M_color        = _S_rb_tree_black;
0386           __x_parent->_M_color = _S_rb_tree_red;
0387           _Rb_tree_rotate_left(__x_parent, __root);
0388           __w = __x_parent->_M_right;
0389         }
0390         if ((__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black) &&
0391             (__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black)) {
0392           __w->_M_color = _S_rb_tree_red;
0393           __x           = __x_parent;
0394           __x_parent    = __x_parent->_M_parent;
0395         } else {
0396           if (__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black) {
0397             if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
0398             __w->_M_color                            = _S_rb_tree_red;
0399             _Rb_tree_rotate_right(__w, __root);
0400             __w = __x_parent->_M_right;
0401           }
0402           __w->_M_color                              = __x_parent->_M_color;
0403           __x_parent->_M_color                       = _S_rb_tree_black;
0404           if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
0405           _Rb_tree_rotate_left(__x_parent, __root);
0406           break;
0407         }
0408       } else { // same as above, with _M_right <-> _M_left.
0409         _Rb_tree_node_base *__w = __x_parent->_M_left;
0410         if (__w->_M_color == _S_rb_tree_red) {
0411           __w->_M_color        = _S_rb_tree_black;
0412           __x_parent->_M_color = _S_rb_tree_red;
0413           _Rb_tree_rotate_right(__x_parent, __root);
0414           __w = __x_parent->_M_left;
0415         }
0416         if ((__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black) &&
0417             (__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black)) {
0418           __w->_M_color = _S_rb_tree_red;
0419           __x           = __x_parent;
0420           __x_parent    = __x_parent->_M_parent;
0421         } else {
0422           if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black) {
0423             if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
0424             __w->_M_color                              = _S_rb_tree_red;
0425             _Rb_tree_rotate_left(__w, __root);
0426             __w = __x_parent->_M_left;
0427           }
0428           __w->_M_color                            = __x_parent->_M_color;
0429           __x_parent->_M_color                     = _S_rb_tree_black;
0430           if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
0431           _Rb_tree_rotate_right(__x_parent, __root);
0432           break;
0433         }
0434       }
0435     if (__x) __x->_M_color = _S_rb_tree_black;
0436   }
0437   return __y;
0438 }
0439 
0440 // Base class to encapsulate the differences between old SGI-style
0441 // allocators and standard-conforming allocators.  In order to avoid
0442 // having an empty base class, we arbitrarily move one of rb_tree's
0443 // data members into the base class.
0444 
0445 template <class _Tp>
0446 struct _Rb_tree_base {
0447 
0448   VECCORE_ATT_HOST_DEVICE
0449   _Rb_tree_base() : _M_header(0) { _M_header = new _Rb_tree_node<_Tp>; }
0450   VECCORE_ATT_HOST_DEVICE
0451   ~_Rb_tree_base() { delete _M_header; }
0452 protected:
0453   _Rb_tree_node<_Tp> *_M_header;
0454 };
0455 
0456 template <class _Key, class _Value, class _KeyOfValue, class _Compare = less<_Key>>
0457 class _Rb_tree : protected _Rb_tree_base<_Value> {
0458   typedef _Rb_tree_base<_Value> _Base;
0459 
0460 protected:
0461   typedef _Rb_tree_node_base *_Base_ptr;
0462   // typedef _Rb_tree_node<_Value> _Rb_tree_node;
0463   typedef _Rb_tree_Color_type _Color_type;
0464 
0465 public:
0466   typedef _Key key_type;
0467   typedef _Value value_type;
0468   typedef value_type *pointer;
0469   typedef const value_type *const_pointer;
0470   typedef value_type &reference;
0471   typedef const value_type &const_reference;
0472 #if !defined(VECCORE_CUDA) && !defined(__INTEL_COMPILER)
0473   typedef __attribute__((__may_alias__)) _Rb_tree_node<_Value> *_Link_type;
0474 #else
0475   typedef _Rb_tree_node<_Value> *_Link_type;
0476 #endif
0477   typedef size_t size_type;
0478   typedef ptrdiff_t difference_type;
0479 
0480 protected:
0481   VECCORE_ATT_HOST_DEVICE
0482   _Link_type _M_create_node(const value_type &__x)
0483   {
0484     _Link_type __tmp = new _Rb_tree_node<value_type>;
0485     //__tmp->_M_value_field = __x ;
0486     __tmp->set_value(__x);
0487     return __tmp;
0488   }
0489 
0490   VECCORE_ATT_HOST_DEVICE
0491   _Link_type _M_clone_node(_Link_type __x)
0492   {
0493     _Link_type __tmp = _M_create_node(__x->_M_value_field);
0494     __tmp->_M_color  = __x->_M_color;
0495     __tmp->_M_left   = 0;
0496     __tmp->_M_right  = 0;
0497     return __tmp;
0498   }
0499 
0500   VECCORE_ATT_HOST_DEVICE
0501   void destroy_node(_Link_type __p)
0502   {
0503     // (__p->_M_value_field).~_Value();
0504     // delete(&__p->_M_value_field);
0505     //&__p->~_Value();
0506     delete __p;
0507   }
0508 
0509 protected:
0510   size_type _M_node_count; // keeps track of size of tree
0511   _Compare _M_key_compare;
0512 
0513   VECCORE_ATT_HOST_DEVICE
0514   _Link_type &_M_root() const { return (_Link_type &)_Base::_M_header->_M_parent; }
0515   VECCORE_ATT_HOST_DEVICE
0516   _Link_type &_M_leftmost() const { return (_Link_type &)_Base::_M_header->_M_left; }
0517   VECCORE_ATT_HOST_DEVICE
0518   _Link_type &_M_rightmost() const { return (_Link_type &)_Base::_M_header->_M_right; }
0519 
0520   VECCORE_ATT_HOST_DEVICE
0521   static _Link_type &_S_left(_Link_type __x) { return (_Link_type &)(__x->_M_left); }
0522   VECCORE_ATT_HOST_DEVICE
0523   static _Link_type &_S_right(_Link_type __x) { return (_Link_type &)(__x->_M_right); }
0524   VECCORE_ATT_HOST_DEVICE
0525   static _Link_type &_S_parent(_Link_type __x) { return (_Link_type &)(__x->_M_parent); }
0526   VECCORE_ATT_HOST_DEVICE
0527   static reference _S_value(_Link_type __x) { return __x->_M_value_field; }
0528   VECCORE_ATT_HOST_DEVICE
0529   static const _Key &_S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
0530   VECCORE_ATT_HOST_DEVICE
0531   static _Color_type &_S_color(_Link_type __x) { return (_Color_type &)(__x->_M_color); }
0532 
0533   VECCORE_ATT_HOST_DEVICE
0534   static _Link_type &_S_left(_Base_ptr __x) { return (_Link_type &)(__x->_M_left); }
0535   VECCORE_ATT_HOST_DEVICE
0536   static _Link_type &_S_right(_Base_ptr __x) { return (_Link_type &)(__x->_M_right); }
0537   VECCORE_ATT_HOST_DEVICE
0538   static _Link_type &_S_parent(_Base_ptr __x) { return (_Link_type &)(__x->_M_parent); }
0539   VECCORE_ATT_HOST_DEVICE
0540   static reference _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; }
0541   VECCORE_ATT_HOST_DEVICE
0542   static const _Key &_S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x))); }
0543   VECCORE_ATT_HOST_DEVICE
0544   static _Color_type &_S_color(_Base_ptr __x) { return (_Color_type &)(_Link_type(__x)->_M_color); }
0545 
0546   VECCORE_ATT_HOST_DEVICE
0547   static _Link_type _S_minimum(_Link_type __x) { return (_Link_type)_Rb_tree_node_base::_S_minimum(__x); }
0548 
0549   VECCORE_ATT_HOST_DEVICE
0550   static _Link_type _S_maximum(_Link_type __x) { return (_Link_type)_Rb_tree_node_base::_S_maximum(__x); }
0551 
0552 public:
0553   typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
0554   typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> const_iterator;
0555   /*
0556     typedef reverse_iterator<const_iterator> const_reverse_iterator;
0557     typedef reverse_iterator<iterator> reverse_iterator;
0558   */
0559 
0560 private:
0561   VECCORE_ATT_HOST_DEVICE
0562   iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type &__v);
0563   VECCORE_ATT_HOST_DEVICE
0564   _Link_type _M_copy(_Link_type __x, _Link_type __p);
0565   VECCORE_ATT_HOST_DEVICE
0566   void _M_erase(_Link_type __x);
0567 
0568 public:
0569   // allocation/deallocation
0570   VECCORE_ATT_HOST_DEVICE
0571   _Rb_tree() : _Base(), _M_node_count(0), _M_key_compare() { _M_empty_initialize(); }
0572 
0573   VECCORE_ATT_HOST_DEVICE
0574   _Rb_tree(const _Compare &__comp) : _Base(), _M_node_count(0)
0575   {
0576     _M_key_compare = __comp;
0577     _M_empty_initialize();
0578   }
0579 
0580   VECCORE_ATT_HOST_DEVICE
0581   _Rb_tree(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x)
0582       : _Base(), _M_node_count(0), _M_key_compare(__x._M_key_compare)
0583   {
0584     if (__x._M_root() == 0)
0585       _M_empty_initialize();
0586     else {
0587       _S_color(_Base::_M_header) = _S_rb_tree_red;
0588       _M_root()                  = _M_copy(__x._M_root(), _Base::_M_header);
0589       _M_leftmost()              = _S_minimum(_M_root());
0590       _M_rightmost()             = _S_maximum(_M_root());
0591     }
0592     _M_node_count = __x._M_node_count;
0593   }
0594   VECCORE_ATT_HOST_DEVICE
0595   ~_Rb_tree() { clear(); }
0596   VECCORE_ATT_HOST_DEVICE
0597   _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &operator=(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x);
0598 
0599   template <class Tsofia>
0600   VECCORE_ATT_HOST_DEVICE
0601   inline void _Rb_tree_swap(Tsofia &a, Tsofia &b)
0602   {
0603     Tsofia tmp = *a;
0604     *a         = *b;
0605     *b         = tmp;
0606   }
0607 
0608 private:
0609   VECCORE_ATT_HOST_DEVICE
0610   void _M_empty_initialize()
0611   {
0612     _S_color(_Base::_M_header) = _S_rb_tree_red; // used to distinguish header from
0613                                                  // __root, in iterator.operator++
0614     _M_root()      = 0;
0615     _M_leftmost()  = _Base::_M_header;
0616     _M_rightmost() = _Base::_M_header;
0617   }
0618 
0619 public:
0620   // accessors:
0621   VECCORE_ATT_HOST_DEVICE
0622   _Compare key_comp() const { return _M_key_compare; }
0623   VECCORE_ATT_HOST_DEVICE
0624   iterator begin() { return _M_leftmost(); }
0625   VECCORE_ATT_HOST_DEVICE
0626   const_iterator begin() const { return _M_leftmost(); }
0627   VECCORE_ATT_HOST_DEVICE
0628   iterator end() { return _Base::_M_header; }
0629   VECCORE_ATT_HOST_DEVICE
0630   const_iterator end() const { return _Base::_M_header; }
0631   /*
0632     reverse_iterator rbegin() { return reverse_iterator(end()); }
0633     const_reverse_iterator rbegin() const {
0634       return const_reverse_iterator(end());
0635     }
0636     reverse_iterator rend() { return reverse_iterator(begin()); }
0637     const_reverse_iterator rend() const {
0638       return const_reverse_iterator(begin());
0639     }
0640   */
0641   VECCORE_ATT_HOST_DEVICE
0642   bool empty() const { return _M_node_count == 0; }
0643   VECCORE_ATT_HOST_DEVICE
0644   size_type size() const { return _M_node_count; }
0645   VECCORE_ATT_HOST_DEVICE
0646   size_type max_size() const { return size_type(-1); }
0647 
0648   VECCORE_ATT_HOST_DEVICE
0649   inline void _Rb_tree_swap(_Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__t)
0650   {
0651     _Rb_tree_swap(_Base::_M_header, __t._Base::_M_header);
0652     _Rb_tree_swap(_M_node_count, __t._M_node_count);
0653     _Rb_tree_swap(_M_key_compare, __t._M_key_compare);
0654   }
0655 
0656 public:
0657   // insert/erase
0658   VECCORE_ATT_HOST_DEVICE
0659   pair<iterator, bool> insert_unique(const value_type &__x);
0660   VECCORE_ATT_HOST_DEVICE
0661   iterator insert_equal(const value_type &__x);
0662 
0663   VECCORE_ATT_HOST_DEVICE
0664   iterator insert_unique(iterator __position, const value_type &__x);
0665   VECCORE_ATT_HOST_DEVICE
0666   iterator insert_equal(iterator __position, const value_type &__x);
0667 
0668   VECCORE_ATT_HOST_DEVICE
0669   void insert_unique(const_iterator __first, const_iterator __last);
0670   VECCORE_ATT_HOST_DEVICE
0671   void insert_unique(const value_type *__first, const value_type *__last);
0672   VECCORE_ATT_HOST_DEVICE
0673   void insert_equal(const_iterator __first, const_iterator __last);
0674   VECCORE_ATT_HOST_DEVICE
0675   void insert_equal(const value_type *__first, const value_type *__last);
0676 
0677   VECCORE_ATT_HOST_DEVICE
0678   void erase(iterator __position);
0679   VECCORE_ATT_HOST_DEVICE
0680   size_type erase(const key_type &__x);
0681   VECCORE_ATT_HOST_DEVICE
0682   void erase(iterator __first, iterator __last);
0683   VECCORE_ATT_HOST_DEVICE
0684   void erase(const key_type *__first, const key_type *__last);
0685   VECCORE_ATT_HOST_DEVICE
0686   void clear()
0687   {
0688     if (_M_node_count != 0) {
0689       _M_erase(_M_root());
0690       _M_leftmost()  = _Base::_M_header;
0691       _M_root()      = 0;
0692       _M_rightmost() = _Base::_M_header;
0693       _M_node_count  = 0;
0694     }
0695   }
0696 
0697 public:
0698   // set operations:
0699   VECCORE_ATT_HOST_DEVICE
0700   iterator find(const key_type &__x);
0701   VECCORE_ATT_HOST_DEVICE
0702   const_iterator find(const key_type &__x) const;
0703   VECCORE_ATT_HOST_DEVICE
0704   size_type count(const key_type &__x) const;
0705   VECCORE_ATT_HOST_DEVICE
0706   iterator lower_bound(const key_type &__x);
0707   VECCORE_ATT_HOST_DEVICE
0708   const_iterator lower_bound(const key_type &__x) const;
0709   VECCORE_ATT_HOST_DEVICE
0710   iterator upper_bound(const key_type &__x);
0711   VECCORE_ATT_HOST_DEVICE
0712   const_iterator upper_bound(const key_type &__x) const;
0713   VECCORE_ATT_HOST_DEVICE
0714   pair<iterator, iterator> equal_range(const key_type &__x);
0715   VECCORE_ATT_HOST_DEVICE
0716   pair<const_iterator, const_iterator> equal_range(const key_type &__x) const;
0717 
0718 public:
0719   // Debugging.
0720   VECCORE_ATT_HOST_DEVICE
0721   bool __rb_verify() const;
0722 };
0723 
0724 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0725 VECCORE_ATT_HOST_DEVICE
0726 inline bool operator==(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x,
0727                        const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__y)
0728 {
0729   return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin());
0730 }
0731 
0732 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0733 VECCORE_ATT_HOST_DEVICE
0734 inline bool operator<(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x,
0735                       const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__y)
0736 {
0737 
0738   return lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
0739 }
0740 
0741 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0742 VECCORE_ATT_HOST_DEVICE
0743 inline bool operator!=(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x,
0744                        const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__y)
0745 {
0746   return !(__x == __y);
0747 }
0748 
0749 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0750 VECCORE_ATT_HOST_DEVICE
0751 inline bool operator>(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x,
0752                       const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__y)
0753 {
0754   return __y < __x;
0755 }
0756 
0757 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0758 VECCORE_ATT_HOST_DEVICE
0759 inline bool operator<=(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x,
0760                        const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__y)
0761 {
0762   return !(__y < __x);
0763 }
0764 
0765 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0766 VECCORE_ATT_HOST_DEVICE
0767 inline bool operator>=(const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x,
0768                        const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__y)
0769 {
0770   return !(__x < __y);
0771 }
0772 
0773 /*
0774 template <class _Key, class _Value, class _KeyOfValue,
0775           class _Compare>
0776 VECCORE_ATT_HOST_DEVICE
0777 void
0778 _Rb_tree_swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare>& __x,
0779      _Rb_tree<_Key,_Value,_KeyOfValue,_Compare>& __y)
0780 {
0781   __x.swap(__y);
0782 }
0783 */
0784 
0785 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0786 VECCORE_ATT_HOST_DEVICE
0787 _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &_Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::operator=(
0788     const _Rb_tree<_Key, _Value, _KeyOfValue, _Compare> &__x)
0789 {
0790   if (this != &__x) {
0791     // Note that _Key may be a constant type.
0792     clear();
0793     _M_node_count  = 0;
0794     _M_key_compare = __x._M_key_compare;
0795     if (__x._M_root() == 0) {
0796       _M_root()      = 0;
0797       _M_leftmost()  = _Base::_M_header;
0798       _M_rightmost() = _Base::_M_header;
0799     } else {
0800       _M_root()      = _M_copy(__x._M_root(), _Base::_M_header);
0801       _M_leftmost()  = _S_minimum(_M_root());
0802       _M_rightmost() = _S_maximum(_M_root());
0803       _M_node_count  = __x._M_node_count;
0804     }
0805   }
0806   return *this;
0807 }
0808 
0809 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0810 VECCORE_ATT_HOST_DEVICE
0811 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator _Rb_tree<_Key, _Value, _KeyOfValue,
0812                                                                           _Compare>::_M_insert(_Base_ptr __x_,
0813                                                                                                _Base_ptr __y_,
0814                                                                                                const _Value &__v)
0815 {
0816   _Link_type __x = (_Link_type)__x_;
0817   _Link_type __y = (_Link_type)__y_;
0818   _Link_type __z;
0819 
0820   if (__y == _Base::_M_header || __x != 0 || _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
0821     __z          = _M_create_node(__v);
0822     _S_left(__y) = __z; // also makes _M_leftmost() = __z
0823                         //    when __y == _M_header
0824     if (__y == _Base::_M_header) {
0825       _M_root()      = __z;
0826       _M_rightmost() = __z;
0827     } else if (__y == _M_leftmost())
0828       _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
0829   } else {
0830     __z                                       = _M_create_node(__v);
0831     _S_right(__y)                             = __z;
0832     if (__y == _M_rightmost()) _M_rightmost() = __z; // maintain _M_rightmost() pointing to max node
0833   }
0834   _S_parent(__z) = __y;
0835   _S_left(__z)   = 0;
0836   _S_right(__z)  = 0;
0837   _Rb_tree_rebalance(__z, _Base::_M_header->_M_parent);
0838   ++_M_node_count;
0839   return iterator(__z);
0840 }
0841 
0842 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0843 VECCORE_ATT_HOST_DEVICE
0844 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator _Rb_tree<_Key, _Value, _KeyOfValue,
0845                                                                           _Compare>::insert_equal(const _Value &__v)
0846 {
0847   _Link_type __y = _Base::_M_header;
0848   _Link_type __x = _M_root();
0849   while (__x != 0) {
0850     __y = __x;
0851     __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? _S_left(__x) : _S_right(__x);
0852   }
0853   return _M_insert(__x, __y, __v);
0854 }
0855 
0856 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0857 VECCORE_ATT_HOST_DEVICE
0858 pair<typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator, bool> _Rb_tree<
0859     _Key, _Value, _KeyOfValue, _Compare>::insert_unique(const _Value &__v)
0860 {
0861   _Link_type __y = _Base::_M_header;
0862   _Link_type __x = _M_root();
0863   bool __comp    = true;
0864   while (__x != 0) {
0865     __y    = __x;
0866     __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
0867     __x    = __comp ? _S_left(__x) : _S_right(__x);
0868   }
0869   iterator __j = iterator(__y);
0870   if (__comp) {
0871     if (__j == begin())
0872       return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
0873     else
0874       --__j;
0875   }
0876   if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
0877     return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
0878   return pair<iterator, bool>(__j, false);
0879 }
0880 
0881 template <class _Key, class _Val, class _KeyOfValue, class _Compare>
0882 VECCORE_ATT_HOST_DEVICE
0883 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare>::iterator _Rb_tree<_Key, _Val, _KeyOfValue,
0884                                                                         _Compare>::insert_unique(iterator __position,
0885                                                                                                  const _Val &__v)
0886 {
0887   if (__position._M_node == _Base::_M_header->_M_left) { // begin()
0888     if (size() > 0 && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
0889       return _M_insert(__position._M_node, __position._M_node, __v);
0890     // first argument just needs to be non-null
0891     else
0892       return insert_unique(__v).first;
0893   } else if (__position._M_node == _Base::_M_header) { // end()
0894     if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
0895       return _M_insert(0, _M_rightmost(), __v);
0896     else
0897       return insert_unique(__v).first;
0898   } else {
0899     iterator __before = __position;
0900     --__before;
0901     if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) &&
0902         _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) {
0903       if (_S_right(__before._M_node) == 0)
0904         return _M_insert(0, __before._M_node, __v);
0905       else
0906         return _M_insert(__position._M_node, __position._M_node, __v);
0907       // first argument just needs to be non-null
0908     } else
0909       return insert_unique(__v).first;
0910   }
0911 }
0912 
0913 template <class _Key, class _Val, class _KeyOfValue, class _Compare>
0914 VECCORE_ATT_HOST_DEVICE
0915 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare>::iterator _Rb_tree<_Key, _Val, _KeyOfValue,
0916                                                                         _Compare>::insert_equal(iterator __position,
0917                                                                                                 const _Val &__v)
0918 {
0919   if (__position._M_node == _Base::_M_header->_M_left) { // begin()
0920     if (size() > 0 && !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
0921       return _M_insert(__position._M_node, __position._M_node, __v);
0922     // first argument just needs to be non-null
0923     else
0924       return insert_equal(__v);
0925   } else if (__position._M_node == _Base::_M_header) { // end()
0926     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
0927       return _M_insert(0, _M_rightmost(), __v);
0928     else
0929       return insert_equal(__v);
0930   } else {
0931     iterator __before = __position;
0932     --__before;
0933     if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node)) &&
0934         !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) {
0935       if (_S_right(__before._M_node) == 0)
0936         return _M_insert(0, __before._M_node, __v);
0937       else
0938         return _M_insert(__position._M_node, __position._M_node, __v);
0939       // first argument just needs to be non-null
0940     } else
0941       return insert_equal(__v);
0942   }
0943 }
0944 
0945 template <class _Key, class _Val, class _KoV, class _Cmp>
0946 VECCORE_ATT_HOST_DEVICE
0947 void _Rb_tree<_Key, _Val, _KoV, _Cmp>::insert_equal(const _Val *__first, const _Val *__last)
0948 {
0949   for (; __first != __last; ++__first)
0950     insert_equal(*__first);
0951 }
0952 
0953 template <class _Key, class _Val, class _KoV, class _Cmp>
0954 VECCORE_ATT_HOST_DEVICE
0955 void _Rb_tree<_Key, _Val, _KoV, _Cmp>::insert_equal(const_iterator __first, const_iterator __last)
0956 {
0957   for (; __first != __last; ++__first)
0958     insert_equal(*__first);
0959 }
0960 
0961 template <class _Key, class _Val, class _KoV, class _Cmp>
0962 VECCORE_ATT_HOST_DEVICE
0963 void _Rb_tree<_Key, _Val, _KoV, _Cmp>::insert_unique(const _Val *__first, const _Val *__last)
0964 {
0965   for (; __first != __last; ++__first)
0966     insert_unique(*__first);
0967 }
0968 
0969 template <class _Key, class _Val, class _KoV, class _Cmp>
0970 VECCORE_ATT_HOST_DEVICE
0971 void _Rb_tree<_Key, _Val, _KoV, _Cmp>::insert_unique(const_iterator __first, const_iterator __last)
0972 {
0973   for (; __first != __last; ++__first)
0974     insert_unique(*__first);
0975 }
0976 
0977 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0978 VECCORE_ATT_HOST_DEVICE
0979 inline void _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::erase(iterator __position)
0980 {
0981   _Link_type __y = (_Link_type)_Rb_tree_rebalance_for_erase(__position._M_node, _Base::_M_header->_M_parent,
0982                                                             _Base::_M_header->_M_left, _Base::_M_header->_M_right);
0983   destroy_node(__y);
0984   --_M_node_count;
0985 }
0986 
0987 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
0988 VECCORE_ATT_HOST_DEVICE
0989 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::size_type _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::erase(
0990     const _Key &__x)
0991 {
0992   pair<iterator, iterator> __p = equal_range(__x);
0993   size_type __n = 0;
0994   distance(__p.first, __p.second, __n);
0995   erase(__p.first, __p.second);
0996   return __n;
0997 }
0998 
0999 template <class _Key, class _Val, class _KoV, class _Compare>
1000 VECCORE_ATT_HOST_DEVICE
1001 typename _Rb_tree<_Key, _Val, _KoV, _Compare>::_Link_type _Rb_tree<_Key, _Val, _KoV, _Compare>::_M_copy(_Link_type __x,
1002                                                                                                         _Link_type __p)
1003 {
1004   // structural copy.  __x and __p must be non-null.
1005   _Link_type __top = _M_clone_node(__x);
1006   __top->_M_parent = __p;
1007 
1008   if (__x->_M_right) __top->_M_right = _M_copy(_S_right(__x), __top);
1009   __p                                = __top;
1010   __x                                = _S_left(__x);
1011 
1012   while (__x != 0) {
1013     _Link_type __y                   = _M_clone_node(__x);
1014     __p->_M_left                     = __y;
1015     __y->_M_parent                   = __p;
1016     if (__x->_M_right) __y->_M_right = _M_copy(_S_right(__x), __y);
1017     __p                              = __y;
1018     __x                              = _S_left(__x);
1019   }
1020 
1021   return __top;
1022 }
1023 
1024 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1025 VECCORE_ATT_HOST_DEVICE
1026 void _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::_M_erase(_Link_type __x)
1027 {
1028   // erase without rebalancing
1029   while (__x != 0) {
1030     _M_erase(_S_right(__x));
1031     _Link_type __y = _S_left(__x);
1032     destroy_node(__x);
1033     __x = __y;
1034   }
1035 }
1036 
1037 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1038 VECCORE_ATT_HOST_DEVICE
1039 void _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::erase(iterator __first, iterator __last)
1040 {
1041   if (__first == begin() && __last == end())
1042     clear();
1043   else
1044     while (__first != __last)
1045       erase(__first++);
1046 }
1047 
1048 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1049 VECCORE_ATT_HOST_DEVICE
1050 void _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::erase(const _Key *__first, const _Key *__last)
1051 {
1052   while (__first != __last)
1053     erase(*__first++);
1054 }
1055 
1056 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1057 VECCORE_ATT_HOST_DEVICE
1058 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::find(
1059     const _Key &__k)
1060 {
1061   _Link_type __y = _Base::_M_header; // Last node which is not less than __k.
1062   _Link_type __x = _M_root();        // Current node.
1063 
1064   while (__x != 0)
1065     if (!_M_key_compare(_S_key(__x), __k))
1066       __y = __x, __x = _S_left(__x);
1067     else
1068       __x = _S_right(__x);
1069 
1070   iterator __j = iterator(__y);
1071   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
1072 }
1073 
1074 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1075 VECCORE_ATT_HOST_DEVICE
1076 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::const_iterator _Rb_tree<_Key, _Value, _KeyOfValue,
1077                                                                                 _Compare>::find(const _Key &__k) const
1078 {
1079   _Link_type __y = _Base::_M_header; /* Last node which is not less than __k. */
1080   _Link_type __x = _M_root();        /* Current node. */
1081 
1082   while (__x != 0) {
1083     if (!_M_key_compare(_S_key(__x), __k))
1084       __y = __x, __x = _S_left(__x);
1085     else
1086       __x = _S_right(__x);
1087   }
1088   const_iterator __j = const_iterator(__y);
1089   return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
1090 }
1091 
1092 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1093 VECCORE_ATT_HOST_DEVICE
1094 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::size_type _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::count(
1095     const _Key &__k) const
1096 {
1097   pair<const_iterator, const_iterator> __p = equal_range(__k);
1098   size_type __n = 0;
1099   distance(__p.first, __p.second, __n);
1100   return __n;
1101 }
1102 
1103 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1104 VECCORE_ATT_HOST_DEVICE
1105 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator _Rb_tree<_Key, _Value, _KeyOfValue,
1106                                                                           _Compare>::lower_bound(const _Key &__k)
1107 {
1108   _Link_type __y = _Base::_M_header; /* Last node which is not less than __k. */
1109   _Link_type __x = _M_root();        /* Current node. */
1110 
1111   while (__x != 0)
1112     if (!_M_key_compare(_S_key(__x), __k))
1113       __y = __x, __x = _S_left(__x);
1114     else
1115       __x = _S_right(__x);
1116 
1117   return iterator(__y);
1118 }
1119 
1120 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1121 VECCORE_ATT_HOST_DEVICE
1122 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::const_iterator _Rb_tree<
1123     _Key, _Value, _KeyOfValue, _Compare>::lower_bound(const _Key &__k) const
1124 {
1125   _Link_type __y = _Base::_M_header; /* Last node which is not less than __k. */
1126   _Link_type __x = _M_root();        /* Current node. */
1127 
1128   while (__x != 0)
1129     if (!_M_key_compare(_S_key(__x), __k))
1130       __y = __x, __x = _S_left(__x);
1131     else
1132       __x = _S_right(__x);
1133 
1134   return const_iterator(__y);
1135 }
1136 
1137 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1138 VECCORE_ATT_HOST_DEVICE
1139 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator _Rb_tree<_Key, _Value, _KeyOfValue,
1140                                                                           _Compare>::upper_bound(const _Key &__k)
1141 {
1142   _Link_type __y = _Base::_M_header; /* Last node which is greater than __k. */
1143   _Link_type __x = _M_root();        /* Current node. */
1144 
1145   while (__x != 0)
1146     if (_M_key_compare(__k, _S_key(__x)))
1147       __y = __x, __x = _S_left(__x);
1148     else
1149       __x = _S_right(__x);
1150 
1151   return iterator(__y);
1152 }
1153 
1154 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1155 VECCORE_ATT_HOST_DEVICE
1156 typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::const_iterator _Rb_tree<
1157     _Key, _Value, _KeyOfValue, _Compare>::upper_bound(const _Key &__k) const
1158 {
1159   _Link_type __y = _Base::_M_header; /* Last node which is greater than __k. */
1160   _Link_type __x = _M_root();        /* Current node. */
1161 
1162   while (__x != 0)
1163     if (_M_key_compare(__k, _S_key(__x)))
1164       __y = __x, __x = _S_left(__x);
1165     else
1166       __x = _S_right(__x);
1167 
1168   return const_iterator(__y);
1169 }
1170 
1171 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1172 VECCORE_ATT_HOST_DEVICE
1173 inline pair<typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator,
1174             typename _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::iterator>
1175 _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::equal_range(const _Key &__k)
1176 {
1177   return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k));
1178 }
1179 
1180 template <class _Key, class _Value, class _KoV, class _Compare>
1181 VECCORE_ATT_HOST_DEVICE
1182 inline pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare>::const_iterator,
1183             typename _Rb_tree<_Key, _Value, _KoV, _Compare>::const_iterator>
1184 _Rb_tree<_Key, _Value, _KoV, _Compare>::equal_range(const _Key &__k) const
1185 {
1186   return pair<const_iterator, const_iterator>(lower_bound(__k), upper_bound(__k));
1187 }
1188 
1189 VECCORE_ATT_HOST_DEVICE
1190 inline int __black_count(_Rb_tree_node_base *__node, _Rb_tree_node_base *__root)
1191 {
1192   if (__node == 0)
1193     return 0;
1194   else {
1195     int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
1196     if (__node == __root)
1197       return __bc;
1198     else
1199       return __bc + __black_count(__node->_M_parent, __root);
1200   }
1201 }
1202 
1203 template <class _Key, class _Value, class _KeyOfValue, class _Compare>
1204 VECCORE_ATT_HOST_DEVICE
1205 bool _Rb_tree<_Key, _Value, _KeyOfValue, _Compare>::__rb_verify() const
1206 {
1207   if (_M_node_count == 0 || begin() == end())
1208     return _M_node_count == 0 && begin() == end() && _Base::_M_header->_M_left == _Base::_M_header &&
1209            _Base::_M_header->_M_right == _Base::_M_header;
1210 
1211   int __len = __black_count(_M_leftmost(), _M_root());
1212   for (const_iterator __it = begin(); __it != end(); ++__it) {
1213     _Link_type __x = (_Link_type)__it._M_node;
1214     _Link_type __L = _S_left(__x);
1215     _Link_type __R = _S_right(__x);
1216 
1217     if (__x->_M_color == _S_rb_tree_red)
1218       if ((__L && __L->_M_color == _S_rb_tree_red) || (__R && __R->_M_color == _S_rb_tree_red)) return false;
1219 
1220     if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) return false;
1221     if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) return false;
1222 
1223     if (!__L && !__R && __black_count(__x, _M_root()) != __len) return false;
1224   }
1225 
1226   if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) return false;
1227   if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) return false;
1228 
1229   return true;
1230 }
1231 }
1232 }
1233 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!