将 CollectionDifference 应用到 NSTableView

Question

对于这个例子，假设我CollectionDifference从一个Int数组生成一个，然后inferringMoves像这样调用它

let a = [18, 18, 19, 11]
let b = [11, 19]
let diff = b.difference(from: a).inferringMoves()

for change in diff {
    switch change {
    case let .insert(offset, _, associatedWith):
        if let from = associatedWith {
            print("MOVE", from, offset)
        } else {
            print("INSERT", offset)
        }
    case let .remove(offset, _, associatedWith):
        // If it is a MOVE it was already recorded in .insert
        if associatedWith == nil {
            print("REMOVE", offset)
        }
    }
}

现在我需要获取更改数组并将其提供给NSTableViews更新方法

• insertRows
• removeRows
• moveRow

以这样的方式，它应用干净。我的问题是move条目的偏移量。上面的代码片段产生：

REMOVE 1
REMOVE 0
MOVE 2 1

现在很明显，我不能打电话removeRows的0和1，然后moveRow(2, 1)，但那是差异暗示什么。

我怎样才能干净利落地应用它？

问题似乎是NSTableView在应用插入/删除时立即更新其内部计数，因此移动将不起作用。

Answer 1

简短回答：

\n\n

inferringMoves()不做你认为它做的事。仔细查看结果，特别是 的值associatedWith，并开发一种算法，该算法实际上会产生您需要的删除、插入和移动\xe2\x80\x93\xc2\xa0inferringMoves()实际上不会产生任何移动...

\n\n

长答案：

\n\n

你的问题引起了我的兴趣，因为我以前从未看过CollectionDifference，所以我要看看它。第一步在互联网上进行一些搜索，这会出现Apple的文档（一如既往的糟糕，它是为那些已经了解语义的人编写的，为什么他们不能再提供像样的文档\xe2\x80\x93\ xc2\xa0大多数像样的东西都在他们的“存档”中，但我分歧......）以及许多描述该功能并包括示例代码的网站。该示例代码的相当一部分与您的不同，但不要感到难过，因为它也不起作用。

\n\n

为什么要这么长的闲逛？发现没有可用的代码会让人们怀疑你是否患有“封锁热”并且你的大脑混乱了。所有的代码真的都不起作用吗？嗯，它适用于某些数据集，但不适用于一般情况，苹果称野兽inferringMoves有点笨拙，它推断出序列中的成对删除和插入操作，它们一起具有移动项目的效果，但它并没有实际上并不能推断单次移动操作。

\n\n

或者说，我可能（比平时更）混乱的大脑是这么说的。继续阅读并确定我是否有封锁发烧......

\n\n

让我们查看您的数据，看看difference会产生什么以及每个步骤如何更改输入：

\n\n

Input: [18, 18, 19, 11]\n\nSequence of changes from `difference` and the changing sequence:\n    remove(offset: 2, element: 19, associatedWith: -) => [18, 18, 11]\n    remove(offset: 1, element: 18, associatedWith: -) => [18, 11]\n    remove(offset: 0, element: 18, associatedWith: -) => [11]\n    insert(offset: 1, element: 19, associatedWith: -) => [11, 19] CORRECT\n

\n\n

此序列中重要的是，offset任何步骤都会考虑所有先前的步骤，即它是中间结果的偏移量。

\n\n

现在inferringMoves设置associatedWith字段来指示remove/insert形成移动的对，将其应用于difference数据生成：

\n\n

remove(offset: 2, element: 19, associatedWith: 1)\nremove(offset: 1, element: 18, associatedWith: -)\nremove(offset: 0, element: 18, associatedWith: -)\ninsert(offset: 1, element: 19, associatedWith: 2)\n

\n\n

因此第一个和最后一个动作被推断为一个移动对。

\n\n

您决定（而且您并不是唯一做出该决定的人）插入操作是应该执行移动的时间，让我们看看会发生什么：

\n\n

[18, 18, 19, 11]\nremove(offset: 2, element: 19, associatedWith: 1) => [18, 18, 19, 11]\n    Noop as part of a move pair\nremove(offset: 1, element: 18, associatedWith: -) => [18, 19, 11]\n    Item 1 was 18 so this seems valid...\nremove(offset: 0, element: 18, associatedWith: -) => [19, 11]\n    Item 0 is not 18 so this looks like things are going wrong\ninsert(offset: 1, element: 19, associatedWith: 2) => Oops\n    Second action of a move pair, Error item 1 is not 19 and there is no item 2\n

\n\n

正如您发现的那样，这不起作用。互联网上的其他人决定采取删除行动，他们的情况是否会更好？

\n\n

[18, 18, 19, 11]\nremove(offset: 2, element: 19, associatedWith: 1) => [18, 19, 18, 11]\n    First of pair, do the move\nremove(offset: 1, element: 18, associatedWith: -) => [18, 18, 11]\n    Warning bell the item removed is 19 not 18 as the action expects\nremove(offset: 0, element: 18, associatedWith: -) => [18, 11]\n    Yah, item 0 is 18, this action is "correct" in isolation\ninsert(offset: 1, element: 19, associatedWith: 2) => [18, 11]\n    Second of pair, so NOOP\n

\n\n

这也不起作用，所以不要因为你的代码不起作用而感到难过，因为我还没有在互联网上找到任何能起作用的代码（这并不是说没有任何那里），犯这个错误很常见，部分原因可能是许多简单的例子都是偶然发生的。

\n\n

解决问题的关键是弄清楚（因为苹果没有明确说明）该associatedWith值是（对于将来的插入）或（对于过去的删除）序列中受影响的索引的索引，如下所示它在相关操作发生时就存在。

\n\n

