diff options
Diffstat (limited to 'core/templates')
| -rw-r--r-- | core/templates/search_array.h | 67 | ||||
| -rw-r--r-- | core/templates/vector.h | 6 |
2 files changed, 73 insertions, 0 deletions
diff --git a/core/templates/search_array.h b/core/templates/search_array.h new file mode 100644 index 0000000000..8efc32df82 --- /dev/null +++ b/core/templates/search_array.h @@ -0,0 +1,67 @@ +/*************************************************************************/ +/* search_array.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2021 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* 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 SEARCH_ARRAY_H +#define SEARCH_ARRAY_H + +#include <core/templates/sort_array.h> + +template <class T, class Comparator = _DefaultComparator<T>> +class SearchArray { +public: + Comparator compare; + + inline int bisect(const T *p_array, int p_len, const T &p_value, bool p_before) const { + int lo = 0; + int hi = p_len; + if (p_before) { + while (lo < hi) { + const int mid = (lo + hi) / 2; + if (compare(p_array[mid], p_value)) { + lo = mid + 1; + } else { + hi = mid; + } + } + } else { + while (lo < hi) { + const int mid = (lo + hi) / 2; + if (compare(p_value, p_array[mid])) { + hi = mid; + } else { + lo = mid + 1; + } + } + } + return lo; + } +}; + +#endif // SEARCH_ARRAY_H diff --git a/core/templates/vector.h b/core/templates/vector.h index 2600604eb7..4b008a45a4 100644 --- a/core/templates/vector.h +++ b/core/templates/vector.h @@ -40,6 +40,7 @@ #include "core/error/error_macros.h" #include "core/os/memory.h" #include "core/templates/cowdata.h" +#include "core/templates/search_array.h" #include "core/templates/sort_array.h" template <class T> @@ -112,6 +113,11 @@ public: sort_custom<_DefaultComparator<T>>(); } + int bsearch(const T &p_value, bool p_before) { + SearchArray<T> search; + return search.bisect(ptrw(), size(), p_value, p_before); + } + Vector<T> duplicate() { return *this; } |