Supporting DiffOperation.Update for items with the same identifier

[FritiofSchander]

Hey!

I have a feature request.

I would like to be able to use a library like Difference like i would use DiffUtils where the differences are based on not only the index in the list, but also the identity of the item. This way i could receive DiffOperations which are not only Add/Remove/Move, but also Update. Not sure if it would be possible to implement with your current algorithm.

Something like
fun <K, V> generateDiffs( original: List<V>, updated: List<V>, detectMoves: Boolean, keySelector: (V) -> K )
or:
fun <K, V> generateDiffs( original: Map<K, V>, updated: Map<K, V>, )

[andrewbailey]

Conceptually, I think this is a two-step operation. If you first diff just against the keys, you can determine which values have also been updated by applying that diff to your starting point and comparing each item using ==. If an item at a given index differs between the starting list state after applying the diff of the keys and the target list state, it must have been updated.

I'm not sure there's a great way to slot that into the library — there doesn't seem to be an obvious way to integrate this directly with Eugene Myers' differencing algorithm, it's unclear what the correct behavior is when there are duplicate keys (the solution I proposed will minimize the diff edit length but not the number of update operations), and this seems easy enough to build on top of the existing library since it just needs another for loop.

That said, I think you do need additional functionality to make this work: You'll need some way to provide a different comparison strategy to override the default behavior of using ==. Does it seem like a viable approach to offer that API and do the update comparison on your end? The code would look something like this:

val diff = differenceOf(
    original = contactsList,
    updated = updatedContactsList,
    // New parameter:
    comparison = { contact1, contact2 -> contact1.uuid == contact2.uuid }
)

val output = contactsList.toMutableList()
diff.applyDiff(
    remove = { index -> output.removeAt(index) },
    insert = { item, index -> output.add(index, item) }
)

// Check for updates on your end
for (i in 0 until output.size) {
    if (output[i] != updatedContactsList[i]) {
        // The contact at index i (in updatedContactsList) was updated.
        output[i] = updatedContactsList[i]
    }
}