-- 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.1.2
module Data.RangeMin.Cartesian
-- | O(n). Given a comparison function and a vector, this function
-- constructs a Vector Int with the property that
-- the minimum index between i and j in the result
-- vector is the same as the minimum index between i and
-- j in the original vector. (In both cases, ties are broken by
-- which index comes first.)
--
-- This allows us to use the specialized range-min implementation on
-- Vector Int, even for other Vector
-- implementations, other element types, and other comparison functions.
--
-- Internally, this function constructs the Cartesian tree of the input
-- vector (implicitly, to save memory and stack space), and returns the
-- vector of the depth of each element in the tree.
buildDepths :: (Vector v a) => LEq a -> v a -> Vector Int
-- | 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) -> Int -> Int -> v a -> Int
-- rangeMin cmp i k xs = 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.
--
-- Performance node: Compiling this library with LLVM can significantly
-- improve its performance. Depending on the target system, this library
-- compiled with -fasm runs between 10% and 30% slower than a fully
-- optimized and unrolled C++ implementation. With -fllvm -optlc-O3, this
-- library has been observed to beat the same C++ implementation by 15%.
module Data.RangeMin
-- | A range min function. Given an index i and a length
-- m, returns the minimum element in the range
-- i..i+m-1.
type RangeMin = Int -> Int -> Int
-- | A function of type LEq a is used as if it were
-- (<=) for comparison purposes.
type LEq a = a -> a -> Bool
-- | O(n). Returns a range-min function on the vector, under the
-- natural ordering. This function can be six times as fast as
-- unsafeVecRangeMin.
--
-- The returned function does not do bounds checks.
unsafeIntRangeMin :: Vector Int -> RangeMin
-- | O(n). Returns a range-min function on the vector, under the
-- natural ordering. This function can be six times as fast as
-- vecRangeMin.
--
-- The returned function does do bounds checks.
intRangeMin :: Vector Int -> RangeMin
-- | O(n). Returns a range-min function on the vector, under the
-- specified ordering. The returned function does not do bounds
-- checks.
unsafeVecRangeMinBy :: (Vector v a) => LEq a -> v a -> RangeMin
-- | O(n). Returns a range-min function on the vector, under the
-- elements' natural ordering. The returned function does not do
-- bounds checks.
unsafeVecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin
-- | O(n). Returns a range-min function on the vector, under the
-- specified ordering. The returned function does do bounds
-- checks.
vecRangeMinBy :: (Vector v a) => LEq a -> v a -> RangeMin
-- | O(n). Returns a range-min function on the vector, under the
-- elements' natural ordering. The returned function does do
-- bounds checks.
vecRangeMin :: (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