1 /*************************************************************************/ 2 /* vset.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 VSET_H 31 #define VSET_H 32 33 #include "typedefs.h" 34 #include "vector.h" 35 36 template <class T> 37 class VSet { 38 39 Vector<T> _data; 40 _find(const T & p_val,bool & r_exact)41 _FORCE_INLINE_ int _find(const T &p_val, bool &r_exact) const { 42 43 r_exact = false; 44 if (_data.empty()) 45 return 0; 46 47 int low = 0; 48 int high = _data.size() - 1; 49 int middle; 50 const T *a = &_data[0]; 51 52 while (low <= high) { 53 middle = (low + high) / 2; 54 55 if (p_val < a[middle]) { 56 high = middle - 1; //search low end of array 57 } else if (a[middle] < p_val) { 58 low = middle + 1; //search high end of array 59 } else { 60 r_exact = true; 61 return middle; 62 } 63 } 64 65 //return the position where this would be inserted 66 if (a[middle] < p_val) 67 middle++; 68 return middle; 69 } 70 _find_exact(const T & p_val)71 _FORCE_INLINE_ int _find_exact(const T &p_val) const { 72 73 if (_data.empty()) 74 return -1; 75 76 int low = 0; 77 int high = _data.size() - 1; 78 int middle; 79 const T *a = &_data[0]; 80 81 while (low <= high) { 82 middle = (low + high) / 2; 83 84 if (p_val < a[middle]) { 85 high = middle - 1; //search low end of array 86 } else if (a[middle] < p_val) { 87 low = middle + 1; //search high end of array 88 } else { 89 return middle; 90 } 91 } 92 93 return -1; 94 } 95 96 public: insert(const T & p_val)97 void insert(const T &p_val) { 98 99 bool exact; 100 int pos = _find(p_val, exact); 101 if (exact) 102 return; 103 _data.insert(pos, p_val); 104 } 105 has(const T & p_val)106 bool has(const T &p_val) const { 107 108 return _find_exact(p_val) != -1; 109 } 110 erase(const T & p_val)111 void erase(const T &p_val) { 112 113 int pos = _find_exact(p_val); 114 if (pos < 0) 115 return; 116 _data.remove(pos); 117 } 118 find(const T & p_val)119 int find(const T &p_val) const { 120 121 return _find_exact(p_val); 122 } 123 empty()124 _FORCE_INLINE_ bool empty() const { return _data.empty(); } 125 size()126 _FORCE_INLINE_ int size() const { return _data.size(); } 127 128 inline T &operator[](int p_index) { 129 130 return _data[p_index]; 131 } 132 133 inline const T &operator[](int p_index) const { 134 135 return _data[p_index]; 136 } 137 }; 138 139 #endif // VSET_H 140