Tuesday, April 27, 2010

Keeping an ObservableCollection sorted with a method override

by Andrea Boschin via Silverlight & XAML Playground on 4/27/2010 4:30:52 PM

Usually the order of elements in a collection is something one does not feel to be important. We have plenty of methods in the Framework to order things and now that there is LINQ to Objects the need to sort something is really matter of seconds.

Since the introduction of LINQ the main problem is that you have many cases where a few lines of code are adding really complex iteration logic and often this hurts performances when the count of milliseconds is something important.

In these days I had this problem because I did need to make a lot of updates to a collection in the short time as possible, because I was working into the a CompositionTarget_Rendering event. A lot of hidden iterations through the collection, made by LINQ queries, has degraded the performances of the application and I had to put my nose on the iteration logic to optimize it.

In a case like this, having a collection that ensure a given order of the elements was key to solve my problem. So I decided to implement a SortedObservableCollection that helped me to minimize scans of the collection. Here is the simple code:

   1: public class SortedObservableCollection<T> : ObservableCollection<T>

   2:     where T : IComparable

   3: {

   4:     protected override void InsertItem(int index, T item)

   5:     {

   6:         for (int i = 0; i < this.Count; i++)

   7:         {

   8:             switch (Math.Sign(this[i].CompareTo(item)))

   9:             {

  10:                 case 0:

  11:                     throw new InvalidOperationException("Cannot insert duplicated items");

  12:                 case 1:

  13:                     base.InsertItem(i, item);

  14:                     return;

  15:                 case -1:

  16:                     break;

  17:             }

  18:         }

  19:  

  20:         base.InsertItem(this.Count, item);

  21:     }

  22: }

The trick has been done in a few minutes, just because the ObservableCollection exposes some overridable methods that enable the developer to change the Insert and Remove behavior. So I simply overriden the InsertItem method. I changed it trying to put elements in the right place, evaluating the position over the elements already in the collection. This helped me to move the sorting logic in another context, out of the Rendering event, and maximize the performances.

The code I wrote in this sample is really simple. I figure out you can improve again the performances of the InsertItem method implementing a binary search algorithm. But it is a little concern when you know where to act.