Instantly share code, notes, and snippets.

# praeclarum/ArrayDiff.swift

Last active January 8, 2021 06:10
Star You must be signed in to star a gist
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // // 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 { 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(source x: [TSource], destination y: [TDestination], match: (TSource, TDestination) -> Bool) -> [ArrayDiffAction] { 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] = [] 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(to destination: [TDestination], match: (Element, TDestination) -> Bool) -> [ArrayDiffAction] { return ArrayDiffAction.diff(source: self, destination: destination, match: match) } /// Calculate a diff that will convert the source array to this array. func diff(from source: [TSource], match: (TSource, Element) -> Bool) -> [ArrayDiffAction] { return ArrayDiffAction.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(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 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.description)
XCTAssertEqual("Remove(B)", diff.description)
XCTAssertEqual("Remove(C)", diff.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.description)
XCTAssertEqual("Append(B)", diff.description)
XCTAssertEqual("Append(C)", diff.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.description)
XCTAssertEqual("Update(B, B)", diff.description)
XCTAssertEqual("Update(C, C)", diff.description)
XCTAssertEqual("Append(D)", diff.description)
XCTAssertEqual("Append(E)", diff.description)

}

}```

### stepanhruda commented Aug 21, 2015

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