VecGeom/base/Map.h

0001 // modified from stl map
0002 // https://gcc.gnu.org/onlinedocs/gcc-4.9.3/libstdc++/api/a01255.html
0003 //
0004 // removed allocators
0005 // removed inverted iterators
0006 // added CUDA annotations
0007 // added select1st struct
0008
0009 #ifndef VECCORE_MAP_H
0010 #define VECCORE_MAP_H
0011
0012 #include "RBTree.h"
0013 namespace vecgeom {
0014 // This fails because of the commas, we would need to use another (new) macro
0015 // VECGEOM_DEVICE_FORWARD_DECLARE(template <class _Key, class _Tp, class _Compare>  class map; );
0016 #ifndef VECCORE_CUDA
0017 namespace cuda {
0018 template <class _key>
0019 struct less;
0020 template <class _Key, class _Tp, class _Compare = cuda::less<_Key>>
0021 class map;
0022 }
0023 #endif
0024
0025 inline namespace VECGEOM_IMPL_NAMESPACE {
0026
0027 template <typename P>
0028 struct select1st {
0029   VECCORE_ATT_HOST_DEVICE
0030   typename P::first_type const &operator()(P const &p) const { return p.first; }
0031 };
0032
0033 template <class _Key, class _Tp, class _Compare = less<_Key>>
0034 class map;
0035
0036 template <class _Key, class _Tp, class _Compare>
0037 VECCORE_ATT_HOST_DEVICE
0038 inline bool operator==(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y);
0039
0040 template <class _Key, class _Tp, class _Compare>
0041 VECCORE_ATT_HOST_DEVICE
0042 inline bool operator<(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y);
0043
0044 template <class _Key, class _Tp, class _Compare>
0045 class map {
0046 public:
0047   // typedefs:
0048
0049   typedef _Key key_type;
0050   typedef _Tp data_type;
0051   typedef _Tp mapped_type;
0052   typedef vecgeom::pair<_Key, _Tp> value_type;
0053   typedef _Compare key_compare;
0054
0055   template <class Key, class T, class Compare>
0056   class value_compare {
0057     friend class map;
0058
0059   protected:
0060     Compare comp;
0061     VECCORE_ATT_HOST_DEVICE
0062     value_compare(Compare c) : comp(c) {}
0063   public:
0064     typedef bool result_type;
0065     typedef value_type first_argument_type;
0066     typedef value_type second_argument_type;
0067     VECCORE_ATT_HOST_DEVICE
0068     bool operator()(const value_type &x, const value_type &y) const { return comp(x.first, y.first); }
0069   };
0070
0071 private:
0072   typedef _Rb_tree<key_type, value_type, select1st<value_type>, key_compare> _Rep_type;
0073   // std::_Select1st<value_type>, key_compare> _Rep_type;
0074   _Rep_type _M_t; // red-black tree representing map
0075 public:
0076   typedef typename _Rep_type::pointer pointer;
0077   typedef typename _Rep_type::const_pointer const_pointer;
0078   typedef typename _Rep_type::reference reference;
0079   typedef typename _Rep_type::const_reference const_reference;
0080   typedef typename _Rep_type::iterator iterator;
0081   typedef typename _Rep_type::const_iterator const_iterator;
0082   // typedef typename _Rep_type::reverse_iterator reverse_iterator;
0083   // typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
0084   typedef typename _Rep_type::size_type size_type;
0085   typedef typename _Rep_type::difference_type difference_type;
0086
0087   // Constructors
0088   VECCORE_ATT_HOST_DEVICE
0089   map() : _M_t(_Compare()) {}
0090   VECCORE_ATT_HOST_DEVICE
0091   map(const key_type /*_key*/) : _M_t() {} // TEST
0092   VECCORE_ATT_HOST_DEVICE
0093   map(const value_type *__first, const value_type *__last) : _M_t(_Compare()) { _M_t.insert_unique(__first, __last); }
0094   VECCORE_ATT_HOST_DEVICE
0095   map(const value_type *__first, const value_type *__last, const _Compare &__comp) : _M_t(__comp)
0096   {
0097     _M_t.insert_unique(__first, __last);
0098   }
0099   VECCORE_ATT_HOST_DEVICE
0100   map(const_iterator __first, const_iterator __last) : _M_t(_Compare()) { _M_t.insert_unique(__first, __last); }
0101   VECCORE_ATT_HOST_DEVICE
0102   map(const_iterator __first, const_iterator __last, const _Compare &__comp) : _M_t(__comp)
0103   {
0104     _M_t.insert_unique(__first, __last);
0105   }
0106
0107   VECCORE_ATT_HOST_DEVICE
0108   map(const map<_Key, _Tp, _Compare> &__x) : _M_t(__x._M_t) {}
0109   VECCORE_ATT_HOST_DEVICE
0110   map<_Key, _Tp, _Compare> &operator=(const map<_Key, _Tp, _Compare> &__x)
0111   {
0112     _M_t = __x._M_t;
0113     return *this;
0114   }
0115
0116   // key/value compare funtions
0117   VECCORE_ATT_HOST_DEVICE
0118   key_compare key_comp() const { return _M_t.key_comp(); }
0119   VECCORE_ATT_HOST_DEVICE
0120   value_compare<_Key, _Tp, _Compare> value_comp() const { return value_compare<_Key, _Tp, _Compare>(_M_t.key_comp()); }
0121
0122   // iterators
0123   VECCORE_ATT_HOST_DEVICE
0124   iterator begin() { return _M_t.begin(); }
0125   VECCORE_ATT_HOST_DEVICE
0126   const_iterator begin() const { return _M_t.begin(); }
0127   VECCORE_ATT_HOST_DEVICE
0128   iterator end() { return _M_t.end(); }
0129   VECCORE_ATT_HOST_DEVICE
0130   const_iterator end() const { return _M_t.end(); }
0131   /*
0132     reverse_iterator rbegin() { return _M_t.rbegin(); }
0133     const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
0134     reverse_iterator rend() { return _M_t.rend(); }
0135     const_reverse_iterator rend() const { return _M_t.rend(); }
0136   */
0137   VECCORE_ATT_HOST_DEVICE
0138   bool empty() const { return _M_t.empty(); }
0139   VECCORE_ATT_HOST_DEVICE
0140   size_type size() const { return _M_t.size(); }
0141   VECCORE_ATT_HOST_DEVICE
0142   size_type max_size() const { return _M_t.max_size(); }
0143   VECCORE_ATT_HOST_DEVICE
0144   _Tp &operator[](const key_type &__k)
0145   {
0146     iterator __i = lower_bound(__k);
0147     // __i->first is greater than or equivalent to __k.
0148     if (__i == end() || key_comp()(__k, (*__i).first)) __i = insert(__i, value_type(__k, _Tp()));
0149     return (*__i).second;
0150   }
0151   VECCORE_ATT_HOST_DEVICE
0152   const _Tp &at(const key_type &__k) const
0153   {
0154     const_iterator __i = lower_bound(__k);
0155     // __i->first is greater than or equivalent to __k.
0156     if (__i == end() || key_comp()(__k, (*__i).first)) {
0157       printf("at(): key out of range \n");
0158     }
0159     return (*__i).second;
0160   }
0161   // void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
0162
0163   // insert/erase
0164   VECCORE_ATT_HOST_DEVICE
0165   pair<iterator, bool> insert(const value_type &__x) { return _M_t.insert_unique(__x); }
0166   VECCORE_ATT_HOST_DEVICE
0167   iterator insert(iterator position, const value_type &__x) { return _M_t.insert_unique(position, __x); }
0168   VECCORE_ATT_HOST_DEVICE
0169   void insert(const value_type *__first, const value_type *__last) { _M_t.insert_unique(__first, __last); }
0170   VECCORE_ATT_HOST_DEVICE
0171   void insert(const_iterator __first, const_iterator __last) { _M_t.insert_unique(__first, __last); }
0172
0173   VECCORE_ATT_HOST_DEVICE
0174   void erase(iterator __position) { _M_t.erase(__position); }
0175   VECCORE_ATT_HOST_DEVICE
0176   size_type erase(const key_type &__x) { return _M_t.erase(__x); }
0177   VECCORE_ATT_HOST_DEVICE
0178   void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
0179   VECCORE_ATT_HOST_DEVICE
0180   void clear() { _M_t.clear(); }
0181
0182   // map operations:
0183   VECCORE_ATT_HOST_DEVICE
0184   iterator find(const key_type &__x) { return _M_t.find(__x); }
0185   VECCORE_ATT_HOST_DEVICE
0186   const_iterator find(const key_type &__x) const { return _M_t.find(__x); }
0187   VECCORE_ATT_HOST_DEVICE
0188   size_type count(const key_type &__x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
0189   VECCORE_ATT_HOST_DEVICE
0190   iterator lower_bound(const key_type &__x) { return _M_t.lower_bound(__x); }
0191   VECCORE_ATT_HOST_DEVICE
0192   const_iterator lower_bound(const key_type &__x) const { return _M_t.lower_bound(__x); }
0193   VECCORE_ATT_HOST_DEVICE
0194   iterator upper_bound(const key_type &__x) { return _M_t.upper_bound(__x); }
0195   VECCORE_ATT_HOST_DEVICE
0196   const_iterator upper_bound(const key_type &__x) const { return _M_t.upper_bound(__x); }
0197   VECCORE_ATT_HOST_DEVICE
0198   pair<iterator, iterator> equal_range(const key_type &__x) { return _M_t.equal_range(__x); }
0199   VECCORE_ATT_HOST_DEVICE
0200   pair<const_iterator, const_iterator> equal_range(const key_type &__x) const { return _M_t.equal_range(__x); }
0201 };
0202
0203 template <class _Key, class _Tp, class _Compare>
0204 VECCORE_ATT_HOST_DEVICE
0205 inline bool operator==(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y)
0206 {
0207   return __x._M_t == __y._M_t;
0208 }
0209
0210 template <class _Key, class _Tp, class _Compare>
0211 VECCORE_ATT_HOST_DEVICE
0212 inline bool operator<(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y)
0213 {
0214   return __x._M_t < __y._M_t;
0215 }
0216
0217 template <class _Key, class _Tp, class _Compare>
0218 VECCORE_ATT_HOST_DEVICE
0219 inline bool operator!=(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y)
0220 {
0221   return !(__x == __y);
0222 }
0223
0224 template <class _Key, class _Tp, class _Compare>
0225 VECCORE_ATT_HOST_DEVICE
0226 inline bool operator>(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y)
0227 {
0228   return __y < __x;
0229 }
0230
0231 template <class _Key, class _Tp, class _Compare>
0232 VECCORE_ATT_HOST_DEVICE
0233 inline bool operator<=(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y)
0234 {
0235   return !(__y < __x);
0236 }
0237
0238 template <class _Key, class _Tp, class _Compare>
0239 VECCORE_ATT_HOST_DEVICE
0240 inline bool operator>=(const map<_Key, _Tp, _Compare> &__x, const map<_Key, _Tp, _Compare> &__y)
0241 {
0242   return !(__x < __y);
0243 }
0244 /*
0245 template <class _Key, class _Tp, class _Compare>
0246 inline void swap(map<_Key,_Tp,_Compare>& __x,
0247                  map<_Key,_Tp,_Compare>& __y) {
0248   __x.swap(__y);
0249 }
0250 */
0251 }
0252 }
0253 #endif