rangemin-2.2.2: Linear range-min algorithms.

Data.RangeMin

Description

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`) -> v a -> `Int` -> `Int` -> `Int`
rangeMin cmp xs i k = 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.

When certain methods are called on an element type which has a natural, order-preserving injection into `Int` -- specifically, on instances of `Injective` -- this module is smart enough to (fusibly) convert the vector into a `Vector Int`, and to use `unsafeIntRangeMin` or `intRangeMin` as appropriate. Though you cannot make your own instances of `Injective`, `unsafeInjectRangeMin` and `injectRangeMin` work the same way.

Synopsis

# Utility types

type RangeMin = Index -> Length -> IndexSource

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

A function of type `LEq a` is used as if it were `(<=)` for comparison purposes. This function must be a total ordering.

type Index = IntSource

The type of a vector index.

type Length = IntSource

The type of the length of a vector.

# Specialized range-mins

Arguments

 :: Vector Int A vector of `Int`s. -> RangeMin A range-min function on the vector which runs in O(1).

O(n). Returns a range-min function on the vector, under the natural ordering of `Int`. This function can be, depending on the `Vector` implementation, three to four times as fast as `unsafeVecRangeMinBy (<=)`.

Example:

``` `unsafeIntRangeMin` (`fromList` [0,7,-10,4,5,4]) 0 6 == 2
`unsafeIntRangeMin` (`fromList` [0,7,-10,4,5,4]) 2 3 == 2
`unsafeIntRangeMin` (`fromList` [0,7,-10,4,5,4]) 3 3 == 3
```

The returned function does not do bounds checks. If `n` is the length of the vector, and `i` and `m` are passed as arguments to the `RangeMin`, then if `i < 0`, `m < 1`, or `i + m > n`, a segfault may occur.

Arguments

 :: Vector Int A vector of `Int`s. -> RangeMin A range-min function on the vector which runs in O(1).

O(n). Returns a range-min function on the vector, with the natural ordering of `Int`. This function can be, depending on the `Vector` implementation, three to four times as fast as `vecRangeMinBy (<=)`.

Equivalent to `unsafeIntRangeMin`, except that the returned function does do bounds checks. When it receives a bad query, it throws an `ArrayException`.

# `Vector` range-mins

Arguments

 :: Vector v a => LEq a A total ordering on the type `a`. -> v a A vector of elements of type `a`. -> RangeMin A range-min function on the vector which runs in O(1).

O(n). Returns a range-min function on the vector, under the specified ordering. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Example:

``` -- Finding the element with the largest absolute value in a subrange.
`unsafeVecRangeMinBy` (\ i j -> `abs` i `>=` `abs` j) (`PV.fromList` [0,7,-10,4,5,4]) 0 6 == 2
`unsafeVecRangeMinBy` (\ i j -> `abs` i `>=` `abs` j) (`PV.fromList` [0,7,-10,4,5,4]) 2 3 == 2
`unsafeVecRangeMinBy` (\ i j -> `abs` i `>=` `abs` j) (`PV.fromList` [0,7,-10,4,5,4]) 3 3 == 4
```

Arguments

 :: (Vector v a, Ord a) => v a A vector of elements of type `a`. -> RangeMin A range-min function (under the natural ordering) on the vector which runs in O(1).

O(n). Equivalent to `unsafeVecRangeMinBy (<=)`. Specialized for instances of `Injective`. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Example:

``` -- In reality, these would be rewritten into calls to `unsafeIntRangeMin`, since `Char` is an
-- instance of `Injective`.
`unsafeVecRangeMin` (`PV.fromList` "banana") 0 6 == 1
`unsafeVecRangeMin` (`PV.fromList` "banana") 1 1 == 1
`unsafeVecRangeMin` (`PV.fromList` "banana") 3 3 == 3
```

Arguments

 :: (Vector v a, Ord a) => v a A vector of elements of type `a`. -> RangeMin A range-max function (under the natural ordering) on the vector which runs in O(1).

O(n). Equivalent to `unsafeVecRangeMinBy (>=)`. Specialized for instances of `Injective`. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Example:

``` -- In reality, these would be rewritten into calls to `unsafeIntRangeMin`, since `Char`
-- is an instance of `Injective`.
`unsafeVecRangeMax` (`PV.fromList` "banana") 0 6 == 2
`unsafeVecRangeMax` (`PV.fromList` "banana") 1 1 == 1
`unsafeVecRangeMax` (`PV.fromList` "banana") 3 3 == 4
```

Arguments

 :: Vector v a => LEq a A total ordering on the type `a`. -> v a A vector of elements of type `a`. -> RangeMin A range-min function on the vector which runs in O(1).

O(n). Returns a range-min function on the vector, under the specified ordering. The returned function does do bounds checks; see `intRangeMin` for details.

Arguments

 :: (Vector v a, Ord a) => v a A vector of elements of type `a`. -> RangeMin A range-min function (under the natural ordering) on the vector which runs in O(1).

O(n). Equivalent to `vecRangeMinBy (<=)`; a safer version of `unsafeVecRangeMin`. Specialized for instances of `Injective`. The returned function does do bounds checks; see `intRangeMin` for details.

Arguments

 :: (Vector v a, Ord a) => v a A vector of elements of type `a`. -> RangeMin A range-max function (under the natural ordering) on the vector which runs in O(1).

O(n). Equivalent to `vecRangeMinBy (>=)`; a safer version of `unsafeVecRangeMax`. Specialized for instances of `Injective`. The returned function does do bounds checks; see `intRangeMin` for details.

# General range-mins

Arguments

 :: LEq a A total ordering on the type `a`. -> Length The number of elements to generate. -> (Index -> a) A function to generate the element at each index. -> RangeMin A range-min function on the elements which runs in O(1).

O(n). `unsafeRangeMinBy (<=?) n look` is equivalent to `unsafeVecRangeMinBy (<=?) (generate n look)`. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Arguments

 :: Ord a => Length The number of elements to generate. -> (Index -> a) A function to generate the element at each index. -> RangeMin A range-min function on the elements (under their natural ordering) which runs in O(1).

O(n). Equivalent to `unsafeRangeMinBy (<=)`. Specialized for instances of `Injective`. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Arguments

 :: Ord a => Length The number of elements to generate. -> (Index -> a) A function to generate the element at each index. -> RangeMin A range-max function on the elements (under their natural ordering) which runs in O(1).

O(n). Equivalent to `unsafeRangeMinBy (>=)`. Specialized for instances of `Injective`. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Arguments

 :: LEq a A total ordering on the type `a`. -> Length The number of elements to generate. -> (Index -> a) A function to generate the element at each index. -> RangeMin A range-min function on the elements which runs in O(1).

O(n). `rangeMinBy (<=?) n look` is equivalent to `vecRangeMinBy (<=?) (generate n look)`, and is a safer version of `unsafeRangeMinBy (<=?) n look`. The returned function does do bounds checks; see `intRangeMin` for details.

Arguments

 :: Ord a => Length The number of elements to generate. -> (Index -> a) A function to generate the element at each index. -> RangeMin A range-min function on the elements (under their natural ordering) which runs in O(1).

O(n). Equivalent to `rangeMinBy (<=)`, and a safer version of `unsafeRangeMin`. Specialized for instances of `Injective`. The returned function does do bounds checks; see `intRangeMin` for details.

Arguments

 :: Ord a => Length The number of elements to generate. -> (Index -> a) A function to generate the element at each index. -> RangeMin A range-max function on the elements (under their natural ordering) which runs in O(1).

O(n). Equivalent to `rangeMinBy (>=)`, and a safer version of `unsafeRangeMax`. Specialized for instances of `Injective`. The returned function does do bounds checks; see `intRangeMin` for details.

# Specialized types

class Enum a => Injective a Source

A type is an instance of `Injective` if it has a natural order-preserving injection into `Int`, typically but not always `fromEnum`. Functions like `rangeMin` and `unsafeVecRangeMax` which use the element type's natural ordering may be auto-specialized when the element type is an `Injective` instance.

Arguments

 :: Vector v a => (a -> Int) An order-preserving function into `Int`. (The ordering on the elements is equivalent to `\ x y -> f x <= f y`.) -> v a The input vector. -> RangeMin A range-min function on the elements (under the above ordering) which runs in O(1).

O(n). `unsafeInjectRangeMin f xs` is equivalent to `unsafeVecRangeMinBy (\ x y -> f x <= f y) xs`, but is frequently much faster, fusing with the input vector and converting it directly to a `Vector Int`. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Arguments

 :: Vector v a => (a -> Int) An order-preserving function into `Int`. (The ordering on the elements is equivalent to `\ x y -> f x <= f y`.) -> v a The input vector. -> RangeMin A range-max function on the elements (under the above ordering) which runs in O(1).

O(n). `unsafeInjectRangeMax f xs` is equivalent to `unsafeVecRangeMinBy (\ x y -> f x >= f y) xs`, but is frequently much faster, fusing with the input vector and converting it directly to a `Vector Int`. The returned function does not do bounds checks; see `unsafeIntRangeMin` for details.

Arguments

 :: Vector v a => (a -> Int) An order-preserving function into `Int`. (The ordering on the elements is equivalent to `\ x y -> f x <= f y`.) -> v a The input vector. -> RangeMin A range-min function on the elements (under the above ordering) which runs in O(1).

O(n). `injectRangeMin f xs` is equivalent to `vecRangeMinBy (\ x y -> f x <= f y) xs`, but is frequently much faster, fusing with the input vector and converting it directly to a `Vector Int`. The returned function does do bounds checks; see `intRangeMin` for details.

Arguments

 :: Vector v a => (a -> Int) An order-preserving function into `Int`. (The ordering on the elements is equivalent to `\ x y -> f x <= f y`.) -> v a The input vector. -> RangeMin A range-max function on the elements (under the above ordering) which runs in O(1).

O(n). `injectRangeMax f xs` is equivalent to `vecRangeMinBy (\ x y -> f x >= f y) xs`, but is frequently much faster, fusing with the input vector and converting it directly to a `Vector Int`. The returned function does do bounds checks; see `intRangeMin` for details.