-- 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
--   <a>http://alfedenzo.livejournal.com/170301.html</a> and
--   <a>http://bramcohen.livejournal.com/73318.html</a>.
@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 <a>diff</a>
Old :: a -> Item a

-- | Value taken from the "new" list, i.e. right argument to <a>diff</a>
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
--   
--   <ul>
--   <li>it is monotonically increasing, and</li>
--   <li>it is at least as long as any other such subsequence.</li>
--   </ul>
--   
--   This function uses patience sort:
--   <a>http://en.wikipedia.org/wiki/Patience_sorting</a>. 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
--   <a>Map</a>s, and ways to manipulate the diffs.
module Patience.Map

-- | The result of a diff of an entry within two <a>Map</a>s.
--   
--   In two <a>Map</a>s 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 <a>Map</a> <tt>k</tt>
--   <tt>a</tt> from a <a>Map</a> <tt>k</tt> (<a>Delta</a> <tt>a</tt>).
--   (Note that this slightly differs from <a>diff</a>, 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 <a>Map</a>s and returns a <a>Map</a> from the same key type
--   to <a>Delta</a> <tt>a</tt>, where <a>Delta</a> <tt>a</tt> encodes
--   differences between entries.
diff :: (Eq a, Ord k) => Map k a -> Map k a -> Map k (Delta a)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- | Map over all the <a>Same</a> 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 <a>Old</a> values, preserving the remaining values in
--   the map.
mapOld' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a)

-- | Map over all the <a>New</a> 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
