Home

Awesome

editdistancelogo

Platform Platform Swift 4.0 Swift 3.2 License Version Carthage compatible

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.

UITableViewUICollectionView
tableviewcollectionview 1

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.

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

Requirements

Installation

Carthage

> ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
> brew update
> brew install carthage
> touch Cartfile
github "kazuhiro4949/EditDistance"
> carthage update --platform iOS
/usr/local/bin/carthage copy-frameworks
$(SRCROOT)/Carthage/Build/iOS/EditDistance.framework
Import EditDistance

CocoaPods

> gem install cocoapods
> pod setup
> pod init
# 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'
> 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! :wink:

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.

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

Class Design

editdistance

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.