Swift数组差异

Question

给定两个数组,其中一个是旧的值集,另一个是新值,我想找到这两个数组的"差异",这样对原始数组的更新可以表示为:

enum CollectionChange<T: SequenceType> {
    case Initial(T)
    case Update(T, deletions: [Int], insertions: [Int], modifications: [Int]) 
}

我试图建立的简化版本这是更改对象基于对象的平等而建,而不是作为指标RAC-MutableCollectionProperty是(对于该代码是在这里,什么可能是代码的最复杂的位,我在看到虽然;没有文件没有帮助).

此项目的另一个重要功能是能够以任何粒度级别观察阵列的更改.例如,一个一维阵列,限制T到Equatable,是一个相对容易的用例.您可以RAC-MutableCollectionProperty构建某种描述更改的表,检查对象的相等性.然而,一旦你开始使用二维数组并且更深入,它会变得有点棘手,因为你不仅需要在最低级别对元素进行区分,还要描述区段级别的删除.实际上,实际上只需要2D阵列,但是无论阵列深度如何,都可以使用一个解决方案.我不一定在寻找解决方案(尽管这很棒),实际上只是关于如何解决这个问题的任何指针和高级解决方案.

我想到观察多个数组级别的一种方法是编写一个在单维数组上工作的diffing函数,并构造一个属性,使得:

let property: MutableCollectionProperty<MutableCollectionProperty<Int>>

属性将检查其泛型类型是否属于自己的类型.我必须将更改描述更改为更接近的内容

enum Changes<T> {
    case Initial(T)
    case Update(T, deletions: [NSIndexPath], insertions: [NSIndexPath], modifications: [NSIndexPath])
}

或者类似的东西

enum Changes<T> {
    case Initial(T)
    case UpdateSections(sections: [T], deletions:[Int], insertions: [Int], modifications: [Int])
    case UpdateIndexes(T, deletions: [Int], insertions: [Int], modifications: [Int])
}

这些只是我的初步想法,但我愿意接受任何解决方案或建议.

BOUNTY编辑:

奖金将颁发给能够提供给出以下参数的解决方案的人:

• 设x和y为两个快速数组
• 两种类型的数组 T: Equatable
• 两个阵列都可以是任何深度
• x的深度= y的深度

可以生成更改集,其中更改集描述:

• 哪些元素已从x到y删除(按索引)
• 哪些元素已插入到y中不在x中(按索引)
• 哪些元素已从x移动到y(按索引)

只需要在数组的最低级别描述更改(无需担心插入和删除更高的段,尽管您真的可以获得300个代表),但更改索引必须指示嵌套的索引路径.

例如,如果数组是3d数组并且array[0][5][2]删除了对象,则生成的索引更改应为数组[0, 5, 2].该数组描述了单个删除,所有删除都是类型[[Int]].

编辑:

我正在删除任何深度的数组的要求.让我们说它们只是一维数组.

Answer 1

我不确定这是否满足您的所有赏金要求,但我会发布一些用于计算数组差异的代码:

func arrayInsertionDeletionAndNoopIndexes<T: Equatable>(objects: [T], originalObjects: [T]) -> ([Int], [Int], [Int]) {
    let insertions = objects.filter({ !originalObjects.contains($0) }).map({ objects.index(of: $0)! })
    let noops = originalObjects.filter({ objects.contains($0) }).map({ originalObjects.index(of: $0)! })
    let deletions = originalObjects.filter({ !objects.contains($0) }).map({ originalObjects.index(of: $0)! })

    return (insertions, deletions, noops)
}

func arrayInsertionDeletionAndNoopIndexPaths<T: Equatable>(objects: [T], originalObjects: [T], section: Int = 0) -> ([IndexPath], [IndexPath], [IndexPath]) {
    let (insertions, deletions, noops) = arrayInsertionDeletionAndNoopIndexes(objects: objects, originalObjects: originalObjects)

    let insertionIndexPaths = insertions.map({ IndexPath(row: $0, section: section) })
    let deletionIndexPaths = deletions.map({ IndexPath(row: $0, section: section) })
    let noopIndexPaths = noops.map({ IndexPath(row: $0, section: section) })

    return (insertionIndexPaths, deletionIndexPaths, noopIndexPaths)
}

我的具体用例是计算差异以更新a UITableView,为此我还有以下内容:

extension UITableView {

    func insertAndDeleteCellsForObjects<T: Equatable>(objects: [T], originalObjects: [T], section: Int = 0) {
        let (insertions, deletions, _) = arrayInsertionDeletionAndNoopIndexPaths(objects: objects, originalObjects: originalObjects, section: section)

        if insertions.count > 0 || deletions.count > 0 {
            beginUpdates()
            insertRows(at: insertions, with: .automatic)
            deleteRows(at: deletions, with: .automatic)
            endUpdates()
        }
    }

}

Answer 2

从Swift 2.2开始,这是不可能的.您提出以下要求:

• 两种类型的数组 T: Equatable
• 两个阵列都可以是任何深度

但是,制定受约束扩展符合新协议的能力仅适用于Swift 3.0,因此您现在无法extension Array where Element: Array<Equatable>遵循Equatable协议.这意味着只有1d数组可以是类型T: Equatable.

编辑:

基本上你需要做的是编写一个算法来解决最长的常见子序列问题.对于1d数组,您可以使用Dwifft库,它通过以下方式解决问题:

public extension Array where Element: Equatable {
    public func diff(other: [Element]) -> Diff<Element> {
        let table = MemoizedSequenceComparison.buildTable(self, other, self.count, other.count)
        return Array.diffFromIndices(table, self, other, self.count, other.count)
    }

    private static func diffFromIndices(table: [[Int]], _ x: [Element], _ y: [Element], _ i: Int, _ j: Int) -> Diff<Element> {
        if i == 0 && j == 0 {
            return Diff<Element>(results: [])
        } else if i == 0 {
            return diffFromIndices(table, x, y, i, j-1) + DiffStep.Insert(j-1, y[j-1])
        } else if j == 0 {
            return diffFromIndices(table, x, y, i - 1, j) + DiffStep.Delete(i-1, x[i-1])
        } else if table[i][j] == table[i][j-1] {
            return diffFromIndices(table, x, y, i, j-1) + DiffStep.Insert(j-1, y[j-1])
        } else if table[i][j] == table[i-1][j] {
            return diffFromIndices(table, x, y, i - 1, j) + DiffStep.Delete(i-1, x[i-1])
        } else {
            return diffFromIndices(table, x, y, i-1, j-1)
        }
    }
}

internal struct MemoizedSequenceComparison<T: Equatable> {
    static func buildTable(x: [T], _ y: [T], _ n: Int, _ m: Int) -> [[Int]] {
        var table = Array(count: n + 1, repeatedValue: Array(count: m + 1, repeatedValue: 0))
        for i in 0...n {
            for j in 0...m {
                if (i == 0 || j == 0) {
                    table[i][j] = 0
                }
                else if x[i-1] == y[j-1] {
                    table[i][j] = table[i-1][j-1] + 1
                } else {
                    table[i][j] = max(table[i-1][j], table[i][j-1])
                }
            }
        }
        return table
    }
}