例如，数据的第一个操作是remove(offset: 2, element: 19, associatedWith: 1)，这并不意味着您可以将项目移动到当前insert(offset: 1, element: 19, associatedWith: 2)序列中的索引 1，而是移动到序列中的索引 1，因为执行关联时它将存在。在该对的删除和插入之间有两个介入的删除操作，因此顺序将发生变化。

\n\n

要获得（不是唯一的inferringMoves()）工作解决方案，您可以使用以下草图算法对结果进行后处理：

\n\n

\n
1. 删除任何带有associatedWith值的删除操作，并调整offset所有后续操作中的值，以允许要删除的元素仍在序列中；和
\n
2. 将值调整associatedWith为未通过已删除的配对删除操作删除的元素的当前偏移量。
\n

\n\n

这将产生一系列零个或多个不带associatedWith值的删除和插入操作，以及一个或多个带值的插入操作associatedWith具有代表移动的值的插入操作。

\n\n

将上述算法草图的实现应用于您的数据会产生：

\n\n

[18, 18, 19, 11]\nremove(offset: 1, element: 18, associatedWith: -) => [18, 19, 11]\nremove(offset: 0, element: 18, associatedWith: -) => [19, 11]\ninsert(offset: 2, element: 19, associatedWith: 0) => [11, 19]\n    a move: insert at offset, remove at associatedWith\n

\n\n

实现这个或另一个算法，就像不是代码编写服务一样，由您决定。希望以上解释是有道理的！如果您在实现过程中遇到困难，您可以提出一个新问题，描述您的算法，显示您的代码，并描述您面临的问题；毫无疑问，有人会帮助您迈出下一步。

\n\n

免责声明：

\n\n

正如一开始所指出的，我很惊讶地发现互联网上没有可用的代码，但有很多损坏的代码，我的锁定大脑是否太混乱了？是否有一个简单的结果解释inferringMoves()是否有一个不需要上述混合步骤感觉应该有，Apple 的文档可能很差，但他们的 API 的语义通常很好。所以也许，如果是这样，我希望有人将其作为答案发布，届时我将删除这个，即使它确实有效。

\n

Answer 2

所以这比我最初想象的要复杂得多！

这是 CollectionDifference 的扩展，它将返回一组包含移动的步骤。我已经在各种复杂的序列上对此进行了测试，它看起来很可靠。

/*
 This extension generates an array of steps that can be applied sequentially to an interface, or
 associated collection, to remove, insert AND move items. Apart from the first and last steps, all
 step indexes are transient and do not relate directly to the start or end collections.
 
 This is complicated than it first appears and not something that I could reduced further. The
 standard Changes are ordered: removals high->low, insertions low->high. Generating moves based on
 insertions means that the associated removes are pulled out-of-order, which requires all the
 later indexes to be offset in subtly different ways.
 
 Delayed removals modify the insert indexes. Out of order removals, and insertions made before the
 delayed removals modify the removal indexes. The effect of something that hasn't happeded yet, is
 different to something that has happened but in the wrong order.
 */

extension CollectionDifference where ChangeElement: Hashable
{
    public typealias Steps = Array<CollectionDifference<ChangeElement>.ChangeStep>
    
    public enum ChangeStep {
        case insert(_ element: ChangeElement, at: Int)
        case remove(_ element: ChangeElement, at: Int)
        case move(_ element: ChangeElement, from: Int, to: Int)
    }
    
    var maxOffset: Int { Swift.max(removals.last?.offset ?? 0, insertions.last?.offset ?? 0) }
    
    public var steps: Steps {
        guard !isEmpty else { return [] }
        
        // A mapping to modify insertion indexees
        let mapSize = maxOffset + count
        var insertionMap = Array(0 ... mapSize)
        
        // Items that may have been completed early relative to the Changes
        var completeRemovals = Set<Int>()
        var completeInsertions = Set<Int>()
        
        var steps = Steps()
        
        inferringMoves().forEach { change in
            switch change {
            case let .remove(offset, element, associatedWith):
                if associatedWith != nil {
                    // Delayed removals can make step changes in insert locations
                    insertionMap.remove(at: offset)
                } else {
                    steps.append(.remove(element, at: offset))
                    completeRemovals.insert(offset)
                }

            case let.insert(offset, element, associatedWith):
                if let associatedWith = associatedWith
                {
                    let from = associatedWith
                        - completeRemovals.filter({ $0 < associatedWith}).count
                        + completeInsertions.filter({ $0 < associatedWith}).count
                    
                    // Late removals re-adjust the insertion map by reducing higher indexes
                    insertionMap.indices.forEach {
                        if insertionMap[$0] >= associatedWith { insertionMap[$0] -= 1} }
                    
                    let to = insertionMap[offset]
                    
                    steps.append(.move(element, from: from, to: to))
                    
                    completeRemovals.insert(associatedWith)
                    completeInsertions.insert(to)
                } else {
                    let to = insertionMap[offset]
                    steps.append(.insert(element, at: to))
                    completeInsertions.insert(to)
                }
            }
        }

        return steps
    }
}

extension CollectionDifference.Change
{
    var offset: Int {
        switch self {
        case let .insert(offset, _, _): return offset
        case let .remove(offset, _, _): return offset
        }
    }
}

这些步骤可以应用于 NSTableView 或 NSOutlineView，如下所示：

for step in updates {
    switch step {
    case let .remove(_, index):
        outlineView.removeItems(at: [index], inParent: node, withAnimation: animation)
                    
    case let .insert(element, index):
        outlineView.insertItems(at: [index], inParent: node, withAnimation: animation)

    case let .move(element, from, to):
        outlineView.moveItem(at: from, inParent: node, to: to, inParent: node)
    }
}