vmap.h 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204
  1. /**************************************************************************/
  2. /* vmap.h */
  3. /**************************************************************************/
  4. /* This file is part of: */
  5. /* GODOT ENGINE */
  6. /* https://godotengine.org */
  7. /**************************************************************************/
  8. /* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
  9. /* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
  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. #include "core/cowdata.h"
  33. #include "core/typedefs.h"
  34. template <class T, class V>
  35. class VMap {
  36. public:
  37. struct Pair {
  38. T key;
  39. V value;
  40. _FORCE_INLINE_ Pair() {}
  41. _FORCE_INLINE_ Pair(const T &p_key, const V &p_value) {
  42. key = p_key;
  43. value = p_value;
  44. }
  45. };
  46. private:
  47. CowData<Pair> _cowdata;
  48. _FORCE_INLINE_ int _find(const T &p_val, bool &r_exact) const {
  49. r_exact = false;
  50. if (_cowdata.empty()) {
  51. return 0;
  52. }
  53. int low = 0;
  54. int high = _cowdata.size() - 1;
  55. const Pair *a = _cowdata.ptr();
  56. int middle = 0;
  57. #ifdef DEBUG_ENABLED
  58. if (low > high)
  59. ERR_PRINT("low > high, this may be a bug");
  60. #endif
  61. while (low <= high) {
  62. middle = (low + high) / 2;
  63. if (p_val < a[middle].key) {
  64. high = middle - 1; //search low end of array
  65. } else if (a[middle].key < p_val) {
  66. low = middle + 1; //search high end of array
  67. } else {
  68. r_exact = true;
  69. return middle;
  70. }
  71. }
  72. //return the position where this would be inserted
  73. if (a[middle].key < p_val) {
  74. middle++;
  75. }
  76. return middle;
  77. }
  78. _FORCE_INLINE_ int _find_exact(const T &p_val) const {
  79. if (_cowdata.empty()) {
  80. return -1;
  81. }
  82. int low = 0;
  83. int high = _cowdata.size() - 1;
  84. int middle;
  85. const Pair *a = _cowdata.ptr();
  86. while (low <= high) {
  87. middle = (low + high) / 2;
  88. if (p_val < a[middle].key) {
  89. high = middle - 1; //search low end of array
  90. } else if (a[middle].key < p_val) {
  91. low = middle + 1; //search high end of array
  92. } else {
  93. return middle;
  94. }
  95. }
  96. return -1;
  97. }
  98. public:
  99. int insert(const T &p_key, const V &p_val) {
  100. bool exact;
  101. int pos = _find(p_key, exact);
  102. if (exact) {
  103. _cowdata.get_m(pos).value = p_val;
  104. return pos;
  105. }
  106. _cowdata.insert(pos, Pair(p_key, p_val));
  107. return pos;
  108. }
  109. bool has(const T &p_val) const {
  110. return _find_exact(p_val) != -1;
  111. }
  112. void erase(const T &p_val) {
  113. int pos = _find_exact(p_val);
  114. if (pos < 0) {
  115. return;
  116. }
  117. _cowdata.remove(pos);
  118. }
  119. int find(const T &p_val) const {
  120. return _find_exact(p_val);
  121. }
  122. int find_nearest(const T &p_val) const {
  123. if (_cowdata.empty()) {
  124. return -1;
  125. }
  126. bool exact;
  127. return _find(p_val, exact);
  128. }
  129. _FORCE_INLINE_ int size() const { return _cowdata.size(); }
  130. _FORCE_INLINE_ bool empty() const { return _cowdata.empty(); }
  131. const Pair *get_array() const {
  132. return _cowdata.ptr();
  133. }
  134. Pair *get_array() {
  135. return _cowdata.ptrw();
  136. }
  137. const V &getv(int p_index) const {
  138. return _cowdata.get(p_index).value;
  139. }
  140. V &getv(int p_index) {
  141. return _cowdata.get_m(p_index).value;
  142. }
  143. const T &getk(int p_index) const {
  144. return _cowdata.get(p_index).key;
  145. }
  146. T &getk(int p_index) {
  147. return _cowdata.get_m(p_index).key;
  148. }
  149. inline const V &operator[](const T &p_key) const {
  150. int pos = _find_exact(p_key);
  151. CRASH_COND(pos < 0);
  152. return _cowdata.get(pos).value;
  153. }
  154. inline V &operator[](const T &p_key) {
  155. int pos = _find_exact(p_key);
  156. if (pos < 0) {
  157. pos = insert(p_key, V());
  158. }
  159. return _cowdata.get_m(pos).value;
  160. }
  161. _FORCE_INLINE_ VMap(){};
  162. _FORCE_INLINE_ VMap(const VMap &p_from) { _cowdata._ref(p_from._cowdata); }
  163. inline VMap &operator=(const VMap &p_from) {
  164. _cowdata._ref(p_from._cowdata);
  165. return *this;
  166. }
  167. };
  168. #endif // VMAP_H