Skip to content

Instantly share code, notes, and snippets.

@praeclarum
Last active January 8, 2021 06:10
  • Star 41 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save praeclarum/642212b54d87f4b7aa9c to your computer and use it in GitHub Desktop.
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++
}
}
}
}
@stepanhruda
Copy link

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