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

-- | Patience diff and longest increasing subsequence
--   
--   This library implements the "patience diff" algorithm, as well as the
--   patience algorithm for the longest increasing subsequence problem.
--   
--   Patience diff computes the difference between two lists, for example
--   the lines of two versions of a source file. It provides a good balance
--   of performance, nice output for humans, and implementation simplicity.
--   For more information, see
--   http://alfedenzo.livejournal.com/170301.html and
--   http://bramcohen.livejournal.com/73318.html.
@package patience
@version 0.3

-- | Implements "patience diff" and the patience algorithm for the longest
--   increasing subsequence problem.
module Patience

-- | The difference between two lists, according to the "patience diff"
--   algorithm.
diff :: Ord a => [a] -> [a] -> [Item a]

-- | An element of a computed difference.
data Item a

-- | Value taken from the "old" list, i.e. left argument to diff
Old :: a -> Item a

-- | Value taken from the "new" list, i.e. right argument to diff
New :: a -> Item a

-- | Value taken from both lists. Both values are provided, in case your
--   type has a non-structural definition of equality.
Both :: a -> a -> Item a

-- | Given: a list of distinct integers. Picks a subset of the integers in
--   the same order, i.e. a subsequence, with the property that
--   
--   
--   
- it is monotonically increasing, and
--   
- it is at least as long as any other such subsequence.
--   
--   
--   This function uses patience sort:
--   http://en.wikipedia.org/wiki/Patience_sorting. For
--   implementation reasons, the actual list returned is the reverse of the
--   subsequence.
--   
--   You can pair each integer with an arbitrary annotation, which will be
--   carried through the algorithm.
longestIncreasing :: [(Int, a)] -> [(Int, a)]
instance GHC.Internal.Data.Data.Data a => GHC.Internal.Data.Data.Data (Patience.Item a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Patience.Item a)
instance GHC.Internal.Base.Functor Patience.Item
instance GHC.Classes.Ord a => GHC.Classes.Ord (Patience.Item a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Patience.Item a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Patience.Item a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Patience.Piece a)

-- | This module provides a lossless way to do diffing between two
--   Maps, and ways to manipulate the diffs.
module Patience.Map

-- | The result of a diff of an entry within two Maps.
--   
--   In two Maps m1 and m2, when performing a diff, this type
--   encodes the following situations:
--   
--   Same key, different values: Stores the two values in the Delta
--   constructor.
--   
--   Same key, same values: Stores the value in the Same constructor.
--   
--   Key exists in m1 but not m2: Stores the value in the Old constructor.
--   
--   Key exists in m2 but not m1: Stores the value in the New constructor.
--   
--   This behaviour ensures that we don't lose any information, meaning we
--   can reconstruct either of the original Map k
--   a from a Map k (Delta a).
--   (Note that this slightly differs from diff, which does not care
--   about the possibility of reconstruction).
data Delta a
Delta :: !a -> !a -> Delta a
Same :: !a -> Delta a
Old :: !a -> Delta a
New :: !a -> Delta a

-- | Takes two Maps and returns a Map from the same key type
--   to Delta a, where Delta a encodes
--   differences between entries.
diff :: (Eq a, Ord k) => Map k a -> Map k a -> Map k (Delta a)

-- | Potentially get the Same value out of a Delta.
getSame :: Eq a => Delta a -> Maybe a

-- | Potentially get the Old value out of a Delta.
getOld :: Delta a -> Maybe a

-- | Potentially get the New value out of a Delta.
getNew :: Delta a -> Maybe a

-- | Potentially get the Changed value out of a Delta.
getDelta :: Delta a -> Maybe (a, a)

-- | Get the original values out of the Delta.
getOriginals :: Delta a -> (Maybe a, Maybe a)

-- | Is the Delta an encoding of same values?
isSame :: Eq a => Delta a -> Bool

-- | Is the Delta an encoding of old values?
isOld :: Delta a -> Bool

-- | Is the Delta an encoding of new values?
isNew :: Delta a -> Bool

-- | Is the Delta an encoding of changed values?
isDelta :: Delta a -> Bool

-- | Retrieve the Same values out of the diff map.
toSame :: Eq a => Map k (Delta a) -> Map k a

-- | Retrieve only the Old values out of the diff map.
toOld :: Map k (Delta a) -> Map k a

-- | Retrieve only the New values out of the diff map.
toNew :: Map k (Delta a) -> Map k a

-- | Retrieve only the DeltaUnit values out of the diff map.
toDelta :: Map k (Delta a) -> Map k (a, a)

-- | Reconstruct both original Maps.
toOriginals :: Map k (Delta a) -> (Map k a, Map k a)

-- | Map over all Same values, returning a map of just the
--   transformed values. This can be more efficient than calling
--   toSame and then Data.Map's map.
mapSame :: Eq a => (a -> b) -> Map k (Delta a) -> Map k b

-- | Map over all Old values, returning a map of just the
--   transformed values. This can be more efficient than calling
--   toOld and then Data.Map's map.
mapOld :: (a -> b) -> Map k (Delta a) -> Map k b

-- | Map over all New values, returning a map of just the
--   transformed values. This can be more efficient than calling
--   toNew and then Data.Map's map.
mapNew :: (a -> b) -> Map k (Delta a) -> Map k b

-- | Map over all the Same values, preserving the remaining values
--   in the map.
mapSame' :: Eq a => (a -> a) -> Map k (Delta a) -> Map k (Delta a)

-- | Map over all the Old values, preserving the remaining values in
--   the map.
mapOld' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a)

-- | Map over all the New values, preserving the remaining values in
--   the map.
mapNew' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Patience.Map.Delta a)
instance GHC.Internal.Data.Foldable.Foldable Patience.Map.Delta
instance GHC.Internal.Base.Functor Patience.Map.Delta
instance GHC.Internal.Generics.Generic1 Patience.Map.Delta
instance GHC.Internal.Generics.Generic (Patience.Map.Delta a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Patience.Map.Delta a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Patience.Map.Delta a)
instance GHC.Internal.Data.Traversable.Traversable Patience.Map.Delta
