rangemin-2.0: Linear range-min algorithms.




This module addresses the specialized algorithmic problem of


Comparison function types

type LEq a = a -> a -> BoolSource

type Comparator a = a -> a -> OrderingSource

General range min operations

type RangeMin = Int -> Int -> IntSource

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

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

Equivalent to rangeMinBy (<=).

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

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 -> IntSource

Equivalent to vecRangeMinBy (<=).

Stable versions

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

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