Data.RangeMin

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.

Documentation

type RangeMin = Int -> Int -> Int

A range min function. Given an index i and a length m, returns the minimum element in the range i..i+m-1.

type LEq a = a -> a -> Bool

A function of type LEq a is used as if it were (<=) for comparison purposes.

unsafeIntRangeMin :: Vector Int -> RangeMin

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

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

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

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

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

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