summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/templates/search_array.h67
-rw-r--r--core/templates/vector.h6
-rw-r--r--core/variant/array.cpp36
-rw-r--r--core/variant/variant_call.cpp9
-rw-r--r--doc/classes/PackedByteArray.xml9
-rw-r--r--doc/classes/PackedColorArray.xml9
-rw-r--r--doc/classes/PackedFloat32Array.xml9
-rw-r--r--doc/classes/PackedFloat64Array.xml9
-rw-r--r--doc/classes/PackedInt32Array.xml9
-rw-r--r--doc/classes/PackedInt64Array.xml9
-rw-r--r--doc/classes/PackedStringArray.xml9
-rw-r--r--doc/classes/PackedVector2Array.xml9
-rw-r--r--doc/classes/PackedVector3Array.xml9
-rw-r--r--tests/test_vector.h13
14 files changed, 182 insertions, 30 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;
}
diff --git a/core/variant/array.cpp b/core/variant/array.cpp
index 8373cbd4e8..b4d6dffc6f 100644
--- a/core/variant/array.cpp
+++ b/core/variant/array.cpp
@@ -34,6 +34,7 @@
#include "core/object/class_db.h"
#include "core/object/script_language.h"
#include "core/templates/hashfuncs.h"
+#include "core/templates/search_array.h"
#include "core/templates/vector.h"
#include "core/variant/callable.h"
#include "core/variant/variant.h"
@@ -484,44 +485,19 @@ void Array::shuffle() {
}
}
-template <typename Less>
-_FORCE_INLINE_ int bisect(const Vector<Variant> &p_array, const Variant &p_value, bool p_before, const Less &p_less) {
- int lo = 0;
- int hi = p_array.size();
- if (p_before) {
- while (lo < hi) {
- const int mid = (lo + hi) / 2;
- if (p_less(p_array.get(mid), p_value)) {
- lo = mid + 1;
- } else {
- hi = mid;
- }
- }
- } else {
- while (lo < hi) {
- const int mid = (lo + hi) / 2;
- if (p_less(p_value, p_array.get(mid))) {
- hi = mid;
- } else {
- lo = mid + 1;
- }
- }
- }
- return lo;
-}
-
int Array::bsearch(const Variant &p_value, bool p_before) {
ERR_FAIL_COND_V(!_p->typed.validate(p_value, "binary search"), -1);
- return bisect(_p->array, p_value, p_before, _ArrayVariantSort());
+ SearchArray<Variant, _ArrayVariantSort> avs;
+ return avs.bisect(_p->array.ptrw(), _p->array.size(), p_value, p_before);
}
int Array::bsearch_custom(const Variant &p_value, Callable p_callable, bool p_before) {
ERR_FAIL_COND_V(!_p->typed.validate(p_value, "custom binary search"), -1);
- _ArrayVariantSortCustom less;
- less.func = p_callable;
+ SearchArray<Variant, _ArrayVariantSortCustom> avs;
+ avs.compare.func = p_callable;
- return bisect(_p->array, p_value, p_before, less);
+ return avs.bisect(_p->array.ptrw(), _p->array.size(), p_value, p_before);
}
void Array::reverse() {
diff --git a/core/variant/variant_call.cpp b/core/variant/variant_call.cpp
index 49a0b455df..752195acc9 100644
--- a/core/variant/variant_call.cpp
+++ b/core/variant/variant_call.cpp
@@ -1839,6 +1839,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedByteArray, reverse, sarray(), varray());
bind_method(PackedByteArray, subarray, sarray("from", "to"), varray());
bind_method(PackedByteArray, sort, sarray(), varray());
+ bind_method(PackedByteArray, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedByteArray, duplicate, sarray(), varray());
bind_function(PackedByteArray, get_string_from_ascii, _VariantCall::func_PackedByteArray_get_string_from_ascii, sarray(), varray());
@@ -1900,6 +1901,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedInt32Array, subarray, sarray("from", "to"), varray());
bind_method(PackedInt32Array, to_byte_array, sarray(), varray());
bind_method(PackedInt32Array, sort, sarray(), varray());
+ bind_method(PackedInt32Array, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedInt32Array, duplicate, sarray(), varray());
/* Int64 Array */
@@ -1919,6 +1921,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedInt64Array, subarray, sarray("from", "to"), varray());
bind_method(PackedInt64Array, to_byte_array, sarray(), varray());
bind_method(PackedInt64Array, sort, sarray(), varray());
+ bind_method(PackedInt64Array, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedInt64Array, duplicate, sarray(), varray());
/* Float32 Array */
@@ -1938,6 +1941,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedFloat32Array, subarray, sarray("from", "to"), varray());
bind_method(PackedFloat32Array, to_byte_array, sarray(), varray());
bind_method(PackedFloat32Array, sort, sarray(), varray());
+ bind_method(PackedFloat32Array, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedFloat32Array, duplicate, sarray(), varray());
/* Float64 Array */
@@ -1957,6 +1961,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedFloat64Array, subarray, sarray("from", "to"), varray());
bind_method(PackedFloat64Array, to_byte_array, sarray(), varray());
bind_method(PackedFloat64Array, sort, sarray(), varray());
+ bind_method(PackedFloat64Array, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedFloat64Array, duplicate, sarray(), varray());
/* String Array */
@@ -1976,6 +1981,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedStringArray, subarray, sarray("from", "to"), varray());
bind_method(PackedStringArray, to_byte_array, sarray(), varray());
bind_method(PackedStringArray, sort, sarray(), varray());
+ bind_method(PackedStringArray, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedStringArray, duplicate, sarray(), varray());
/* Vector2 Array */
@@ -1995,6 +2001,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedVector2Array, subarray, sarray("from", "to"), varray());
bind_method(PackedVector2Array, to_byte_array, sarray(), varray());
bind_method(PackedVector2Array, sort, sarray(), varray());
+ bind_method(PackedVector2Array, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedVector2Array, duplicate, sarray(), varray());
/* Vector3 Array */
@@ -2014,6 +2021,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedVector3Array, subarray, sarray("from", "to"), varray());
bind_method(PackedVector3Array, to_byte_array, sarray(), varray());
bind_method(PackedVector3Array, sort, sarray(), varray());
+ bind_method(PackedVector3Array, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedVector3Array, duplicate, sarray(), varray());
/* Color Array */
@@ -2033,6 +2041,7 @@ static void _register_variant_builtin_methods() {
bind_method(PackedColorArray, subarray, sarray("from", "to"), varray());
bind_method(PackedColorArray, to_byte_array, sarray(), varray());
bind_method(PackedColorArray, sort, sarray(), varray());
+ bind_method(PackedColorArray, bsearch, sarray("value", "before"), varray(true));
bind_method(PackedColorArray, duplicate, sarray(), varray());
/* Register constants */
diff --git a/doc/classes/PackedByteArray.xml b/doc/classes/PackedByteArray.xml
index 9b8057d91a..e0c6fb4eba 100644
--- a/doc/classes/PackedByteArray.xml
+++ b/doc/classes/PackedByteArray.xml
@@ -43,6 +43,15 @@
Appends a [PackedByteArray] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="int" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="compress" qualifiers="const">
<return type="PackedByteArray" />
<argument index="0" name="compression_mode" type="int" default="0" />
diff --git a/doc/classes/PackedColorArray.xml b/doc/classes/PackedColorArray.xml
index fb744d7534..16d64826b8 100644
--- a/doc/classes/PackedColorArray.xml
+++ b/doc/classes/PackedColorArray.xml
@@ -43,6 +43,15 @@
Appends a [PackedColorArray] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="Color" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedColorArray" />
<description>
diff --git a/doc/classes/PackedFloat32Array.xml b/doc/classes/PackedFloat32Array.xml
index 0c05e8f3c2..b2a96e90c3 100644
--- a/doc/classes/PackedFloat32Array.xml
+++ b/doc/classes/PackedFloat32Array.xml
@@ -44,6 +44,15 @@
Appends a [PackedFloat32Array] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="float" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedFloat32Array" />
<description>
diff --git a/doc/classes/PackedFloat64Array.xml b/doc/classes/PackedFloat64Array.xml
index e55bc0e657..bf8c8dd333 100644
--- a/doc/classes/PackedFloat64Array.xml
+++ b/doc/classes/PackedFloat64Array.xml
@@ -44,6 +44,15 @@
Appends a [PackedFloat64Array] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="float" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedFloat64Array" />
<description>
diff --git a/doc/classes/PackedInt32Array.xml b/doc/classes/PackedInt32Array.xml
index 887a7a1e51..1d724f0e67 100644
--- a/doc/classes/PackedInt32Array.xml
+++ b/doc/classes/PackedInt32Array.xml
@@ -44,6 +44,15 @@
Appends a [PackedInt32Array] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="int" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedInt32Array" />
<description>
diff --git a/doc/classes/PackedInt64Array.xml b/doc/classes/PackedInt64Array.xml
index da661b12c3..f7d232c634 100644
--- a/doc/classes/PackedInt64Array.xml
+++ b/doc/classes/PackedInt64Array.xml
@@ -44,6 +44,15 @@
Appends a [PackedInt64Array] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="int" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedInt64Array" />
<description>
diff --git a/doc/classes/PackedStringArray.xml b/doc/classes/PackedStringArray.xml
index 8f16abaf37..7e807f6fea 100644
--- a/doc/classes/PackedStringArray.xml
+++ b/doc/classes/PackedStringArray.xml
@@ -44,6 +44,15 @@
Appends a [PackedStringArray] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="String" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedStringArray" />
<description>
diff --git a/doc/classes/PackedVector2Array.xml b/doc/classes/PackedVector2Array.xml
index 3678222da4..f9d2bc6d69 100644
--- a/doc/classes/PackedVector2Array.xml
+++ b/doc/classes/PackedVector2Array.xml
@@ -44,6 +44,15 @@
Appends a [PackedVector2Array] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="Vector2" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedVector2Array" />
<description>
diff --git a/doc/classes/PackedVector3Array.xml b/doc/classes/PackedVector3Array.xml
index 84d4297a3b..fc609665e9 100644
--- a/doc/classes/PackedVector3Array.xml
+++ b/doc/classes/PackedVector3Array.xml
@@ -43,6 +43,15 @@
Appends a [PackedVector3Array] at the end of this array.
</description>
</method>
+ <method name="bsearch">
+ <return type="int" />
+ <argument index="0" name="value" type="Vector3" />
+ <argument index="1" name="before" type="bool" default="true" />
+ <description>
+ Finds the index of an existing value (or the insertion index that maintains sorting order, if the value is not yet present in the array) using binary search. Optionally, a [code]before[/code] specifier can be passed. If [code]false[/code], the returned index comes after all existing entries of the value in the array.
+ [b]Note:[/b] Calling [method bsearch] on an unsorted array results in unexpected behavior.
+ </description>
+ </method>
<method name="duplicate">
<return type="PackedVector3Array" />
<description>
diff --git a/tests/test_vector.h b/tests/test_vector.h
index 02c56e59f6..bfdf389aa7 100644
--- a/tests/test_vector.h
+++ b/tests/test_vector.h
@@ -472,6 +472,19 @@ TEST_CASE("[Vector] Sort custom") {
CHECK(vector[7] == "World");
}
+TEST_CASE("[Vector] Search") {
+ Vector<int> vector;
+ vector.push_back(1);
+ vector.push_back(2);
+ vector.push_back(3);
+ vector.push_back(5);
+ vector.push_back(8);
+ CHECK(vector.bsearch(2, true) == 1);
+ CHECK(vector.bsearch(2, false) == 2);
+ CHECK(vector.bsearch(5, true) == 3);
+ CHECK(vector.bsearch(5, false) == 4);
+}
+
TEST_CASE("[Vector] Operators") {
Vector<int> vector;
vector.push_back(2);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-29 22:32:07 +0000