smawk-0: Linear time row minima for totally monotone matrices
Safe HaskellNone
LanguageHaskell2010

Data.Smawk

Description

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 Map-based implementations, the runtime of this is actually linear.

Synopsis

Documentation

smawk Source #

Arguments

:: (Traversable f, Foldable g, Ord a) 
=> f r

rows (in any desired ascending order)

-> g c

columns (in any desired ascending order)

-> (r -> c -> a)

a monotone matrix

-> Maybe (f c)

each of the row minima

O(|rows| + |cols|).

Computes row minima in totally monotone matrices using the SMAWK algorithm.

Returns Nothing if we have no columns.

smawk1 Source #

Arguments

:: (Traversable f, Foldable1 g, Ord a) 
=> f r

rows (in any desired ascending order)

-> g c

columns (in any desired ascending order)

-> (r -> c -> a)

a monotone matrix

-> f c

each of the row minima

O(|rows| + |cols|).

Computes row minima in totally monotone matrices using the SMAWK algorithm.