Issue #119

This is about collection update, how to provide correct IndexPath and a simple diffing algorithm

CollectionView

It’s hard to imagine of any apps that don’t use Table View or CollectionView. And by CollectionView, I actually mean UICollectionView 😉 . Most of the time, we show something with response from backend, then potentially update and insert new items as data changed.

collectionview

We can totally call reloadData to reflect the changes, but an animation is better here as it gives user better understanding of what’s going on, and to not surprise them.

This talks about UICollectionView, but UITableView behaves the same

Drag and Drop

Let’s imagine an app where user are allowed to customise their experience by moving items from one collection to another.

You can take a look at the example DragAndDrop which is using the new drag and drop API in iOS 11.

ipad

You must ensure that your data is changed before calling update methods on UICollectionView. And then we call deleteItems and insertItems to reflect data changes. UICollectionView performs a nice animation for you

func collectionView(_ collectionView: UICollectionView, performDropWith coordinator: UICollectionViewDropCoordinator) {

  let destinationIndexPath = coordinator.destinationIndexPath
  let sourceIndexPath = coordinator.items.last?.dragItem.localObject as! IndexPath

  // remove
  sourceItems.remove(at: sourceIndexPath.item)
  sourceCollectionView.deleteItems(at: [sourceIndexPath])

  // insert
  destinationItems.insert(draggedItem, at: destinationIndexPath.item)
  destinationCollectionView.insertItems(at: [destinationIndexPath])
}

NSInternalInconsistencyException

If you have large number of items with many insertions and deletions from backend response, you need to calculate the correct IndexPath to call, which are not easy thing. Most the time you will get the following crashes

Terminating app due to uncaught exception ‘NSInternalInconsistencyException’, reason: ‘Invalid update: invalid number of items in section 0. The number of items contained in an existing section after the update (213) must be equal to the number of items contained in that section before the update (154), plus or minus the number of items inserted or deleted from that section (40 inserted, 0 deleted) and plus or minus the number of items moved into or out of that section (0 moved in, 0 moved out).’

In my experience it happened randomly because everyone has different data. Although the message is very descriptive, it may take a while to figure it out.

Game of IndexPath

Let’s refine our knowledge of IndexPath by going through some examples. With a collection of 6 items, we perform some update operations and figure out what IndexPath should be.

items = ["a", "b", "c", "d", "e", "f"]

Take a look at my example here CollectionUpdateExample, there are many more examples

index vs offset

Before we go any further, I just want to mention that, by index I actually mean offset from the start. If you take a look at the enumerated function, it suggests the name as offset instead of index

Array(0..<10).enumerated().forEach { (offset, element) in

}

This zero based numbering could shed some light on this matter

Particularly in C, where arrays are closely tied to pointer arithmetic, this makes for a simpler implementation: the subscript refers to an offset from the starting position of an array, so the first element has an offset of zero.

1. Insert 3 items at the end

items.append(contentsOf: ["g", "h", "i"])

// a, b, c, d, e, f, g, h, i

let indexPaths = Array(6...8).map { IndexPath(item: $0, section: 0) }
collectionView.insertItems(at: indexPaths)

2. Delete 3 items at the end

items.removeLast()
items.removeLast()
items.removeLast()

// a, b, c

let indexPaths = Array(3...5).map { IndexPath(item: $0, section: 0) }
collectionView.deleteItems(at: indexPaths)

3. Update item at index 2

items[2] = "👻"

// a, b, 👻, d, e, f

let indexPath = IndexPath(item: 2, section: 0)
collectionView.reloadItems(at: [indexPath])

4. Move item “c” to the end

items.remove(at: 2)
items.append("c")

// a, b, d, e, f, c

collectionView.moveItem(
  at: IndexPath(item: 2, section: 0),
  to: IndexPath(item: 5, section :0)
)

5. Delete 3 items at the beginning, then insert 3 items at the end

With multiple different operations, we should use performBatchUpdates

You can use this method in cases where you want to make multiple changes to the collection view in one single animated operation, as opposed to in several separate animations. You might use this method to insert, delete, reload, or move cells or use it to change the layout parameters associated with one or more cells

items.removeFirst()
items.removeFirst()
items.removeFirst()

items.append(contentsOf: ["g", "h", "i"])

// d, e, f, g, h, i

collectionView.performBatchUpdates({
  let deleteIndexPaths = Array(0...2).map { IndexPath(item: $0, section: 0) }
  collectionView.deleteItems(at: deleteIndexPaths)

  let insertIndexPaths = Array(3...5).map { IndexPath(item: $0, section: 0) }
  collectionView.insertItems(at: insertIndexPaths)
}, completion: nil)

6. Insert 3 items at the end, then delete 3 items beginning

items.append(contentsOf: ["g", "h", "i"])

items.removeFirst()
items.removeFirst()
items.removeFirst()

// d, e, f, g, h, i

