EditDistance is one of the incremental update tool for UITableView and UICollectionView.

The followings show how this library update UI. They generate the random items and update their UI incrementally.

UITableView	UICollectionView

What's this?

This library pipelines the process to update UITableView and UICollectionView. It is so difficult to update them incrementally, because iOS app developers need to manage differences between the two DataSources.

If you update items for DataSource:

// dataSource has ["Francis Elton", "Stanton Denholm", "Arledge Camden", "Farland Ridley", "Alex Helton"]
var nextDataSource = dataSource

// insertion and deletion to data source
nextDataSource.remove(at: 2)
nextDataSource.insert("Woodruff Chester", at: 1)
nextDataSource.insert("Eduard Colby", at: 3)

Typical code:

// You have to update UITableView according to array's diff.
dataSource = nextDataSource
tableView.beginUpdates()
tableView.deleteRows(at: [IndexPath(row: 2, section: 0)], with: .fade)
tableView.insertRows(at: [IndexPath(row: 1, section: 0), IndexPath(row: 3, section: 0)], with: .fade)
tableView.endUpdates()

EditDistance takes on that task:

// You don't need to write insertion and deletion.
let container = dataSource.diff.compare(to: nextDataSource)
dataSource = nextDataSource
tableView.diff.reload(to: container) 

All you need is to make the updated array.

You don't have to manage how to update incrementally. That enables to pileline the process.

How dose it work?

EditDistance calculates the difference and converts it into an incremental update of UITableView or UICollectionView.

The difference is based on Edit Distance Algorithm. There are many ways to calculate it and almost all of them nearly run in linear time.

• Dynamic Programming (O(NM))
• Mayer's Algorithm (O(ND))
• Wu's Algorithm (O(NP))
• etc.

N and M are sequence sizes of each array. D is edit distance and P is the number of deletion.

In our context, Wu's Algorithm seems to be the best algorithm. It has better performance than the others when your app has many items and adds (or deletes) a few items. (e.g. autopager, access history and notification)

Pros and Cons

Calculation in this library is not always reasonable to update UI. I recommend that your app calculates edit distance in sub-thread and update UI in main-thread.

Feature

• You don't need to calculate diff manually.
• You can choose any diff algorithm as you like.
• You don't need to call reloadRows(at:with:) and performBatchUpdates(_:completion:) anymore.
• minimum implimentation for incremental update

Requirements

• iOS 8.0+
• Xcode 8.1+
• Swift 3.0+

Installation

Carthage

• Install Carthage from Homebrew

> ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
> brew update
> brew install carthage

• Move your project dir and create Cartfile

> touch Cartfile

• add the following line to Cartfile

github "kazuhiro4949/EditDistance"

• Create framework

> carthage update --platform iOS

• In Xcode, move to "Genera > Build Phase > Linked Frameworks and Library"
• Add the framework to your project
• Add a new run script and put the following code

/usr/local/bin/carthage copy-frameworks

• Click "+" at Input file and Add the framework path

$(SRCROOT)/Carthage/Build/iOS/EditDistance.framework

• Write Import statement on your source file

Import EditDistance

CocoaPods

• Install CocoaPods

> gem install cocoapods
> pod setup

• Create Podfile

> pod init

• Edit Podfile

# Uncomment this line to define a global platform for your project
platform :ios, '8.0'  # add
use_framework!  # add

target 'MyAppName' do
  pod 'EditDistance' # add
end

target 'MyAppTests' do

end

target 'MyAppUITests'

• Install

> pod install

open .xcworkspace

Usage

Calculation of differences between two arrays

One dimentional array

1. prepare two arrays.

let current = ["Francis", "Woodruff", "Stanton"]
let next = ["Francis", "Woodruff", "Stanton", "Eduards"]

2. calling diff from Array makes EditDistanceProxy<T> instance.

let proxy = current.diff // => EditDistanceProxy<String>

3. the instance has compare(to:) to calculate diff with next array.

let container = proxy.compare(to: next) // => EditDistanceContainer<String>

Two dimentional array

1. prepare two arrays.

let current = [["Francis", "Woodruff"], ["Stanton"]]
let next = [["Francis", "Woodruff"], ["Stanton", "Eduard"]]

2. instantiate EditDistance object

let editDistance = EditDistance(from: current, to: next) // => EditDistance<String>

3. the instance has compare(to:) to calculate diff with next array.

let container = editDistance.calculate() // => EditDistanceContainer<String>

customizing algorithm

to preset algorithm objcts

let container = current.diff.compare(to: next, with: DynamicAlgorithm())

to closure

// implement algorithm
let algorithm = AnyEditDistanceAlgorithm { (from, to) -> EditDistanceContainer<String> in
    //...
    //...
}

let container = current.diff.compare(to: next, with: algorithm)

make a new algorithm class.

//implements protocol
public struct Wu<T: Equatable>: EditDistanceAlgorithm {
    public typealias Element = T
    
    public func calculate(from: [[T]], to: [[T]]) -> EditDistanceContainer<T> {
      //...
      //...
    }
}

Incremental Update to UITableView

1. Calculate Diff between two arrays

let nextDataSource = ["Francis Elton", "Woodruff Chester", "Stanton Denholm", "Eduard Colby", "Farland Ridley", "Alex Helton"]
let container = dataSource.diff.compare(to: nextDataSource)

2. update DataSource and UI

dataSource = nextDataSource
tableView.diff.reload(with: container) 

If you won't use this library anymore

ataSource = nextDataSource
// tableView.diff.reload(with: container) 
tableView.reloadData()

That's it! 😉

Performance

Wu's algorithm is recommended in this library. The actual speed depends on the number of differences between two arrays and the cost of "==" the elements have. The followings are some avarage speeds for reference. They were executed on iPhone7, iOS 10.2 Simulator and build with "whole module optimization option" setting. The sample arrays are composed of random UUID Strings.

• from 100 items to 120 items (20 addition), avg: 0.001 sec
• from 100 items to 100 items (10 addition and 10 deletion), avg: 0.001 sec
• from 100 items to 200 items (100 addition), avg: 0.001 ms
• from 100 items to 100 items (50 addition and 50 deletion), avg: 0.001 sec
• from 1000 items to 1050 items (50 addition), avg: 0.003 sec
• from 1000 items to 1000 items (25 addition and 25 deletion), avg: 0.003 sec
• from 1000 items to 1200 items (200 addition), avg: 0.003 sec
• from 1000 items to 1000 items (100 addition and 100 deletion), avg: 0.008 sec
• from 10000 items to 10100 items (100 addition), avg: 0.031 sec
• from 10000 items to 10000 items (50 addition and 50 deletion), avg: 0.032 sec
• from 10000 items to 12000 items (2000 addition), avg: 0.033 sec
• from 10000 items to 10000 items (1000 addition and 1000 deletion), avg: 0.055 sec

Test Case is here. You can take reexamination with them.

Class Design

• EditDistance is a director to calculate EditDistanceAlgorithm with two input Array.
• AnyEditDistanceAlgorithm is a type-erased structure to EditDistanceAlgorithm.
• EditDistanceContainer is a container to bridge result of algorithm and view's update.
• EditScriptConverter is a kind of namespace to use some extensions to UIKit classes.
• EditScriptConverterProxy is a proxy for UITableView and UICollectionView. It has method to update the items.

License

Copyright (c) 2017 Kazuhiro Hayashi

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.