LCS-diff.swift

import Swift


func LCS<T: Equatable>(a: [T], b: [T]) -> [[UInt]] {
    let rows = a.count + 1
    let cols = b.count + 1

    var matrix: [[UInt]] = Array(count: rows, repeatedValue: Array(count: cols, repeatedValue: 0))

    for i in 1..<rows {
        for j in 1..<cols {
            if a[i - 1] == b[j - 1] {
                matrix[i][j] = matrix[i - 1][j - 1] + 1
            }
            else {
                matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])
            }
        }
    }

    return matrix;
}

enum Change<T> : Printable, DebugPrintable {
    case Insertion(index: Int, value: @autoclosure () -> T)
    case Removal(index: Int, value: @autoclosure () -> T)

    var description: String {
        switch (self) {
        case let .Insertion(index, value): return "Insertion at \(index), string: \(value())"
        case let .Removal(index, value): return "Removal from \(index), string: \(value())"
        }
    }

    var debugDescription: String {
        return self.description
    }
}

func arrayDiffIter<T: Equatable>(LCS: [[UInt]], i: Int, j: Int, a: [T], b: [T], acc: [Change<T>]) -> [Change<T>] {
    if i > 0 && j > 0 && a[i - 1] == b[j - 1] {
        return arrayDiffIter(LCS, i - 1, j - 1, a, b, acc)
    }
    else if j > 0 && (i == 0 || LCS[i][j - 1] >= LCS[i - 1][j]) {
        let insertion = Change.Insertion(index: j - 1, value: b[j - 1])
        return arrayDiffIter(LCS, i, j - 1, a, b, [ insertion ] + acc)
    }
    else if i > 0 && (j == 0 || LCS[i][j - 1] < LCS[i - 1][j]) {
        let removal = Change.Removal(index: i - 1, value: a[i - 1])
        return arrayDiffIter(LCS, i - 1, j, a, b, [ removal ] + acc)
    }
    else {
        return acc
    }
}

func arrayDiff<T: Equatable>(LCS: [[UInt]], a: [T], b: [T]) -> [Change<T>] {
    return arrayDiffIter(LCS, a.count, b.count, a, b, [])
}

let before = [
    "feedbackType",
    "name",
    "phoneNumber",
    "email",
    "selectedImage",
    "comment",
]

let after = [
    "wat",
    "feedbackType",
    "restaurant",
    "name",
    "phoneNumber",
    "email",
    "comment",
]

let matrix = LCS(before, after)
let diff = arrayDiff(matrix, before, after)

for change in diff {
    println(change.description)
}