-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Linear range-min algorithms.
--
-- Rapidly (in linear time) preprocesses a vector so that the minimum
-- element of any given subrange can be looked up in constant time.
@package rangemin
@version 2.0
-- | This module addresses the specialized algorithmic problem of
module Data.RangeMin
type LEq a = a -> a -> Bool
type Comparator a = a -> a -> Ordering
type RangeMin = Int -> Int -> Int
-- | Given a lookup function and a (<=) comparison function,
-- returns a function which takes a starting index i and a range
-- length n and returns the index of a minimum element from the
-- indices a..a+n-1. (For example, if rM is the
-- returned RangeMin function, then the minimum element in the
-- range 5..10 is rM 5 6.)
--
-- This method does not do bounds checking, and further makes no
-- guarantees as to how ties are broken. Both of these guarantees
-- are made by stableRangeMinBy.
--
-- This function does O(n) preprocessing, assuming that the lookup
-- function is O(1), but the returned RangeMin function
-- runs in O(1). Thus, this function is suited for making frequent
-- range-min queries.
--
-- To make range-max queries, substitute (>=) for
-- (<=).
rangeMinBy :: LEq a -> Int -> (Int -> a) -> RangeMin
-- | Equivalent to rangeMinBy (<=).
rangeMin :: (Ord a) => Int -> (Int -> a) -> RangeMin
-- | Equivalent to rangeMinBy, except that it breaks ties by picking
-- the element which comes first, and provides bounds checking. This
-- comes with some overhead, but has the same asymptotic guarantees.
stableRangeMinBy :: Comparator a -> Int -> (Int -> a) -> RangeMin
-- | Equivalent to stableRangeMinBy compare.
stableRangeMin :: (Ord a) => Int -> (Int -> a) -> RangeMin
-- | vecRangeMinBy (<=) xs is equivalent to
-- rangeMinBy (<=) (length xs) (xs !),
-- but can frequently optimize better, especially on unboxed vectors.
vecRangeMinBy :: (Vector v a) => LEq a -> v a -> RangeMin
-- | Equivalent to vecRangeMinBy (<=).
vecRangeMin :: (Vector v a, Ord a) => v a -> Int -> Int -> Int
-- | stableVecRangeMinBy cmp xs is equivalent to
-- stableRangeMinBy cmp (length xs) (xs !),
-- but can frequently optimize better, especially on unboxed vectors.
stableVecRangeMinBy :: (Vector v a) => Comparator a -> v a -> RangeMin
-- | stableVecRangeMin is equivalent to
-- stableVecRangeMinBy compare.
stableVecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin
-- | Functions for finding lowest common ancestors in trees in
-- O(1) time, with O(n) preprocessing.
module Data.RangeMin.LCA
-- | Index is used as a node identifier, so that the user can refer
-- to tree nodes in a random-access fashion.
type Index = Int
-- | lowestCommonAncestor n ix tree takes a tree whose
-- nodes are mapped by ix to a unique index in the range
-- 0..n-1, and returns a function which takes two indices
-- (corresponding to two nodes in the tree) and returns the label of
-- their lowest common ancestor.
--
-- This takes O(n) preprocessing and answers queries in
-- O(1), as it is an application of Data.RangeMin.
--
-- For binary trees, consider using Data.RangeMin.LCA.Binary.
lowestCommonAncestor :: Int -> (a -> Index) -> Tree a -> Index -> Index -> a
-- | Takes a tree and indexes it in depth-first order, returning the number
-- of nodes, the indexed tree, and the lowest common ancestor function.
quickLCA :: Tree a -> (Int, Tree (Index, a), Index -> Index -> (Index, a))
-- | Functions for finding lowest common ancestors in binary trees
-- in O(1) time, with O(n) preprocessing.
module Data.RangeMin.LCA.Binary
-- | Index is used as a node identifier, so that the user can refer
-- to tree nodes in a random-access fashion.
type Index = Int
-- | A generic binary tree.
data BinTree a
Tip :: BinTree a
BinTree :: a -> (BinTree a) -> (BinTree a) -> BinTree a
-- | Takes a binary tree and indexes it inorder, returning the number of
-- nodes, the indexed tree, and the lowest common ancestor function.
quickLCABinary :: BinTree a -> (Int, BinTree (Index, a), Index -> Index -> (Index, a))
-- | Similar to LCA.lowestCommonAncestor, but optimized for binary
-- trees. This method can reasonably be expected to run twice as fast as
-- lowestCommonAncestor.
lcaBinary :: Int -> (a -> Index) -> BinTree a -> Index -> Index -> a