Observable collection that keeps suitable items

[xperiandri]

When an ItemsControl derived control is bound to a collection it creates visuals to display such items. When you switch reference in ItemsSource to another one all that visuals are thrown away and new visuals are created. So this is not the best solution for performance reasons. Hence in order to make this scenario performant required an implementation of INotifyCollectionChanged which can check which items were deleted, which changed, which added and fires appropriate events.

[GuillaumeSalles]

Hi @xperiandri.

You are right. 👍 We need a way to patch items like react does with its vdom.

One way to do this is to use patch algorithm like the Levenstein distance (https://en.wikipedia.org/wiki/Levenshtein_distance). It has a O(m*n) complexity so it could have performance issue on large collection. I wrote a small extension method on ObservableCollection without much tests so it could contains bugs:

public static class ObservableCollectionExtensions
    {
        public static void LevenshteinPatch<T>(this ObservableCollection<T> source, IList<T> target)
        {
            if(source.Count == 0 && target.Count != 0)
            {
                foreach(var item in target)
                {
                    source.Add(item);
                }
                return;
            }

            if(target.Count == 0)
            {
                source.Clear();
                return;
            }

            var matrix = BuildLevenshteinMatrix(source, target);
            ApplyLevenshteinMatrix(source, target, matrix);
        }

        private static int[,] BuildLevenshteinMatrix<T>(ObservableCollection<T> source, IList<T> target)
        {
            var m = new int[source.Count + 1, target.Count + 1];

            for (var i = 1; i < source.Count; i++)
            {
                m[i, 0] = i;
            }

            for (var j = 1; j < target.Count; j++)
            {
                m[0, j] = j;
            }

            for (var j = 1; j < target.Count + 1; j++)
            {
                for (var i = 1; i < source.Count + 1; i++)
                {
                    var substitutionCost = Equals(source[i - 1], target[j - 1]) ? 0 : 1;

                    var deletion = m[i - 1, j] + 1;
                    var insertion = m[i, j - 1] + 1;
                    var substitution = m[i - 1, j - 1] + substitutionCost;
                    m[i, j] = Min(deletion, insertion, substitution);
                }
            }

            return m;
        }

        private static void ApplyLevenshteinMatrix<T>(ObservableCollection<T> source, IList<T> target, int[,] matrix)
        {
            var i = source.Count;
            var j = target.Count;

            while (i > 0 && j > 0)
            {
                if (matrix[i - 1, j] < matrix[i, j])
                {
                    i--;
                    source.RemoveAt(i);
                }
                else if (matrix[i, j - 1] < matrix[i, j])
                {
                    j--;
                    source.Insert(i, target[j]);
                }
                else if (matrix[i - 1, j - 1] < matrix[i, j])
                {
                    i--;
                    j--;
                    source[i] = target[j];
                }
                else
                {
                    i--;
                    j--;
                }
            }

            for (var k = 0; k < j; k++)
            {
                source.Insert(k, target[k]);
            }

            for (var k = 0; k < i; k++)
            {
                source.RemoveAt(0);
            }
        }

        private static int Min(int a, int b, int c)
        {
            var min = a < b ? a : b;
            return min < c ? min : c;
        }
    }

A more efficient way to do it would be to extract a unique key for each item to reduce the complexity. React documentation explain it briefly : https://facebook.github.io/react/docs/reconciliation.html

If you are interested in this, Inferno has a great algorithm to patch keyed children : https://github.com/infernojs/inferno/blob/master/packages/inferno/src/DOM/patching.ts#L462

I would be great if Redux shipped a custom INotifyCollectionChanged collection or an extension method on ObservableCollection to patch items.

If someone is interested to make a PR, I would be glad to review it and merge it!

[xperiandri]

Extension method will not be as efficient as custom collection, a collection can batch update as a batch update within args of a single time raised event. Maybe not single time but not as much as 4 times. I don't remember the args type implementation

[cmeeren]

I don't really know what the issue is here, but it seems the core of it is that something akin to a ListView is fully re-rendered even though only part of a collection in the state has changed, because the state collection does not implement INotifyCollectionChanged (and, indeed, is not and should not be mutable).

What about having a view model where you bind the control to to a local ObservableCollection that you update from the immutable collection in the state?

Sorry if I totally missed the point here.