diff options
| author | Bruce Hill <bruce@bruce-hill.com> | 2024-08-15 01:59:42 -0400 |
|---|---|---|
| committer | Bruce Hill <bruce@bruce-hill.com> | 2024-08-15 01:59:42 -0400 |
| commit | eccc4e4721f698bd85397cc56d55921f9db2e214 (patch) | |
| tree | 1b4099723e5c6163d18b5a219386f49f54b10c99 /builtins | |
| parent | 9c2d7c437d7576b44f4cf0e6b6a293acd7188a5d (diff) | |
Add binary search method to arrays
Diffstat (limited to 'builtins')
| -rw-r--r-- | builtins/array.c | 18 | ||||
| -rw-r--r-- | builtins/array.h | 3 |
2 files changed, 21 insertions, 0 deletions
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 |