- Comparison function types
- General range min operations
- Specialized
`Vector`

range min operations

This module addresses the specialized algorithmic problem of

- type LEq a = a -> a -> Bool
- type Comparator a = a -> a -> Ordering
- type RangeMin = Int -> Int -> Int
- rangeMinBy :: LEq a -> Int -> (Int -> a) -> RangeMin
- rangeMin :: Ord a => Int -> (Int -> a) -> RangeMin
- stableRangeMinBy :: Comparator a -> Int -> (Int -> a) -> RangeMin
- stableRangeMin :: Ord a => Int -> (Int -> a) -> RangeMin
- vecRangeMinBy :: Vector v a => LEq a -> v a -> RangeMin
- vecRangeMin :: (Vector v a, Ord a) => v a -> Int -> Int -> Int
- stableVecRangeMinBy :: Vector v a => Comparator a -> v a -> RangeMin
- stableVecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin

# Comparison function types

type Comparator a = a -> a -> OrderingSource

# General range min operations

rangeMinBy :: LEq a -> Int -> (Int -> a) -> RangeMinSource

Given a lookup function and a `(<=)`

comparison function, returns a function
which takes a starting index `i`

and a range length `n`

and returns the index
of a minimum element from the indices `a..a+n-1`

. (For example, if `rM`

is the
returned `RangeMin`

function, then the minimum element in the range `5..10`

is
`rM 5 6`

.)

This method *does not do bounds checking*, and further makes no guarantees as to how
ties are broken. Both of these guarantees *are* made by `stableRangeMinBy`

.

This function does *O(n)* preprocessing, assuming that the lookup function is *O(1)*,
but the returned `RangeMin`

function runs in *O(1)*.
Thus, this function is suited for making frequent range-min queries.

To make range-max queries, substitute `(>=)`

for `(<=)`

.

## Stable versions

stableRangeMinBy :: Comparator a -> Int -> (Int -> a) -> RangeMinSource

Equivalent to `rangeMinBy`

, except that it breaks ties by picking the element which comes first,
and provides bounds checking. This comes with some overhead, but has the same asymptotic guarantees.

stableRangeMin :: Ord a => Int -> (Int -> a) -> RangeMinSource

Equivalent to

.
`stableRangeMinBy`

`compare`

# Specialized `Vector`

range min operations

vecRangeMinBy :: Vector v a => LEq a -> v a -> RangeMinSource

is equivalent to `vecRangeMinBy`

(<=) xs

,
but can frequently optimize better, especially on unboxed vectors.
`rangeMinBy`

(<=) (`length`

xs) (xs `!`

)

vecRangeMin :: (Vector v a, Ord a) => v a -> Int -> Int -> IntSource

Equivalent to

.
`vecRangeMinBy`

(`<=`

)

## Stable versions

stableVecRangeMinBy :: Vector v a => Comparator a -> v a -> RangeMinSource

is equivalent to `stableVecRangeMinBy`

cmp xs

,
but can frequently optimize better, especially on unboxed vectors.
`stableRangeMinBy`

cmp (`length`

xs) (xs `!`

)

stableVecRangeMin :: (Vector v a, Ord a) => v a -> RangeMinSource

`stableVecRangeMin`

is equivalent to

.
`stableVecRangeMinBy`

`compare`