Pure Swift implementation of Paul Heckel's A Technique for Isolating Differences Between Files
This is a simple diff algorithm that provides the minimum set of steps to transform one collection into another. Transformations are listed as discrete operations:
- Insertion - what items should be inserted into the array, and at what index.
- Deletion - what items should be removed from the array, and at what index.
- Move - what items should be moved, and their origin and destination indices.
- Update - what items should be updated/replaced with new context, and at what index.
These operations are calculated in linear time, using the algorithm described in this paper.
Knowing this set of operations is especially handy for efficiently updating UITableViews and UICollectionViews.
Consider a simple example that compares lists of integers:
let o = [1, 2, 3, 3, 4] let n = [2, 3, 1, 3, 4] let result = diff(o, n) // [.move(1, 0), .move(2, 1), .move(0, 2)] let o = [0, 1, 2, 3, 4, 5, 6, 7, 8] let n = [0, 2, 3, 4, 7, 6, 9, 5, 10] let result = diff(o, n) // [.delete(1), .delete(8), .move(7, 4), .insert(6), .move(5, 7), .insert(8)]
orderedDiff is also available, which provides a set of operations that are friendly for batched updates in UIKit contexts (note how
move is replaced by pairs of
let o = [1, 2, 3, 3, 4] let n = [2, 3, 1, 3, 4] let result = orderedDiff(o, n) // [.delete(2), .delete(1), .delete(0), .insert(0), .insert(1), .insert(2)]
HeckelDiff has built-in support for generating efficient batched updates for
UICollectionView. Methods are made available on both that allow informing the corresponding table or collection view that their data model has changed.
tableView.applyDiff(previousItems, newItems, withAnimation: .fade)
Elements in collections passed into
diff must conform to
Hashable. HeckelDiff uses elements'
hashValues to determine whether they should be inserted, deleted or moved. In some cases, elements are instead marked for update. This is because even though the
hashValues of two elements might be equivalent, the elements may not be equal. You can take advantage of this by implementing the
Hashable protocol in such a way that your elements get updated when appropriate.
For example, you may have two records that refer to the same person (perhaps you use a record ID as a hash value). You may want to support a case where a person's phone number may change, but the record itself remains in the same position in the array. Your
Equatable implementation may take the phone number value into account, whereas your
hashValue may only reflect the underlying record ID value.
In the context of a
UICollectionView, you would most efficiently handle this by reloading the given row that needs updating (rather than deleting it and re-inserting it). Use the supplied
applyDiff functions to have HeckelDiff perform this for you.
You can install Carthage with Homebrew using the following command:
$ brew update $ brew install carthage
Add the following line to your Cartfile:
carthage update, then make sure to add
HeckelDiff.framework to "Linked Frameworks and Libraries" and "copy-frameworks" Build Phases.
CocoaPods is a dependency manager for Cocoa projects. You can install it with the following command:
$ gem install cocoapods
To integrate TemplateKit into your Xcode project using CocoaPods, specify it in your
source 'https://github.com/CocoaPods/Specs.git' platform :ios, '10.0' use_frameworks! target '<Your Target Name>' do pod 'HeckelDiff', '~> 0.1.0' end
Then, run the following command:
$ pod install
- iOS 9.0+
- Xcode 8.0+
- Swift 3.0+