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
- unsafeInjectRangeMax :: Vector v a => (a -> Int) -> v a -> RangeMin
- injectRangeMin :: Vector v a => (a -> Int) -> v a -> RangeMin
- injectRangeMax :: 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 == 2unsafeIntRangeMin
(fromList
[0,7,-10,4,5,4]) 2 3 == 2unsafeIntRangeMin
(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(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 == 2unsafeVecRangeMinBy
(\ i j ->abs
i>=
abs
j) (PV.fromList
[0,7,-10,4,5,4]) 2 3 == 2unsafeVecRangeMinBy
(\ i j ->abs
i>=
abs
j) (PV.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(1). |
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 tounsafeIntRangeMin
, sinceChar
is an -- instance ofInjective
.unsafeVecRangeMin
(PV.fromList
"banana") 0 6 == 1unsafeVecRangeMin
(PV.fromList
"banana") 1 1 == 1unsafeVecRangeMin
(PV.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(1). |
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 tounsafeIntRangeMin
, sinceChar
-- is an instance ofInjective
.unsafeVecRangeMax
(PV.fromList
"banana") 0 6 == 2unsafeVecRangeMax
(PV.fromList
"banana") 1 1 == 1unsafeVecRangeMax
(PV.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(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.
:: (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(1). |
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(1). |
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(1). |
O(n).
is equivalent to
unsafeRangeMinBy
(<=?) n look
. The returned function does not do bounds checks; see unsafeVecRangeMinBy
(<=?) (generate
n look)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(1). |
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(1). |
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(1). |
O(n).
is equivalent to rangeMinBy
(<=?) n look
,
and is a safer version of vecRangeMinBy
(<=?) (generate
n look)
. The returned function does do bounds checks; see unsafeRangeMinBy
(<=?) n lookintRangeMin
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(1). |
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(1). |
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
:: Vector v a | |
=> (a -> Int) | An order-preserving function into |
-> v a | The input vector. |
-> RangeMin | A range-min function on the elements (under the above ordering) which runs in O(1). |
O(n).
is equivalent to unsafeInjectRangeMin
f xs
, but is frequently much faster, fusing with the input vector and converting it directly to a unsafeVecRangeMinBy
(\ x y -> f x <=
f y) xs
. The returned function does not do bounds checks;
see Vector
Int
unsafeIntRangeMin
for details.
:: Vector v a | |
=> (a -> Int) | An order-preserving function into |
-> v a | The input vector. |
-> RangeMin | A range-max function on the elements (under the above ordering) which runs in O(1). |
O(n).
is equivalent to unsafeInjectRangeMax
f xs
, but is frequently much faster, fusing with the input vector and converting it directly to a unsafeVecRangeMinBy
(\ x y -> f x >=
f y) xs
. The returned function does not do bounds checks;
see Vector
Int
unsafeIntRangeMin
for details.
:: Vector v a | |
=> (a -> Int) | An order-preserving function into |
-> v a | The input vector. |
-> RangeMin | A range-min function on the elements (under the above ordering) which runs in O(1). |
O(n).
is equivalent to injectRangeMin
f xs
, but is frequently much faster, fusing with the input vector and converting it directly to a vecRangeMinBy
(\ x y -> f x <=
f y) xs
. The returned function does do bounds checks; see Vector
Int
intRangeMin
for details.
:: Vector v a | |
=> (a -> Int) | An order-preserving function into |
-> v a | The input vector. |
-> RangeMin | A range-max function on the elements (under the above ordering) which runs in O(1). |
O(n).
is equivalent to injectRangeMax
f xs
, but is frequently much faster, fusing with the input vector and converting it directly to a vecRangeMinBy
(\ x y -> f x >=
f y) xs
. The returned function does do bounds checks; see Vector
Int
intRangeMin
for details.