Instantly share code, notes, and snippets.

Embed
What would you like to do?
A generic diffing operation that can calculate the minimal steps needed to convert one array to another. It can be used to generate standard diffs, or it can be used more creatively to calculate minimal UI updates.
//
// ArrayDiff.swift
//
// Created by Frank A. Krueger on 6/30/15.
// Copyright © 2015 Krueger Systems, Inc. All rights reserved.
// License: MIT http://opensource.org/licenses/MIT
//
import Foundation
/// Encapsulates a single action in a diff.
enum ArrayDiffAction<TSource, TDestination> {
case Append(TDestination)
case Update(TSource, TDestination)
case Remove(TSource)
var description: String {
switch self {
case Append(let d): return "Append(\(d))"
case Update(let s, let d): return "Update(\(s), \(d))"
case Remove(let s): return "Remove(\(s))"
}
}
/// Calculate the diff actions from `source` to `destination`.
/// Based on: [Longest Common Subsequence Problem](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem)
private static func diff<TSource, TDestination>(source x: [TSource], destination y: [TDestination], match: (TSource, TDestination) -> Bool) -> [ArrayDiffAction<TSource, TDestination>] {
let m = x.count
let n = y.count
//
// Construct the C matrix
//
var c = (0...m).map({ _ in [Int](count: n + 1, repeatedValue: 0) })
if m > 0 {
for i in 1...m {
if n > 0 {
for j in 1...n {
if match(x[i - 1], y[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1
}
else {
c[i][j] = max (c[i][j - 1], c[i - 1][j])
}
}
}
}
}
//
// Generate the actions
//
var actions: [ArrayDiffAction<TSource, TDestination>] = []
func genDiff(i: Int, _ j: Int) {
if (i > 0 && j > 0 && (match(x[i - 1], y[j - 1]))) {
genDiff(i - 1, j - 1)
actions.append (.Update(x[i - 1], y[j - 1]))
}
else if (j > 0 && (i == 0 || c[i][j - 1] >= c[i - 1][j])) {
genDiff(i, j - 1)
actions.append(.Append(y[j - 1]))
}
else if (i > 0 && (j == 0 || c[i][j - 1] < c[i - 1][j])) {
genDiff(i - 1, j)
actions.append(.Remove(x[i - 1]))
}
}
genDiff(m, n)
return actions
}
}
extension Array {
/// Calculate a diff that will convert this array to another.
func diff<TDestination>(to destination: [TDestination], match: (Element, TDestination) -> Bool) -> [ArrayDiffAction<Element, TDestination>] {
return ArrayDiffAction<Element, TDestination>.diff(source: self, destination: destination, match: match)
}
/// Calculate a diff that will convert the source array to this array.
func diff<TSource>(from source: [TSource], match: (TSource, Element) -> Bool) -> [ArrayDiffAction<TSource, Element>] {
return ArrayDiffAction<TSource, Element>.diff(source: source, destination: self, match: match)
}
/// Mutates this array to match another array while also calling the side-effect functions create, update, and delete.
mutating func merge<TDestination>(to destination: [TDestination], match: (Element, TDestination) -> Bool, create: TDestination -> Element, update: (Element, TDestination) -> Void, delete: Element -> Void) {
let diff = self.diff(to: destination, match: match)
var p = 0
for a in diff {
switch a {
case .Append(let y):
self.insert(create(y), atIndex: p)
p++
case .Remove(let x):
delete(x)
self.removeAtIndex(p)
case .Update(let x, let y):
update(x, y)
p++
}
}
}
}
@praeclarum

This comment has been minimized.

Owner

praeclarum commented Jul 1, 2015

Some tests:

class ArrayDiffTests: XCTestCase {

    func testDiff3to0() {
        let s: [String] = ["A", "B", "C"]
        let d: [String] = []

        let diff = d.diff(from: s, match: ==)

        XCTAssertEqual(3, diff.count)

        XCTAssertEqual("Remove(A)", diff[0].description)
        XCTAssertEqual("Remove(B)", diff[1].description)
        XCTAssertEqual("Remove(C)", diff[2].description)

    }

    func testDiff0to3() {
        let s: [String] = []
        let d: [String] = ["A", "B", "C"]

        let diff = d.diff(from: s, match: ==)

        XCTAssertEqual(3, diff.count)

        XCTAssertEqual("Append(A)", diff[0].description)
        XCTAssertEqual("Append(B)", diff[1].description)
        XCTAssertEqual("Append(C)", diff[2].description)

    }

    func testDiff3to4() {
        let s: [String] = ["A", "B", "C"]
        let d: [String] = ["B", "C", "D", "E"]

        let diff = d.diff(from: s, match: ==)

        XCTAssertEqual(5, diff.count)

        XCTAssertEqual("Remove(A)", diff[0].description)
        XCTAssertEqual("Update(B, B)", diff[1].description)
        XCTAssertEqual("Update(C, C)", diff[2].description)
        XCTAssertEqual("Append(D)", diff[3].description)
        XCTAssertEqual("Append(E)", diff[4].description)

    }

}
@stepanhruda

This comment has been minimized.

stepanhruda commented Aug 21, 2015

This seems useful. Care to release it through a dependency manager?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment