IGListKit

使用Android的RecyclerView時系統(tǒng)有一個很好用的工具類DiffUtil，它可以幫我們比對兩組數(shù)據(jù)的差異，然后輸出結(jié)果直接應(yīng)用到RecyclerView進行更新，不需要我們自己執(zhí)行插入刪除移動這些指令。但iOS系統(tǒng)沒有提供類似的方法，不過我們可以利用IGListKit來實現(xiàn)。

IGListKit的基本使用：

首先要創(chuàng)建一個IGListAdapter，創(chuàng)建時需設(shè)置IGListAdapterUpdater、UIViewController、UICollectionView，另外還要設(shè)置IGListAdapter的`IGListAdapterDataSource。

通IGListAdapterDataSource的objectsForListAdapter:提供IGListAdapter需要的數(shù)據(jù)，還有listAdapter:sectionControllerForObject:提供每個數(shù)據(jù)對應(yīng)的IGListSectionController。

IGListSectionController顧名思義就是設(shè)置Section的，默認的numberOfItems是1。另外通過cellForItemAtIndex:來返回這個section下面的cell。

數(shù)據(jù)更新

當(dāng)我們修改數(shù)據(jù)源后，調(diào)用IGListAdapter的performUpdatesAnimated:completion:請求更新。

IGListAdapter有一個IGListSectionMap 保存了objects和對應(yīng)的sectionControllers，這個類讓這兩個東西雙向綁定。objects和sectionControllers的設(shè)置是在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:中調(diào)用。

要比對兩組數(shù)據(jù)的差異，就需要fromObjects和toObjects。更新時先從IGListSectionMap取出現(xiàn)在的objects也就是fromObjects。

toObjects這里提供了兩種方式獲取，一種是在調(diào)用更新是就直接拿到并保存下來，一種是真正執(zhí)行比對的時候再獲取，因為后面執(zhí)行更新是異步到主線程的。這里實現(xiàn)的方式是把它包裝 到一個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;
        };
    }

接著調(diào)用IGListUpdatingDelegate的performUpdateWithCollectionViewBlock:fromObjects:toObjectsBlock:animated:objectTransitionBlock:completion:，這里有兩個類實現(xiàn)了這個協(xié)議，IGListAdapterUpdater和IGListReloadDataUpdater，我們主要看IGListAdapterUpdater。

IGListAdapterUpdater會先把fromObjects保存下來，但這時可能已經(jīng)存在fromObjects了，因為后面真正執(zhí)行更新的操作是異步的，可以假設(shè)這個異步要等很久，在這個過程IGListAdapter可能持續(xù)被調(diào)用更新，所以得取最初的fromObjects和最后的toObjects。

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

self.fromObjects是上一次更新后和下一次開始之前這段時間內(nèi)的第一個fromObjects。self.pendingTransitionToObjects是上一次還未完成的toObjects。這樣設(shè)置可以保證fromObjects是取最初的fromObjects和最后的toObjects。

再來到_queueUpdateWithCollectionViewBlock:通過異步把更新操作分發(fā)除去，為什么要異步？因為要預(yù)留一些時間來收集更新，以防每次都都要更新。

- (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];
        }
    });
}

這里有個判斷，是直接執(zhí)行reloadData還是執(zhí)行Batch Updates。如果外面調(diào)用了reloadDataWithCollectionViewBlock:reloadUpdateBlock:completion:那么hasQueuedReloadData就為YES。

看看Batch Updates做了什么：

• 1、把相關(guān)數(shù)據(jù)保存到局部變量，然后清除所有狀態(tài)，這樣新的一輪更新狀態(tài)可以先進行保存；

• 2、把toObjects保存到pendingTransitionToObjects，這樣在更新時如果有新的刷新進來那fromObjects就是pendingTransitionToObjects；

• 3、執(zhí)行數(shù)據(jù)比對performDiff()拿到結(jié)果；

• 4、根據(jù)比對結(jié)果來performUpdate；

• 5、通知IGListAdapter更新sectionMap的數(shù)據(jù)，包括objects和sectionControllers，因為要開始通知collectionview更新了，數(shù)據(jù)要先更新；

• 6、執(zhí)行_flushCollectionView:withDiffResult:batchUpdates:fromObjects: 把diff結(jié)果更新到collectionview；

• 7、更新結(jié)束后清空batchUpdates和pendingTransitionToObjects；

• 8、更新完成后調(diào)用completionBlock；

• 9、接著繼續(xù)調(diào)用_queueUpdateWithCollectionViewBlock:以防在這期間有更新。

到這里更新就結(jié)束了。

Diff算法

算法的基本思路是這樣的：

• 1、遍歷新數(shù)組，創(chuàng)建一個列表nl，這個列表的元素是數(shù)據(jù)的值和Index；
• 2、遍歷舊數(shù)組，創(chuàng)建一個列表ol；
• 3、遍歷nl，如果該元素在ol中也存在，那么記為為entry match；
• 4、遍歷ol，如果該元素已經(jīng)被標(biāo)為entry match就跳過，否則記為delete；
• 5、遍歷nl，如果該元素沒有entry match則記為insert；如果有entry match，看index是否變化，如果有就記為move，否則就是not modified。

整個算法的復(fù)雜度為O(n)。

來看IGListKit的實現(xiàn)：

• 1、首先如果newCount為空，則直接返回全部刪除；如果oldCount為空，則直接返回全部插入。

• 2、接著創(chuàng)建一個表來保存每個元素及其對應(yīng)的位置信息，

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

key的類型是id<NSObject>，我們的元素都是實現(xiàn)IGListDiffable協(xié)議的，所以key直接就是id<NSObject> key = [object diffIdentifier];，這個表保存了新舊所有數(shù)據(jù)以及對應(yīng)的位置index信息。

IGListEntry保存了這個元素在新舊數(shù)組分別出現(xiàn)的次數(shù)以及在舊數(shù)組的index數(shù)組

/// 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;
};

接下來創(chuàng)建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;
    }

把新數(shù)組的元素保存到table并記錄元素在新數(shù)組出現(xiàn)的次數(shù)，同時把新數(shù)組中的元素在舊數(shù)組的index設(shè)為NSNotFound，此外還要用一個單獨的數(shù)組newResultsArray把新數(shù)組中元素的位置信息(也就是保存在table的數(shù)據(jù))保存起來。

創(chuàng)建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;
    }

記錄元素在舊數(shù)組出現(xiàn)的次數(shù)以及下標(biāo)，這里是逆序的。

遍歷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;
        }
    }

如果這個元素沒有在舊數(shù)組中出現(xiàn)過，也就是originalIndex為NSNotFound，那就直接跳過。否則取出新舊值進行比較，如果不同updated就標(biāo)記為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，如果沒有對應(yīng)的在新數(shù)組的位置，那么就標(biāo)記為刪除。

計算插入：

    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如果沒有對應(yīng)的在舊數(shù)組的位置則標(biāo)記為插入。如果是更新，還要判斷是否移動了，這個根據(jù)舊位置oldIndex加上插入的個數(shù)以及減去刪除的個數(shù)之后是否和新位置是否一樣來判斷。

• 先遍歷新數(shù)組，統(tǒng)計每個元素出現(xiàn)的次數(shù)newCount，得到newResultsArray

• 接著遍歷舊數(shù)組，同樣統(tǒng)計每個元素出現(xiàn)的次數(shù)oldCount，同時記錄每個元素出現(xiàn)的位置oldIndexes，因為同一個元素可能會出現(xiàn)多次，這次的遍歷是逆序的，因為oldIndexes是通過pop來讀取的，這里得到oldResultsArray
  這里使用了一個table保存了位置信息，新舊兩個數(shù)組key相同的對應(yīng)同一個位置信息，這樣避免了多余的查找

• 接著遍歷newResultsArray，取出元素的信息，再通過oldIndexes.top()取到該元素在舊數(shù)組的信息，如果存在這個元素，那比較新舊兩個元素內(nèi)容是否相同，如果不相同就把這個位置信息的updated置為YES（key一樣內(nèi)容不一樣），另外如果該元素在信息兩個數(shù)組都出現(xiàn)過，則記錄下新元素在舊數(shù)組的位置，舊元素在新數(shù)組的位置

• 接著遍歷oldResultsArray，如果舊元素在新數(shù)組的位置為NSNotFound，則將這個元素標(biāo)記為刪除

• 再次遍歷newResultsArray，如果新元素在舊數(shù)組的位置為NSNotFound，則將這個元素標(biāo)記為插入，否則判斷當(dāng)前元素的位置和該元素在舊數(shù)組的位置是否一致，這里需要舊位置-刪除的個數(shù)+插入的個數(shù)在比較，然后得出需要移動的元素

• IGListKit diff 實現(xiàn)簡析