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


-- | Linear time row minima for totally monotone matrices
--   
--   This implements the SMAWK algorithm by Peter Shor, Shlomo Moran, Alok
--   Aggarwal, Robert Wilber and Maria Klawe for finding the minimum value
--   in each row of an implicitly defined totally monotone matrix.
--   
--   This has many applications in computational geometry, such as finding
--   the farthest point from each point in a convex polygon, finding
--   optimal enclosing polygon. It can also be used to implement paragraph
--   line breaking in a manner analogous to Knuth and Platt, but in linear
--   time. It also has uses in RNA secondary structure prediction, various
--   sequence alignment problems, construction of prefix codes, image
--   thresholding, etc.
@package smawk
@version 0


-- | This module implements a generalized version of the SMAWK algorithm
--   for computing row minima in totally ordered matrices.
--   
--   I do not require rows or column numbers to be actual numbers, or even
--   ordered, instead comparing columns using occurrence order.
--   
--   Unlike <tt>Map</tt>-based implementations, the runtime of this is
--   actually linear.
module Data.Smawk

-- | <i>O(|rows| + |cols|)</i>.
--   
--   Computes <b>row</b> minima in totally monotone matrices using the
--   SMAWK algorithm.
--   
--   Returns <a>Nothing</a> if we have no columns.
smawk :: (Traversable f, Foldable g, Ord a) => f r -> g c -> (r -> c -> a) -> Maybe (f c)

-- | <i>O(|rows| + |cols|)</i>.
--   
--   Computes <b>row</b> minima in totally monotone matrices using the
--   SMAWK algorithm.
smawk1 :: (Traversable f, Foldable1 g, Ord a) => f r -> g c -> (r -> c -> a) -> f c