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

-- | Calculate edit distances and edit scripts between vectors.
--   
--   An implementation of the Wagner–Fischer dynamic programming algorithm
--   to find the optimal edit script and cost between two sequences.
--   
--   The implementation in this package is specialised to sequences
--   represented with Data.Vector but is otherwise agnostic to:
--   
--   
--   
- The type of values in the vectors;
--   
- The type representing edit operations; and
--   
- The type representing the cost of operations.
--   
@package edit-distance-vector
@version 1.0.0.4

-- | This module implements a variation on the Wagner-Fischer
--   algorithm to find the shortest sequences of operations which
--   transforms one vector of values into another.
module Data.Vector.Distance

-- | Operations invoked by the Wagner-Fischer algorithm.
--   
--   The parameters to this type are as follows:
--   
--   
--   
- v is the type of values being compared,
--   
- o is the type representing operations,
--   
- c is the type representing costs.
--   
--   
--   The chief restrictions on these type parameters is that the cost type
--   c must have instances of Monoid and Ord. A good
--   default choice might be the type (Sum Int).
data Params v o c
Params :: (v -> v -> Bool) -> (Int -> v -> o) -> (Int -> v -> o) -> (Int -> v -> v -> o) -> (o -> c) -> (o -> Int) -> Params v o c

-- | Are two values equivalent?
[equivalent] :: Params v o c -> v -> v -> Bool

-- | Delete the element at an index.
[delete] :: Params v o c -> Int -> v -> o

-- | Insert an element at an index.
[insert] :: Params v o c -> Int -> v -> o

-- | Substitute an element at an index.
[substitute] :: Params v o c -> Int -> v -> v -> o

-- | Cost of a change.
[cost] :: Params v o c -> o -> c

-- | Positions to advance after a change. E.g. 0 for a deletion.
[positionOffset] :: Params v o c -> o -> Int

-- | Matrix of optimal edit scripts and costs for all prefixes of two
--   vectors.
--   
--   This is a representation of the n * m dynamic programming
--   matrix constructed by the algorithm. The matrix is stored in a
--   Vector in row-major format with an additional row and column
--   corresponding to the empty prefix of the source and destination
--   Vectors.
type ChangeMatrix o c = Vector (c, [o])

-- | O(nm). Find the cost and optimal edit script to transform one
--   Vector into another.
leastChanges :: (Monoid c, Ord c) => Params v o c -> Vector v -> Vector v -> (c, [o])

-- | O(nm). Calculate the complete matrix of edit scripts and costs
--   between two vectors.
allChanges :: (Monoid c, Ord c) => Params v o c -> Vector v -> Vector v -> ChangeMatrix o c

-- | Example Params to compare (Vector Char)
--   values.
--   
--   The algorithm will produce edit distances in terms of (Sum
--   Int) and edit scripts containing (String, Int,
--   Char) values.
--   
--   The first component of each operation is either "delete",
--   "insert", or "replace".
strParams :: Params Char (String, Int, Char) (Sum Int)
