名词作用解释
IGListEntry： 用于记录数据在新数组和老数组出现的情况table：存放所有的 Entry，key-valuenewResultsArray：存到new数据的元素 EntryoldResultsArray：存到old数据的元素 EntrynewArry存放着原始新数据的arrayoldArry存放着原始老数据的array
Entry类
1 | struct IGListEntry { |
算法流程
第一步
遍历 newArry，创建 newResultsArray 里面存放着 IGListRecord，每个元素的newCounter大于0，并向oldIndexs栈添加NSNotFound
1 | vector<IGListRecord> newResultsArray(newCount); |
第二步：
遍历 oldArray，创建 oldResultsArray 里面存放着 IGListRecord，每个元素的 oldCounter大于0，并且oldIndexs的top为
当前元素在oldArray的index1
2
3
4
5
6
7
8
9
10
11
12vector<IGListRecord> oldResultsArray(oldCount);
for (NSInteger i = oldCount - 1; i >= 0; i--) {
id<NSObject> key = IGListTableKey(oldArray[i]);
IGListEntry &entry = table[key];
entry.oldCounter++;
// push the original indices where the item occurred onto the index stack
entry.oldIndexes.push(i);
// note: the entry is just a pointer to the entry which is stack-allocated in the table
oldResultsArray[i].entry = &entry;
}
第三步
- 遍历 newResultArray
- 如果当前 oldIndexes pop出来的位置是小于oldCount的话，即表示该元素在oldArray也存在。
- 分别从 newArray[i] (注：这是原始数据，并不是上面的newResultArray) 和oldArray[originalIndex] (同样) 取出元素。进行 diff 比较，如果两个不等，设置 updated = YES
- 如果 newCount 和 oldCount 且 originalIndex != NSNotFound (为什么第三步不用这个来判断？？)。设置 newResultArray和 oldResultArray 里面的 Record 的 index 互为对方的位置;
1 | for (NSInteger i = 0; i < newCount; i++) { |
处理Delete的数据
遍历 oldResultArray ，index 为NSNotFound设置为删除
1 | for (NSInteger i = 0; i < oldCount; i++) { |
offset的示意图(橙色表示会被删除）
Insert、Update、Move处理
添加判断逻辑
在newResultArray 中，代码的判断 record.index == NSNotFound ，那就属于要被添加进去的
更新判断逻辑
同样看下面代码，之前设置了update直接添加到update结果里面就行了。
移动的判断逻辑：
在上面会记录了删除后和插入后的偏移位置，如果 oldIndex - deleteOffset + insertOffset 计算后和当前的位置是一样的，就表示不用移动。就好比：[“1”, “2”, “3”] => [“”2, “3”]，2的这个位置在新数组里面是 0 ，他的oldIndex = 1, deleteOffset也是1，经过删除后，就是0，即不用移动。
1 | for (NSInteger i = 0; i < newCount; i++) { |
最后生成结果
主要把update的变成 insert和delete1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22// convert move+update to delete+insert, respecting the from/to of the move
// 遍历 又要moves和update的值，（前面设置update的时候是还没delete和insert），所以后面会有可能产生 update + move
const NSInteger moveCount = moves.count;
for (NSInteger i = moveCount - 1; i >= 0; i--) {
IGListMoveIndexPath *move = moves[i];
if ([filteredUpdates containsObject:move.from]) {
[filteredMoves removeObjectAtIndex:i];
[filteredUpdates removeObject:move.from];
[deletes addObject:move.from];
[inserts addObject:move.to];
}
}
// iterate all new identifiers. if its index is updated, delete from the old index and insert the new index
// 同理，把从老数数的Map里面，取出要更新的，变成insert和delete
for (id<NSObject> key in [_oldIndexPathMap keyEnumerator]) {
NSIndexPath *indexPath = [_oldIndexPathMap objectForKey:key];
if ([filteredUpdates containsObject:indexPath]) {
[deletes addObject:indexPath];
[inserts addObject:(id)[_newIndexPathMap objectForKey:key]];
}
}
扩展阅读
- DeepDiff库（diff算法的另一种实现）
- https://medium.com/flawless-app-stories/a-better-way-to-update-uicollectionview-data-in-swift-with-diff-framework-924db158db86
- https://xiaozhuanlan.com/topic/6921308745 Wagner–Fischer算法
