Reconciling a new BindingList into a master BindingList using LINQ

Question

I have a seemingly simple problem whereby I wish to reconcile two lists so that an 'old' master list is updated by a 'new' list containing updated elements. Elements are denoted by a key property. These are my requirements:

• All elements in either list that have the same key results in an assignment of that element from the 'new' list over the original element in the 'old' list only if any properties have changed.
• Any elements in the 'new' list that have keys not in the 'old' list will be added to the 'old' list.
• Any elements in the 'old' list that have keys not in the 'new' list will be removed from the 'old' list.

I found an equivalent problem here - http://stackoverflow.com/questions/161432/ - but it hasn't really been answered properly. So, I came up with an algorithm to iterate through the old and new lists and perform the reconciliation as per the above. Before anyone asks why I'm not just replacing the old list object with the new list object in its entirety, it's for presentation purposes - this is a BindingList bound to a grid on a GUI and I need to prevent refresh artifacts such as blinking, scrollbars moving, etc. So the list object must remain the same, only its updated elements changed.

Another thing to note is that the objects in the 'new' list, even if the key is the same and all the properties are the same, are completely different instances to the equivalent objects in the 'old' list, so copying references is not an option.

Below is what I've come up with so far - it's a generic extension method for a BindingList. I've put comments in to demonstrate what I'm trying to do.

public static class BindingListExtension
{
    public static void Reconcile<T>(this BindingList<T> left,
                                    BindingList<T> right,
                                    string key)
    {
        PropertyInfo piKey = typeof(T).GetProperty(key);

        // Go through each item in the new list in order to find all updated and new elements
        foreach (T newObj in right)
        {
            // First, find an object in the new list that shares its key with an object in the old list
            T oldObj = left.First(call => piKey.GetValue(call, null).Equals(piKey.GetValue(newObj, null)));

            if (oldObj != null)
            {
                // An object in each list was found with the same key, so now check to see if any properties have changed and
                // if any have, then assign the object from the new list over the top of the equivalent element in the old list
                foreach (PropertyInfo pi in typeof(T).GetProperties())
                {
                    if (!pi.GetValue(oldObj, null).Equals(pi.GetValue(newObj, null)))
                    {
                        left[left.IndexOf(oldObj)] = newObj;
                        break;
                    }
                }
            }
            else
            {
                // The object in the new list is brand new (has a new key), so add it to the old list
                left.Add(newObj);
            }
        }

        // Now, go through each item in the old list to find all elements with keys no longer in the new list
        foreach (T oldObj in left)
        {
            // Look for an element in the new list with a key matching an element in the old list
            if (right.First(call => piKey.GetValue(call, null).Equals(piKey.GetValue(oldObj, null))) == null)
            {
                // A matching element cannot be found in the new list, so remove the item from the old list
                left.Remove(oldObj);
            }
        }
    }
}

It can be called like this:

_oldBindingList.Reconcile(newBindingList, "MyKey")

However, I'm looking for perhaps a method of doing the same using LINQ type methods such as GroupJoin<>, Join<>, Select<>, SelectMany<>, Intersect<>, etc. So far, the problem I've had is that each of these LINQ type methods result in brand new intermediary lists (as a return value) and really, I only want to modify the existing list for all the above reasons.

If anyone can help with this, would be most appreciated. If not, no worries, the above method (as it were) will suffice for now.

Thanks, Jason

Answer 1

Suggestion:

Instead of string key, use Expression<Func<T,object>> key.

Example to get you going:

class Bar
{
  string Baz { get; set; }

  static void Main()
  {
    Foo<Bar>(x => x.Baz);
  }

  static void Foo<T>(Expression<Func<T, object>> key)
  {
    // what do we have here?
    // set a breakpoint here
    // look at key
  }
}

Answer 2

I'm not sure about BindingList, but you could use Continuous LINQ against an ObservableCollection<T> to do this. Rather than periodically reconciling the list, Continuous LINQ will create a read only list which updates as a result of change notifications from the list you query and, if your objects implement INotifyPropertyChanged, from the objects in the list.

This will allow you to use LINQ without generating a new list every time.

Answer 3

Your main loop is O(m*n), where m and n are sizes of old and new lists. This is pretty bad. A better idea might be to build sets of key-element mappings first, and then work on them. Also, avoiding Reflection would be a good idea - a lambda can be used instead as key selector. So:

 public static void Reconcile<T, TKey>(
     this BindingList<T> left,
     BindingList<T> right,
     Func<T, TKey> keySelector)
 {
     var leftDict = left.ToDictionary(l => keySelector(l));

     foreach (var r in right)
     {
         var key = keySelector(r);
         T l;
         if (leftDict.TryGetValue(key, out l))
         {
              // copy properties from r to l
              ...
              leftDict.RemoveKey(key);
         }
         else
         {
              left.Add(r);
         }
     }

     foreach (var key in leftDict.Keys)
     {
         left.RemoveKey(key);
     }
 }

For copying properties, I'd avoid Reflection, too - either make an interface for that, similar to ICloneable, but for transferring properties between objects rather than creating new instances, and have all your objects implement it; or, supply it to Reconcile via another lambda.

Answer 4

Thanks for the replies. I used Pavel's very nifty solution and slightly modified it to not use var objects (and not sure where you got RemoveKey from), and here is the updated version of my extension method:

