IGListKit
使用Android的RecyclerView時(shí)系統(tǒng)有一個(gè)很好用的工具類DiffUtil，它可以幫我們比對(duì)兩組數(shù)據(jù)的差異，然后輸出結(jié)果直接應(yīng)用到RecyclerView進(jìn)行更新博烂，不需要我們自己執(zhí)行插入刪除移動(dòng)這些指令驱还。但iOS系統(tǒng)沒有提供類似的方法称簿，不過我們可以利用IGListKit來實(shí)現(xiàn)耸棒。
IGListKit的基本使用：
首先要?jiǎng)?chuàng)建一個(gè)IGListAdapter，創(chuàng)建時(shí)需設(shè)置IGListAdapterUpdater姨蟋、UIViewController屉凯、UICollectionView敷鸦，另外還要設(shè)置IGListAdapter的`IGListAdapterDataSource皿伺。
通IGListAdapterDataSource的objectsForListAdapter:提供IGListAdapter需要的數(shù)據(jù)，還有listAdapter:sectionControllerForObject:提供每個(gè)數(shù)據(jù)對(duì)應(yīng)的IGListSectionController饥侵。
IGListSectionController顧名思義就是設(shè)置Section的偷仿，默認(rèn)的numberOfItems是1哩簿。另外通過cellForItemAtIndex:來返回這個(gè)section下面的cell。
數(shù)據(jù)更新
當(dāng)我們修改數(shù)據(jù)源后酝静，調(diào)用IGListAdapter的performUpdatesAnimated:completion:請(qǐng)求更新节榜。
IGListAdapter有一個(gè)IGListSectionMap 保存了objects和對(duì)應(yīng)的sectionControllers，這個(gè)類讓這兩個(gè)東西雙向綁定别智。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;
}];
}
這個(gè)方法在IGListAdapter的_updateObjects:dataSource:中調(diào)用宗苍。
要比對(duì)兩組數(shù)據(jù)的差異，就需要fromObjects和toObjects薄榛。更新時(shí)先從IGListSectionMap取出現(xiàn)在的objects也就是fromObjects讳窟。
toObjects這里提供了兩種方式獲取，一種是在調(diào)用更新是就直接拿到并保存下來敞恋，一種是真正執(zhí)行比對(duì)的時(shí)候再獲取丽啡，因?yàn)楹竺鎴?zhí)行更新是異步到主線程的。這里實(shí)現(xiàn)的方式是把它包裝 到一個(gè)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:硬猫，這里有兩個(gè)類實(shí)現(xiàn)了這個(gè)協(xié)議补箍，IGListAdapterUpdater和IGListReloadDataUpdater改执，我們主要看IGListAdapterUpdater。
IGListAdapterUpdater會(huì)先把fromObjects保存下來坑雅，但這時(shí)可能已經(jīng)存在fromObjects了辈挂，因?yàn)楹竺嬲嬲龍?zhí)行更新的操作是異步的，可以假設(shè)這個(gè)異步要等很久裹粤，在這個(gè)過程IGListAdapter可能持續(xù)被調(diào)用更新终蒂，所以得取最初的fromObjects和最后的toObjects。
self.fromObjects = self.fromObjects ? : self.pendingTransitionToObjects ? : fromObjects;
self.fromObjects是上一次更新后和下一次開始之前這段時(shí)間內(nèi)的第一個(gè)fromObjects遥诉。self.pendingTransitionToObjects是上一次還未完成的toObjects后豫。這樣設(shè)置可以保證fromObjects是取最初的fromObjects和最后的toObjects。
再來到_queueUpdateWithCollectionViewBlock:通過異步把更新操作分發(fā)除去突那，為什么要異步？因?yàn)橐A(yù)留一些時(shí)間來收集更新构眯，以防每次都都要更新愕难。
- (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];
}
});
}
這里有個(gè)判斷，是直接執(zhí)行reloadData還是執(zhí)行Batch Updates惫霸。如果外面調(diào)用了reloadDataWithCollectionViewBlock:reloadUpdateBlock:completion:那么hasQueuedReloadData就為YES猫缭。
看看Batch Updates做了什么：
1、把相關(guān)數(shù)據(jù)保存到局部變量壹店，然后清除所有狀態(tài)猜丹，這樣新的一輪更新狀態(tài)可以先進(jìn)行保存；
2硅卢、把
toObjects保存到pendingTransitionToObjects射窒，這樣在更新時(shí)如果有新的刷新進(jìn)來那fromObjects就是pendingTransitionToObjects；3将塑、執(zhí)行數(shù)據(jù)比對(duì)
performDiff()拿到結(jié)果脉顿；4、根據(jù)比對(duì)結(jié)果來
performUpdate点寥；5艾疟、通知
IGListAdapter更新sectionMap的數(shù)據(jù)，包括objects和sectionControllers敢辩，因?yàn)橐_始通知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)建一個(gè)列表nl讼育，這個(gè)列表的元素是數(shù)據(jù)的值和Index；
- 2稠集、遍歷舊數(shù)組奶段，創(chuàng)建一個(gè)列表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。
整個(gè)算法的復(fù)雜度為O(n)撑帖。
來看IGListKit的實(shí)現(xiàn)：
1蓉坎、首先如果newCount為空，則直接返回全部刪除胡嘿；如果oldCount為空蛉艾，則直接返回全部插入。
2衷敌、接著創(chuàng)建一個(gè)表來保存每個(gè)元素及其對(duì)應(yīng)的位置信息勿侯，
unordered_map<id<NSObject>, IGListEntry, IGListHashID, IGListEqualID> table;
key的類型是id<NSObject>，我們的元素都是實(shí)現(xiàn)IGListDiffable協(xié)議的缴罗，所以key直接就是id<NSObject> key = [object diffIdentifier];助琐，這個(gè)表保存了新舊所有數(shù)據(jù)以及對(duì)應(yīng)的位置index信息。
IGListEntry保存了這個(gè)元素在新舊數(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ù)組中的元素在舊數(shù)組的index設(shè)為NSNotFound兵钮，此外還要用一個(gè)單獨(dú)的數(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;
}
}
如果這個(gè)元素沒有在舊數(shù)組中出現(xiàn)過泰演，也就是originalIndex為NSNotFound，那就直接跳過葱轩。否則取出新舊值進(jìn)行比較睦焕，如果不同updated就標(biāo)記為YES。
計(jì)算刪除：
// 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靴拱，如果沒有對(duì)應(yīng)的在新數(shù)組的位置垃喊，那么就標(biāo)記為刪除。
計(jì)算插入：
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如果沒有對(duì)應(yīng)的在舊數(shù)組的位置則標(biāo)記為插入袜炕。如果是更新本谜，還要判斷是否移動(dòng)了，這個(gè)根據(jù)舊位置oldIndex加上插入的個(gè)數(shù)以及減去刪除的個(gè)數(shù)之后是否和新位置是否一樣來判斷偎窘。
先遍歷新數(shù)組耕突，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)newCount，得到newResultsArray
接著遍歷舊數(shù)組评架，同樣統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)oldCount，同時(shí)記錄每個(gè)元素出現(xiàn)的位置oldIndexes炕泳，因?yàn)橥粋€(gè)元素可能會(huì)出現(xiàn)多次纵诞，這次的遍歷是逆序的，因?yàn)閛ldIndexes是通過pop來讀取的培遵，這里得到oldResultsArray
這里使用了一個(gè)table保存了位置信息浙芙，新舊兩個(gè)數(shù)組key相同的對(duì)應(yīng)同一個(gè)位置信息，這樣避免了多余的查找接著遍歷newResultsArray籽腕，取出元素的信息嗡呼，再通過oldIndexes.top()取到該元素在舊數(shù)組的信息，如果存在這個(gè)元素皇耗，那比較新舊兩個(gè)元素內(nèi)容是否相同南窗，如果不相同就把這個(gè)位置信息的updated置為YES（key一樣內(nèi)容不一樣），另外如果該元素在信息兩個(gè)數(shù)組都出現(xiàn)過郎楼，則記錄下新元素在舊數(shù)組的位置万伤，舊元素在新數(shù)組的位置
接著遍歷oldResultsArray，如果舊元素在新數(shù)組的位置為NSNotFound呜袁，則將這個(gè)元素標(biāo)記為刪除
再次遍歷newResultsArray敌买，如果新元素在舊數(shù)組的位置為NSNotFound，則將這個(gè)元素標(biāo)記為插入阶界，否則判斷當(dāng)前元素的位置和該元素在舊數(shù)組的位置是否一致虹钮，這里需要舊位置-刪除的個(gè)數(shù)+插入的個(gè)數(shù)在比較聋庵，然后得出需要移動(dòng)的元素
