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


-- | (Fast) Dynamic Time Warping
--   
@package dtw
@version 0.9.2.0


-- | This module implements dynamic time warping as described here:
--   <a>http://en.wikipedia.org/w/index.php?title=Dynamic_time_warping&amp;oldid=643501828</a>
--   
--   Additionally <a>fastDtw</a> is implemented as described in the paper:
--   "FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and
--   Space" by Stan Salvador and Philip Chan.
--   
--   Please note that <a>fastDtw</a> is only an approximative solution. If
--   you need the optimal solution and can bear with the heavily increased
--   demand both in cpu and in memory you should use <a>dtwMemo</a> or
--   <a>dtwMemoWindowed</a>.
--   
--   <h2>Example</h2>
--   
--   <pre>
--   &gt;&gt;&gt; -- create two sample datasets
--   
--   &gt;&gt;&gt; let as = [ sin x | x &lt;- [0,0.1..pi] ]
--   
--   &gt;&gt;&gt; let bs = [ sin (x+0.1) | x &lt;- [0,0.1..pi] ]
--   
--   &gt;&gt;&gt; -- define a cost function between two datapoints
--   
--   &gt;&gt;&gt; let dist x y = abs (x-y)
--   
--   &gt;&gt;&gt; -- define a function that will half the size of a dataset (see below)
--   
--   &gt;&gt;&gt; let shrink xs = case xs of (a:b:cs) -&gt; (a+b)/2 : shrink cs; a:[] -&gt; [a]; [] -&gt; []
--   
--   &gt;&gt;&gt; -- calculate the cost with fastDtw and dtwMemo for comparison
--   
--   &gt;&gt;&gt; cost $ fastDtw dist shrink 2 as bs :: Float
--   0.19879311
--   
--   &gt;&gt;&gt; cost $ dtwMemo (\x y -&gt; abs (x-y)) as bs :: Float
--   0.19879311
--   </pre>
--   
--   <h2>Some words on the shrink function</h2>
--   
--   Care must be taken when choosing a shrink function. It's vital that
--   the resolution is halfed, this is not exactly a problem with the
--   algorithm but with the implementation. The lower resolution dataset
--   should be an honest representation of the higher resolution dataset.
--   For starters binning as in the example above should suffice.
module Data.DTW

-- | this is the naive implementation of dynamic time warping no caching
--   what so ever is taking place this should not be used and is just used
--   as a reference for the other implementations
dtwNaive :: (Ord c, Fractional c, DataSet a, DataSet b) => (Item a -> Item b -> c) -> a -> b -> c

-- | this is the "standard" implementation of dynamic time warping O(N^2)
--   is achieved by memoization of previous results
dtwMemo :: (Ord c, Fractional c, DataSet a, DataSet b) => (Item a -> Item b -> c) -> a -> b -> Result c

-- | this is the "fast" implementation of dynamic time warping as per the
--   authors this methods calculates a good approximate result in O(N),
--   depending on the usecase the windowsize should be tweaked
fastDtw :: (Ord c, Fractional c, DataSet a) => (Item a -> Item a -> c) -> (a -> a) -> Int -> a -> a -> Result c

-- | a generic dataset is basically just an indexing function | and an
--   indicator of the dataset size
class DataSet dataset where type family Item dataset :: *
ix :: DataSet dataset => dataset -> Int -> Item dataset
len :: DataSet dataset => dataset -> Int
data Result a
Result :: a -> Path -> Result a
cost :: Result a -> a
path :: Result a -> Path
type Path = [Index]
type Index = (Int, Int)
instance Show a => Show (Result a)
instance Read a => Read (Result a)
instance Eq a => Eq (Result a)
instance Storable a => DataSet (Vector a)
instance Unbox a => DataSet (Vector a)
instance DataSet (Vector a)
instance DataSet [a]
instance DataSet (Seq a)