Missing SortedList?
April 10, 2009 by Daniel HoelblingI 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:
[Fact]
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();
}
#endregion
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.
