ios/Pods/WeexSDK/ios/sdk/WeexSDK/Sources/Utility/WXDiffUtil.m

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

#import "WXDiffUtil.h"
#import "WXLog.h"

typedef enum : NSUInteger {
    WXDiffOperationDoNothing,
    WXDiffOperationUpdate,
    WXDiffOperationDelete,
    WXDiffOperationInsert
} WXDiffOperation;

@implementation WXDiffUpdateIndex

- (instancetype)initWithOldIndex:(NSUInteger)oldIndex newIndex:(NSUInteger)newIndex
{
    if (self = [super init]) {
        _oldIndex = oldIndex;
        _newIndex = newIndex;
    }
    
    return self;
}

@end

@implementation WXDiffResult

- (instancetype)initWithInserts:(NSIndexSet *)inserts
                        deletes:(NSIndexSet *)deletes
                        updates:(NSArray<WXDiffUpdateIndex *> *)updates
{
    if (self = [super init]) {
        _inserts = [inserts copy];
        _deletes = [deletes copy];
        _updates = [updates copy];
    }
    
    return self;
}

- (BOOL)hasChanges
{
    return _updates.count > 0 || _inserts.count > 0 || _deletes.count > 0;
}

- (NSString *)description
{
    return [NSString stringWithFormat:@"<%@: %p; %lu inserts; %lu deletes; %lu updates", NSStringFromClass([self class]), self, (unsigned long)_inserts.count, (unsigned long)_deletes.count, (unsigned long)_updates.count];
}


@end

@implementation WXDiffUtil

+ (WXDiffResult *)diffWithMinimumDistance:(NSArray<id<WXDiffable>> *)newArray oldArray:(NSArray<id<WXDiffable>> *)oldArray
{
    // Using the levenshtein algorithm
    // https://en.wikipedia.org/wiki/Levenshtein_distance
    
    int oldSize = (int)(oldArray.count + 1);
    int newSize = (int)(newArray.count + 1);
    
    int **matrix = malloc(oldSize * sizeof(int *));
    for (int i = 0; i < oldSize; i++) {
        matrix[i] = malloc(newSize * sizeof(int));
    }
    
    matrix[0][0] = 0;
    
    for (int i = 1; i < oldSize; i++) {
        matrix[i][0] = i;
    }
    
    for (int j = 1; j < newSize; j++) {
        matrix[0][j] = j;
    }
    
    for (int oldIndex = 1; oldIndex < oldSize; oldIndex ++) {
        for (int newIndex = 1; newIndex < newSize; newIndex ++) {
            if ([oldArray[oldIndex - 1] weex_isEqualTo:newArray[newIndex - 1]]) {
                matrix[oldIndex][newIndex] = matrix[oldIndex - 1][newIndex - 1];
            } else {
                int updateCost = matrix[oldIndex - 1][newIndex - 1] + 1;
                int insertCost = matrix[oldIndex][newIndex - 1] + 1;
                int deleteCost = matrix[oldIndex - 1][newIndex] + 1;
                matrix[oldIndex][newIndex] = MIN(MIN(insertCost, deleteCost), updateCost);
            }
        }
    }
    
#if DEBUG
    [self _printMatrix:matrix rowSize:oldSize columnSize:newSize];
#endif
    
    NSMutableArray *updates = [NSMutableArray array];
    NSMutableIndexSet *inserts = [NSMutableIndexSet indexSet];
    NSMutableIndexSet *deletes = [NSMutableIndexSet indexSet];
    int oldIndex = oldSize - 1;
    int newIndex = newSize - 1;
    while (oldIndex != 0 || newIndex != 0) {
        WXDiffOperation operation = [self _operationInMatrix:matrix newIndex:newIndex oldIndex:oldIndex];
        switch (operation) {
            case WXDiffOperationUpdate:
                newIndex --;
                oldIndex --;
                [updates addObject:[[WXDiffUpdateIndex alloc] initWithOldIndex:oldIndex newIndex:newIndex]];
                break;
            case WXDiffOperationDelete:
                oldIndex --;
                [deletes addIndex:oldIndex];
                break;
            case WXDiffOperationInsert:
                newIndex --;
                [inserts addIndex:newIndex];
                break;
            case WXDiffOperationDoNothing:
                newIndex --;
                oldIndex --;
                break;
        }
    }
    
    for (int i = 0; i < oldSize; i++) {
        free(matrix[i]);
    }
    free(matrix);
    
    WXDiffResult *result = [[WXDiffResult alloc] initWithInserts:inserts deletes:deletes updates:updates];
    return result;
}

