diff options
Diffstat (limited to 'core/vset.h')
| -rw-r--r-- | core/vset.h | 145 |
1 files changed, 145 insertions, 0 deletions
diff --git a/core/vset.h b/core/vset.h new file mode 100644 index 000000000..3764b015b --- /dev/null +++ b/core/vset.h @@ -0,0 +1,145 @@ +/*************************************************************************/ +/* vset.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* http://www.godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ +#ifndef VSET_H +#define VSET_H + +#include "typedefs.h" +#include "vector.h" + +template<class T> +class VSet { + + + Vector<T> _data; + + _FORCE_INLINE_ int _find(const T& p_val,bool &r_exact) const { + + r_exact=false; + if (_data.empty()) + return 0; + + int low = 0; + int high = _data.size() -1; + int middle; + const T *a=&_data[0]; + + while( low <= high ) + { + middle = ( low + high ) / 2; + + if( p_val < a[ middle] ) { + high = middle - 1; //search low end of array + } else if ( a[middle] < p_val) { + low = middle + 1; //search high end of array + } else { + r_exact=true; + return middle; + } + } + + //return the position where this would be inserted + if (a[middle]<p_val) + middle++; + return middle; + } + + _FORCE_INLINE_ int _find_exact(const T& p_val) const { + + if (_data.empty()) + return -1; + + int low = 0; + int high = _data.size() -1; + int middle; + const T *a=&_data[0]; + + while( low <= high ) + { + middle = ( low + high ) / 2; + + if( p_val < a[ middle] ) { + high = middle - 1; //search low end of array + } else if ( a[middle] < p_val) { + low = middle + 1; //search high end of array + } else { + return middle; + } + } + + return -1; + } + +public: + + void insert(const T& p_val) { + + bool exact; + int pos = _find(p_val,exact); + if (exact) + return; + _data.insert(pos,p_val); + } + + bool has(const T& p_val) const { + + return _find_exact(p_val)!=-1; + } + + void erase(const T& p_val) { + + int pos = _find_exact(p_val); + if (pos<0) + return; + _data.remove(pos); + } + + int find(const T& p_val) const { + + return _find_exact(p_val); + + } + + _FORCE_INLINE_ bool empty() const { return _data.empty(); } + + _FORCE_INLINE_ int size() const { return _data.size(); } + + inline T& operator[](int p_index) { + + return _data[p_index]; + } + + inline const T& operator[](int p_index) const { + + return _data[p_index]; + } + + +}; + +#endif // VSET_H |