rangemin-2.2.1: Linear range-min algorithms.

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

unsafeIntRangeMinSource

Arguments

:: Vector Int

A vector of Ints.

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

intRangeMinSource

Arguments

:: Vector Int

A vector of Ints.

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

unsafeVecRangeMinBySource

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

unsafeVecRangeMinSource

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 (fromList "banana") 0 6 == 1
 unsafeVecRangeMin (fromList "banana") 1 1 == 1
 unsafeVecRangeMin (fromList "banana") 3 3 == 3

unsafeVecRangeMaxSource

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 (fromList "banana") 0 6 == 2
 unsafeVecRangeMax (fromList "banana") 1 1 == 1
 unsafeVecRangeMax (fromList "banana") 3 3 == 4

vecRangeMinBySource

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.

vecRangeMinSource

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.

vecRangeMaxSource

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

unsafeRangeMinBySource

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.

unsafeRangeMinSource

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.

unsafeRangeMaxSource

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.

rangeMinBySource

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.

rangeMinSource

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.

rangeMaxSource

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 :: Vector v a => (a -> Int) -> v a -> RangeMinSource

O(n). unsafeInjectRangeMin inject xs is equivalent to unsafeVecRangeMinBy (\ x y -> inject x <= inject 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 :: Vector v a => (a -> Int) -> v a -> RangeMinSource

O(n). injectRangeMin inject xs is equivalent to vecRangeMinBy (\ x y -> inject x <= inject 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.