Consider the following function, which, given `i`

and `k`

, finds the index of
the minimum element in the range `i..i+k-1`

.

rangeMin ::`Vector`

v a => (a -> a ->`Ordering`

) ->`Int`

->`Int`

-> v a ->`Int`

rangeMin cmp i k xs = i +`minIndexBy`

cmp (`slice`

i k xs)

This module implements functions which, given a fixed comparison function, preprocess
an array in *O(n)* time to support queries of this form in *O(1)* time.

Compiling this library with LLVM can significantly improve its performance. Even with only -fasm, however, it has been clocked within 30% of a fully optimized and unrolled C++ implementation. (With -fllvm -optlc-O3, it has been within 10%.)

For all methods in this module, ties are broken by which element comes first in the array.

- type RangeMin = Int -> Int -> Int
- type LEq a = a -> a -> Bool
- unsafeIntRangeMin :: Vector Int -> RangeMin
- intRangeMin :: Vector Int -> RangeMin
- unsafeVecRangeMinBy :: Vector v a => LEq a -> v a -> RangeMin
- unsafeVecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin
- vecRangeMinBy :: Vector v a => LEq a -> v a -> RangeMin
- vecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin

# Documentation

type RangeMin = Int -> Int -> IntSource

A range min function. Given an index `i`

and a length `m`

, returns the
minimum element in the range `i..i+m-1`

.

unsafeIntRangeMin :: Vector Int -> RangeMinSource

*O(n)*. Returns a range-min function on the vector, under the natural ordering.
This function can be six times as fast as `unsafeVecRangeMin`

.

The returned function *does not* do bounds checks.

intRangeMin :: Vector Int -> RangeMinSource

*O(n)*. Returns a range-min function on the vector, under the natural ordering.
This function can be six times as fast as `vecRangeMin`

.

The returned function *does* do bounds checks.

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

*O(n)*. Returns a range-min function on the vector, under the specified ordering.
The returned function *does not* do bounds checks.

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

*O(n)*. Returns a range-min function on the vector, under the elements' natural ordering.
The returned function *does not* do bounds checks.

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

*O(n)*. Returns a range-min function on the vector, under the specified ordering.
The returned function *does* do bounds checks.

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

*O(n)*. Returns a range-min function on the vector, under the elements' natural ordering.
The returned function *does* do bounds checks.