I'm a software developer based in the UK. I am blogging regularly about software development & Apple

Custom collection diffing

As mentioned in my previous blog post, I wrote my own custom collection diffing algorithm a while back. Although it's now redundant due to Swift 5's collection diffing support, I'd like to take a look in this post on how I implemented it.

The interface

Since collection diffing should be available to any Collection, the implementation extends Collection. The basic idea for the interface is to provide the steps of how to transform an old List A into a new List A'. These steps can be divided into

  • insertions
  • deletions
  • updates and
  • moves

An updated element is any element that is not inserted, deleted or moved. If there’s no interest in potential updates, it can of course be ignored. By the way, it’s potential updates since the algorithm is based on unique identifiers and hence there is no definite way to know if this is an actual update for the respective data model or not. Nonetheless, it's nice to have these potential candidates handy. The algorithm takes advantage of basic Set methods to categorise each element. For this reason, all Collection elements need to conform to the Hashable protocol.

Putting it all together, the result is the following declaration:

extension Collection where Element : Hashable {

    func transformTo(newList : [Element])  -> (inserted :[(element:Element,index:Int)],
                                                deleted : [(element:Element,index:Int)],
                                             updated : [(element:Element,index:Int)],
                                             moved : [(element:Element,oldIndex:Int,newIndex:Int)])
}

The implementation

Inserted and deleted Elements

Insertions can be determined by removing all elements in the old List from the new List i.e. in Swift using Set methods it looks like this:

let insertedSet = newSet.subtracting(oldSet)

Vice versa, all deleted elements in the new List can be determined by removing all the elements in the new list from the old list:

let deletedSet = oldSet.subtracting(newSet)

With those 2 sets in place, it's time to determine moved elements.

Moved Elements

The basic idea on how to identify moved elements is to gradually convert the old list to the new list:

  1. delete removed elements from old list results in reducedOldList
  2. order the elements in reducedOldList in the order they appear in the new list, which results in updatedList
  3. add new elements to updatedList to get unsortedNewList
  4. compare elements in unsortedNewList and new list to determine movedElementList
  5. reduce movedElementList by transforming unsortedNewList into new list by gradually performing moves from movedElementList. This last step is necessary to get the minimal number of steps to transform old list into new list.

Updated Elements

As mentioned above, having identified inserted, deleted and moved elements, the updated Set is defined by the elements that are not in any of these lists.

Conclusion

To see the algorithm in action check out my iOS app in the Appstore which still uses this algorithm (up to version 1.3). The app visualises arriving buses for nearby bus stops in the London area. The source code can be found here. It's bundled in a sample mac app. To ensure correctness of the algorithm, I backed it up with 20+ tests that can also be found there.

iOS 13 Beta issues