DeepDiff

DeepDiff tells the difference between 2 collections and the changes as edit steps. It works on any collection of Equatable and Hashable items.

Usage

Basic

The result of diff is an array of changes, which is [Change]. A Change can be

• .insert: The item was inserted at an index
• .delete: The item was deleted from an index
• .replace: The item at this index was replaced by another item
• .move: The same item has moved from this index to another index

By default, there is no .move. But since .move is just .delete followed by .insert of the same item, it can be reduced by specifying reduceMove to true.

Here are some examples

let old = Array("abc")
let new = Array("bcd")
let changes = diff(old: old, new: new)

// Delete "a" at index 0
// Insert "d" at index 2

let old = Array("abcd")
let new = Array("adbc")
let changes = diff(old: old, new: new, reduceMove: true)

// Move "d" from index 3 to index 1

let old = [
  City(name: "New York"),
  City(name: "Imagine City"),
  City(name: "London")
]

let new = [
  City(name: "New York"),
  City(name: "Oslo"),
  City(name: "London"),
]

let changes = diff(old: old, new: new)

// Replace "Imagine City" with "Oslo" at index 1

Animate UITableView and UICollectionView

Changes to DataSource can be animated by using batch update, as guided in Batch Insertion, Deletion, and Reloading of Rows and Sections

Since Change returned by DeepDiff follows the way batch update works, animating DataSource changes is easy.

let oldItems = items
items = DataSet.generateNewItems()
let changes = diff(old: oldItems, new: items, reduceMove: true)

collectionView.reload(changes: changes, completion: { _ in })

Take a look at Demo where changes are made via random number of items, and the items are shuffled.

How does it work

If you recall from school, there is Levenshtein distance which counts the minimum edit distance to go from one string to another.

Based on that, the current version of DeepDiff implements Wagner–Fischer algorithm, which uses dynamic programming to compute the edit steps between 2 strings of characters. DeepDiff generalizes this to make it work for any collection.

Some optimisations

• Check empty old or new collection to return early
• Use Hashable to quickly check that 2 items are not equal
• Follow "We can adapt the algorithm to use less space, O(m) instead of O(mn), since it only requires that the previous row and current row be stored at any one time." to use 2 rows, instead of matrix to reduce memory storage.

The performance greatly depends on the number of items, the changes and the complexity of the equal function.

Wagner–Fischer algorithm has O(mn) complexity, so it should be used for collection with < 100 items.

There are other algorithms that are interesting

• A technique for isolating differences between files
• An O(ND) Difference Algorithm and Its Variations
• An O(NP) Sequence Comparison Algorithm

Installation

DeepDiff is available through CocoaPods. To install it, simply add the following line to your Podfile:

pod 'DeepDiff'

DeepDiff is also available through Carthage. To install just write into your Cartfile:

github "onmyway133/DeepDiff"

DeepDiff can also be installed manually. Just download and drop Sources folders in your project.

Author

Khoa Pham, onmyway133@gmail.com

Contributing

We would love you to contribute to DeepDiff, check the CONTRIBUTING file for more info.

License

DeepDiff is available under the MIT license. See the LICENSE file for more info.