collectionView.performBatchUpdates({
  let insertIndexPaths = Array(6...8).map { IndexPath(item: $0, section: 0) }
  collectionView.insertItems(at: insertIndexPaths)

  let deleteIndexPaths = Array(0...2).map { IndexPath(item: $0, section: 0) }
  collectionView.deleteItems(at: deleteIndexPaths)
}, completion: nil)

🙀

If you run the example 6, you will get a crash

Terminating app due to uncaught exception 
'NSInternalInconsistencyException', 
reason: 'attempt to insert item 6 into section 0, 
but there are only 6 items in section 0 after the update'

performBatchUpdates

It is because the way performBatchUpdates works. If you take a look at the documentation

Deletes are processed before inserts in batch operations. This means the indexes for the deletions are processed relative to the indexes of the collection view’s state before the batch operation, and the indexes for the insertions are processed relative to the indexes of the state after all the deletions in the batch operation.

No matter how we call insert or delete, performBatchUpdates always performs deletions first. So we need to call deleteItems and insertItems as if the deletions occur first.

items.append(contentsOf: ["g", "h", "i"])

items.removeFirst()
items.removeFirst()
items.removeFirst()

// d, e, f, g, h, i

collectionView.performBatchUpdates({
  let deleteIndexPaths = Array(0...2).map { IndexPath(item: $0, section: 0) }
  collectionView.deleteItems(at: deleteIndexPaths)

  let insertIndexPaths = Array(3...5).map { IndexPath(item: $0, section: 0) }
  collectionView.insertItems(at: insertIndexPaths)
}, completion: nil)

Operations

There are many operations on UICollectionView, and there are operations to update whole section as well. Take a look Ordering of Operations and Index Paths

insertItems(at indexPaths: [IndexPath])
deleteItems(at indexPaths: [IndexPath])
reloadItems(at indexPaths: [IndexPath])
moveItem(at indexPath: IndexPath, to newIndexPath: IndexPath)
performBatchUpdates(_ updates, completion)


insertSections(_ sections: IndexSet)
deleteSections(_ sections: IndexSet)
reloadSections(_ sections: IndexSet)
moveSection(_ section: Int, toSection newSection: Int)

inline

Edit distance

Doing these calculations by hand is quite tedious and error prone. We can build our own abstraction using some algorithms. The naive one is Wagner–Fischer algorithm which uses Dynamic Programming to tell the edit distance between two strings of characters.

Edit distance means the number of steps needed to change from one string to another. String is just a collection of characters, so we can generalise this concept to make it work for any collection of items. Instead of comparing character, we require items to conform to Equatable

“kit” -> “kat”

How can we transform form the word “kit” to “kat”? What kinds of operations do we nede to perform? You may tell “just change the i to a”, but this trivial example helps you understand the algorithm. Let’s get started.

inline

Deletions

If we go from “kit” to an empty string “”, we need 3 deletions

inline

“k” -> "" 👉 1 deletion “ki” -> "" 👉 2 deletions “kit” -> "" 👉 3 deletions

Insertions

If we go from an empty string "" to “kat”, we need 3 insertions

inline

"" -> “k” 👉 1 insertion "" -> “ka” 👉 2 insertions "" -> “kat” 👉 3 insertions

If equal, take value from the top left

You can think of the algorithm as if we go from source string, to empty string, to destination string. We try to find the minimum steps to update. Going horizontally means insertions, vertically means deletions and diagonally means substitutions

This way we can build our matrix, iterate from row to row, column by column. First, the letter “k” from source collection is the same with letter “k” from destination collection, we simply take value from the top left, which is 0 substituion

inline

If not equal

We continue with the next letter from the destination collection. Here “k” and “a” are not the same. We take minimum value from left, top, top left. Then increase by one

inline

Here we take value from left, which is horizontally, so we increase by 1 insertion

“k” -> “kat” 👉 2 insertions

Continue, they are not the same, so we take value from left horizontally. Here you can see it kind makes sense, as to go from “k” to “kat”, we need 2 insertions, which is to insert letters “a” and “t”

inline

The bottom right value

Continue with the next row, and next row until we got to the bottom right value, which gives you the edit distance. Here 1 substitution means that we need to perform 1 substitution to go from “kit” to “kat”, which is update “i” with “a'

final

You can easily see that we need to update index 1. But how do we know that it is index 1 🤔

Edit steps

In each step, we need to associate the index of item in source and destination collection. You can take a look at my implementation DeepDiff

inline

Complexity

We iterate through the matrix, with m and n are the length of source and destination collection respectively, we can see that the complexity of this algorithm is 0(mn).

Also the performance greatly depends on the size of the collection and how complex the item is. The more complex and how deep you want to perform Equatable can greatly affect your performance.

Improving performance

The section How does it work shows several ways we can improve performance.

Firstly, instead of building a matrix, which costs memory m*n, we can just use temporary arrays as holder.

Secondly, to quickly compare 2 items, we can use Hashable, as 2 identical items will always have the same hash.

More performance

If you want better performance, then algorithms with linear complexity may be interested to you. Take a look at Diff algorithm