Observable collection that keeps suitable items

[guillaumesalles]

Observable collection that keeps suitable items

[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.