A fast and flexible O(n) difference algorithm framework for Swift collection.
The algorithm is optimized based on the Paul Heckel's algorithm.

Made with ❤️ byRyo AoyamaandContributors

---

Features

💡 FastestO(n)diffing algorithm optimized for Swift collection

💡 Calculate diffs for batch updates of list UI inUIKit,AppKitandTexture

💡 Supports both linear and sectioned collection even if contains duplicates

💡 Supportsall kind of diffsfor animated UI batch updates

---

Algorithm

This is a diffing algorithm developed forCarbon,works stand alone.
The algorithm optimized based on the Paul Heckel's algorithm.
See also his paper"A technique for isolating differences between files"released in 1978.
It allows all kind of diffs to be calculated in linear timeO(n).
RxDataSourcesandIGListKitare also implemented based on his algorithm.

However, inperformBatchUpdatesofUITableView,UICollectionView,etc, there are combinations of diffs that cause crash when applied simultaneously.
To solve this problem,DifferenceKittakes an approach of split the set of diffs at the minimal stages that can be perform batch updates with no crashes.

Implementation ishere.

---

Getting Started

• API Documentation
• Example Apps
• Benchmark
• Playground

Basic Usage

The type of the element that to take diffs must be conform to theDifferentiableprotocol.
ThedifferenceIdentifier's type is generic associated type:

structUser:Differentiable{
letid:Int
letname:String

vardifferenceIdentifier:Int{
returnid
}

funcisContentEqual(to source:User)->Bool{
returnname==source.name
}
}

In the case of definition above,iduniquely identifies the element and get to know the user updated by comparing equality ofnameof the elements in source and target.

There are default implementations ofDifferentiablefor the types that conforming toEquatableorHashable:

// If `Self` conforming to `Hashable`.
vardifferenceIdentifier:Self{
returnself
}

// If `Self` conforming to `Equatable`.
funcisContentEqual(to source:Self)->Bool{
returnself==source
}

Therefore, you can simply:

extensionString:Differentiable{}

Calculate the diffs by creatingStagedChangesetfrom two collections of elements conforming toDifferentiable:

letsource=[
User(id:0,name:"Vincent"),
User(id:1,name:"Jules")
]
lettarget=[
User(id:1,name:"Jules"),
User(id:0,name:"Vincent"),
User(id:2,name:"Butch")
]

letchangeset=StagedChangeset(source:source,target:target)

If you want to include multiple types conforming toDifferentiablein the collection, useAnyDifferentiable:

