Add Array.Extra.bisectRightWith

[gampleman]

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.