elmcraft / elmcraft/core-extra

Add Array.Extra.bisectRightWith

Open
#23 0 comments 0 reactions 0 assignees View on GitHub
new function
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.