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.

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

Performance node: Compiling this library with LLVM can significantly improve its performance. Depending on the target system, this library compiled with -fasm runs between 10% and 30% slower than a fully optimized and unrolled C++ implementation. With -fllvm -optlc-O3, this library has been observed to beat the same C++ implementation by 15%.

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.