Support moves

[eliasbagley]

First off, great library! I've struggled with this issue for years and have always fallen back to an NSFetchedResultsController or just calling reloadData.

I watched your meetup video about Dwifft 0.6 online, and saw you mentioned having support for move operations for 1.0, which would be rad! I just wanted to make you aware of the Android implementation of this functionality (if you aren't already) - maybe you can take some inspiration from it, since it supports moves, inserts, and deletes. I think it's a different algorithm than the one you're using, but might be useful. The docs say it uses two passes of the Myers Difference Algorithm (which I believe is the same LCS algorithm you're using?) in order to detect the moves, since it can't be done in a single pass.

https://developer.android.com/reference/android/support/v7/util/DiffUtil.html

Keep up the good work!

[jack-stripe]

@eliasbagley - thank you! wow, i had no idea this was in android; that is super helpful. I've looked over the DiffUtil source a bit, but it'll take a more thorough read to see how easy it'd be to steal port their move reconciliation stuff over to Dwifft. Thanks again for the link!

[marcprux]

This is pretty easy to do as a post-processing step by collapsing .insert and .delete with the same item into a single .move. This is the approach that DeepDiff takes (see https://github.com/onmyway133/DeepDiff/blob/master/Sources/Shared/MoveReducer.swift).

I've done a quick implementation below, and it can be used by changing the sectionedValues updater to be:

  let diff = Dwifft.synthesizeMoves(Dwifft.diff(lhs: oldSectionedValues, rhs: newSectionedValues))

I've implemented it in my own NSCollectionView, and it seems to have tolerable performance (plus it looks great!). I could probably put together a PR if there is sufficient interest.

public extension Dwifft {

    /// Takes a series of diff steps and collapses matching inserts and deletes into a single move operation.
    ///
    /// Note that this requires adding a case move(Int, Int, Value, Int, Int) to SectionedDiffStep
    /// and processing moves appropriately in the various AbstractDiffCalculator implementations, e.g.:
    ///   case let .move(fromSection, fromItem, _, toSection, toItem):
    ///       collectionView.moveItem(at: IndexPath(item: fromItem, section: fromSection), to: IndexPath(item: toItem, section: toSection))
    static func synthesizeMoves<Section, Value: Equatable>(_ source: [SectionedDiffStep<Section, Value>]) -> [SectionedDiffStep<Section, Value>] {
        typealias Mutation = (offset: Int, element: (section: Int, index: Int, value: Value))

        func insertMutation(offset: Int, forStep: SectionedDiffStep<Section, Value>) -> Mutation? {
            if case let .insert(section, index, value) = forStep { return (offset, (section, index, value)) } else { return nil }
        }

        func deleteMutation(offset: Int, forStep: SectionedDiffStep<Section, Value>) -> Mutation? {
            if case let .delete(section, index, value) = forStep { return (offset, (section, index, value)) } else { return nil }
        }

        // this could be a set, but we might have the same value more than once in the model
        let deleteValues = source.enumerated().compactMap(deleteMutation).map({ $0.element.value })

        // no deletes means no moves
        if deleteValues.isEmpty { return source }

        var changes = source

        for candidate in deleteValues {
            guard let deleteItem = changes.lazy.enumerated().compactMap(deleteMutation).first(where: { $0.element.value == candidate }) else { continue }
            guard let insertItem = changes.lazy.enumerated().compactMap(insertMutation).first(where: { $0.element.value == candidate }) else { continue }

            let (lower, upper) = (min(deleteItem.offset, insertItem.offset), max(deleteItem.offset, insertItem.offset))

            changes.remove(at: upper)
            changes.remove(at: lower)
            changes.insert(.move(deleteItem.element.section, deleteItem.element.index, candidate, insertItem.element.section, insertItem.element.index), at: lower)
        }

        return changes
    }
}

[Alex293]

+1 @marcprux