✅ Calculate commands for batch-updates of UITableView and UICollectionView automatically
✅ O(n) difference algorithm optimized for performance in Swift
✅ Supports both linear and sectioned collection
✅ Supports calculating differences with best effort even if elements or section contains duplicates
✅ Supports all commands for animating UI batch-updates including section reloads

The algorithm is optimized based on the Paul Heckel's algorithm.
See also his paper A technique for isolating differences between files released in 1978.
RxDataSources and IGListKit are also implemented based on his algorithm.
This allows all types of differences to be computed in linear time O(n).

However, in performBatchUpdates of UITableView and UICollectionView, there are combinations of commands that cause crash when applied simultaneously.
To solve this problem, DifferenceKit takes an approach of split the set of differences at the minimal stages that can be perform batch-updates with no crashes.

Implementation is here.

See docs in GitHub Pages.
Documentation is generated by jazzy.

• Example app
• Playground

The type of the element that to take the differences must be conform to the Differentiable protocol:

struct User: Differentiable {
    let id: Int
    let name: String

    var differenceIdentifier: Int {
        return id
    }

    func isUpdated(from source: User) -> Bool {
        return name != source.name
    }
}

In the case of definition above, id uniquely identifies the element and get to know the user updated by comparing name of the elements in source and target.

There are default implementations of Differentiable for the types that conformed to Equatable or Hashable.
However, isUpdated(from:) is always returns false on the algorithm in default, so you can't know the update:

extension String: Differentiable {}

You can calculate the differences by creating StagedChangeset from two collections of elements conforming to Differentiable:

let source = [
    User(id: 0, name: "Vincent"),
    User(id: 1, name: "Jules")
]
let target = [
    User(id: 1, name: "Jules"),
    User(id: 0, name: "Vincent"),
    User(id: 2, name: "Butch")
]

let changeset = StagedChangeset(source: source, target: target)

If you want to include multiple types conformed to Differentiable in the collection, use AnyDifferentiable:

let source = [
    AnyDifferentiable("A"),
    AnyDifferentiable(User(id: 0, name: "Vincent"))
]

In the case of sectioned collection, the section itself must have a unique identifier and be able to compare whether there is an update.
So each section must conform to DifferentiableSection protocol, but in most cases you can use Section that general type conformed to it.
Section requires a model conforming to Differentiable for differentiate from other sections:

enum Model: Differentiable {
    case a, b, c
}

let source: [Section<Model, String>] = [
    Section(model: .a, elements: ["A", "B"]),
    Section(model: .b, elements: ["C"])
]
let target: [Section<Model, String>] = [
    Section(model: .c, elements: ["D", "E"])
    Section(model: .a, elements: ["A"]),
    Section(model: .b, elements: ["B", "C"])
]

let changeset = StagedChangeset(source: source, target: target)

You can incremental updates UITableView and UICollectionView using the created StagedChangeset.
Don't forget to update the data referenced by the dataSource in setData closure, as the differences is applied in stages:

tableView.reload(using: changeset, with: .fade) { data in
    dataSource.data = data
}

Batch-updates using too large amount of differences may adversely affect to performance.
Returning true with interrupt closure then falls back to reloadDate:

collectionView.reload(using: changeset, interrupt: { $0.changeCount > 100 }) { data in
    dataSource.data = data
}

Made a fair comparison as much as possible in features and performance with other popular and awesome frameworks.
The frameworks and its version that compared is below.

• DifferenceKit - 0.1.0
• RxDataSources (Differentiator) - 3.0.2
• IGListKit - 3.4.0
• ListDiff - 0.1.0
• Differ (Diff.swift) - 1.2.3
• Dwifft - 0.8

• Supported collection
  Linear means 1-dimensional collection.
  Sectioned means 1-dimensional collection.

• Supported element differences

• Supported section differences

Performance was measured using XCTestCase.measure with -O -whole-module-optimization.
Each framework uses a function that can compute as much differences as possible.
Use Foundation.UUID as an element.

• From 5,000 elements to 500 deleted and 500 inserted

• From 10,000 elements to 1,000 deleted and 1,000 inserted

• From 100,000 elements to 10,000 deleted and 10,000 inserted

• Swift4.1+
• iOS 10.0+
• tvOS 10.0+

Add the following to your Podfile:

use_frameworks!

target 'TargetName' do
  pod 'DifferenceKit'
end

To use only algorithm without extensions for UI, add the following:

use_frameworks!

target 'TargetName' do
  pod 'DifferenceKit/Core'
end

And run

pod install

Add the following to your Cartfile:

github "ra1028/DifferenceKit"

And run

carthage update

Welcome to fork and submit pull requests.
Before submitting pull request, please ensure you have passed the included tests.
If your pull request including new function, please write test cases for it.

DifferenceKit is released under the MIT License.