public static class BindingListExtension
{
    public static void Reconcile<T, TKey>(this BindingList<T> left,
                                          BindingList<T> right,
                                          Func<T, TKey> keySelector) where T : class
    {
        Dictionary<TKey, T> leftDict = left.ToDictionary(key => keySelector(key));

        // Go through each item in the new list in order to find all updated and new elements
        foreach (T newObj in right)
        {
            TKey key = keySelector(newObj);
            T oldObj = null;

            // First, find an object in the new list that shares its key with an object in the old list
            if (leftDict.TryGetValue(key, out oldObj))
            {
                // An object in each list was found with the same key, so now check to see if any properties have changed and
                // if any have, then assign the object from the new list over the top of the equivalent element in the old list
                foreach (PropertyInfo pi in typeof(T).GetProperties())
                {
                    if (!pi.GetValue(oldObj, null).Equals(pi.GetValue(newObj, null)))
                    {
                        left[left.IndexOf(oldObj)] = newObj;
                        break;
                    }
                }

                // Remove the item from the dictionary so that all that remains after the end of the current loop are objects
                // that were not found (sharing a key with any object) in the new list - so these can be removed in the next loop
                leftDict.Remove(key);
            }
            else
            {
                // The object in the new list is brand new (has a new key), so add it to the old list
                left.Add(newObj);
            }
        }

        // Go through all remaining objects in the dictionary and remove them from the master list as the references to them were
        // not removed earlier, thus indicating they no longer exist in the new list (by key)
        foreach (T removed in leftDict.Values)
        {
            left.Remove(removed);
        }
    }
}

I'm not sure how or why to use Expression - this seems like it might be slightly better to use than just Func, but could you elaborate on this a little more please leppie, in particular, how to use this in my method to extract the key?

And is there any other way of comparing the properties of my objects without using reflection as I don't wish to implement a special interface on all my objects that might use this extension method? I've thought about simply overriding Equals in my classes, but I want to try and achieve the comparison without having to disrupt my existing classes if possible.

Thanks.

Answer 5

Just to keep this Question updated with the latest incarnation of my solution based on Pavel's original Answer, here's the latest version of the code which fixes some problems with the original version, particularly with regard to maintaining order, treating ObservableCollection specially and handling collections without a key field:

internal static class ListMergeExtension
{
    public static void Reconcile<T, TKey>(this IList<T> left, IList<T> right, Func<T, TKey> keySelector) where T : class
    {
        Dictionary<TKey, T> leftDict = left.ToDictionary(keySelector);
        int index = 0;

        // Go through each item in the new list in order to find all updated and new elements
        foreach (T newObj in right)
        {
            TKey key = keySelector(newObj);
            T oldObj = null;

            // First, find an object in the new list that shares its key with an object in the old list
            if (leftDict.TryGetValue(key, out oldObj))
            {
                // An object in each list was found with the same key, so now check to see if any properties have changed and
                // if any have, then assign the object from the new list over the top of the equivalent element in the old list
                ReconcileObject(left, oldObj, newObj);

                // Remove the item from the dictionary so that all that remains after the end of the current loop are objects
                // that were not found (sharing a key with any object) in the new list - so these can be removed in the next loop
                leftDict.Remove(key);
            }
            else
            {
                // The object in the new list is brand new (has a new key), so insert it in the old list at the same position
                left.Insert(index, newObj);
            }

            index++;
        }

        // Go through all remaining objects in the dictionary and remove them from the master list as the references to them were
        // not removed earlier, thus indicating they no longer exist in the new list (by key)
        foreach (T removed in leftDict.Values)
        {
            left.Remove(removed);
        }
    }

    public static void ReconcileOrdered<T>(this IList<T> left, IList<T> right) where T : class
    {
        // Truncate the old list to be the same size as the new list if the new list is smaller
        for (int i = left.Count; i > right.Count; i--)
        {
            left.RemoveAt(i - 1);
        }

        // Go through each item in the new list in order to find all updated and new elements
        foreach (T newObj in right)
        {
            // Assume that items in the new list with an index beyond the count of the old list are brand new items
            if (left.Count > right.IndexOf(newObj))
            {
                T oldObj = left[right.IndexOf(newObj)];

                // Check the corresponding objects (same index) in each list to see if any properties have changed and if any
                // have, then assign the object from the new list over the top of the equivalent element in the old list
                ReconcileObject(left, oldObj, newObj);
            }
            else
            {
                // The object in the new list is brand new (has a higher index than the previous highest), so add it to the old list
                left.Add(newObj);
            }
        }
    }

    private static void ReconcileObject<T>(IList<T> left, T oldObj, T newObj) where T : class
    {
        if (oldObj.GetType() == newObj.GetType())
        {
            foreach (PropertyInfo pi in oldObj.GetType().GetProperties())
            {
                // Don't compare properties that have this attribute and it is set to false
                var mergable = (MergablePropertyAttribute)pi.GetCustomAttributes(false).FirstOrDefault(attribute => attribute is MergablePropertyAttribute);

                if ((mergable == null || mergable.AllowMerge) && !object.Equals(pi.GetValue(oldObj, null), pi.GetValue(newObj, null)))
                {
                    if (left is ObservableCollection<T>)
                    {
                        pi.SetValue(oldObj, pi.GetValue(newObj, null), null);
                    }
                    else
                    {
                        left[left.IndexOf(oldObj)] = newObj;

                        // The entire record has been replaced, so no need to continue comparing properties
                        break;
                    }
                }
            }
        }
        else
        {
            // If the objects are different subclasses of the same base type, assign the new object over the old object
            left[left.IndexOf(oldObj)] = newObj;
        }
    }
}

Reconcile is used when there is a unique key field available for comparing the two lists. ReconcileOrdered is used when there is no key field available, but the order between the two lists is guaranteed to be synonymous and new records are appended (if they are inserted, not appended, it will still work, but performance will be compromised).