Diff (empty) → 0.1

raw patch · 4 files changed

+130/−0 lines, 4 filesdep +arraydep +basesetup-changed

Dependencies added: array, base

Files

Data/Algorithm/Diff.hs +77/−0
Diff.cabal +23/−0
LICENSE +27/−0
Setup.lhs +3/−0

+ Data/Algorithm/Diff.hs view

@@ -0,0 +1,77 @@+-----------------------------------------------------------------------------+-- |+-- Module      :  Data.Algorithm.Diff+-- Copyright   :  (c) Sterling Clover 2008+-- 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.Unboxed+import Data.List++data DL = DL {poi::Int, poj::Int, path::[DI]} deriving (Show, Eq)++instance Ord DL where x <= y = poi x <= poj x++-- | Difference Indicator. A value is either from the First list, the Second+-- or from Both.+data DI = F | S | B deriving (Show, Eq)++canDiag :: Eq a => [a] -> [a] -> Int -> Int -> (Int, Int) -> Bool+canDiag as bs lena lenb =+    safeGet $ array ( (0, 0) , (lena-1, lenb-1) )+      [( (i, j), a'==b' ) | (a',i) <- zip as [0..], (b',j) <- zip bs [0..]]+    where+      safeGet :: UArray (Int, Int) Bool -> (Int, Int) -> Bool+      safeGet ar ind@(i,j) = if i < lena && j < lenb then ar ! ind else False++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)}]++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 :: (Eq a) => [a] -> [a] -> [DI]+lcs 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+                  lena = length as; lenb = length bs++-- | Takes two lists and returns a list indicating the differnences+-- between them.+getDiff :: (Eq t) => [t] -> [t] -> [(DI, t)]+getDiff x y = markup x y . reverse $ lcs x y+    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) (y:ys) (B:ds) = (B, x) : markup xs ys ds+          markup _ _ _ = []++-- | Takes two lists and returns a list indicating the differnences+-- 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+    where go ((d,x) : xs) = (d, x : map snd xs)

+ Diff.cabal view

@@ -0,0 +1,23 @@+name:                Diff+version:             0.1+synopsis:            O(ND) diff algorithm in haskell.+description:         Basic implementation of the standard diff algorithm.+category:            Algorithms+license:             BSD3+license-file:        LICENSE+author:              Sterling Clover+maintainer:          s.clover@gmail.com+Tested-With:         GHC == 6.8.2+Build-Type:          Simple+build-Depends:       base+Cabal-Version:       >= 1.2++flag small-base++library+  if flag(small-base)+    build-depends:     base >= 3, array+  else+    build-depends:     base < 3+  exposed-modules:   Data.Algorithm.Diff+  ghc-options:       -Wall

+ LICENSE view

@@ -0,0 +1,27 @@+Copyright (c) Stering Clover 2008++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:+1. Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.+2. Redistributions in binary form must reproduce the above copyright+   notice, this list of conditions and the following disclaimer in the+   documentation and/or other materials provided with the distribution.+3. Neither the name of the author nor the names of his contributors+   may be used to endorse or promote products derived from this software+   without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE+ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY+OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF+SUCH DAMAGE.

+ Setup.lhs view

@@ -0,0 +1,3 @@+#!/usr/bin/env runhaskell+> import Distribution.Simple+> main = defaultMain