Search code examples
c#listdiffarray-differenceinotifycollectionchanged

Replicating changes in a list

Imagine I have a list of items:

 - A
 - B
 - C

Now from somewhere a server tells my application that element B was removed, yet it only provides the entire new list, not the exact change details. Since WinRT ListViews automatically animate addition, removal, and movement of items inside them, I would prefer not to refresh the backing list and call a Reset-INotifyCollectionChanged-event, since this animates every item looking rather blunt and rough. Instead, I want to compute the steps that are needed to transform my local list into the list that I get from the server. (Kind of like a levenshtein distance, just not with the count of steps but the with steps themselves)

e. g.:

 1. Delete element B
 2. Add new element D to position 3

How would I do that?

EDIT: Order matters in my case.

Solution

  • Based on the title of the page @MihaiCaracostea suggested, I was able to find a working diff algorithm that works on any IList<T>. It even uses yield to calculate the diff lazily as you are enumerating the changes.

    The article can be found here, the actual source code (if you don't want to read how it's done) is here.

    Beware though, the algorithm runs in O(n²) time. There certainly is room for improvement in that area.