-- | Basic diff type and instances.
module Data.Algorithm.Diff.Type where

import Data.Bifunctor

-- | A value tagged with which of two input sequences it came from.
-- The type parameters @a@ and @b@ may differ, which is useful when comparing
-- sequences of different element types via a custom equality predicate.
--
-- Each constructor corresponds to one outcome for a position in the aligned
-- sequences:
--
-- * 'First' — the element exists only in the /first/ input (a deletion).
-- * 'Second' — the element exists only in the /second/ input (an insertion).
-- * 'Both' — the element is common to both inputs.
--   Both the left and right values are retained so that the original
--   elements can be recovered even when equality ignores some fields.
{-@ data PolyDiff a b = First a | Second b | Both a b @-}
data PolyDiff a b = First a | Second b | Both a b
    deriving (Int -> PolyDiff a b -> ShowS
[PolyDiff a b] -> ShowS
PolyDiff a b -> String
(Int -> PolyDiff a b -> ShowS)
-> (PolyDiff a b -> String)
-> ([PolyDiff a b] -> ShowS)
-> Show (PolyDiff a b)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall a b. (Show a, Show b) => Int -> PolyDiff a b -> ShowS
forall a b. (Show a, Show b) => [PolyDiff a b] -> ShowS
forall a b. (Show a, Show b) => PolyDiff a b -> String
$cshowsPrec :: forall a b. (Show a, Show b) => Int -> PolyDiff a b -> ShowS
showsPrec :: Int -> PolyDiff a b -> ShowS
$cshow :: forall a b. (Show a, Show b) => PolyDiff a b -> String
show :: PolyDiff a b -> String
$cshowList :: forall a b. (Show a, Show b) => [PolyDiff a b] -> ShowS
showList :: [PolyDiff a b] -> ShowS
Show, PolyDiff a b -> PolyDiff a b -> Bool
(PolyDiff a b -> PolyDiff a b -> Bool)
-> (PolyDiff a b -> PolyDiff a b -> Bool) -> Eq (PolyDiff a b)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a b. (Eq a, Eq b) => PolyDiff a b -> PolyDiff a b -> Bool
$c== :: forall a b. (Eq a, Eq b) => PolyDiff a b -> PolyDiff a b -> Bool
== :: PolyDiff a b -> PolyDiff a b -> Bool
$c/= :: forall a b. (Eq a, Eq b) => PolyDiff a b -> PolyDiff a b -> Bool
/= :: PolyDiff a b -> PolyDiff a b -> Bool
Eq)

instance Functor (PolyDiff a) where
  fmap :: forall a b. (a -> b) -> PolyDiff a a -> PolyDiff a b
fmap a -> b
_ (First a
a) = a -> PolyDiff a b
forall a b. a -> PolyDiff a b
First a
a
  fmap a -> b
g (Second a
b) = b -> PolyDiff a b
forall a b. b -> PolyDiff a b
Second (a -> b
g a
b)
  fmap a -> b
g (Both a
a a
b) = a -> b -> PolyDiff a b
forall a b. a -> b -> PolyDiff a b
Both a
a (a -> b
g a
b)

instance Bifunctor PolyDiff where
  bimap :: forall a b c d.
(a -> b) -> (c -> d) -> PolyDiff a c -> PolyDiff b d
bimap a -> b
f c -> d
_ (First a
a) = b -> PolyDiff b d
forall a b. a -> PolyDiff a b
First (a -> b
f a
a)
  bimap a -> b
_ c -> d
g (Second c
b) = d -> PolyDiff b d
forall a b. b -> PolyDiff a b
Second (c -> d
g c
b)
  bimap a -> b
f c -> d
g (Both a
a c
b) = b -> d -> PolyDiff b d
forall a b. a -> b -> PolyDiff a b
Both (a -> b
f a
a) (c -> d
g c
b)

-- | This is 'PolyDiff' specialized so both sides are the same type.
type Diff a = PolyDiff a a