Finds a diff between two sequences (that contain possibly different types). Include merge.

ListDiff.fs

namespace Praeclarum

type ListDiffAction<'TSource, 'TDestination> =
    | Add of Destination : 'TDestination
    | Update of Source : 'TSource * Destination : 'TDestination
    | Remove of Source : 'TSource 


/// Finds a diff between two sequences (that contain possibly different types).
/// Actions are generated such that the order of items in the
/// destination list is preserved.
/// The algorithm is from: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
type ListDiff<'TSource, 'TDestination> (sources : 'TSource seq, destinations : 'TDestination seq, matcher : 'TSource -> 'TDestination -> bool) =

    let x = sources |> Seq.toArray
    let y = destinations |> Seq.toArray

    let m = x.Length
    let n = y.Length

    //
    // Construct the C matrix
    //
    let c = Array2D.zeroCreate (m + 1) (n + 1)
    do
        for i = 1 to m do
            for j = 1 to n do
                if matcher x.[i - 1] y.[j - 1] then
                    c.[i, j] <- c.[i - 1, j - 1] + 1
                else
                    c.[i, j] <- System.Math.Max (c.[i, j - 1], c.[i - 1, j])

    //
    // Generate the actions
    //
    let actions = ResizeArray<ListDiffAction<'TSource, 'TDestination>>();

    let rec genDiff i j =
        if (i > 0 && j > 0 && (matcher x.[i - 1] y.[j - 1])) then
            genDiff (i - 1) (j - 1)
            actions.Add (Update (x.[i - 1], y.[j - 1]))
        else
            if (j > 0 && (i = 0 || c.[i, j - 1] >= c.[i - 1, j])) then
                genDiff i (j - 1)
                actions.Add (Add y.[j - 1])
            else
                if (i > 0 && (j = 0 || c.[i, j - 1] < c.[i - 1, j])) then
                    genDiff (i - 1) j
                    actions.Add (Remove x.[i - 1])

    do genDiff m n

    /// The actions needed to transform a source list to a destination list.
    member this.Actions = actions




[<AutoOpen>]
module ListDiffEx =
    type System.Collections.Generic.IList<'T> with
        member source.MergeInto<'TDestination> (destination : 'TDestination seq) (matcher : 'T -> 'TDestination -> bool) create update remove =

            let diff = ListDiff<'T, 'TDestination> (source, destination, matcher)

            let mutable p = 0

            for a in diff.Actions do
                match a with
                | Add x -> 
                    source.Insert (p, create x)
                    p <- p + 1
                | Remove x ->
                    remove x
                    source.RemoveAt (p)
                | Update (x, y) ->
                    update x y
                    p <- p + 1

            diff