bisectRightWith : (a -> a -> Order) -> a -> Array a -> Int
Given an ordering function, a needle element and a sorted array haystack, it finds an insertion point that would maintain the sorted order of the array.
The returned insertion point I partitions the array into two halves so that all v <= x for v in Array.slice 0 i array for the left side and all v > x for v in Array.slice i (Array length array) array) for the right side.
Runs in O(log(n)) time.
Motivating use case
Allows you to turn an array into an ad hoc binary search tree. Personally, I've used this function to compute histograms for instance, but it is useful to speed up any alogirthm that needs to maintain a sorted array while inserting stuff into it.
Family
As the name suggests, there are a number of functions that work essentially similarly, but with small variations:
bisectLeftWith works the same, but differs on items where the comparison returns EQ. bisectRightWith gives the insertion point after, bisectLeftWith gives the insertion point before.
bisectRightBy : (a -> comparable) -> a -> Array a -> Int and bisectRight : comparable -> Array comparable -> Int naturally suggest themselves, but I sort of feel that with the rich library of helpers we have in Order.Extra, these are probably unnecessary.
bisectRightWithWithin : (a -> a -> Order) -> Int -> Int -> a -> Array a -> Int (ugh or maybe a better naming convention?) which takes a start and end index within which to perform the search. Can further accelerate the search if we already know something about the region.
bisectCenter : (a -> Float) -> a -> Array a -> Int is a fun variation, where instead of a sort order, items can give back a signed distance. Can be handy for instance if you want to find the index of UI element closest to the mouse position.
And of course potentially the grid of their combinations:
order
left
right
centre
with
bisectLeftWith / bisectLeftWithWithin
bisectRightWith / bisectRightWithWithin
-
by
bisectLeftBy / bisectLeftByWithin
bisectRightBy / bisectRightByWithin
bisectCenterBy / bisectCenterByWithin
comparable
bisectLeft / bisectLeftWithin
bisectRight / bisectRightWithin
bisectCenter / bisectCenterWithin
Which if any of these to add is an open question. Suddenly adding all 16 certainly feels like massive overkill. Personally I would start with bisectRightWith and perhaps bisectLeftWith and leave the rest for now.
Rationale
A naive implementation looks something like this:
bisectRightWith : (a -> a -> Order) -> a -> Array a -> Int
bisectRightWith compare item array =
case Array.get 0 array of
Nothing ->
0
Just default ->
let
gt =
Order.Extra.greaterThanBy compare
-- we start by doing a bounds check, so this shouldn't fail
get index =
Array.get index array |> Maybe.withDefault default
helper lo hi =
if lo < hi then
let
mid =
(lo + hi) // 2
in
if gt (get mid) item then
helper lo mid
else
helper (mid + 1) hi
else
lo
in
helper 0 (Array.length array)
And although this is a fairly standard CS algorithm, there are a few things that make it a bit tricky. Mostly the mandatory Maybe checks are annoying, since (if this is implemented correctly) there are already bounds checks and there is no case where where a Nothing should be seen.
bisectRightWith : (a -> a -> Order) -> a -> Array a -> IntGiven an ordering function, a needle element and a sorted array haystack, it finds an insertion point that would maintain the sorted order of the array. The returned insertion point
Ipartitions thearrayinto two halves so that all v <= x for v inArray.slice 0 i arrayfor the left side and all v > x for v inArray.slice i (Array length array) array)for the right side.Runs in O(log(n)) time.
Motivating use case
Allows you to turn an array into an ad hoc binary search tree. Personally, I've used this function to compute histograms for instance, but it is useful to speed up any alogirthm that needs to maintain a sorted array while inserting stuff into it.
Family
As the name suggests, there are a number of functions that work essentially similarly, but with small variations:
bisectLeftWithworks the same, but differs on items where the comparison returnsEQ.bisectRightWithgives the insertion point after,bisectLeftWithgives the insertion point before.bisectRightBy : (a -> comparable) -> a -> Array a -> IntandbisectRight : comparable -> Array comparable -> Intnaturally suggest themselves, but I sort of feel that with the rich library of helpers we have inOrder.Extra, these are probably unnecessary.bisectRightWithWithin : (a -> a -> Order) -> Int -> Int -> a -> Array a -> Int(ugh or maybe a better naming convention?) which takes a start and end index within which to perform the search. Can further accelerate the search if we already know something about the region.bisectCenter : (a -> Float) -> a -> Array a -> Intis a fun variation, where instead of a sort order, items can give back a signed distance. Can be handy for instance if you want to find the index of UI element closest to the mouse position.And of course potentially the grid of their combinations:
bisectLeftWith/bisectLeftWithWithinbisectRightWith/bisectRightWithWithinbisectLeftBy/bisectLeftByWithinbisectRightBy/bisectRightByWithinbisectCenterBy/bisectCenterByWithinbisectLeft/bisectLeftWithinbisectRight/bisectRightWithinbisectCenter/bisectCenterWithinWhich if any of these to add is an open question. Suddenly adding all 16 certainly feels like massive overkill. Personally I would start with
bisectRightWithand perhapsbisectLeftWithand leave the rest for now.Rationale
A naive implementation looks something like this:
And although this is a fairly standard CS algorithm, there are a few things that make it a bit tricky. Mostly the mandatory
Maybechecks are annoying, since (if this is implemented correctly) there are already bounds checks and there is no case where where aNothingshould be seen.