UITableView has built-in methods for adding and removing cells with animations, but it has no way of peeking into your data source to understand how it has changed. Understanding which elements in a list were removed, which stayed the same, and which were added, seems like a thing computers would be really good at. It turns out, it is.
The technique is called the Longest Common Subsequence. I wrote a category on NSArray to calculate this. For the actual algorithm, I used a bottom-up dynamic programming solution, with results cached in a C matrix. It isn’t terribly complex, and I shamelessly stole my implementation from this page. You can also read a more in-depth explanation on Wikipedia.
The algorithm operates in O(mn) time, where m and n are the lengths of the two arrays. Determining the equality of objects is done through the isEquals: method, so be sure that your implementation of that method represents equality for your objects.
Adaptation
In adapting this algorithm for Cocoa, I took advantage of NSIndexSet, which is a great class that lets you store a group of unique indexes. Returning NSIndexSets gives you the benefit of being able to call -[NSArray objectsAtIndexes:] to easily get access to the objects themselves.
Building the table of the lengths of common subsequences is the first step. Once we have our table of subsequence lengths, we can backtrack through it to get the indexes of the common objects. This technique is documented in a few places, including both of the links above. If all you need is the common indexes, there is a convenience method for you:
- (NSIndexSet*) indexesOfCommonElementsWithArray:(NSArray*)array;
Of course, this is Cocoa, and we want to be able to use this information with UIKit, namely, UITableView and UICollectionView. If we can figure out what format the data should be for the -insertRowsAtIndexPaths:withRowAnimation: and -deleteRowsAtIndexPaths:withRowAnimation: methods, we can really easily transform from any arbitrary array to any other array.
For this, a second method is provided. It has two inout parameters that return the extra data that is needed.
- (NSIndexSet*) indexesOfCommonElementsWithArray:(NSArray*)array addedIndexes:(NSIndexSet**)addedIndexes removedIndexes:(NSIndexSet**)removedIndexes;
You can see that a sample implementation (for any general case of data!) is pretty simple.
NSIndexSet *addedIndexes, *removedIndexes;
[oldData indexesOfCommonElementsWithArray:newData addedIndexes:&addedIndexes removedIndexes:&removedIndexes];
self.dataSource = newData;
NSMutableArray *indexPathsToAdd = [NSMutableArray array], *indexPathsToDelete = [NSMutableArray array];
[addedIndexes enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
[indexPathsToAdd addObject:[NSIndexPath indexPathForRow:idx inSection:0]];
}];
[removedIndexes enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
[indexPathsToDelete addObject:[NSIndexPath indexPathForRow:idx inSection:0]];
}];
[_tableView beginUpdates];
[_tableView insertRowsAtIndexPaths:indexPathsToAdd withRowAnimation:UITableViewRowAnimationAutomatic];
[_tableView deleteRowsAtIndexPaths:indexPathsToDelete withRowAnimation:UITableViewRowAnimationAutomatic];
[_tableView endUpdates];
Calculation of the added and removed indexes
The key to finding the right indexes was (as always) in the Apple documentation:
[
UITableView] defers any insertions of rows or sections until after it has handled the deletions of rows or sections.
This means the deleted objects have to be found first. Once they’ve been removed, we have only the common objects left. We can then compare the new array to the list of common objects, and find the indexes that the new tableview rows will need to be added at.
One caveat is that UITableView doesn’t like when you try to add two insert animations for the same row, so we increment by one if that index is already in the addedIndexes set.
Source
The source can be found on GitHub. Pull requests are encouraged, but make sure that the tests are all passing before submitting a pull request.
