elmcraft / elmcraft/core-extra
Add Array.Extra.bisectRightWith
- Dominant language
- Elm
- Stars
- 31
- Forks
- 17
- PR merge metrics
- No merged PRs in 30d
Description
## `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:
```elm
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.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.