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

, and to use
`Vector`

`Int`

`unsafeIntRangeMin`

or `intRangeMin`

as appropriate. Though you cannot make your
own instances of `Injective`

, `unsafeInjectRangeMin`

and `injectRangeMin`

work the same
way.

- type RangeMin = Index -> Length -> Index
- type LEq a = a -> a -> Bool
- type Index = Int
- type Length = Int
- unsafeIntRangeMin :: Vector Int -> RangeMin
- intRangeMin :: Vector Int -> RangeMin
- unsafeVecRangeMinBy :: Vector v a => LEq a -> v a -> RangeMin
- unsafeVecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin
- unsafeVecRangeMax :: (Vector v a, Ord a) => v a -> RangeMin
- vecRangeMinBy :: Vector v a => LEq a -> v a -> RangeMin
- vecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin
- vecRangeMax :: (Vector v a, Ord a) => v a -> RangeMin
- unsafeRangeMinBy :: LEq a -> Length -> (Index -> a) -> RangeMin
- unsafeRangeMin :: Ord a => Length -> (Index -> a) -> RangeMin
- unsafeRangeMax :: Ord a => Length -> (Index -> a) -> RangeMin
- rangeMinBy :: LEq a -> Length -> (Index -> a) -> RangeMin
- rangeMin :: Ord a => Length -> (Index -> a) -> RangeMin
- rangeMax :: Ord a => Length -> (Index -> a) -> RangeMin
- class Enum a => Injective a
- unsafeInjectRangeMin :: Vector v a => (a -> Int) -> v a -> RangeMin
- injectRangeMin :: Vector v a => (a -> Int) -> v a -> RangeMin

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

.

# Specialized range-mins

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

*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

:: Vector v a | |

=> LEq a | A total ordering on the type |

-> v a | A vector of elements of type |

-> RangeMin | A range-min function on the vector which runs in |

*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 thelargest absolute valuein a subrange.`unsafeVecRangeMinBy`

(\ i j ->`abs`

i`>=`

`abs`

j) (`fromList`

[0,7,-10,4,5,4]) 0 6 == 2`unsafeVecRangeMinBy`

(\ i j ->`abs`

i`>=`

`abs`

j) (`fromList`

[0,7,-10,4,5,4]) 2 3 == 2`unsafeVecRangeMinBy`

(\ i j ->`abs`

i`>=`

`abs`

j) (`fromList`

[0,7,-10,4,5,4]) 3 3 == 4

:: (Vector v a, Ord a) | |

=> v a | A vector of elements of type |

-> RangeMin | A range-min function (under the natural ordering)
on the vector which runs in |

*O(n)*. Equivalent to

. Specialized for instances of `unsafeVecRangeMinBy`

(`<=`

)`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`

(`fromList`

"banana") 0 6 == 1`unsafeVecRangeMin`

(`fromList`

"banana") 1 1 == 1`unsafeVecRangeMin`

(`fromList`

"banana") 3 3 == 3

:: (Vector v a, Ord a) | |

=> v a | A vector of elements of type |

-> RangeMin | A range-max function (under the natural ordering)
on the vector which runs in |

*O(n)*. Equivalent to

. Specialized for instances of `unsafeVecRangeMinBy`

(`>=`

)`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`

(`fromList`

"banana") 0 6 == 2`unsafeVecRangeMax`

(`fromList`

"banana") 1 1 == 1`unsafeVecRangeMax`

(`fromList`

"banana") 3 3 == 4

:: Vector v a | |

=> LEq a | A total ordering on the type |

-> v a | A vector of elements of type |

-> RangeMin | A range-min function on the vector which runs in |

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

:: (Vector v a, Ord a) | |

=> v a | A vector of elements of type |

-> RangeMin | A range-min function (under the natural ordering)
on the vector which runs in |

*O(n)*. Equivalent to

; a safer version of `vecRangeMinBy`

(`<=`

)`unsafeVecRangeMin`

.
Specialized for instances of `Injective`

. The returned function *does* do bounds checks;
see `intRangeMin`

for details.

:: (Vector v a, Ord a) | |

=> v a | A vector of elements of type |

-> RangeMin | A range-max function (under the natural ordering)
on the vector which runs in |

*O(n)*. Equivalent to

; a safer version of `vecRangeMinBy`

(`>=`

)`unsafeVecRangeMax`

.
Specialized for instances of `Injective`

. The returned function *does* do bounds checks;
see `intRangeMin`

for details.

# General range-mins

:: LEq a | A total ordering on the type |

-> 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(n)*.

is equivalent to
`unsafeRangeMinBy`

(<=?) n look

.
The returned function `unsafeVecRangeMinBy`

(<=?) (`generate`

n look)*does not* do bounds checks; see `unsafeIntRangeMin`

for details.

:: 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(n)*. Equivalent to

. Specialized for instances of `unsafeRangeMinBy`

(`<=`

)`Injective`

.
The returned function *does not* do bounds checks; see `unsafeIntRangeMin`

for details.

:: 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(n)*. Equivalent to

. Specialized for instances of `unsafeRangeMinBy`

(`>=`

)`Injective`

.
The returned function *does not* do bounds checks; see `unsafeIntRangeMin`

for details.

:: LEq a | A total ordering on the type |

-> 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(n)*.

is equivalent to
`rangeMinBy`

(<=?) n look

, and is a safer version of
`vecRangeMinBy`

(<=?) (`generate`

n look)

. The returned function `unsafeRangeMinBy`

(<=?) n look*does* do bounds checks; see
`intRangeMin`

for details.

:: 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(n)*. Equivalent to

, and a safer version of `rangeMinBy`

(`<=`

)`unsafeRangeMin`

.
Specialized for instances of `Injective`

.
The returned function *does* do bounds checks; see `intRangeMin`

for details.

:: 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(n)*. Equivalent to

, and a safer version of `rangeMinBy`

(`>=`

)`unsafeRangeMax`

.
Specialized for instances of `Injective`

.
The returned function *does* do bounds checks; see `intRangeMin`

for details.

# Specialized types

unsafeInjectRangeMin :: Vector v a => (a -> Int) -> v a -> RangeMinSource

*O(n)*.

is equivalent to
`unsafeInjectRangeMin`

inject xs

, but is frequently much faster,
fusing with the input vector and converting it directly to a `unsafeVecRangeMinBy`

(\ x y -> inject x `<=`

inject y) xs

.
The returned function `Vector`

`Int`

*does not* do bounds checks; see `unsafeIntRangeMin`

for details.

injectRangeMin :: Vector v a => (a -> Int) -> v a -> RangeMinSource

*O(n)*.

is equivalent to
`injectRangeMin`

inject xs

, but is frequently much faster,
fusing with the input vector and converting it directly to a `vecRangeMinBy`

(\ x y -> inject x `<=`

inject y) xs

.
The returned function `Vector`

`Int`

*does* do bounds checks; see `intRangeMin`

for details.