-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Effectively linear range-min algorithms.
--   
--   Rapidly and lazily preprocesses an array or list so that the smallest
--   element in an arbitrary subrange can be found in constant time.
@package rangemin
@version 1.0


-- | This module is designed to implement high-speed versions of the
--   function
--   
--   <pre>
--   rangeMinBy :: (Ix i, IArray a e) =&gt; (e -&gt; e -&gt; Ordering) -&gt; a i e -&gt; ((i, i) -&gt; (i, e))
--   rangeMinBy cmp arr = \r -&gt; minimumBy (\ (i1, e1) (i2, e2) -&gt; cmp e1 e2) [(i, arr ! i) | i &lt;- range r]
--   </pre>
--   
--   To be precise, the implementation this module supplies for
--   sufficiently large n has asymptotics <tt>O(n log* n)</tt> where
--   <tt>log* n</tt> is defined as
--   
--   <pre>
--   log* n	| n &lt;= 2	= 0
--   	| otherwise	= 1 + log* (log2 n)
--   </pre>
--   
--   While there is an asymptotically O(n) algorithm, the overhead
--   associated with certain conversions in that algorithm take
--   considerably longer than this implementation for all reasonable n.
--   Note that log* n grows extraordinarily slowly with n: log* n &lt; 5
--   for n&lt;10^19729.
--   
--   It also includes implementations of a lowest-common-ancestor algorithm
--   on trees with identical asymptotics.
module Data.RangeMin

-- | 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 RangeMin i e = (i, i) -> (i, e)

-- | Given a tree of indexed nodes, returns a function that takes two nodes
--   and returns their lowest common ancestor.
lowestCommonAncestor :: (Ix i) => (i, i) -> Tree i -> ((i, i) -> i)

-- | 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 :: (Ix i) => (a -> Maybe i) -> (i, i) -> Tree a -> ((a, a) -> a)

-- | 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.
lowestCommonAncestorBy' :: (Ix i) => (a -> Maybe i) -> (i, i) -> Tree a -> ((i, i) -> a)

-- | 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. <i>NOT</i> necessarily faster than
--   <a>rangeMinBy'</a>, primarily because most of the algorithms used are
--   based upon careful list folding.
rangeMinBy :: (IArray a e, Ix i, Num i, Enum i) => Comparator e -> a i e -> RangeMin i e

-- | A version of <a>rangeMinBy</a> on elements with their default
--   ordering.
rangeMin :: (IArray a e, Ix i, Num i, Enum i, Ord e) => a i e -> RangeMin i e
rangeMinByM :: (Monad m, MArray a e m, Ix i, Num i, Enum i) => Comparator e -> a i e -> m (RangeMin i e)
rangeMinM :: (Monad m, MArray a e m, Ix i, Num i, Enum i, Ord e) => a i e -> m (RangeMin i e)

-- | 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.
rangeMinBy' :: (Ix i, Num i, Enum i) => Comparator e -> (i, i) -> [e] -> RangeMin i e

-- | A version of <a>rangeMinBy'</a> on elements with their default
--   ordering.
rangeMin' :: (Ix i, Num i, Enum i, Ord e) => (i, i) -> [e] -> RangeMin i e