From d6e54de50239e8ac1de645bd411eeddbf627e4dc Mon Sep 17 00:00:00 2001
From: poke1024
Date: Thu, 2 Nov 2017 19:04:38 +0100
Subject: Add bsearch and bsearch_custom to Array

---
 core/array.cpp | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

(limited to 'core/array.cpp')

diff --git a/core/array.cpp b/core/array.cpp
index 171c11776..b7d4ae413 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();
-- 
cgit v1.2.3-70-g09d2