rangemin-1.0: Effectively linear range-min algorithms.

Data.RangeMin

Description

This module is designed to implement high-speed versions of the function

```rangeMinBy :: (Ix i, IArray a e) => (e -> e -> Ordering) -> a i e -> ((i, i) -> (i, e))
rangeMinBy cmp arr = \r -> minimumBy (\ (i1, e1) (i2, e2) -> cmp e1 e2) [(i, arr ! i) | i <- range r]
```

To be precise, the implementation this module supplies for sufficiently large n has asymptotics `O(n log* n)` where `log* n` is defined as

```log* n	| n <= 2	= 0
| otherwise	= 1 + log* (log2 n)
```

While there is an asymptotically O(n) algorithm, the overhead associated with certain conversions in that algorithm take considerably longer than this implementation for all reasonable n. Note that log* n grows extraordinarily slowly with n: log* n < 5 for n<10^19729.

It also includes implementations of a lowest-common-ancestor algorithm on trees with identical asymptotics.

Synopsis

# Documentation

type RangeMin i e = (i, i) -> (i, e)Source

The type of a range-min function. Takes as an argument a range of indices and returns the position and value of the smallest element in that range.

Arguments

 :: Ix i => (i, i) Bounds on node labels. -> Tree i The tree to provide lowest-common-ancestor service for. -> (i, i) -> i A function that takes two node labels and returns the label of their lowest common ancestor.

Given a tree of indexed nodes, returns a function that takes two nodes and returns their lowest common ancestor.

Arguments

 :: Ix i => (a -> Maybe i) An index on tree labels so they can be indexed on an array. Need not account for every node label, hence the Maybe. -> (i, i) Bounds on indices of tree labels. -> Tree a The tree to provide lowest-common-ancestor service for. -> (a, a) -> a Given two node labels, returns the label of their lowest common ancestor.

Given an indexing function on node labels, returns a function that takes two node labels and returns the label of their lowest common ancestor.

Arguments

 :: Ix i => (a -> Maybe i) An index on tree labels, so they can be indexed in an array. Need not account for every node label, hence the Maybe. -> (i, i) Bounds on indices of tree labels. -> Tree a The tree to provide lowest-common-ancestor service for. -> (i, i) -> a Given two indices, return the label of the associated nodes' lowest common ancestor. The behavior of this method is not specified if these indices do not correspond to any trees.

Given an indexing function on node labels, returns a function that takes two indices and returns the label of the associated nodes' lowest common ancestor.

Arguments

 :: (IArray a e, Ix i, Num i, Enum i) => Comparator e A comparator function on elements. -> a i e An array of elements. -> RangeMin i e Given a subrange, returns the index and value at the minimum in that range.

Given a comparator and an array, returns a function that takes a subrange of the array and returns the index and value at the minimum in that subrange. NOT necessarily faster than `rangeMinBy'`, primarily because most of the algorithms used are based upon careful list folding.

rangeMin :: (IArray a e, Ix i, Num i, Enum i, Ord e) => a i e -> RangeMin i eSource

A version of `rangeMinBy` on elements with their default ordering.

rangeMinByM :: (Monad m, MArray a e m, Ix i, Num i, Enum i) => Comparator e -> a i e -> m (RangeMin i e)Source

rangeMinM :: (Monad m, MArray a e m, Ix i, Num i, Enum i, Ord e) => a i e -> m (RangeMin i e)Source

Arguments

 :: (Ix i, Num i, Enum i) => Comparator e A comparator function on elements. -> (i, i) Index range. -> [e] List of elements in index order. -> RangeMin i e Given a subrange, returns the index and value at the minimum in that range.

Given a comparator, an index range and a list of elements in index order, returns a function that takes two indices and returns the index and the value at the minimum value between those two indices inclusive.

Arguments

 :: (Ix i, Num i, Enum i, Ord e) => (i, i) Index range. -> [e] List of elements in index order. -> RangeMin i e Given a subrange, returns the index and value at the minimum in that range.

A version of `rangeMinBy'` on elements with their default ordering.