NSArray+JBDiff.h

//
//  NSArray+JBDiff.h
//  Tyche
//
//  Created by Joel Bernstein on 9/16/09.
//



#import <Foundation/Foundation.h>



@interface JBDiffResult : NSObject

@property (nonatomic, copy) NSArray* firstArray;
@property (nonatomic, copy) NSArray* secondArray;
@property (nonatomic, copy) NSArray* lcsArray;
@property (nonatomic, copy) NSArray* combinedArray;

@property (nonatomic, copy) NSArray* deletedObjects;
@property (nonatomic, copy) NSArray* insertedObjects;

// deletedIndexes and insertedIndexes are the indexes that must be deleted from the oldArray, 
// and then inserted to form the newArray. These are useful for tableview animation.

@property (nonatomic, copy) NSIndexSet* deletedIndexes;
@property (nonatomic, copy) NSIndexSet* insertedIndexes;

// combinedDeletedIndexes and combinedInsertedIndexes are indexes to the combinedArray,
// used to display which elements in combinedArray were inserted or deleted.

@property (nonatomic, copy) NSIndexSet* combinedDeletedIndexes;
@property (nonatomic, copy) NSIndexSet* combinedInsertedIndexes;

@end



@interface NSArray (JBDiff)

-(JBDiffResult*)diffWithArray:(NSArray*)newArray;

@end

NSArray+JBDiff.m

//
//  NSArray+JBDiff.m
//  Tyche
//
//  Created by Joel Bernstein on 9/16/09.
//



#import "NSArray+JBDiff.h"



@implementation JBDiffResult

@end



@implementation NSArray (JBDiff)

// Bottom-Up Iterative LCS algorithm from http://www.ics.uci.edu/~eppstein/161/960229.html

-(JBDiffResult*)diffWithArray:(NSArray*)secondArray;
{
    NSUInteger lengthArray[self.count + 1][secondArray.count + 1];    
    memset(lengthArray, (self.count + 1) * (secondArray.count + 1), sizeof(NSUInteger));
    
    for(NSInteger firstArrayIndex = self.count; firstArrayIndex >= 0; firstArrayIndex--)
    {    
        for(NSInteger secondArrayIndex = secondArray.count; secondArrayIndex >= 0; secondArrayIndex--)
        {
            if(firstArrayIndex == (NSInteger)self.count || secondArrayIndex == (NSInteger)secondArray.count)
            {
                lengthArray[firstArrayIndex][secondArrayIndex] = 0;
            }
            else if([self[firstArrayIndex] isEqual:secondArray[secondArrayIndex]]) 
            {
                lengthArray[firstArrayIndex][secondArrayIndex] = 1 + lengthArray[firstArrayIndex + 1][secondArrayIndex + 1];
            }
            else
            {
                lengthArray[firstArrayIndex][secondArrayIndex] = MAX(lengthArray[firstArrayIndex + 1][secondArrayIndex], lengthArray[firstArrayIndex][secondArrayIndex + 1]);
            }
        }
    }
    
    NSMutableArray*    lcsArray                = [NSMutableArray array];
    NSMutableArray*    combinedArray           = [NSMutableArray array];
    NSMutableArray*    deletedObjects          = [NSMutableArray array];
    NSMutableArray*    insertedObjects         = [NSMutableArray array]; 
    NSMutableIndexSet* deletedIndexes          = [NSMutableIndexSet indexSet];
    NSMutableIndexSet* insertedIndexes         = [NSMutableIndexSet indexSet]; 
    NSMutableIndexSet* combinedDeletedIndexes  = [NSMutableIndexSet indexSet];
    NSMutableIndexSet* combinedInsertedIndexes = [NSMutableIndexSet indexSet]; 
    
    NSUInteger firstArrayIndex = 0;
    NSUInteger secondArrayIndex = 0;
    NSUInteger combinedArrayIndex = 0;
    
    while(firstArrayIndex < self.count && secondArrayIndex < secondArray.count)
    {
        if([self[firstArrayIndex] isEqual:secondArray[secondArrayIndex]])
        {
            [lcsArray      addObject:self[firstArrayIndex]];
            [combinedArray addObject:self[firstArrayIndex]];
            
            firstArrayIndex++; 
            secondArrayIndex++;
            combinedArrayIndex++;
        }
        else if(lengthArray[firstArrayIndex + 1][secondArrayIndex] >= lengthArray[firstArrayIndex][secondArrayIndex + 1])
        {
            [combinedArray          addObject:self[firstArrayIndex]];
            [deletedObjects         addObject:self[firstArrayIndex]];
            [deletedIndexes         addIndex:firstArrayIndex];
            [combinedDeletedIndexes addIndex:combinedArrayIndex];
            
            firstArrayIndex++;
            combinedArrayIndex++;
        }
        else
        {
            [combinedArray           addObject:secondArray[secondArrayIndex]];
            [insertedObjects         addObject:secondArray[secondArrayIndex]];
            [insertedIndexes         addIndex:secondArrayIndex];
            [combinedInsertedIndexes addIndex:combinedArrayIndex];
            
            secondArrayIndex++;
            combinedArrayIndex++;
        }
    }
    
    while(firstArrayIndex < self.count) 
    {
        [combinedArray          addObject:self[firstArrayIndex]];
        [deletedObjects         addObject:self[firstArrayIndex]];
        [deletedIndexes         addIndex:firstArrayIndex];
        [combinedDeletedIndexes addIndex:combinedArrayIndex];
        
        firstArrayIndex++;
        combinedArrayIndex++;
    }
    
    while(secondArrayIndex < secondArray.count) 
    {
        [combinedArray           addObject:secondArray[secondArrayIndex]];
        [insertedObjects         addObject:secondArray[secondArrayIndex]];
        [insertedIndexes         addIndex:secondArrayIndex];
        [combinedInsertedIndexes addIndex:combinedArrayIndex];
        
        secondArrayIndex++;
        combinedArrayIndex++;
    }
    
    JBDiffResult* result = [[JBDiffResult alloc] init];
    
    result.firstArray              = [self copy];
    result.secondArray             = [secondArray copy];
    result.lcsArray                = lcsArray;               
    result.combinedArray           = combinedArray;          
    result.deletedObjects          = deletedObjects;         
    result.insertedObjects         = insertedObjects;        
    result.deletedIndexes          = deletedIndexes;         
    result.insertedIndexes         = insertedIndexes;        
    result.combinedDeletedIndexes  = combinedDeletedIndexes; 
    result.combinedInsertedIndexes = combinedInsertedIndexes;
    
    return result;
}

@end