1 /*************************************************************************/ 2 /* vmap.h */ 3 /*************************************************************************/ 4 /* This file is part of: */ 5 /* GODOT ENGINE */ 6 /* https://godotengine.org */ 7 /*************************************************************************/ 8 /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ 9 /* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ 10 /* */ 11 /* Permission is hereby granted, free of charge, to any person obtaining */ 12 /* a copy of this software and associated documentation files (the */ 13 /* "Software"), to deal in the Software without restriction, including */ 14 /* without limitation the rights to use, copy, modify, merge, publish, */ 15 /* distribute, sublicense, and/or sell copies of the Software, and to */ 16 /* permit persons to whom the Software is furnished to do so, subject to */ 17 /* the following conditions: */ 18 /* */ 19 /* The above copyright notice and this permission notice shall be */ 20 /* included in all copies or substantial portions of the Software. */ 21 /* */ 22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ 23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ 24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ 25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ 26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ 27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ 28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ 29 /*************************************************************************/ 30 31 #ifndef VMAP_H 32 #define VMAP_H 33 34 #include "core/cowdata.h" 35 #include "core/typedefs.h" 36 37 template <class T, class V> 38 class VMap { 39 public: 40 struct Pair { 41 42 T key; 43 V value; 44 PairPair45 _FORCE_INLINE_ Pair() {} 46 PairPair47 _FORCE_INLINE_ Pair(const T &p_key, const V &p_value) { 48 49 key = p_key; 50 value = p_value; 51 } 52 }; 53 54 private: 55 CowData<Pair> _cowdata; 56 _find(const T & p_val,bool & r_exact)57 _FORCE_INLINE_ int _find(const T &p_val, bool &r_exact) const { 58 59 r_exact = false; 60 if (_cowdata.empty()) 61 return 0; 62 63 int low = 0; 64 int high = _cowdata.size() - 1; 65 const Pair *a = _cowdata.ptr(); 66 int middle = 0; 67 68 #ifdef DEBUG_ENABLED 69 if (low > high) 70 ERR_PRINT("low > high, this may be a bug"); 71 #endif 72 while (low <= high) { 73 middle = (low + high) / 2; 74 75 if (p_val < a[middle].key) { 76 high = middle - 1; //search low end of array 77 } else if (a[middle].key < p_val) { 78 low = middle + 1; //search high end of array 79 } else { 80 r_exact = true; 81 return middle; 82 } 83 } 84 85 //return the position where this would be inserted 86 if (a[middle].key < p_val) 87 middle++; 88 return middle; 89 } 90 _find_exact(const T & p_val)91 _FORCE_INLINE_ int _find_exact(const T &p_val) const { 92 93 if (_cowdata.empty()) 94 return -1; 95 96 int low = 0; 97 int high = _cowdata.size() - 1; 98 int middle; 99 const Pair *a = _cowdata.ptr(); 100 101 while (low <= high) { 102 middle = (low + high) / 2; 103 104 if (p_val < a[middle].key) { 105 high = middle - 1; //search low end of array 106 } else if (a[middle].key < p_val) { 107 low = middle + 1; //search high end of array 108 } else { 109 return middle; 110 } 111 } 112 113 return -1; 114 } 115 116 public: insert(const T & p_key,const V & p_val)117 int insert(const T &p_key, const V &p_val) { 118 119 bool exact; 120 int pos = _find(p_key, exact); 121 if (exact) { 122 _cowdata.get_m(pos).value = p_val; 123 return pos; 124 } 125 _cowdata.insert(pos, Pair(p_key, p_val)); 126 return pos; 127 } 128 has(const T & p_val)129 bool has(const T &p_val) const { 130 131 return _find_exact(p_val) != -1; 132 } 133 erase(const T & p_val)134 void erase(const T &p_val) { 135 136 int pos = _find_exact(p_val); 137 if (pos < 0) 138 return; 139 _cowdata.remove(pos); 140 } 141 find(const T & p_val)142 int find(const T &p_val) const { 143 144 return _find_exact(p_val); 145 } 146 find_nearest(const T & p_val)147 int find_nearest(const T &p_val) const { 148 149 bool exact; 150 return _find(p_val, exact); 151 } 152 size()153 _FORCE_INLINE_ int size() const { return _cowdata.size(); } empty()154 _FORCE_INLINE_ bool empty() const { return _cowdata.empty(); } 155 get_array()156 const Pair *get_array() const { 157 158 return _cowdata.ptr(); 159 } 160 get_array()161 Pair *get_array() { 162 163 return _cowdata.ptrw(); 164 } 165 getv(int p_index)166 const V &getv(int p_index) const { 167 168 return _cowdata.get(p_index).value; 169 } 170 getv(int p_index)171 V &getv(int p_index) { 172 173 return _cowdata.get_m(p_index).value; 174 } 175 getk(int p_index)176 const T &getk(int p_index) const { 177 178 return _cowdata.get(p_index).key; 179 } 180 getk(int p_index)181 T &getk(int p_index) { 182 183 return _cowdata.get_m(p_index).key; 184 } 185 186 inline const V &operator[](const T &p_key) const { 187 188 int pos = _find_exact(p_key); 189 190 CRASH_COND(pos < 0); 191 192 return _cowdata.get(pos).value; 193 } 194 195 inline V &operator[](const T &p_key) { 196 197 int pos = _find_exact(p_key); 198 if (pos < 0) { 199 pos = insert(p_key, V()); 200 } 201 202 return _cowdata.get_m(pos).value; 203 } 204 VMap()205 _FORCE_INLINE_ VMap(){}; VMap(const VMap & p_from)206 _FORCE_INLINE_ VMap(const VMap &p_from) { _cowdata._ref(p_from._cowdata); } 207 inline VMap &operator=(const VMap &p_from) { 208 _cowdata._ref(p_from._cowdata); 209 return *this; 210 } 211 }; 212 #endif // VMAP_H 213