IGListKit

使用Android的RecyclerView时系统有一个很好用的工具类DiffUtil，它可以帮我们比对两组数据的差异，然后输出结果直接应用到RecyclerView进行更新，不需要我们自己执行插入删除移动这些指令。但iOS系统没有提供类似的方法，不过我们可以利用IGListKit来实现。

IGListKit的基本使用：

首先要创建一个IGListAdapter，创建时需设置IGListAdapterUpdater、UIViewController、UICollectionView，另外还要设置IGListAdapter的`IGListAdapterDataSource。

通IGListAdapterDataSource的objectsForListAdapter:提供IGListAdapter需要的数据，还有listAdapter:sectionControllerForObject:提供每个数据对应的IGListSectionController。

IGListSectionController顾名思义就是设置Section的，默认的numberOfItems是1。另外通过cellForItemAtIndex:来返回这个section下面的cell。

数据更新

当我们修改数据源后，调用IGListAdapter的performUpdatesAnimated:completion:请求更新。

IGListAdapter有一个IGListSectionMap 保存了objects和对应的sectionControllers，这个类让这两个东西双向绑定。objects和sectionControllers的设置是在updateWithObjects:sectionControllers:方法中完成的：

- (void)updateWithObjects:(NSArray *)objects sectionControllers:(NSArray *)sectionControllers {
    IGParameterAssert(objects.count == sectionControllers.count);

    [self reset];

    self.mObjects = [objects mutableCopy];

    id firstObject = objects.firstObject;
    id lastObject = objects.lastObject;

    [objects enumerateObjectsUsingBlock:^(id object, NSUInteger idx, BOOL *stop) {
        IGListSectionController *sectionController = sectionControllers[idx];

        // set the index of the list for easy reverse lookup
        [self.sectionControllerToSectionMap setObject:@(idx) forKey:sectionController];
        [self.objectToSectionControllerMap setObject:sectionController forKey:object];

        sectionController.isFirstSection = (object == firstObject);
        sectionController.isLastSection = (object == lastObject);
        sectionController.section = (NSInteger)idx;
    }];
}

这个方法在IGListAdapter的_updateObjects:dataSource:中调用。

要比对两组数据的差异，就需要fromObjects和toObjects。更新时先从IGListSectionMap取出现在的objects也就是fromObjects。

toObjects这里提供了两种方式获取，一种是在调用更新是就直接拿到并保存下来，一种是真正执行比对的时候再获取，因为后面执行更新是异步到主线程的。这里实现的方式是把它包装到一个block里面：

    IGListToObjectBlock toObjectsBlock;
    __weak __typeof__(self) weakSelf = self;
    if (IGListExperimentEnabled(self.experiments, IGListExperimentDeferredToObjectCreation)) {
        toObjectsBlock = ^NSArray *{
            __typeof__(self) strongSelf = weakSelf;
            if (strongSelf == nil) {
                return nil;
            }
            return [dataSource objectsForListAdapter:strongSelf];
        };
    } else {
        NSArray *newObjects = [dataSource objectsForListAdapter:self];
        toObjectsBlock = ^NSArray *{
            return newObjects;
        };
    }

接着调用IGListUpdatingDelegate的performUpdateWithCollectionViewBlock:fromObjects:toObjectsBlock:animated:objectTransitionBlock:completion:，这里有两个类实现了这个协议，IGListAdapterUpdater和IGListReloadDataUpdater，我们主要看IGListAdapterUpdater。

IGListAdapterUpdater会先把fromObjects保存下来，但这时可能已经存在fromObjects了，因为后面真正执行更新的操作是异步的，可以假设这个异步要等很久，在这个过程IGListAdapter可能持续被调用更新，所以得取最初的fromObjects和最后的toObjects。

self.fromObjects = self.fromObjects ? : self.pendingTransitionToObjects ? : fromObjects;

self.fromObjects是上一次更新后和下一次开始之前这段时间内的第一个fromObjects。self.pendingTransitionToObjects是上一次还未完成的toObjects。这样设置可以保证fromObjects是取最初的fromObjects和最后的toObjects。

再来到_queueUpdateWithCollectionViewBlock:通过异步把更新操作分发除去，为什么要异步？因为要预留一些时间来收集更新，以防每次都都要更新。

- (void)_queueUpdateWithCollectionViewBlock:(IGListCollectionViewBlock)collectionViewBlock {
    IGAssertMainThread();

    __weak __typeof__(self) weakSelf = self;

    // dispatch_async to give the main queue time to collect more batch updates so that a minimum amount of work
    // (diffing, etc) is done on main. dispatch_async does not garauntee a full runloop turn will pass though.
    // see -performUpdateWithCollectionView:fromObjects:toObjects:animated:objectTransitionBlock:completion: for more
    // details on how coalescence is done.
    dispatch_async(dispatch_get_main_queue(), ^{
        if (weakSelf.state != IGListBatchUpdateStateIdle
            || ![weakSelf hasChanges]) {
            return;
        }

        if (weakSelf.hasQueuedReloadData) {
            [weakSelf performReloadDataWithCollectionViewBlock:collectionViewBlock];
        } else {
            [weakSelf performBatchUpdatesWithCollectionViewBlock:collectionViewBlock];
        }
    });
}

这里有个判断，是直接执行reloadData还是执行Batch Updates。如果外面调用了reloadDataWithCollectionViewBlock:reloadUpdateBlock:completion:那么hasQueuedReloadData就为YES。

看看Batch Updates做了什么：

1、把相关数据保存到局部变量，然后清除所有状态，这样新的一轮更新状态可以先进行保存；
2、把toObjects保存到pendingTransitionToObjects，这样在更新时如果有新的刷新进来那fromObjects就是pendingTransitionToObjects；
3、执行数据比对performDiff()拿到结果；
4、根据比对结果来performUpdate；
5、通知IGListAdapter更新sectionMap的数据，包括objects和sectionControllers，因为要开始通知collectionview更新了，数据要先更新；
6、执行_flushCollectionView:withDiffResult:batchUpdates:fromObjects: 把diff结果更新到collectionview；
7、更新结束后清空batchUpdates和pendingTransitionToObjects；
8、更新完成后调用completionBlock；
9、接着继续调用_queueUpdateWithCollectionViewBlock:以防在这期间有更新。

到这里更新就结束了。

Diff算法

算法的基本思路是这样的：

1、遍历新数组，创建一个列表nl，这个列表的元素是数据的值和Index；
2、遍历旧数组，创建一个列表ol；
3、遍历nl，如果该元素在ol中也存在，那么记为为entry match；
4、遍历ol，如果该元素已经被标为entry match就跳过，否则记为delete；
5、遍历nl，如果该元素没有entry match则记为insert；如果有entry match，看index是否变化，如果有就记为move，否则就是not modified。

整个算法的复杂度为O(n)。

来看IGListKit的实现：

1、首先如果newCount为空，则直接返回全部删除；如果oldCount为空，则直接返回全部插入。
2、接着创建一个表来保存每个元素及其对应的位置信息，

unordered_map<id<NSObject>, IGListEntry, IGListHashID, IGListEqualID> table;

key的类型是id<NSObject>，我们的元素都是实现IGListDiffable协议的，所以key直接就是id<NSObject> key = [object diffIdentifier];，这个表保存了新旧所有数据以及对应的位置index信息。

IGListEntry保存了这个元素在新旧数组分别出现的次数以及在旧数组的index数组

/// Used to track data stats while diffing.
struct IGListEntry {
    /// The number of times the data occurs in the old array
    NSInteger oldCounter = 0;
    /// The number of times the data occurs in the new array
    NSInteger newCounter = 0;
    /// The indexes of the data in the old array
    stack<NSInteger> oldIndexes;
    /// Flag marking if the data has been updated between arrays by checking the isEqual: method
    BOOL updated = NO;
};

接下来创建nl：

    // pass 1
    // create an entry for every item in the new array
    // increment its new count for each occurence
    vector<IGListRecord> newResultsArray(newCount);
    for (NSInteger i = 0; i < newCount; i++) {
        id<NSObject> key = IGListTableKey(newArray[i]);
        IGListEntry &entry = table[key];
        entry.newCounter++;

        // add NSNotFound for each occurence of the item in the new array
        entry.oldIndexes.push(NSNotFound);

        // note: the entry is just a pointer to the entry which is stack-allocated in the table
        newResultsArray[i].entry = &entry;
    }

把新数组的元素保存到table并记录元素在新数组出现的次数，同时把新数组中的元素在旧数组的index设为NSNotFound，此外还要用一个单独的数组newResultsArray把新数组中元素的位置信息(也就是保存在table的数据)保存起来。

创建ol：

    // pass 2
    // update or create an entry for every item in the old array
    // increment its old count for each occurence
    // record the original index of the item in the old array
    // MUST be done in descending order to respect the oldIndexes stack construction
    vector<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;
    }

记录元素在旧数组出现的次数以及下标，这里是逆序的。

遍历nl也就是newResultsArray：

    // pass 3
    // handle data that occurs in both arrays
    for (NSInteger i = 0; i < newCount; i++) {
        IGListEntry *entry = newResultsArray[i].entry;

        // grab and pop the top original index. if the item was inserted this will be NSNotFound
        NSCAssert(!entry->oldIndexes.empty(), @"Old indexes is empty while iterating new item %li. Should have NSNotFound", (long)i);
        const NSInteger originalIndex = entry->oldIndexes.top();
        entry->oldIndexes.pop();

        if (originalIndex < oldCount) {
            const id<IGListDiffable> n = newArray[i];
            const id<IGListDiffable> o = oldArray[originalIndex];
            switch (option) {
                case IGListDiffPointerPersonality:
                    // flag the entry as updated if the pointers are not the same
                    if (n != o) {
                        entry->updated = YES;
                    }
                    break;
                case IGListDiffEquality:
                    // use -[IGListDiffable isEqualToDiffableObject:] between both version of data to see if anything has changed
                    // skip the equality check if both indexes point to the same object
                    if (n != o && ![n isEqualToDiffableObject:o]) {
                        entry->updated = YES;
                    }
                    break;
            }
        }
        if (originalIndex != NSNotFound
            && entry->newCounter > 0
            && entry->oldCounter > 0) {
            // if an item occurs in the new and old array, it is unique
            // assign the index of new and old records to the opposite index (reverse lookup)
            newResultsArray[i].index = originalIndex;
            oldResultsArray[originalIndex].index = i;
        }
    }

如果这个元素没有在旧数组中出现过，也就是originalIndex为NSNotFound，那就直接跳过。否则取出新旧值进行比较，如果不同updated就标记为YES。

计算删除：

    // iterate old array records checking for deletes
    // incremement offset for each delete
    for (NSInteger i = 0; i < oldCount; i++) {
        deleteOffsets[i] = runningOffset;
        const IGListRecord record = oldResultsArray[i];
        // if the record index in the new array doesn't exist, its a delete
        if (record.index == NSNotFound) {
            addIndexToCollection(returnIndexPaths, mDeletes, fromSection, i);
            runningOffset++;
        }

        addIndexToMap(returnIndexPaths, fromSection, i, oldArray[i], oldMap);
    }

遍历oldResultsArray，如果没有对应的在新数组的位置，那么就标记为删除。

计算插入：

    for (NSInteger i = 0; i < newCount; i++) {
        insertOffsets[i] = runningOffset;
        const IGListRecord record = newResultsArray[i];
        const NSInteger oldIndex = record.index;
        // add to inserts if the opposing index is NSNotFound
        if (record.index == NSNotFound) {
            addIndexToCollection(returnIndexPaths, mInserts, toSection, i);
            runningOffset++;
        } else {
            // note that an entry can be updated /and/ moved
            if (record.entry->updated) {
                addIndexToCollection(returnIndexPaths, mUpdates, fromSection, oldIndex);
            }

            // calculate the offset and determine if there was a move
            // if the indexes match, ignore the index
            const NSInteger insertOffset = insertOffsets[i];
            const NSInteger deleteOffset = deleteOffsets[oldIndex];
            if ((oldIndex - deleteOffset + insertOffset) != i) {
                id move;
                if (returnIndexPaths) {
                    NSIndexPath *from = [NSIndexPath indexPathForItem:oldIndex inSection:fromSection];
                    NSIndexPath *to = [NSIndexPath indexPathForItem:i inSection:toSection];
                    move = [[IGListMoveIndexPath alloc] initWithFrom:from to:to];
                } else {
                    move = [[IGListMoveIndex alloc] initWithFrom:oldIndex to:i];
                }
                [mMoves addObject:move];
            }
        }

        addIndexToMap(returnIndexPaths, toSection, i, newArray[i], newMap);
    }

遍历newResultsArray如果没有对应的在旧数组的位置则标记为插入。如果是更新，还要判断是否移动了，这个根据旧位置oldIndex加上插入的个数以及减去删除的个数之后是否和新位置是否一样来判断。

先遍历新数组，统计每个元素出现的次数newCount，得到newResultsArray
接着遍历旧数组，同样统计每个元素出现的次数oldCount，同时记录每个元素出现的位置oldIndexes，因为同一个元素可能会出现多次，这次的遍历是逆序的，因为oldIndexes是通过pop来读取的，这里得到oldResultsArray
这里使用了一个table保存了位置信息，新旧两个数组key相同的对应同一个位置信息，这样避免了多余的查找
接着遍历newResultsArray，取出元素的信息，再通过oldIndexes.top()取到该元素在旧数组的信息，如果存在这个元素，那比较新旧两个元素内容是否相同，如果不相同就把这个位置信息的updated置为YES（key一样内容不一样），另外如果该元素在信息两个数组都出现过，则记录下新元素在旧数组的位置，旧元素在新数组的位置
接着遍历oldResultsArray，如果旧元素在新数组的位置为NSNotFound，则将这个元素标记为删除
再次遍历newResultsArray，如果新元素在旧数组的位置为NSNotFound，则将这个元素标记为插入，否则判断当前元素的位置和该元素在旧数组的位置是否一致，这里需要旧位置-删除的个数+插入的个数在比较，然后得出需要移动的元素
IGListKit diff 实现简析

IGListKit源码阅读

IGListKit源码阅读

IGListKit

IGListKit的基本使用：

数据更新

Diff算法