+ (WXDiffOperation)_operationInMatrix:(int **)matrix newIndex:(int)newIndex oldIndex:(int)oldIndex
{
    if (newIndex == 0) {
        return WXDiffOperationDelete;
    }
    
    if (oldIndex == 0) {
        return WXDiffOperationInsert;
    }
    
    int cost = matrix[oldIndex][newIndex];
    
    int costBeforeInsert = matrix[oldIndex][newIndex - 1];
    if (costBeforeInsert + 1 == cost) {
        return WXDiffOperationInsert;
    }
    
    int costBeforDelete = matrix[oldIndex - 1][newIndex];
    if (costBeforDelete + 1 == cost) {
        return WXDiffOperationDelete;
    }
    
    int costBeforUpdate = matrix[oldIndex - 1][newIndex - 1];
    if (costBeforUpdate + 1 == cost) {
        return WXDiffOperationUpdate;
    }
    
    return WXDiffOperationDoNothing;
}

+ (void)_printMatrix:(int **)matrix rowSize:(int)rowSize columnSize:(int)columnSize
{
    for (int i = 0; i < rowSize; i ++) {
        NSMutableArray *array = [NSMutableArray array];
        for (int j = 0; j < columnSize; j ++) {
            int value = matrix[i][j];
            NSString *result;
            if (value < 10) {
                result = [NSString stringWithFormat:@"0%i", value];
            } else {
                result = [NSString stringWithFormat:@"%i", value];
            }
            [array addObject:result];
        }
        WXLogDebug(@"%@", [array componentsJoinedByString:@" "]);
    }
}

@end

@implementation NSNumber (WXDiffable)

- (BOOL)weex_isEqualTo:(id<WXDiffable>)object
{
    return [self isEqual:object];
}

@end

@implementation NSString (WXDiffable)

- (BOOL)weex_isEqualTo:(id<WXDiffable>)object
{
    return [self isEqual:object];
}

@end

@implementation NSArray (WXDiffable)

- (BOOL)weex_isEqualTo:(id<WXDiffable>)object
{
    if (![object isKindOfClass:[NSArray class]]) {
        return NO;
    }
    
    NSArray *array = (NSArray *)object;
    if (self.count != array.count) {
        return NO;
    }
    
    __block BOOL isEqual = YES;
    [array enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        id obj2 = [self objectAtIndex:idx];
        if ([obj conformsToProtocol:@protocol(WXDiffable)] && [obj2 conformsToProtocol:@protocol(WXDiffable)]) {
            if (![obj weex_isEqualTo:obj2]) {
                isEqual = NO;
                *stop = YES;
            }
        } else {
            isEqual = NO;
            *stop = YES;
        }
    }];
    
    return isEqual;
}

@end

@implementation NSDictionary (WXDiffable)

- (BOOL)weex_isEqualTo:(id<WXDiffable>)object
{
    if (![object isKindOfClass:[NSDictionary class]]) {
        return NO;
    }
    
    NSDictionary *dictionary = (NSDictionary *)object;
    if (self.count != dictionary.count) {
        return NO;
    }
    
    __block BOOL isEqual = YES;
    [dictionary enumerateKeysAndObjectsUsingBlock:^(id  _Nonnull key, id  _Nonnull obj, BOOL * _Nonnull stop) {
        id obj2 = [self objectForKey:key];
        if (obj2 && [obj2 conformsToProtocol:@protocol(WXDiffable)] && [obj conformsToProtocol:@protocol(WXDiffable)]) {
            if (![obj weex_isEqualTo:obj2]) {
                isEqual = NO;
                *stop = YES;
            }
        } else {
            isEqual = NO;
            *stop = YES;
        }
    }];
    
    return isEqual;
}

@end

@implementation NSNull (WXDiffable)

- (BOOL)weex_isEqualTo:(id<WXDiffable>)object
{
    if ([object isKindOfClass:[NSNull class]]) {
        return YES;
    }
    return NO;
}

@end