{-
Copyright (C) 2007 John MacFarlane <jgm@berkeley.edu>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
-}

{- |
   Module      : Diff
   Copyright   : Copyright (C) 2007 John MacFarlane
   License     : GNU GPL, version 2 or above 

   Maintainer  : John MacFarlane <jgm@berkeley@edu>
   Stability   : alpha 
   Portability : portable

Functions for computing and applying diffs between a source and a target
list.
-}
module Diff ( Change (..), applyChanges, diffsFrom ) where

-- http://urchin.earth.li/darcs/igloo/lcs/Data/List/LCS
import Data.List.LCS.HuntSzymanski (lcs) 
import Data.List (break)
import Data.Char (ord)
import Test.QuickCheck

-- | A changeset is represented as a set of instructions to insert,
-- delete, or skip (keep) characters in the source string.
data Change a = Ins [a] | Keep Int | Del Int deriving (Eq, Show, Read)

-- | Apply a changeset to a list.
applyChanges :: [Change a] -> [a] -> [a]
applyChanges changes source = 
    snd $ foldl applyChange (source, []) changes 
    where applyChange (source, dest) (Ins x) = (source, dest ++ x)
          applyChange (source, dest) (Keep n) = let common = take n source
                                                in  (drop n source, dest ++ common) 
          applyChange (source, dest) (Del n) = (drop n source, dest) 

adjust :: Eq a => ([a], [a], [Change a]) -> a -> ([a], [a], [Change a])
adjust (left, right, diffs) elt = 
    let (lfront, lback) = break (== elt) left
        (rfront, rback) = break (== elt) right
        dels = if null lfront then [] else [Del (length lfront)]
        inss = if null rfront then [] else [Ins rfront]
    in  (tail lback, tail rback, 
         diffs ++ dels ++ inss ++ [(Keep 1)])

-- | Generate list of changes needed to get from source to target list.
diffsFrom :: Ord a => [a] -> [a] -> [Change a]
diffsFrom left right =
    let common = lcs left right 
        (left', right', diffs') = foldl adjust (left, right, []) common 
    in  diffs' ++ (if null left' then [] else [Del (length left')]) ++ 
        (if null right' then [] else [Ins right']) 

-- Tests

testDiff = quickCheck ((\x y -> (applyChanges (diffsFrom x y) x) == y) :: [Int] -> [Int] -> Bool)