1 /*************************************************************************/ 2 /* vmap.h */ 3 /*************************************************************************/ 4 /* This file is part of: */ 5 /* GODOT ENGINE */ 6 /* https://godotengine.org */ 7 /*************************************************************************/ 8 /* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ 9 /* Copyright (c) 2014-2019 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 #ifndef VMAP_H 31 #define VMAP_H 32 33 #include "typedefs.h" 34 #include "vector.h" 35 36 template <class T, class V> 37 class VMap { 38 39 struct _Pair { 40 41 T key; 42 V value; 43 _Pair_Pair44 _FORCE_INLINE_ _Pair() {} 45 _Pair_Pair46 _FORCE_INLINE_ _Pair(const T &p_key, const V &p_value) { 47 48 key = p_key; 49 value = p_value; 50 } 51 }; 52 53 Vector<_Pair> _data; 54 _find(const T & p_val,bool & r_exact)55 _FORCE_INLINE_ int _find(const T &p_val, bool &r_exact) const { 56 57 r_exact = false; 58 if (_data.empty()) 59 return 0; 60 61 int low = 0; 62 int high = _data.size() - 1; 63 int middle; 64 const _Pair *a = &_data[0]; 65 66 while (low <= high) { 67 middle = (low + high) / 2; 68 69 if (p_val < a[middle].key) { 70 high = middle - 1; //search low end of array 71 } else if (a[middle].key < p_val) { 72 low = middle + 1; //search high end of array 73 } else { 74 r_exact = true; 75 return middle; 76 } 77 } 78 79 //return the position where this would be inserted 80 if (a[middle].key < p_val) 81 middle++; 82 return middle; 83 } 84 _find_exact(const T & p_val)85 _FORCE_INLINE_ int _find_exact(const T &p_val) const { 86 87 if (_data.empty()) 88 return -1; 89 90 int low = 0; 91 int high = _data.size() - 1; 92 int middle; 93 const _Pair *a = &_data[0]; 94 95 while (low <= high) { 96 middle = (low + high) / 2; 97 98 if (p_val < a[middle].key) { 99 high = middle - 1; //search low end of array 100 } else if (a[middle].key < p_val) { 101 low = middle + 1; //search high end of array 102 } else { 103 return middle; 104 } 105 } 106 107 return -1; 108 } 109 110 public: insert(const T & p_key,const V & p_val)111 int insert(const T &p_key, const V &p_val) { 112 113 bool exact; 114 int pos = _find(p_key, exact); 115 if (exact) { 116 _data[pos].value = p_val; 117 return pos; 118 } 119 _data.insert(pos, _Pair(p_key, p_val)); 120 return pos; 121 } 122 has(const T & p_val)123 bool has(const T &p_val) const { 124 125 return _find_exact(p_val) != -1; 126 } 127 erase(const T & p_val)128 void erase(const T &p_val) { 129 130 int pos = _find_exact(p_val); 131 if (pos < 0) 132 return; 133 _data.remove(pos); 134 } 135 find(const T & p_val)136 int find(const T &p_val) const { 137 138 return _find_exact(p_val); 139 } 140 find_nearest(const T & p_val)141 int find_nearest(const T &p_val) const { 142 143 bool exact; 144 return _find(p_val, exact); 145 } 146 size()147 _FORCE_INLINE_ int size() const { return _data.size(); } empty()148 _FORCE_INLINE_ bool empty() const { return _data.empty(); } 149 get_array()150 const _Pair *get_array() const { 151 152 return _data.ptr(); 153 } 154 get_array()155 _Pair *get_array() { 156 157 return _data.ptr(); 158 } 159 getv(int p_index)160 const V &getv(int p_index) const { 161 162 return _data[p_index].value; 163 } 164 getv(int p_index)165 V &getv(int p_index) { 166 167 return _data[p_index].value; 168 } 169 getk(int p_index)170 const T &getk(int p_index) const { 171 172 return _data[p_index].key; 173 } 174 getk(int p_index)175 T &getk(int p_index) { 176 177 return _data[p_index].key; 178 } 179 180 inline const V &operator[](const T &p_key) const { 181 182 int pos = _find_exact(p_key); 183 184 PRAY_COND(pos < 0, V); 185 186 return _data[pos].value; 187 } 188 189 inline V &operator[](const T &p_key) { 190 191 int pos = _find_exact(p_key); 192 if (pos < 0) { 193 V val; 194 pos = insert(p_key, val); 195 } 196 197 return _data[pos].value; 198 } 199 }; 200 #endif // VMAP_H 201