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]

for indices that are, in a sense, scalars -- that is, the array is one-dimensional. This restriction is
encapsulated in the type restriction `Enum`

.

To be precise, the implementation this module supplies is O(n) and answers queries in constant time.

Based on analysis from Test.Benchpress, making `q`

queries on a range-min of size `n`

,
constructed from an `Int`

-indexed list of `Int`

s, takes approximately `0.0015n + 0.0023q`

ms on
a Dell Latitude D630 with 2.50 GHz Intel Core Duo processors.

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

Warning: the internal libraries of this module include several nonstandard list fusions. For details, see http://hackage.haskell.org/packages/archive/rangemin/1.0.1/doc/html/src/Data-RangeMin-Internal-HandyList.html.

Warning: This module does *not* include bounds checking!

- type RangeMin i e = (i, i) -> (i, e)
- type Comparator e = e -> e -> Ordering
- rangeMinBy :: (IArray a e, Enum i, Ix i) => Comparator e -> a i e -> RangeMin i e
- rangeMin :: (IArray a e, Enum i, Ix i, Ord e) => a i e -> RangeMin i e
- rangeMinValue :: (IArray a e, Enum i, Ix i, Ord e) => a i e -> (i, i) -> e
- rangeMinValueBy :: (IArray a e, Enum i, Ix i) => Comparator e -> a i e -> (i, i) -> e
- rangeMinOpt :: UArray Int Int -> RangeMinVal Int Int
- rangeMinBy' :: Enum i => Comparator e -> (i, i) -> [e] -> RangeMin i e
- rangeMin' :: (Enum i, Ord e) => (i, i) -> [e] -> RangeMin i e
- rangeMinValue' :: (Enum i, Ord e) => (i, i) -> [e] -> (i, i) -> e
- rangeMinValueBy' :: Enum i => Comparator e -> (i, i) -> [e] -> (i, i) -> e
- rangeMinByM :: (Monad m, MArray a e m, Enum i, Ix i) => Comparator e -> a i e -> m (RangeMin i e)
- rangeMinM :: (Monad m, MArray a e m, Enum i, Ix i, Ord e) => a i e -> m (RangeMin i e)
- lowestCommonAncestor :: Ix i => (i, i) -> Tree i -> (i, i) -> i
- lowestCommonAncestorBy :: Ix i => (a -> Maybe i) -> (i, i) -> Tree a -> (a, a) -> a
- lowestCommonAncestorBy' :: Ix i => (a -> Maybe i) -> (i, i) -> Tree a -> (i, i) -> a

# Convenient type aliases

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.

type Comparator e = e -> e -> OrderingSource

# Functions

## Range-min functions

### On IArrays

:: (IArray a e, Enum i, Ix 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.

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

A version of `rangeMinBy`

on elements with their default ordering.

rangeMinValueBy :: (IArray a e, Enum i, Ix i) => Comparator e -> a i e -> (i, i) -> eSource

### On lists

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

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

rangeMinValue' :: (Enum i, Ord e) => (i, i) -> [e] -> (i, i) -> eSource

rangeMinValueBy' :: Enum i => Comparator e -> (i, i) -> [e] -> (i, i) -> eSource

### On MArrays

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

## LCA functions

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

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

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