From eccc4e4721f698bd85397cc56d55921f9db2e214 Mon Sep 17 00:00:00 2001
From: Bruce Hill <bruce@bruce-hill.com>
Date: Thu, 15 Aug 2024 01:59:42 -0400
Subject: Add binary search method to arrays

---
 builtins/array.c | 18 ++++++++++++++++++
 builtins/array.h |  3 +++
 2 files changed, 21 insertions(+)

(limited to 'builtins')

diff --git a/builtins/array.c b/builtins/array.c
index a6e0dca2..abc9f923 100644
--- a/builtins/array.c
+++ b/builtins/array.c
@@ -634,4 +634,22 @@ public void Array$heapify(array_t *heap, closure_t comparison, int64_t padded_it
     ARRAY_DECREF(*heap);
 }
 
+public Int_t Array$binary_search(array_t array, void *target, closure_t comparison)
+{
+    typedef int32_t (*cmp_fn_t)(void*, void*, void*);
+    int64_t lo = 0, hi = array.length-1;
+    while (lo <= hi) {
+        int64_t mid = (lo + hi) / 2;
+        int32_t cmp = ((cmp_fn_t)comparison.fn)(
+            array.data + array.stride*mid, target, comparison.userdata);
+        if (cmp == 0)
+            return I(mid+1);
+        else if (cmp < 0)
+            lo = mid + 1;
+        else if (cmp > 0)
+            hi = mid - 1;
+    }
+    return I(lo+1); // Return the index where the target would be inserted
+}
+
 // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/builtins/array.h b/builtins/array.h
index a3305ca3..88184f8a 100644
--- a/builtins/array.h
+++ b/builtins/array.h
@@ -85,5 +85,8 @@ void Array$heap_pop(array_t *heap, closure_t comparison, int64_t padded_item_siz
 #define Array$heap_pop_value(heap, comparison, padded_item_size, type) \
     ({ array_t *_heap = heap; if (_heap->length == 0) fail("Attempt to pop from an empty array"); \
      type value = *(type*)_heap->data; Array$heap_pop(_heap, comparison, padded_item_size); value; })
+Int_t Array$binary_search(array_t array, void *target, closure_t comparison);
+#define Array$binary_search_value(array, target, comparison) \
+    ({ __typeof(target) _target = target; Array$binary_search(array, &_target, comparison); })
 
 // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
-- 
cgit v1.2.3