Diff 0.1.2 → 0.1.3

raw patch · 2 files changed

+45/−30 lines, 2 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/Algorithm/Diff.hs +36/−25
• Diff.cabal +9/−5

@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module      :  Data.Algorithm.Diff--- Copyright   :  (c) Sterling Clover 2008+-- Copyright   :  (c) Sterling Clover 2008-2011, Kevin Charter 2011 -- License     :  BSD 3 Clause -- Maintainer  :  s.clover@gmail.com -- Stability   :  experimental@@ -26,51 +26,62 @@ -- or from Both. data DI = F | S | B deriving (Show, Eq) -data DL = DL {poi::Int, poj::Int, path::[DI]} 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 :: (Eq a)  => [a] -> [a] -> Int -> Int -> (Int, Int) -> Bool-canDiag as bs lena lenb = \(i,j) ->-   if i < lena && j < lenb then arAs ! i == arBs ! j else False+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 -chunk :: Int -> [a] -> [[a]]-chunk x = unfoldr (\a -> case splitAt x a of ([],[]) -> Nothing; a' -> Just a')--dstep :: ((Int,Int)->Bool) -> [DL] -> [DL]-dstep cd dls = map maximum $ [hd]:(chunk 2 rst)-    where (hd:rst)  = concatMap extend dls-          extend dl = let pdl = path dl-                      in [addsnake cd $ dl {poi=poi dl + 1, path=(F : pdl)},-                          addsnake cd $ dl {poj=poj dl + 1, path=(S : pdl)}]+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 :: (Int -> Int -> Bool) -> DL -> DL addsnake cd dl-    | cd (pi, pj) = addsnake cd $-                   dl {poi = pi + 1, poj = pj + 1, path=(B : path 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 :: (Eq a) => [a] -> [a] -> [DI]-lcs as bs = path . head . dropWhile (\dl -> poi dl /= lena || poj dl /= lenb) .+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 as bs lena lenb+            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 a b = markup a b . reverse $ lcs a b+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 _ _ _ = [] --- | Takes two lists and returns a list indicating the differences--- between them, grouped into chunks.-getGroupedDiff :: (Eq t) => [t] -> [t] -> [(DI, [t])]-getGroupedDiff a b = map go . groupBy (\x y -> fst x == fst y) $ getDiff a b+-- | 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.2+version:             0.1.3 synopsis:            O(ND) diff algorithm in haskell. description:         Basic implementation of the standard diff algorithm. category:            Algorithms@@ -10,14 +10,18 @@ Tested-With:         GHC == 6.8.2 Build-Type:          Simple build-Depends:       base-Cabal-Version:       >= 1.2+Cabal-Version:       >= 1.6  flag small-base  library   if flag(small-base)-    build-depends:     base >= 3, array+    build-depends:     base >= 3 && <= 5, array   else-    build-depends:     base < 3+    build-depends:     base < 3    exposed-modules:   Data.Algorithm.Diff-  ghc-options:       -Wall+  ghc-options:       -O2 -Wall -funbox-strict-fields++source-repository head+  type:      darcs+  location:  http://patch-tag.com/r/sclv/diff