dymokomi/luce-browser-foundation
Source of release 0.6.1
0.6.1 / src / ak / binary_search.lucb
#==============================================================================================
#
# binary_search - binary search over a sorted span
#
# DESCRIPTION:
# Port of AK/BinarySearch.h (lines 1-72). The haystack is a span; the comparator is a
# Function2[const N*, const T*, i32] of the needle and an element (negative, zero or
# positive); default_comparator() gives DefaultComparator's `>`/`<` comparison.
#
#==============================================================================================
## Ported from AK/BinarySearch.h:16 AK::DefaultComparator::operator(): 1 when lhs > rhs, -1 when
## lhs < rhs, else 0.
pub func default_comparator_call[T: luce.Comparable](this: DefaultComparator*, lhs: const T*, rhs: const T*) -> i32:
_ = this
let order = lhs.compare(*rhs)
if order > 0:
return 1
if order < 0:
return -1
return 0
# DefaultComparator as a callback.
func binary_search_default_comparator[T: luce.Comparable](context: void*?, lhs: const T*, rhs: const T*) -> i32:
_ = context
var comparator = DefaultComparator(empty_ = 0)
return default_comparator_call(&comparator, lhs, rhs)
## DefaultComparator as the comparator argument of binary_search.
pub func default_comparator[T: luce.Comparable]() -> Function2[const T*, const T*, i32]:
let call: func(void*?, const T*, const T*) -> i32 = binary_search_default_comparator
return Function2[const T*, const T*, i32](call = call, context = none)
## Ported from AK/BinarySearch.h:29 AK::binary_search: the element comparing equal to `needle`,
## or none; `nearby_index` receives its index, or where the search ended.
pub func binary_search[T, N](haystack: const T[], needle: N, nearby_index: usize*?, comparator: Function2[const N*, const T*, i32]) -> const T*?:
if haystack.length == 0:
if let index = nearby_index:
*index = 0
return none
var low: usize = 0
var high = haystack.length - 1
while low <= high:
let middle = low + (high - low) // 2
let comparison = function2_call(&comparator, &needle, &haystack[middle])
if comparison < 0:
if middle != 0:
high = middle - 1
else:
break
elif comparison > 0:
low = middle + 1
else:
if let index = nearby_index:
*index = middle
return &haystack[middle]
if let index = nearby_index:
*index = low if low < high else high
return none