The blog of dlaa.me

Recently, I wrote a post about the IListExtensions collection of extension methods I created to make it easy to maintain a sorted list based on any IList(T) implementation without needing to create a special subclass. In that post, I explained why I implemented IListExtensions the way I did and outlined some of the benefits for scenarios like using ObservableCollection(T) for dynamic updates on Silverlight, WPF, and Windows Phone where the underlying class doesn't intrinsically support sorting. A couple of readers followed up with some good questions and clarifications which I'd encourage having a look for additional context.

 

During the time I've been using IListExtensions in a project of my own, I have noticed two patterns that prompted today's update:

1. It's easy to get performant set-like behavior from a sorted list. Recall that a set is simply a collection in which a particular item appears either 0 or 1 times (i.e., there are no duplicates in the collection). While this invariant can be easily maintained with any sorted list by performing a remove before each add (recall that ICollection(T).Remove (and therefore IListExtensions.RemoveSorted) doesn't throw if an element is not present), it also means there are two searches of the list every time an item is added: one for the call to RemoveSorted and another for the call to AddSorted. While it's possible to be a bit more clever and avoid the extra search sometimes, the API doesn't let you to "remember" the right index between calls to *Sorted methods, so you can't get rid of the redundant search every time.

   Therefore, I created the AddOrReplaceSorted method which has the same signature as AddSorted (and therefore ICollection(T).Add) and implements the set-like behavior of ensuring there is at most one instance of a particular item (i.e., the IComparable(T) search key) present in the collection at any time. Because this one method does everything, it only ever needs to perform a single search of the list and can help save a few CPU cycles in relevant scenarios.

2. It's convenient to be able to call RemoveSorted/IndexOfSorted/ContainsSorted with an instance of the search key. Recall from the original post that IListExtensions requires items in the list to implement the IComparable(T) interface in order to define their sort order. This is fine most of the time, but can require a bit of extra overhead in situations where the items' sort order depends on only some (or commonly just one) of their properties.

   For example, note that the sort order the Person class below depends only on the Name property:

   class Person : IComparable<Person>
   {
       public string Name { get; set; }
       public string Details { get; set; }
   
       public int CompareTo(Person other)
       {
           return Name.CompareTo(other.Name);
       }
   }

   In this case, using ContainsSorted on a List(Person) to search for a particular name would require the creation of a fake Person instance to pass as the parameter to ContainsSorted in order to match the type of the underlying collection. This isn't usually a big deal (though it can be if the class doesn't have a public constructor!), but it complicates the code and seems like it ought to be unnecessary.

   Therefore, I've added new versions of RemoveSorted/IndexOfSorted/ContainsSorted that take a key parameter and a keySelector Func(T, K). The selector is passed an item from the list and needs to return that item's sort key (the thing that its IComparable(T).CompareTo operates on). Not surprisingly, the underlying type of the keys must implement IComparable(T); keys are then compared directly (instead of indirectly via the containing items). In this way, it's possible to look up (or remove) a Person in a List(Person) by passing only the person's name and not having to bother with the temporary Person object at all!

 

In addition to the code changes discussed above, I've updated the automated test project that comes with IListExtensions to cover all the new scenarios. Conveniently, the new implementation of AddOrReplaceSorted is nearly identical to that of AddSorted and can be easily validated with SortedSet(T). Similarly, the three new key-based methods have all been implemented as variations of the pre-existing methods and those have been modified to call directly into the new methods. Aside from a bit of clear, deliberate redundancy for AddOrReplaceSorted, there's hardly any more code in this release than there was in the previous one - yet refactoring the implementation slightly enabled some handy new scenarios!

 

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

 

Proper sorting libraries offer a wide variety of ways to sort, compare, and work with sorted lists. IListExtensions is not a proper sorting library - nor does it aspire to be one. :) Rather, it's a small collection of handy methods that make it easy to incorporate sorting into some common Silverlight, WPF, and Windows Phone scenarios. Sometimes you're forced to use a collection (like ObservableCollection(T)) that doesn't do everything you want - but if all you're missing is basic sorting functionality, then IListExtensions just might be the answer!