-- 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.
--
-- This implementation is based on an algorithm of Fischer and Heun,
-- which can be found at http://dx.doi.org/10.1007/11780441_5.
-- Despite being written entirely in Haskell (and maintaining referential
-- transparency internally), it is competitive against the C++
-- implementation written by Fischer and Heun themselves (included in the
-- tarball), especially when compiled with LLVM.
--
-- Depending on the target system, this library compiled with -fasm
-- approximately ties with the original authors' C++ implementation
-- compiled with -O3 -funroll-loops. With -fllvm -optlc-O3, this library
-- has been observed to beat the same C++ implementation by 20-30%.
--
-- Internally, this library rolls its own stream fusion system, avoiding
-- the vector package's issues with duplicated index variables
-- and providing a few other special features. This package's API does,
-- however, fuse (to the extent possible) with input vectors using the
-- vector package fusion system. In particular, it automagically
-- recognizes input vectors whose element types have a natural
-- order-preserving injection into Int, converts them, and uses
-- the specialized range-min implementation for Int vectors. See
-- Data.RangeMin for more details.
@package rangemin
@version 2.2.1
module Data.RangeMin.Cartesian
-- | O(n). Given a comparison function and a lookup function, 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 from the original elements. (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.
equivVectorBy :: (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) -> v a -> Int -> Int -> Int
-- rangeMin cmp xs i k = 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.
--
-- When certain methods are called on an element type which has a
-- natural, order-preserving injection into Int -- specifically,
-- on instances of Injective -- this module is smart enough to
-- (fusibly) convert the vector into a Vector Int,
-- and to use unsafeIntRangeMin or intRangeMin as
-- appropriate. Though you cannot make your own instances of
-- Injective, unsafeInjectRangeMin and
-- injectRangeMin work the same way.
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 = Index -> Length -> Index
-- | A function of type LEq a is used as if it were
-- (<=) for comparison purposes. This function
-- must be a total ordering.
type LEq a = a -> a -> Bool
-- | The type of a vector index.
type Index = Int
-- | The type of the length of a vector.
type Length = Int
-- | O(n). Returns a range-min function on the vector, under the
-- natural ordering of Int. This function can be, depending on the
-- Vector implementation, three to four times as fast as
-- unsafeVecRangeMinBy (<=).
--
-- Example:
--
--
-- unsafeIntRangeMin (fromList [0,7,-10,4,5,4]) 0 6 == 2
-- unsafeIntRangeMin (fromList [0,7,-10,4,5,4]) 2 3 == 2
-- unsafeIntRangeMin (fromList [0,7,-10,4,5,4]) 3 3 == 3
--
--
-- The returned function does not do bounds checks. If n
-- is the length of the vector, and i and m are passed
-- as arguments to the RangeMin, then if i < 0, m
-- < 1, or i + m > n, a segfault may occur.
unsafeIntRangeMin :: Vector Int -> RangeMin
-- | O(n). Returns a range-min function on the vector, with the
-- natural ordering of Int. This function can be, depending on the
-- Vector implementation, three to four times as fast as
-- vecRangeMinBy (<=).
--
-- Equivalent to unsafeIntRangeMin, except that the returned
-- function does do bounds checks. When it receives a bad query,
-- it throws an ArrayException.
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; see unsafeIntRangeMin for details.
--
-- Example:
--
--
-- -- Finding the element with the largest absolute value in a subrange.
-- unsafeVecRangeMinBy (\ i j -> abs i >= abs j) (fromList [0,7,-10,4,5,4]) 0 6 == 2
-- unsafeVecRangeMinBy (\ i j -> abs i >= abs j) (fromList [0,7,-10,4,5,4]) 2 3 == 2
-- unsafeVecRangeMinBy (\ i j -> abs i >= abs j) (fromList [0,7,-10,4,5,4]) 3 3 == 4
--
unsafeVecRangeMinBy :: (Vector v a) => LEq a -> v a -> RangeMin
-- | O(n). Equivalent to unsafeVecRangeMinBy
-- (<=). Specialized for instances of Injective.
-- The returned function does not do bounds checks; see
-- unsafeIntRangeMin for details.
--
-- Example:
--
--
-- -- In reality, these would be rewritten into calls to unsafeIntRangeMin, since Char is an
-- -- instance of Injective.
-- unsafeVecRangeMin (fromList "banana") 0 6 == 1
-- unsafeVecRangeMin (fromList "banana") 1 1 == 1
-- unsafeVecRangeMin (fromList "banana") 3 3 == 3
--
unsafeVecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin
-- | O(n). Equivalent to unsafeVecRangeMinBy
-- (>=). Specialized for instances of Injective.
-- The returned function does not do bounds checks; see
-- unsafeIntRangeMin for details.
--
-- Example:
--
--
-- -- In reality, these would be rewritten into calls to unsafeIntRangeMin, since Char
-- -- is an instance of Injective.
-- unsafeVecRangeMax (fromList "banana") 0 6 == 2
-- unsafeVecRangeMax (fromList "banana") 1 1 == 1
-- unsafeVecRangeMax (fromList "banana") 3 3 == 4
--
unsafeVecRangeMax :: (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; see intRangeMin for details.
vecRangeMinBy :: (Vector v a) => LEq a -> v a -> RangeMin
-- | O(n). Equivalent to vecRangeMinBy
-- (<=); a safer version of unsafeVecRangeMin.
-- Specialized for instances of Injective. The returned function
-- does do bounds checks; see intRangeMin for details.
vecRangeMin :: (Vector v a, Ord a) => v a -> RangeMin
-- | O(n). Equivalent to vecRangeMinBy
-- (>=); a safer version of unsafeVecRangeMax.
-- Specialized for instances of Injective. The returned function
-- does do bounds checks; see intRangeMin for details.
vecRangeMax :: (Vector v a, Ord a) => v a -> RangeMin
-- | O(n). unsafeRangeMinBy (<=?) n look is
-- equivalent to unsafeVecRangeMinBy (<=?) (generate
-- n look). The returned function does not do bounds checks;
-- see unsafeIntRangeMin for details.
unsafeRangeMinBy :: LEq a -> Length -> (Index -> a) -> RangeMin
-- | O(n). Equivalent to unsafeRangeMinBy
-- (<=). Specialized for instances of Injective.
-- The returned function does not do bounds checks; see
-- unsafeIntRangeMin for details.
unsafeRangeMin :: (Ord a) => Length -> (Index -> a) -> RangeMin
-- | O(n). Equivalent to unsafeRangeMinBy
-- (>=). Specialized for instances of Injective.
-- The returned function does not do bounds checks; see
-- unsafeIntRangeMin for details.
unsafeRangeMax :: (Ord a) => Length -> (Index -> a) -> RangeMin
-- | O(n). rangeMinBy (<=?) n look is equivalent
-- to vecRangeMinBy (<=?) (generate n look),
-- and is a safer version of unsafeRangeMinBy (<=?) n
-- look. The returned function does do bounds checks; see
-- intRangeMin for details.
rangeMinBy :: LEq a -> Length -> (Index -> a) -> RangeMin
-- | O(n). Equivalent to rangeMinBy (<=),
-- and a safer version of unsafeRangeMin. Specialized for
-- instances of Injective. The returned function does do
-- bounds checks; see intRangeMin for details.
rangeMin :: (Ord a) => Length -> (Index -> a) -> RangeMin
-- | O(n). Equivalent to rangeMinBy (>=),
-- and a safer version of unsafeRangeMax. Specialized for
-- instances of Injective. The returned function does do
-- bounds checks; see intRangeMin for details.
rangeMax :: (Ord a) => Length -> (Index -> a) -> RangeMin
-- | A type is an instance of Injective if it has a natural
-- order-preserving injection into Int, typically but not always
-- fromEnum. Functions like rangeMin and
-- unsafeVecRangeMax which use the element type's natural
-- ordering may be auto-specialized when the element type is an
-- Injective instance.
class (Enum a) => Injective a
-- | O(n). unsafeInjectRangeMin inject xs is
-- equivalent to unsafeVecRangeMinBy (\ x y -> inject x
-- <= inject y) xs, but is frequently much faster, fusing
-- with the input vector and converting it directly to a
-- Vector Int. The returned function does
-- not do bounds checks; see unsafeIntRangeMin for details.
unsafeInjectRangeMin :: (Vector v a) => (a -> Int) -> v a -> RangeMin
-- | O(n). injectRangeMin inject xs is equivalent to
-- vecRangeMinBy (\ x y -> inject x <= inject y)
-- xs, but is frequently much faster, fusing with the input vector
-- and converting it directly to a Vector Int. The
-- returned function does do bounds checks; see intRangeMin
-- for details.
injectRangeMin :: (Vector v a) => (a -> Int) -> v a -> RangeMin
-- | Functions for finding lowest common ancestors in trees in
-- O(1) time, with O(n) preprocessing.
module Data.RangeMin.LCA
-- | The type of a vector index.
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
-- | The type of a vector index.
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