Data.RangeMin

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 Ints, 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!

Convenient type aliases

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

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

Functions

Range-min functions

On IArrays

rangeMinBy

Arguments

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

A version of rangeMinBy on elements with their default ordering.

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

On lists

rangeMinBy'

Arguments

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

rangeMin'

Arguments

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

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

On MArrays

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)

LCA functions

lowestCommonAncestor

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.

lowestCommonAncestorBy

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.

lowestCommonAncestorBy'

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.