Data.RangeMin

Contents

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 -> Index Source

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 Source

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

type Index = Int Source

The type of a vector index.

type Length = Int Source

The type of the length of a vector.

Specialized range-mins

unsafeIntRangeMin Source

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.

intRangeMin Source

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

unsafeVecRangeMinBy Source

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

unsafeVecRangeMin Source

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

unsafeVecRangeMax Source

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

vecRangeMinBy Source

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.

vecRangeMin Source

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.

vecRangeMax Source

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

unsafeRangeMinBy Source

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.

unsafeRangeMin Source

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.

unsafeRangeMax Source

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.

rangeMinBy Source

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.

rangeMin Source

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.

rangeMax Source

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.

unsafeInjectRangeMin Source

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.

unsafeInjectRangeMax Source

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.

injectRangeMin Source

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.

injectRangeMax Source

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.

Injective Bool
Injective Char
Injective Int
Injective Int8
Injective Int16
Injective Int32
Injective Ordering
Injective Word
Injective Word8
Injective Word16
Injective Word32
Injective ()

Utility types

Specialized range-mins

Vector range-mins

General range-mins

Specialized types

`Vector` range-mins