The blog of dlaa.me

If you want to display a dynamically changing collection of items in WPF, Silverlight, or Windows Phone, there are a lot of collection classes to pick from - but there's really just one good choice: ObservableCollection(T). Although nearly all the IList(T)/ICollection(T)/IEnumerable(T) implementations work well for static data, dynamic data only updates automatically when it's in a collection that implements INotifyCollectionChanged. And while it's possible to write your own INotifyCollectionChanged code, doing a good job takes a fair amount of work. Fortunately, ObservableCollection(T) does nearly everything you'd want and is a great choice nearly all of the time.

Unless you want your data sorted...

By design, ObservableCollection(T) doesn't sort data - that's left to the CollectionView class which is the officially recommended way to sort lists for display (for more details, please refer to the Data Binding Overview's "Binding to Collections" section). The way CollectionView works is to add an additional layer of indirection on top of your list. That gets sorted and the underlying collection isn't modified at all. This is a fine, flexible design (it enables a variety of other scenarios like filtering, grouping, and multiple views), but sometimes it'd be easier if the actual collection were sorted and the extra layer wasn't present (in addition to imposing a bit of overhead, working with CollectionView requires additional code to account for the indirection).

 

So it would be nice if there were a handy way to sort an ObservableCollection(T) - something like the List(T).Sort method. Unfortunately, ObservableCollection(T) doesn't derive from List(T), so it doesn't have that method... Besides, it'd be better if adding items to the list put them in the right place to begin with - instead of adding them to the wrong place and then re-sorting the entire list after the fact. Along the same lines, scenarios that could take advantage of sorting for faster look-ups would benefit from something like List(T).BinarySearch - which also doesn't exist on ObservableCollection(T).

All we really need to do here is provide custom implementations of add/remove/contains/index-of for ObservableCollection(T) and we'd have the best of both worlds. One way of doing that is to subclass - but that ties the code to a specific base class and limits its usefulness somewhat (just like Sort and BinarySearch for List(T) above). What we can do instead is implement these helper methods in a standalone class and enable them to target the least common denominator, IList(T), and therefore apply in a variety of scenarios (i.e., all classes that implement that interface). What's more, these helpers can be trivially written as extension methods so they'll look just like APIs on the underlying classes!

 

This sounds promising - let's see how it might work by considering the complete IList(T) interface hierarchy:

public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
{
    T this[int index] { get; set; }         // Good as-is
    int IndexOf(T item);                    // Okay as-is; could be faster if sorted
    void Insert(int index, T item);         // Should NOT be used with a sorted collection (might un-sort it)
    void RemoveAt(int index);               // Good as-is
}
public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    int Count { get; }                      // Good as-is
    bool IsReadOnly { get; }                // Good as-is
    void Add(T item);                       // Needs custom implementation that preserves sort order
    void Clear();                           // Good as-is
    bool Contains(T item);                  // Okay as-is; could be faster if sorted
    void CopyTo(T[] array, int arrayIndex); // Good as-is
    bool Remove(T item);                    // Okay as-is; could be faster if sorted
}
public interface IEnumerable<T> : IEnumerable
{
    IEnumerator<T> GetEnumerator();         // Good as-is
}
public interface IEnumerable
{
    IEnumerator GetEnumerator();            // Good as-is
}

To create a sorted IList(T), there's only one method that needs to be written (add) and three others that should be written to take advantage of the sorted collection for better performance (remove, contains, and index-of). (Aside: If you know a list is sorted, finding the right location changes from an O(n) problem to an O(log n) problem. Read more about "big O" notation here.) The only additional requirement we'll impose is that the elements of the collection must have a natural order. One way this is commonly done is by implementing the IComparable(T) interface on the item class. Basic .NET types already do this, as do other classes in the framework (ex: DateTime, Tuple, etc.). Because this interface has just one method, it's easy to add - and can often be implemented in terms of IComparable(T) for its constituent parts!

 

So here's what the IListExtensions class I've created looks like:

static class IListExtensions
{
    public static void AddSorted<T>(this IList<T> list, T item) where T : IComparable<T> { ... }
    public static bool RemoveSorted<T>(this IList<T> list, T item) where T : IComparable<T> { ... }
    public static int IndexOfSorted<T>(this IList<T> list, T item) where T : IComparable<T> { ... }
    public static bool ContainsSorted<T>(this IList<T> list, T item) where T : IComparable<T> { ... }
}

You can use it to create and manage a sorted ObservableCollection(T) simply by adding "Sorted" to the code you already have!

 

[Click here to download the IListExtensions implementation and its complete unit test project.]

 

One downside to the extension method approach is that the existing List(T) methods remain visible and can be called by code that doesn't know to use the *Sorted versions instead. For Contains, IndexOf, and Remove, this is inefficient, but will still yield the correct answer - but for Add and Insert it's a bug because these two methods are likely to ruin the sorted nature of the list when used without care. Once a list becomes unsorted, the *Sorted methods will return incorrect results because they optimize searches based on the assumption that the list is correctly sorted. Subclassing would be the obvious "solution" to this problem, but it's not a good option here because the original methods aren't virtual on ObservableCollection(T)...

I'm not aware of a good way to make things foolproof without giving up on the nice generality benefits of the current approach, so this seems like one of those times where you just need to be careful about what you're doing. Fortunately, most programs probably only call the relevant methods a couple of times, so it's pretty easy to visit all the call sites and change them to use the corresponding *Sorted method instead. [Trust me, I've done this myself. :) ]

Aside: There's a subtle ambiguity regarding what to do if the collection contains duplicate items (i.e., multiple items that sort to the same location). It doesn't seem like it will matter most of the time, so IListExtensions takes the performant way out and returns the first correct answer it finds. It's important to note this is not necessarily the first of a group of duplicate items, nor the last of them - nor will it always be the same one of them! Basically, if the items' IComparable(T) implementation says two items are equivalent, then IListExtensions assumes they are and that they're equally valid answers. If the distinction matters in your scenario, please feel free to tweak this code and take the corresponding performance hit. :) (Alternatively, if the items' IComparable(T) implementation can be modified to distinguish between otherwise "identical" items, the underlying ambiguity will be resolved and things will be deterministic again.)

 

It's usually best to leverage platform support for something when it's available, so please look to CollectionView for your sorting needs in WPF, Silverlight, and Windows Phone applications. But if you end up in a situation where it'd be better to maintain a sorted list yourself, maybe IListExtensions is just what you need!