Daniel Hoelbling-Inzko talks about programming

Missing SortedList?

Posted by Daniel Hölbling on April 10, 2009

I made it a habit to always program towards an Interface if possible. So all my lists in code are of type IList<T> and the IList<T> lacks the .Sort() method of the List<T> class.

Usually this isn’t a problem since there is LinQ’s .OrderBy to save the day. But this time my class is too generic for that so I have to fall back to good old OO principles with comparer classes etc.

Now, my problem is that I need a simple IList that is sorted on insertion. I first thought, no problem I’ll just use the SortedList<Tkey, Tvalue> that’s already in the framework. But there is always a catch: SortedList is more of a dictionary than a list. Duplicate key items aren’t accepted, there is no collision handling. Trying to insert a duplicate key will result in a ArgumentException:

public void SortedList_AcceptsNoDuplicateKeys()
    SortedList<int, string> list = new SortedList<int, string>();
    var key = 1;
    list.Add(key, "test");
    Assert.Throws(typeof (ArgumentException), () => list.Add(key, "test2)"));

Now, what I need is a real sorted List that allows duplicate values (as would a List.Sort()).

Implementing the IList interface isn’t that hard after all, so I gave it a shot with a SortedKeylessCollection<T> that wraps a real List<T> (to use it’s .Sort(), I know I’m lazy):

public class SortedKeylessCollection<T> : ICollection<T> where T : class
    private readonly IComparer<T> comparer;
    private readonly List<T> list = new List<T>();

    public SortedKeylessCollection(IComparer<T> comparer)     {         this.comparer = comparer;     }

    public SortedKeylessCollection() : this(Comparer<T>.Default)     {     }

    #region ICollection<T> Members

    public void Add(T item)     {         list.Add(item);         SortList();     }

    public void Clear()     {         list.Clear();     }

    public bool Contains(T item)     {         return list.Contains(item);     }

    public void CopyTo(T[] array, int arrayIndex)     {         list.CopyTo(array, arrayIndex);     }

    public bool Remove(T item)     {         bool b = list.Remove(item);         if (b) SortList();         return b;     }

    public int Count     {         get { return list.Count; }     }

    public bool IsReadOnly     {         get { return false; }     }

    public IEnumerator<T> GetEnumerator()     {         return list.GetEnumerator();     }

    IEnumerator IEnumerable.GetEnumerator()     {         return list.GetEnumerator();     }


    public void SortList()     {         list.Sort(comparer);     } }

You can download the file here: SortedKeylessCollection.cs.

I didn’t call it List but Collection because IList<T> has a defined contract through InsertAt that can’t be fulfilled by a self-sorting list (since the insertion at a position shouldn’t be possible).

Also, as someone at StackOverlow pointed out there are already implementations of such lists like the Wintellect Power Collections for .NET but I didn’t want to bring yet another dependency into my codebase just for one puny little class.

Filed under net, programmierung
comments powered by Disqus

My Photography business


dynamic css for .NET