Diff 0.1.3 → 0.2.0

raw patch · 3 files changed

+123/−89 lines, 3 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/Algorithm/Diff.hs +0/−87
• Diff.cabal +13/−2
• src/Data/Algorithm/Diff.hs +110/−0

@@ -1,87 +0,0 @@--------------------------------------------------------------------------------- |--- Module      :  Data.Algorithm.Diff--- Copyright   :  (c) Sterling Clover 2008-2011, Kevin Charter 2011--- License     :  BSD 3 Clause--- Maintainer  :  s.clover@gmail.com--- Stability   :  experimental--- Portability :  portable------ This is an implementation of the O(ND) diff algorithm as described in--- \"An O(ND) Difference Algorithm and Its Variations (1986)\"--- <http://citeseer.ist.psu.edu/myers86ond.html>. It is O(mn) in space.--- The algorithm is the same one used by standared Unix diff.--- The assumption is that users of this library will want to diff over--- interesting things or peform interesting tasks with the results--- (given that, otherwise, they would simply use the standard Unix diff--- utility). Thus no attempt is made to present a fancier API to aid--- in doing standard and uninteresting things with the results.--------------------------------------------------------------------------------module Data.Algorithm.Diff (DI(..), getDiff, getGroupedDiff) where-import Data.Array-import Data.List---- | Difference Indicator. A value is either from the First list, the Second--- or from Both.-data DI = F | S | B deriving (Show, Eq)--data DL = DL {poi :: !Int, poj :: !Int, path::[DI]} deriving (Show, Eq)--instance Ord DL where x <= y = poi x <= poi y--canDiag :: (a -> a -> Bool) -> [a] -> [a] -> Int -> Int -> Int -> Int -> Bool-canDiag eq as bs lena lenb i j =-   if i < lena && j < lenb then (arAs ! i) `eq` (arBs ! j) else False-    where arAs = listArray (0,lena - 1) as-          arBs = listArray (0,lenb - 1) bs--dstep :: (Int -> Int -> Bool) -> [DL] -> [DL]-dstep cd dls = hd:pairMaxes rst-  where (hd:rst) = nextDLs dls-        nextDLs [] = []-        nextDLs (dl:rest) = dl':dl'':nextDLs rest-          where dl'  = addsnake cd $ dl {poi=poi dl + 1, path=(F : pdl)}-                dl'' = addsnake cd $ dl {poj=poj dl + 1, path=(S : pdl)}-                pdl = path dl-        pairMaxes [] = []-        pairMaxes [x] = [x]-        pairMaxes (x:y:rest) = max x y:pairMaxes rest--addsnake :: (Int -> Int -> Bool) -> DL -> DL-addsnake cd dl-    | cd pi pj = addsnake cd $-                 dl {poi = pi + 1, poj = pj + 1, path=(B : path dl)}-    | otherwise   = dl-    where pi = poi dl; pj = poj dl--lcs :: (a -> a -> Bool) -> [a] -> [a] -> [DI]-lcs eq as bs = path . head . dropWhile (\dl -> poi dl /= lena || poj dl /= lenb) .-            concat . iterate (dstep cd) . (:[]) . addsnake cd $-            DL {poi=0,poj=0,path=[]}-            where cd = canDiag eq as bs lena lenb-                  lena = length as; lenb = length bs---- | Takes two lists and returns a list indicating the differences--- between them.-getDiff :: (Eq t) => [t] -> [t] -> [(DI, t)]-getDiff = getDiffBy (==) ---- | Takes two lists and returns a list indicating the differences--- between them, grouped into chunks.-getGroupedDiff :: (Eq t) => [t] -> [t] -> [(DI, [t])]-getGroupedDiff = getGroupedDiffBy (==)---- | generalized `getDiff`-getDiffBy :: (t -> t -> Bool) -> [t] -> [t] -> [(DI, t)]-getDiffBy eq a b = markup a b . reverse $ lcs eq a b-    where markup (x:xs)   ys   (F:ds) = (F, x) : markup xs ys ds-          markup   xs   (y:ys) (S:ds) = (S, y) : markup xs ys ds-          markup (x:xs) (_:ys) (B:ds) = (B, x) : markup xs ys ds-          markup _ _ _ = []---- | generalized `getGroupedDiff`-getGroupedDiffBy eq a b = map go . groupBy (\x y -> fst x == fst y) $ getDiffBy eq a b-    where go ((d,x) : xs) = (d, x : map snd xs)--

@@ -1,5 +1,5 @@ name:                Diff-version:             0.1.3+version:             0.2.0 synopsis:            O(ND) diff algorithm in haskell. description:         Basic implementation of the standard diff algorithm. category:            Algorithms@@ -16,11 +16,22 @@  library   if flag(small-base)-    build-depends:     base >= 3 && <= 5, array+    build-depends:     base >= 3 && <= 6, array   else     build-depends:     base < 3 +  hs-source-dirs:    src   exposed-modules:   Data.Algorithm.Diff   ghc-options:       -O2 -Wall -funbox-strict-fields++-- test-suite properties+--   hs-source-dirs: src, test+--   main-is:        Test.hs+--   type:           exitcode-stdio-1.0++--   build-depends:+--     QuickCheck     >= 2.4,+--     test-framework >= 0.4,+--     test-framework-quickcheck2 >= 0.2  source-repository head   type:      darcs

