Swiftpack.co - Package - kandelvijaya/FastDiff



Fast Diff CI status

General purpose, fast diff algorithm supporting [m] level nested diffs.

Time Complexity

  • Linear i.e. O(n)

Why?

  1. Faster than the mainstream algorithm. Most diffing algorithm are O(nlogn) or O(n.m). This one is linear O(n).
  2. Most algorithm solve Least Common Subsequence problem which has hard to grasp implementation. This uses 6 simple looping passes.
  3. Supports nested diffing (if you desire)

Installation

Via cocoapods

pod 'FastDiff'

And then in the terminal pod update. If you are new to cocoapods please check out Cocoapods Installation

Via Swift Package Manager

Declare the dependency in the swift Package.swift file like such:

dependencies: [
  ///.... other deps
  .package(url: "https://www.github.com/kandelvijaya/FastDiff", from: "1.0.0"),
]

Execute the update command swift package update and then swift package generate-xcodeproj.

Running the tests

Go to the source directory, and run:

$ swift test

Usage

Algorithm & Verification

let oldModels = ["apple", "microsoft"]
let newModels = ["apple", "microsoft", "tesla"]


/// Algorithm
let changeSet = diff(oldModels, newModels)
// [.addition("tesla", at: 2)]


/// Verification
oldModels.merged(with: changeSet) == newModels 
// true


Note that diff produces changeset that can't be merged into old collections as is, most of the times. The changeset has to be ordered in-order for successful merge. This is also useful if you want to apply changeset to UITableView or UICollectionView.

let chnageSet = diff(["A","B"], [ā€œCā€,"D"])
// [.delete("A",0), .delete("B",1), .add("C",0), .add(ā€œD",1)]

let orderedChangeSet = orderedOperation(from: changeSet)
// [.delete("b",1), .delete("a",0), .add("c",0), .add("d",1)]

Advanced usage & notes

  1. This algorithm works accurately with value types Struct's. Please refrain from using reference type (Class instance). When you must use class instance / object, you might get more updates than you expect. If you want to resolve this issue for your use case please DM me www.twitter.com/kandelvijaya
  2. Tree diffing is possible. However not something the library encourages due to added complexity O(n^2). If you so choose to diff then please use this routine:
    public func diffAllLevel<T>(_ oldContent: [T], _ newContent: [T]) -> [DiffOperation<T>] where T: Diffable, T.InternalItemType == T {
     if oldContent.isEmpty && newContent.isEmpty { return [] }
     var accumulator: [DiffOperation<T>] = []
     let thisLevelDiff = diff(oldContent, newContent)
     for index in thisLevelDiff {
         if case let .update(o, n, _) = index {
             accumulator = accumulator + diffAllLevel(o.children, n.children)
         } else {
             accumulator.append(index)
         }
       }
       return accumulator
     }
    
    
  3. The complexity of Graph diffing depends on graph structure. For Trees, its O(n^2). Please note that this change set is not mergeable to the original tree. To circumvent this limitation, use a node with indexes or indepath that points to the graph position implicitly.

Concept and advanced usage in List View Controller (iOS)

Please check out this presentation slides that I gave at @mobiconf 2018

Contributing

Feel free to contribute with Pull Requests. Should you require more feature, find a bug or want to propose new idea; feel free to post a issue.

Potential Tasks

  • Check the issues section for helpful tasks and more description. This is a good place to start contributing.

Authors

  1. @kandelvijaya (https://twitter.com/kandelvijaya)

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Acknowledgments

  • Inspired by Paul Heckel's paper & algorithm

Github

link
Stars: 17
Help us keep the lights on

Dependencies