Data.RangeMin

This module addresses the specialized algorithmic problem of

Comparison function types

type LEq a = a -> a -> Bool

type Comparator a = a -> a -> Ordering

General range min operations

type RangeMin = Int -> Int -> Int

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

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 (<=).

rangeMin :: Ord a => Int -> (Int -> a) -> RangeMin

Equivalent to rangeMinBy (<=).

Stable versions

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

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) -> RangeMin

Equivalent to stableRangeMinBy compare.

Specialized Vector range min operations

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

vecRangeMinBy (<=) xs is equivalent to rangeMinBy (<=) (length xs) (xs !), but can frequently optimize better, especially on unboxed vectors.

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

Equivalent to vecRangeMinBy (<=).

Stable versions

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

stableVecRangeMinBy cmp xs is equivalent to stableRangeMinBy cmp (length xs) (xs !), but can frequently optimize better, especially on unboxed vectors.

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

stableVecRangeMin is equivalent to stableVecRangeMinBy compare.