• Stars
    star
    3,421
  • Rank 13,070 (Top 0.3 %)
  • Language
    Swift
  • License
    Apache License 2.0
  • Created over 6 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

πŸ’» A fast and flexible O(n) difference algorithm framework for Swift collection.

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

Swift5 Release CocoaPods Carthage Swift Package Manager
CI Status Platform Lincense


Made with ❀️ by Ryo Aoyama and Contributors


Features

πŸ’‘ Fastest O(n) diffing algorithm optimized for Swift collection

πŸ’‘ Calculate diffs for batch updates of list UI in UIKit, AppKit and Texture

πŸ’‘ Supports both linear and sectioned collection even if contains duplicates

πŸ’‘ Supports all kind of diffs for animated UI batch updates


Algorithm

This is a diffing algorithm developed for Carbon, 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 time O(n).
RxDataSources and IGListKit are also implemented based on his algorithm.

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

Implementation is here.


Getting Started

Basic Usage

The type of the element that to take diffs must be conform to the Differentiable protocol.
The differenceIdentifier's type is generic associated type:

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

    var differenceIdentifier: Int {
        return id
    }

    func isContentEqual(to 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 equality of name of the elements in source and target.

There are default implementations of Differentiable for the types that conforming to Equatable or Hashable:

// If `Self` conforming to `Hashable`.
var differenceIdentifier: Self {
    return self
}

// If `Self` conforming to `Equatable`.
func isContentEqual(to source: Self) -> Bool {
    return self == source
}

Therefore, you can simply:

extension String: Differentiable {}

Calculate the diffs 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 conforming 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 conforming to DifferentiableSection protocol, but in most cases you can use ArraySection that general type conforming to it.
ArraySection requires a model conforming to Differentiable for diffing from other sections:

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

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

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

You can perform diffing batch updates of UITableView and UICollectionView using the created StagedChangeset.

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

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

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

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

Comparison with Other Frameworks

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

Performance Comparison

Benchmark project is here.
Performance was mesured by code compiled using Xcode11.1 and Swift 5.1 with -O optimization and run on iPhone11 Pro simulator.
Use Foundation.UUID as 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 βœ… ❌ βœ…

* Linear means 1-dimensional collection
* Sectioned means 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

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

pod 'DifferenceKit/Core'

iOS / tvOS

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

pod 'DifferenceKit'

or

pod 'DifferenceKit/UIKitExtension'

macOS

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

pod 'DifferenceKit/AppKitExtension'

watchOS

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

pod 'DifferenceKit/Core'

Add the following to your Cartfile:

github "ra1028/DifferenceKit"

Select Xcode menu File > Swift Packages > Add Package Dependency and enter repository URL with GUI.

Repository: https://github.com/ra1028/DifferenceKit

Add the following to the dependencies of your Package.swift:

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

Contribution

Pull requests, bug reports and feature requests are welcome πŸš€
Please see the CONTRIBUTING file for learn how to contribute to DifferenceKit.


Credit

Bibliography

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

OSS using DifferenceKit

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

Other diffing libraries

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


License

DifferenceKit is released under the Apache 2.0 License.

More Repositories

1

RACollectionViewReorderableTripletLayout

The custom collectionView layout that can perform reordering of cells by dragging it.
Objective-C
1,481
star
2

Former

Former is a fully customizable Swift library for easy creating UITableView based form.
Swift
1,307
star
3

Carbon

🚴 A declarative library for building component-based user interfaces in UITableView and UICollectionView.
Swift
1,291
star
4

RAReorderableLayout

A UICollectionView layout whitch can move item with drag and drop.
Swift
867
star
5

DiffableDataSources

πŸ’Ύ A library for backporting UITableView/UICollectionViewDiffableDataSource.
Swift
836
star
6

swiftui-hooks

πŸͺ A SwiftUI implementation of React Hooks. Enhances reusability of stateful logic and gives state and lifecycle to function view.
Swift
479
star
7

SwiftUI-Combine

This is an example project of SwiftUI and Combine using GitHub API.
Swift
452
star
8

VueFlux

♻️ Unidirectional State Management Architecture for Swift - Inspired by Vuex and Flux
Swift
331
star
9

PathDynamicModal

A modal view using UIDynamicAnimator, like the Path for iOS.
Swift
286
star
10

swiftui-atom-properties

βš›οΈ Atomic approach state management and dependency injection for SwiftUI
Swift
232
star
11

FloatingActionSheetController

FloatingActionSheetController is a cool design ActionSheetController library written in Swift2.
Swift
140
star
12

DelegateProxy

Proxy for receive delegate events more practically
Swift
129
star
13

RASlideInViewController

RASlideInViewController has an transition effect expressing the depth, and you can dismiss it by draging
Objective-C
127
star
14

Alembic

βš—οΈ Functional JSON Parser - Linux Ready 🐧
Swift
116
star
15

swift-mod

A tool for Swift code modification intermediating between code generation and formatting.
Swift
101
star
16

SwiftUI-Flux

πŸš€ This is a tiny experimental application using SwiftUI with Flux architecture.
Swift
54
star
17

monkey-lang-swift

The Monkey Programming Language written in Swift -- Writing An Interpreter In Go
Swift
17
star
18

LiveStreamingApp

A sample app repository that broadcasting and player of HLS for iOS.
Swift
16
star
19

KenBurnsSlideshowView

Slideshow with Ken Burns effect for iOS.
Swift
11
star
20

VueFluxExample-GitHub

VueFlux VueFluxReactive example project
Swift
8
star
21

OwnKit

My own utility toolkit for ios
Swift
7
star
22

ra1028

2
star
23

Dribbble_client_sample

Swift
1
star