rangemin-2.0: Linear range-min algorithms.

Data.RangeMin

Contents

Description

This module addresses the specialized algorithmic problem of

Synopsis

# 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.

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

`stableVecRangeMin` is equivalent to `stableVecRangeMinBy compare`.