fast-myers-diff-0.0.0: A fast implementation of the Myers diff algorithm.

Myers.Diff

Description

Myers Diff

This is an implementation of the O(ND) diff algorithm as described in "An O(ND) Difference Algorithm and Its Variations (1986)" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927.

Synopsis

# Diffing

type Diff a = PolyDiff a a Source #

data PolyDiff a b Source #

A value is either from the First list, the Second or from Both. Both contains both the left and right values, in case you are using a form of equality that doesn't check all data (for example, if you are using a custom equality relation to only perform equality on side of a tuple).

Constructors

 First a Second b Both a b

#### Instances

Instances details
 (Show a, Show b) => Show (PolyDiff a b) Source # Instance detailsDefined in Myers.Diff MethodsshowsPrec :: Int -> PolyDiff a b -> ShowS #show :: PolyDiff a b -> String #showList :: [PolyDiff a b] -> ShowS # (Eq a, Eq b) => Eq (PolyDiff a b) Source # Instance detailsDefined in Myers.Diff Methods(==) :: PolyDiff a b -> PolyDiff a b -> Bool #(/=) :: PolyDiff a b -> PolyDiff a b -> Bool #

Text diff

Uses pack and unpack, so does not roundtrip. It uses pack and unpack because Text is not the same as Vector Char; You can't index a text in O(1) time, it takes O(n) time.

String diff

You probably want to use getTextDiff with packed strings instead, but this function doesn't have the roundtripping problem that getTextDiff has.

Grouped String diff

Like getStringDiff but with entire strings instead of individual characters.

getVectorDiff :: Eq a => Vector a -> Vector a -> Vector (Diff a) Source #

Diff two Vectors

Prefer getGroupedVectorDiff for performance reasons.

getGroupedVectorDiff :: Eq a => Vector a -> Vector a -> Vector (Diff (Vector a)) Source #

Diff two Vectors with grouped results

getVectorDiffBy :: forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Vector (PolyDiff a b) Source #

Diff two Vectors with different types using a custom equality operator

Prefer getGroupedVectorDiffBy for performance reasons.

getGroupedVectorDiffBy :: forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Vector (PolyDiff (Vector a) (Vector b)) Source #

Diff two Vectors with grouped results using a custom equality operator

## Internals

data Edit Source #

Constructors

 Delete Delete from the old vector FieldsIntposition in the old vectorIntnumber of items to delete Insert Insert into the old vector FieldsIntposition in the old vectorIntposition in the new vectorIntnumber of items to insert

#### Instances

Instances details
 Source # Instance detailsDefined in Myers.Diff MethodsshowsPrec :: Int -> Edit -> ShowS #show :: Edit -> String #showList ::  -> ShowS # Source # Instance detailsDefined in Myers.Diff Methods(==) :: Edit -> Edit -> Bool #(/=) :: Edit -> Edit -> Bool # Source # Instance detailsDefined in Myers.Diff Methodscompare :: Edit -> Edit -> Ordering #(<) :: Edit -> Edit -> Bool #(<=) :: Edit -> Edit -> Bool #(>) :: Edit -> Edit -> Bool #(>=) :: Edit -> Edit -> Bool #max :: Edit -> Edit -> Edit #min :: Edit -> Edit -> Edit #

getEditScript :: forall a. Eq a => Vector a -> Vector a -> Vector Edit Source #

Compute the edit script to turn a given Vector into the second given Vector

getEditScriptBy :: forall a b. (a -> b -> Bool) -> Vector a -> Vector b -> Vector Edit Source #

Compute the edit script to turn a given Vector into the second given Vector with a custom equality relation

computeDiffFromEditScript :: Vector a -> Vector b -> Vector Edit -> Vector (PolyDiff a b) Source #

Compute a diff using an edit script.

Prefer computeGroupedDiffFromEditScript for performance reasons.

Compute a diff using an edit script.

Prefer computeGroupedDiffFromEditScript for performance reasons.

## Backwards compatibility with Diff

getDiff :: Eq a => [a] -> [a] -> [Diff a] Source #

For backward compatibility with Diff, use more specific functions if you can.

getDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b] Source #

For backward compatibility with Diff, use more specific functions if you can.

getGroupedDiff :: Eq a => [a] -> [a] -> [Diff [a]] Source #

For backward compatibility with Diff, use more specific functions if you can.

getGroupedDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]] Source #

For backward compatibility with Diff, use more specific functions if you can.