Add bsearch and bsearch_custom to Array

7 files changed, 110 insertions, 0 deletions

diff --git a/core/array.cpp b/core/array.cpp
index 171c11776c..b7d4ae413a 100644
--- a/core/array.cpp
+++ b/core/array.cpp
@@ -265,6 +265,49 @@ Array &Array::sort_custom(Object *p_obj, const StringName &p_function) {
 	return *this;
 }
 
+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) {
+
+	return bisect(_p->array, p_value, p_before, _ArrayVariantSort());
+}
+
+int Array::bsearch_custom(const Variant &p_value, Object *p_obj, const StringName &p_function, bool p_before) {
+
+	ERR_FAIL_NULL_V(p_obj, 0);
+
+	_ArrayVariantSortCustom less;
+	less.obj = p_obj;
+	less.func = p_function;
+
+	return bisect(_p->array, p_value, p_before, less);
+}
+
 Array &Array::invert() {
 
 	_p->array.invert();
diff --git a/core/array.h b/core/array.h
index 2c29103108..3d70a31d2f 100644
--- a/core/array.h
+++ b/core/array.h
@@ -70,6 +70,8 @@ public:
 
 	Array &sort();
 	Array &sort_custom(Object *p_obj, const StringName &p_function);
+	int bsearch(const Variant &p_value, bool p_before = true);
+	int bsearch_custom(const Variant &p_value, Object *p_obj, const StringName &p_function, bool p_before = true);
 	Array &invert();
 
 	int find(const Variant &p_value, int p_from = 0) const;
diff --git a/core/variant_call.cpp b/core/variant_call.cpp
index 9e6aaeb911..da6e602ccb 100644
--- a/core/variant_call.cpp
+++ b/core/variant_call.cpp
@@ -483,6 +483,8 @@ struct _VariantCall {
 	VCALL_LOCALMEM1(Array, erase);
 	VCALL_LOCALMEM0(Array, sort);
 	VCALL_LOCALMEM2(Array, sort_custom);
+	VCALL_LOCALMEM2R(Array, bsearch);
+	VCALL_LOCALMEM4R(Array, bsearch_custom);
 	VCALL_LOCALMEM0R(Array, duplicate);
 	VCALL_LOCALMEM0(Array, invert);
 
@@ -1625,6 +1627,8 @@ void register_variant_methods() {
 	ADDFUNC0RNC(ARRAY, NIL, Array, pop_front, varray());
 	ADDFUNC0NC(ARRAY, NIL, Array, sort, varray());
 	ADDFUNC2NC(ARRAY, NIL, Array, sort_custom, OBJECT, "obj", STRING, "func", varray());
+	ADDFUNC2R(ARRAY, INT, Array, bsearch, NIL, "value", BOOL, "before", varray(true));
+	ADDFUNC4R(ARRAY, INT, Array, bsearch_custom, NIL, "value", OBJECT, "obj", STRING, "func", BOOL, "before", varray(true));
 	ADDFUNC0NC(ARRAY, NIL, Array, invert, varray());
 	ADDFUNC0RNC(ARRAY, ARRAY, Array, duplicate, varray());
 
diff --git a/doc/classes/Array.xml b/doc/classes/Array.xml
index 203c60e644..3bb40755a6 100644
--- a/doc/classes/Array.xml
+++ b/doc/classes/Array.xml
@@ -260,6 +260,32 @@
 				Sort the array using a custom method and return reference to the array. The arguments are an object that holds the method and the name of such method. The custom method receives two arguments (a pair of elements from the array) and must return true if the first argument is less than the second, and return false otherwise. Note: you cannot randomize the return value as the heapsort algorithm expects a deterministic result. Doing so will result in unexpected behavior.
 			</description>
 		</method>
+		<method name="bsearch">
+			<return type="int">
+			</return>
+			<argument index="0" name="value" type="var">
+			</argument>
+			<argument index="1" name="before" type="bool" default="true">
+			</argument>
+			<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 before specifier can be passed. If false, the returned index comes after all existing entries of the value in the array. Note that calling bsearch on an unsorted array results in unexpected behavior.
+			</description>
+		</method>
+		<method name="bsearch_custom">
+			<return type="int">
+			</return>
+			<argument index="0" name="value" type="var">
+			</argument>
+			<argument index="1" name="obj" type="Object">
+			</argument>
+			<argument index="2" name="func" type="String">
+			</argument>
+			<argument index="3" name="before" type="bool" default="true">
+			</argument>
+			<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 and a custom comparison method. Optionally, a before specifier can be passed. If false, the returned index comes after all existing entries of the value in the array.  The custom method receives two arguments (an element from the array and the value searched for) and must return true if the first argument is less than the second, and return false otherwise. Note that calling bsearch on an unsorted array results in unexpected behavior.
+			</description>
+		</method>
 	</methods>
 	<constants>
 	</constants>
diff --git a/modules/gdnative/gdnative/array.cpp b/modules/gdnative/gdnative/array.cpp
index e0d9514985..8351c43574 100644
--- a/modules/gdnative/gdnative/array.cpp
+++ b/modules/gdnative/gdnative/array.cpp
@@ -302,6 +302,17 @@ void GDAPI godot_array_sort_custom(godot_array *p_self, godot_object *p_obj, con
 	self->sort_custom((Object *)p_obj, *func);
 }
 
+godot_int GDAPI godot_array_bsearch(godot_array *p_self, const godot_variant *p_value, const godot_bool p_before) {
+	Array *self = (Array *)p_self;
+	return self->bsearch((const Variant *)p_value, p_before);
+}
+
+godot_int GDAPI godot_array_bsearch_custom(godot_array *p_self, const godot_variant *p_value, godot_object *p_obj, const godot_string *p_func, const godot_bool p_before) {
+	Array *self = (Array *)p_self;
+	const String *func = (const String *)p_func;
+	return self->bsearch_custom((const Variant *)p_value, (Object *)p_obj, *func, p_before);
+}
+
 void GDAPI godot_array_destroy(godot_array *p_self) {
 	((Array *)p_self)->~Array();
 }
diff --git a/modules/gdnative/gdnative_api.json b/modules/gdnative/gdnative_api.json
index 007c7955d4..0438a196cf 100644
--- a/modules/gdnative/gdnative_api.json
+++ b/modules/gdnative/gdnative_api.json
@@ -2680,6 +2680,26 @@
         ]
       },
       {
+        "name": "godot_array_bsearch",
+        "return_type": "godot_int",
+        "arguments": [
+          ["godot_array *", "p_self"],
+          ["const godot_variant *", "p_value"],
+          ["const godot_bool", "p_before"]
+        ]
+      },
+      {
+        "name": "godot_array_bsearch_custom",
+        "return_type": "godot_int",
+        "arguments": [
+          ["godot_array *", "p_self"],
+          ["const godot_variant *", "p_value"],
+          ["godot_object *", "p_obj"],
+          ["const godot_string *", "p_func"],
+          ["const godot_bool", "p_before"]
+        ]
+      },
+      {
         "name": "godot_array_destroy",
         "return_type": "void",
         "arguments": [
diff --git a/modules/gdnative/include/gdnative/array.h b/modules/gdnative/include/gdnative/array.h
index 01ae61e280..484ffd10ba 100644
--- a/modules/gdnative/include/gdnative/array.h
+++ b/modules/gdnative/include/gdnative/array.h
@@ -124,6 +124,10 @@ void GDAPI godot_array_sort(godot_array *p_self);
 
 void GDAPI godot_array_sort_custom(godot_array *p_self, godot_object *p_obj, const godot_string *p_func);
 
+godot_int GDAPI godot_array_bsearch(godot_array *p_self, const godot_variant *p_value, const godot_bool p_before);
+
+godot_int GDAPI godot_array_bsearch_custom(godot_array *p_self, const godot_variant *p_value, godot_object *p_obj, const godot_string *p_func, const godot_bool p_before);
+
 void GDAPI godot_array_destroy(godot_array *p_self);
 
 #ifdef __cplusplus