lxcid / listdiff

Swift port of IGListKit's IGListDiff

ListDiff

ListDiff is a Swift port of IGListKit's IGListDiff. It is an implementation of an algorithm by Paul Heckel that calculates the diff between 2 arrays.

Motivation

The motivation for this project came from the following challenge which I learnt about it from Ryan Nystrom's talk at iOSConf.SG.

Getting Started

swift package generate-xcodeproj

Installation

CocoaPods

pod 'ListDiff'

Carthage

github "lxcid/ListDiff" "master"

Usage

import ListDiff

extension Int : Diffable {
    public var diffIdentifier: AnyHashable {
        return self
    }
}
let o = [0, 1, 2]
let n = [2, 1, 3]
let result = List.diffing(oldArray: o, newArray: n)
// result.hasChanges == true
// result.deletes == IndexSet(integer: 0)
// result.inserts == IndexSet(integer: 2)
// result.moves == [List.MoveIndex(from: 2, to: 0), List.MoveIndex(from: 1, to: 1)]
// result.changeCount == 4

Rationale

During the port, I made several decisions which I would like to rationalize here.

• Using caseless enum as namespace. See Erica Sadun's post here.
• No support for index paths. Decided that this is out of the scope.
• Stack vs Heap. AFAIK, Swift does not advocates thinking about stack vs heap allocation model, leaving the optimization decisions to compiler instead. Nevertheless, some of the guideline do favour struct more, so only List.Entry is a (final) class as we need reference to its instances.

Alternatives

• Diff by Andrew Breckenridge

listdiff's Issues

Adopting walkarounds for UICollectionView

The original implementation of the diffing algorythm has some walkarounds to respect UICollectionView's internal behaviour and prevent UICollectionView from throwing exceptions in performBatchUpdates function:

https://github.com/Instagram/IGListKit/blob/master/Source/Common/IGListIndexPathResult.m#L41
https://github.com/Instagram/IGListKit/blob/master/Source/Common/IGListIndexSetResult.m#L43

Without those walkarounds I receive lots of

attempt to perform a delete and a move from the same index path (<NSIndexPath: 0xc00000000ce00016> {length = 2, path = 0 - 103})

in a stress test with a collection of 1000 elements being under repeated random inserts, deletes, moves and updates repeated

So, I wonder, were there any reasons for loosing that functionality in this port?

Equatable intersects with other comparing parts in project

Diffable uses == operator to determine if two objects are same or not. If you are using ListDiff when some model stores visual information and in the same time is a part of another system which is basing on == operator it breaks the logic.
For example you have a Post and each post has a badge of views.

class Post: Diffable {
  var id: Int
  var badge: Int

 func ==(lhs: Post, rhs: Post) -> Bool { return lhs.id == rhs.id && lhs.badge == rhs.badge }
 var diffIdentifier: AnyHashable { return self.id }
}

The PK is id attribute. Badge is just a number to render and doesn't represent object itself. Let's assume you want to refresh your views since badge is not the same. Then badge becomes a part of ==. So if you are trying to lookup though the array of posts having id only then it requires write blocks like where: { $0.id == some_id } which is not correct and other libs based on == couldn't success to find an object, etc.

Expected behaviour is to have an independent operator/method to differentiate two objects for updates.

Thanks

Thanks for making this library. Very good performance compared to other libraries! ❤️