diff -Nru haskell-diff-0.1.3/Data/Algorithm/Diff.hs haskell-diff-0.2.0/Data/Algorithm/Diff.hs --- haskell-diff-0.1.3/Data/Algorithm/Diff.hs 2011-07-29 22:18:34.000000000 +0000 +++ haskell-diff-0.2.0/Data/Algorithm/Diff.hs 1970-01-01 00:00:00.000000000 +0000 @@ -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)\" --- . 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) - - diff -Nru haskell-diff-0.1.3/Diff.cabal haskell-diff-0.2.0/Diff.cabal --- haskell-diff-0.1.3/Diff.cabal 2011-07-29 22:18:34.000000000 +0000 +++ haskell-diff-0.2.0/Diff.cabal 2012-12-11 22:04:18.000000000 +0000 @@ -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,12 +16,23 @@ 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 location: http://patch-tag.com/r/sclv/diff diff -Nru haskell-diff-0.1.3/debian/changelog haskell-diff-0.2.0/debian/changelog --- haskell-diff-0.1.3/debian/changelog 2012-03-10 19:11:54.000000000 +0000 +++ haskell-diff-0.2.0/debian/changelog 2013-06-11 23:01:52.000000000 +0000 @@ -1,8 +1,29 @@ -haskell-diff (0.1.3-1build1) precise; urgency=low +haskell-diff (0.2.0-2~ppa1) precise; urgency=low - * No-change rebuild to fix broken haddock dependency + * Backport from Debian unstable - -- Iain Lane Sat, 10 Mar 2012 19:11:54 +0000 + -- Francois Marier Wed, 12 Jun 2013 11:01:40 +1200 + +haskell-diff (0.2.0-2) unstable; urgency=low + + * Enable compat level 9 + + -- Joachim Breitner Fri, 24 May 2013 12:50:27 +0200 + +haskell-diff (0.2.0-1) experimental; urgency=low + + * New upstream release + * Enable test suite + + -- Joachim Breitner Fri, 08 Feb 2013 21:10:52 +0100 + +haskell-diff (0.1.3-2) experimental; urgency=low + + * Depend on haskell-devscripts 0.8.13 to ensure this packages is built + against experimental + * Bump standards version, no change + + -- Joachim Breitner Sun, 14 Oct 2012 12:00:40 +0200 haskell-diff (0.1.3-1) unstable; urgency=low diff -Nru haskell-diff-0.1.3/debian/compat haskell-diff-0.2.0/debian/compat --- haskell-diff-0.1.3/debian/compat 2012-02-07 21:51:10.000000000 +0000 +++ haskell-diff-0.2.0/debian/compat 2013-05-24 07:53:20.000000000 +0000 @@ -1 +1 @@ -7 +9 diff -Nru haskell-diff-0.1.3/debian/control haskell-diff-0.2.0/debian/control --- haskell-diff-0.1.3/debian/control 2012-02-07 21:51:10.000000000 +0000 +++ haskell-diff-0.2.0/debian/control 2013-06-11 23:01:39.000000000 +0000 @@ -3,13 +3,16 @@ Priority: extra Maintainer: Debian Haskell Group Uploaders: Chris Lamb -Build-Depends: debhelper (>= 7) +Build-Depends: debhelper (>= 9) , cdbs - , haskell-devscripts (>= 0.7) + , haskell-devscripts (>= 0.8.13) , ghc , ghc-prof , ghc-doc -Standards-Version: 3.8.4 + , libghc-quickcheck2-dev (>= 2.5) + , libghc-test-framework-dev (>= 0.6) + , libghc-test-framework-quickcheck2-dev (>= 0.2.12.3) +Standards-Version: 3.9.4 Homepage: http://hackage.haskell.org/package/Diff Vcs-Darcs: http://darcs.debian.org/pkg-haskell/haskell-diff Vcs-Browser: http://darcs.debian.org/cgi-bin/darcsweb.cgi?r=pkg-haskell/haskell-diff diff -Nru haskell-diff-0.1.3/debian/rules haskell-diff-0.2.0/debian/rules --- haskell-diff-0.1.3/debian/rules 2012-02-07 21:51:10.000000000 +0000 +++ haskell-diff-0.2.0/debian/rules 2013-02-08 20:10:31.000000000 +0000 @@ -1,4 +1,6 @@ #!/usr/bin/make -f +DEB_ENABLE_TESTS = yes + include /usr/share/cdbs/1/rules/debhelper.mk include /usr/share/cdbs/1/class/hlibrary.mk diff -Nru haskell-diff-0.1.3/src/Data/Algorithm/Diff.hs haskell-diff-0.2.0/src/Data/Algorithm/Diff.hs --- haskell-diff-0.1.3/src/Data/Algorithm/Diff.hs 1970-01-01 00:00:00.000000000 +0000 +++ haskell-diff-0.2.0/src/Data/Algorithm/Diff.hs 2012-12-11 22:04:18.000000000 +0000 @@ -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)\" +-- . 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)