@@ -0,0 +1,110 @@+-----------------------------------------------------------------------------+-- |+-- Module      :  Data.Algorithm.Diff+-- Copyright   :  (c) Sterling Clover 2008-2011, Kevin Charter 2011+-- License     :  BSD 3 Clause+-- Maintainer  :  s.clover@gmail.com+-- Stability   :  experimental+-- Portability :  portable+--+-- 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>. It is O(mn) in space.+-- The algorithm is the same one used by standared Unix diff.+-----------------------------------------------------------------------------++module Data.Algorithm.Diff+    ( Diff(..)+    -- * Comparing lists for differences+    , getDiff+    , getDiffBy++    -- * Finding chunks of differences+    , getGroupedDiff+    , getGroupedDiffBy+    ) where++import Prelude hiding (pi)++import Data.Array++data DI = F | S | B deriving (Show, Eq)++-- | 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+-- newtype to only perform equality on side of a tuple).+data Diff a = First a | Second a | Both a a deriving (Show, Eq)++data DL = DL {poi :: !Int, poj :: !Int, path::[DI]} deriving (Show, Eq)++instance Ord DL where x <= y = poi x <= poi y++canDiag :: (a -> a -> Bool) -> [a] -> [a] -> Int -> Int -> Int -> Int -> Bool+canDiag eq as bs lena lenb i j =+   if i < lena && j < lenb then (arAs ! i) `eq` (arBs ! j) else False+    where arAs = listArray (0,lena - 1) as+          arBs = listArray (0,lenb - 1) bs++dstep :: (Int -> Int -> Bool) -> [DL] -> [DL]+dstep cd dls = hd:pairMaxes rst+  where (hd:rst) = nextDLs dls+        nextDLs [] = []+        nextDLs (dl:rest) = dl':dl'':nextDLs rest+          where dl'  = addsnake cd $ dl {poi=poi dl + 1, path=(F : pdl)}+                dl'' = addsnake cd $ dl {poj=poj dl + 1, path=(S : pdl)}+                pdl = path dl+        pairMaxes [] = []+        pairMaxes [x] = [x]+        pairMaxes (x:y:rest) = max x y:pairMaxes rest++addsnake :: (Int -> Int -> Bool) -> DL -> DL+addsnake cd dl+    | cd pi pj = addsnake cd $+                 dl {poi = pi + 1, poj = pj + 1, path=(B : path dl)}+    | otherwise   = dl+    where pi = poi dl; pj = poj dl++lcs :: (a -> a -> Bool) -> [a] -> [a] -> [DI]+lcs eq as bs = path . head . dropWhile (\dl -> poi dl /= lena || poj dl /= lenb) .+            concat . iterate (dstep cd) . (:[]) . addsnake cd $+            DL {poi=0,poj=0,path=[]}+            where cd = canDiag eq as bs lena lenb+                  lena = length as; lenb = length bs++-- | Takes two lists and returns a list of differences between them. This is+-- 'getDiffBy' with '==' used as predicate.+getDiff :: (Eq t) => [t] -> [t] -> [Diff t]+getDiff = getDiffBy (==)++-- | Takes two lists and returns a list of differences between them, grouped+-- into chunks. This is 'getGroupedDiffBy' with '==' used as predicate.+getGroupedDiff :: (Eq t) => [t] -> [t] -> [Diff [t]]+getGroupedDiff = getGroupedDiffBy (==)++-- | A form of 'getDiff' with no 'Eq' constraint. Instead, an equality predicate+-- is taken as the first argument.+getDiffBy :: (t -> t -> Bool) -> [t] -> [t] -> [Diff t]+getDiffBy eq a b = markup a b . reverse $ lcs eq a b+    where markup (x:xs)   ys   (F:ds) = First x  : markup xs ys ds+          markup   xs   (y:ys) (S:ds) = Second y : markup xs ys ds+          markup (x:xs) (y:ys) (B:ds) = Both x y : markup xs ys ds+          markup _ _ _ = []++getGroupedDiffBy :: (t -> t -> Bool) -> [t] -> [t] -> [Diff [t]]+getGroupedDiffBy eq a b = go $ getDiffBy eq a b+    where go (First x  : xs) = let (fs, rest) = goFirsts  xs in First  (x:fs)     : go rest+          go (Second x : xs) = let (fs, rest) = goSeconds xs in Second (x:fs)     : go rest+          go (Both x y : xs) = let (fs, rest) = goBoth    xs +                                   (fxs, fys) = unzip fs+                               in Both (x:fxs) (y:fys) : go rest+          go [] = []                                  ++          goFirsts  (First x  : xs) = let (fs, rest) = goFirsts  xs in (x:fs, rest)+          goFirsts  xs = ([],xs)++          goSeconds (Second x : xs) = let (fs, rest) = goSeconds xs in (x:fs, rest)+          goSeconds xs = ([],xs)++          goBoth    (Both x y : xs) = let (fs, rest) = goBoth xs    in ((x,y):fs, rest)+          goBoth    xs = ([],xs)