将 CollectionDifference 应用于 NSTableView

Question

对于这个例子，假设我从一个 Int 数组生成一个 CollectionDifference，然后像这样调用 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

现在显然我不能为 0 和 1 调用 removeRows，然后 moveRow(2, 1)，但这就是 diff 所暗示的。

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

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

Answer 1

简答：

inferringMoves() 并不像您想象的那样。仔细查看结果，特别是 associatedWith 的值，并开发一种算法，该算法实际生成您需要的删除、插入和移动 – inferringMoves()实际上并没有产生任何动作...

长答案：

你的问题引起了我的兴趣，因为我以前从未看过 CollectionDifference，所以我要看看它。第一步在 Internet 上进行一些搜索，这会出现 Apple 的文档（像往常一样糟糕，它是为那些已经知道语义的人编写的，为什么他们不能再提供像样的文档了——大多数像样的东西都在他们的 "archive"，但我不同意...) 和许多描述该功能并包括示例代码的网站。该示例代码中有相当一部分与您的不同，但不要难过，因为它也不起作用。

为什么那么长的漫游？好吧，发现没有工作代码让人怀疑您是否正在遭受 "lockdown fever" 并且您的大脑混乱了。所有的代码真的不起作用吗？好吧，它适用于某些数据集，但在一般情况下不起作用，Apple calling the beast inferringMoves 有点不对劲，它推断序列中的删除和插入操作对，它们一起具有移动的效果一个项目，但它实际上并没有推断出单一的移动操作。

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

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

Input: [18, 18, 19, 11]

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

在这个序列中重要的是任何一步的 offset 都考虑了之前的所有步骤，也就是说它是中间结果的偏移量。

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

remove(offset: 2, element: 19, associatedWith: 1)
remove(offset: 1, element: 18, associatedWith: -)
remove(offset: 0, element: 18, associatedWith: -)
insert(offset: 1, element: 19, associatedWith: 2)

所以第一个和最后一个动作被推断为一对移动。

您决定插入操作是应该执行移动的时间，让我们看看会发生什么：

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

如您所见，那是行不通的。互联网上的其他人认为这是移动的删除操作，他们的表现是否更好？

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

这也行不通，所以不要因为你的行不通而难过，因为我还没有在互联网上找到任何行之有效的代码（这并不是说那里没有任何代码), 犯这个错误很常见，部分原因可能是许多简单的例子偶然出现。

解决问题的关键是弄清楚（因为 Apple 没有明确说明）associatedWith 值是将（对于未来插入）或曾经（对于过去）的索引删除) 序列中受影响的索引，因为它 exists/existed 在时间 关联的操作 takes/took 位置。

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

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

删除任何具有 associatedWith 值的删除操作，并调整所有后续操作中的 offset 值，以允许要删除的元素仍在序列中；和
将associatedWith值调整为未被删除的成对删除操作删除的元素的当前偏移量。

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

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

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

实现这个或另一个算法是留给你的，因为 SO 方式不是代码编写服务。希望上面的解释是有道理的！如果您在实施过程中遇到困难，您可以提出一个新问题，描述您的算法，展示您的代码，并描述您面临的问题；肯定有人会帮助你迈出下一步。

免责声明：

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

Answer 2

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

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

编辑：在@paxos 创建的测试套件的大力帮助下，我 re-wrote 下面的代码消除了一些边缘故障。 https://github.com/paxos/NSOutlineViewPatchTestSuite

/*
 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.
 
 The standard Changes are ordered: removals high->low, insertions low->high. RemainingRemovalTracker
 is used to track the position of items left in the collection, but that are assumed absent in the
 offsets provided for later insertions.
 */

typealias RemainingRemovalTracker = [Int:Int]

extension RemainingRemovalTracker {
    
    mutating func addSkippedRemoval(atOffset offset: Int) {
        self[offset] = offset }
    
    mutating func useSkippedRemoval(withOriginalOffset originalOffset: Int) -> Int {
        let currentOffset = removeValue(forKey: originalOffset)!
        removalMade(at: currentOffset)
        return currentOffset }
    
    mutating func removalMade(at offset: Int) {
        forEach({ key, value in
            if value > offset {
                self[key] = value - 1 } })
    }
    
    mutating func insertionMade(at offset: Int) {
        forEach { key, value in
            if value >= offset {
                self[key] = value + 1 } }
    }

    func adjustedInsertion(withOriginalOffset originalOffset: Int) -> Int {
        var adjustedOffset = originalOffset

        values.sorted().forEach { offset in
            if offset <= adjustedOffset {
                adjustedOffset += 1 } }
        
        return adjustedOffset
    }
}

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 [] }
        
        var steps = Steps()
        var offsetTracker = RemainingRemovalTracker()

        inferringMoves().forEach { change in
            switch change {
            case let .remove(offset, element, associatedWith):
                if associatedWith != nil {
                    offsetTracker.addSkippedRemoval(atOffset: offset)
                } else {
                    steps.append(.remove(element, at: offset))
                    offsetTracker.removalMade(at: offset)
                }

            case let.insert(offset, element, associatedWith):
                if let associatedWith = associatedWith {
                    let from = offsetTracker.useSkippedRemoval(withOriginalOffset: associatedWith)
                    let to = offsetTracker.adjustedInsertion(withOriginalOffset: offset)
                    steps.append(.move(element, from: from, to: to))
                    offsetTracker.insertionMade(at: to)
                } else {
                    let to = offsetTracker.adjustedInsertion(withOriginalOffset: offset)
                    steps.append(.insert(element, at: to))
                    offsetTracker.insertionMade(at: 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)
    }
}

将 CollectionDifference 应用于 NSTableView

Applying CollectionDifference to NSTableView

macos

cocoa

swift