Changeset
This is an attempt at implementing the solution outlined in Dave DeLong’s article, Edit distance and edit steps.
A Changeset describes the minimal edits required to go from one Collection of Equatable elements to another.
It has been written primarily to be used in conjunction with UITableView and UICollectionView data sources by detecting additions, deletions, substitutions, and moves between the two sets of data. But it can also be used to compute more general changes between two data sets.
Usage
The following code computes the minimal edits of the canonical example, going from the String collections “kitten” to “sitting”:
let changeset = Changeset(source: "kitten", target: "sitting")
print(changeset)
// 'kitten' -> 'sitting':
// replace with s at offset 0
// replace with i at offset 4
// insert g at offset 6
The following assertion would then succeed:
let edits = [
Changeset<String>.Edit(operation: .substitution, value: "s", destination: 0),
Changeset<String>.Edit(operation: .substitution, value: "i", destination: 4),
Changeset<String>.Edit(operation: .insertion, value: "g", destination: 6),
]
assert(changeset.edits == edits)
If you don’t want the overhead of Changeset itself, which also stores the source and target collections, you can call edits directly (here with example data from Apple’s Table View Programming Guide for iOS):
let source = ["Arizona", "California", "Delaware", "New Jersey", "Washington"]
let target = ["Alaska", "Arizona", "California", "Georgia", "New Jersey", "Virginia"]
let edits = Changeset.edits(from: source, to: target)
print(edits)
// [insert Alaska at offset 0, replace with Georgia at offset 2, replace with Virginia at offset 4]
Note that Changeset uses offsets, not indices, to refer to elements in the collections. This is mainly because Swift collections aren’t guaranteed to use zero-based integer indices. See discussion in issue #37 for more details.
UIKit Integration
The offset values can be used directly in the animation blocks of beginUpdates/endUpdates on UITableView and performBatchUpdates on UICollectionView in that Changeset follows the principles explained under Batch Insertion, Deletion, and Reloading of Rows and Sections in Apple’s guide.
In short; first all deletions and substitutions are made, relative to the source collection, then, relative to the resulting collection, insertions. A move is just a deletion followed by an insertion.
In the iOS framework, two convenience extensions (one on UITableView and one on UICollectionView) have been included to make animated table/collection view updates a breeze. Just call update, like this:
tableView.update(with: changeset.edits)
Custom Comparator
By default a Changeset uses == to compare elements, but you can write your own comparator, illustrated below, where the occurence of an “a” always triggers a change:
let alwaysChangeA: (Character, Character) -> Bool = {
if $0 == "a" || $1 == "a" {
return false
} else {
return $0 == $1
}
}
let changeset = Changeset(source: "ab", target: "ab", comparator: alwaysChangeA)
As a result, the changeset will consist of a substitution of the “a” (to another “a”):
let expectedEdits: [Changeset<String>.Edit] = [Changeset.Edit(operation: .substitution, value: "a", destination: 0)]
assert(changeset.edits == expectedEdits)
One possible use of this is when a cell in a UITableView or UICollectionView shouldn’t animate when they change.
Test App
The Xcode project also contains a target to illustrate the usage in an app:
This uses the extensions mentioned above to animate transitions based on the edits of a Changeset.
License
This project is available under The MIT License.
Copyright © 2015-18, Joachim Bondo. See LICENSE file.
3.3k Jan 4, 2023
2 May 23, 2022
43 Jan 5, 2023
99 Aug 27, 2021
3 Nov 21, 2021
1 Oct 13, 2021
2.8k Dec 30, 2022
89 Dec 26, 2022
43 Nov 6, 2022
25 Dec 29, 2022
44 Dec 24, 2021
415 Dec 5, 2022
53 Mar 31, 2022
0 Nov 7, 2021
773 Dec 27, 2022
119 Dec 7, 2022
64 Aug 17, 2022
157 Sep 26, 2022
128 Dec 28, 2022