letsource=[
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 conforming toDifferentiableSectionprotocol, but in most cases you can useArraySectionthat general type conforming to it.
ArraySectionrequires a model conforming toDifferentiablefor diffing from other sections:

enumModel:Differentiable{
casea,b,c
}

letsource:[ArraySection<Model,String>]=[
ArraySection(model:.a,elements:["A","B"]),
ArraySection(model:.b,elements:["C"])
]
lettarget:[ArraySection<Model,String>]=[
ArraySection(model:.c,elements:["D","E"]),
ArraySection(model:.a,elements:["A"]),
ArraySection(model:.b,elements:["B","C"])
]

letchangeset=StagedChangeset(source:source,target:target)

You can perform diffing batch updates ofUITableViewandUICollectionViewusing the createdStagedChangeset.

⚠️Don't forgettosynchronouslyupdate the data referenced by the data-source, with the data passed in thesetDataclosure. The diffs are applied in stages, and failing to do so is bound to create a crash:

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

Batch updates using too large amount of diffs may adversely affect to performance.
Returningtruewithinterruptclosure then falls back toreloadData:

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

[See More Usage]

---

Comparison with Other Frameworks

Made a fair comparison as much as possible in performance and features with otherpopularandawesomeframeworks.
This doesNOTdetermine superiority or inferiority of the frameworks.
I know that each framework has different benefits.
The frameworks and its version that compared is below.

• DifferenceKit- master
• RxDataSources(Differentiator) - 4.0.1
• FlexibleDiff- 0.0.8
• IGListKit- 3.4.0
• DeepDiff- 2.2.0
• Differ(Diff.swift) - 1.4.3
• Dwifft- 0.9
• Swift.CollectionDifference- Swift 5.1

Performance Comparison

Benchmark project ishere.
Performance was mesured by code compiled usingXcode11.1andSwift 5.1with-Ooptimization and run oniPhone11 Pro simulator.
UseFoundation.UUIDas an element of collections.

- From 5,000 elements to 1,000 deleted, 1,000 inserted and 200 shuffled

	Time(sec)
DifferenceKit	0.0019
RxDataSources	0.0074
IGListKit	0.0346
FlexibleDiff	0.0161
DeepDiff	0.0373
Differ	1.0581
Dwifft	0.4732
Swift.CollectionDifference	0.0620

- From 100,000 elements to 10,000 deleted, 10,000 inserted and 2,000 shuffled

	Time(sec)
DifferenceKit	0.0348
RxDataSources	0.1024
IGListKit	0.7002
FlexibleDiff	0.2189
DeepDiff	0.5537
Differ	153.8007
Dwifft	187.1341
Swift.CollectionDifference	5.0281

Features Comparison

- Algorithm

	Base algorithm	Order
DifferenceKit	Heckel	O(N)
RxDataSources	Heckel	O(N)
FlexibleDiff	Heckel	O(N)
IGListKit	Heckel	O(N)
DeepDiff	Heckel	O(N)
Differ	Myers	O(ND)
Dwifft	Myers	O(ND)
Swift.CollectionDifference	Myers	O(ND)

*Heckel algorithm
*Myers algorithm

- Supported Collection

	Linear	Sectioned	Duplicate element/section
DifferenceKit	✅	✅	✅
RxDataSources	❌	✅	❌
FlexibleDiff	✅	✅	✅
IGListKit	✅	❌	✅
DeepDiff	✅	❌	✅
Differ	✅	✅	✅
Dwifft	✅	✅	✅
Swift.CollectionDifference	✅	❌	✅

*Linearmeans 1-dimensional collection
*Sectionedmeans 2-dimensional collection

- Supported Element Diff

	Delete	Insert	Move	Reload	Move across sections
DifferenceKit	✅	✅	✅	✅	✅
RxDataSources	✅	✅	✅	✅	✅
FlexibleDiff	✅	✅	✅	✅	❌
IGListKit	✅	✅	✅	✅	❌
DeepDiff	✅	✅	✅	✅	❌
Differ	✅	✅	✅	❌	❌
Dwifft	✅	✅	❌	❌	❌
Swift.CollectionDifference	✅	✅	✅	❌	❌

- Supported Section Diff

	Delete	Insert	Move	Reload
DifferenceKit	✅	✅	✅	✅
RxDataSources	✅	✅	✅	❌
FlexibleDiff	✅	✅	✅	✅
IGListKit	❌	❌	❌	❌
DeepDiff	❌	❌	❌	❌
Differ	✅	✅	✅	❌
Dwifft	✅	✅	❌	❌
Swift.CollectionDifference	❌	❌	❌	❌

---

Requirements

• Swift 4.2+
• iOS 9.0+
• tvOS 9.0+
• OS X 10.9+
• watchOS 2.0+ (only algorithm)

---

Installation

CocoaPods

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

pod'DifferenceKit/Core'

iOS / tvOS

To use DifferenceKit with UIKit extension, add the following to yourPodfile:

pod'DifferenceKit'

or

pod'DifferenceKit/UIKitExtension'

macOS

To use DifferenceKit with AppKit extension, add the following to yourPodfile:

pod'DifferenceKit/AppKitExtension'

watchOS

There is no UI extension for watchOS.
To use only algorithm without extensions for UI, add the following to yourPodfile:

pod'DifferenceKit/Core'

Carthage

Add the following to yourCartfile:

github"ra1028/DifferenceKit"

Swift Package Manager for Apple platforms

Select Xcode menuFile > Swift Packages > Add Package Dependencyand enter repository URL with GUI.

Repository: https://github /ra1028/DifferenceKit

Swift Package Manager

Add the following to the dependencies of yourPackage.swift:

.package(url:"https://github /ra1028/DifferenceKit.git",from:"version")

---

Contribution

Pull requests, bug reports and feature requests are welcome 🚀
Please see theCONTRIBUTINGfile for learn how to contribute to DifferenceKit.

---

Credit

Bibliography

DifferenceKit was developed with reference to the following excellent materials and framework.

• A technique for isolating differences between files(byPaul Heckel)
• DifferenceAlgorithmComparison(by@horita-yuya)

OSS using DifferenceKit

The list of the awesome OSS which uses this library. They also help to understanding how to use DifferenceKit.

• Carbon(by@ra1028)
• DiffableDataSources(by@ra1028)
• Rocket.Chat.iOS(byRocketChat)
• wire-ios(byWire Swiss GmbH)
• ReactiveLists(byPlanGrid)
• ReduxMovieDB(by@cardoso)
• TetrisDiffingCompetition(by@skagedal)

Other diffing libraries

I respect and ️❤️ all libraries involved in diffing.

• RxDataSources(by@kzaher,RxSwift Community)
• IGListKit(byInstagram)
• FlexibleDiff(by@andersio,RACCommunity)
• DeepDiff(by@onmyway133)
• Differ(by@tonyarnold)
• Dwifft(by@jflinter)
• Changeset(by@osteslag)

---

License

DifferenceKit is released under theApache 2.0 License.