I have an IList<T> that I need to sort, and I would rather not copy the list if possible. I've noticed that ArrayList has an Adapter static method that wraps the passed list without copying it, but this takes an IList and I have an IList<T>. Is it safe to cast from a System.Collections.Generic.IList<T> to a System.Collections.IList and just use the Adapter method?
Note that this is .Net 2.0, so LINQ is not an option.
From the blog of Paul Fox, I recommend the post "How to sort an IList": http://foxsys.blogspot.com/2007/06/how-to-sort-generic-ilist.html
Just in case that blog goes away in the future, I'll copy the post here:
How to sort a generic IList
Update
You can read and updated post about sorting generic IList and List. Many people will prefer the methods mentioned in the updated post.
Sorting a generic IList
I was trying to sort a generic IList<> and found a fairly simple way of doing it.
Step 1
You need to implement IComparable for the type contained in your IList. For this example I am going to use a simple Language Dto class.
public class LanguageDto : IComparable {
private String name;
public string Name { get { return name; } set { name = value; } }
public LanguageDto(string name) {
this.name = name;
}
#region IComparable Members
public int CompareTo(object obj) {
if (obj is LanguageDto) {
LanguageDto language = (LanguageDto)obj;
return this.name.CompareTo(language.name);
}
throw new ArgumentException(string.Format("Cannot compare a LanguageDto to an {0}", obj.GetType().ToString()));
}
#endregion
}
STEP 2
Sort your IList. To do this you will use the ArrayList.Adapter() method passing in your IList, and then calling the Sort method. Like so...
ArrayList.Adapter((IList)languages).Sort();
Note: languages is of type "IList"
Languages should then be a sorted list of your type!
You cannot cast IList(T) to IList.
After some sniffing with Reflector, it seems like ArrayList.Adapter(IList).Sort() will first copy the list to an object array, sort the array and then copy the array back to a list:
object[] array = new object[count];
this.CopyTo(index, array, 0, count);
Array.Sort(array, 0, count, comparer);
for (int i = 0; i < count; i++)
{
this._list[i + index] = array[i];
}
You might get boxing overhead if T in your List(T) a value type.
If you need to alter the sequence of the objects in the list that you have, you can do it similarly:
IList<object> unsorted = ...
List<object> sorted = new List<object>(unsorted);
sorted.Sort();
for (int i = 0; i < unsorted.Countt; i++)
{
unsorted[i] = sorted[i];
}
If the list is so huge (as in hundreds of million items) that you cannot make an extra copy in memory, I suggest using a List(T) in the first place or implement your favorite in-place sorting algorithm.
Since the Sort method isn't on the IList interface you might consider creating your own:
interface ISortableList<T> : IList<T>
{
void Sort();
void Sort(IComparer<T> comparer);
}
class SortableList<T> : List<T>, ISortableList<T> { }
/* usage */
void Example(ISortedList<T> list)
{
list.Sort();
list.Sort(new MyCustomerComparer());
}
In general the parameter type you specify in your method should be the lowest common denominator of members you actually need to call. If you really need to call the Sort() method then your parameter should have that member defined. Otherwise you should probably load it into another object that can do what you want such as:
void Example(IList<T> list)
{
list = new List<T>(list).Sort();
}
This should actually be pretty fast, almost certainly faster still than writing your own custom inline sort algorithm.
I know it isn't .NET 2.0 but I love LINQ so much and will endorse it every chance I get :)
Simple Sort:
var sortedProducts =
from p in products
orderby p.ProductName
select p;
ObjectDumper.Write(sortedProducts);
Sort by multiple conditions:
string[] digits = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
var sortedDigits =
from d in digits
orderby d.Length, d
select d;
Both examples are from 101 Linq Samples
If you need to sort Lists (not ILists) of different classes without the need to create a seperate comparer class for all of them and still keep your entity classes clean (you don't want to implement IComparable), you can use the following (compatible with .NET 2.0):
public class DynamicComparer<T> : IComparer<T>
{
private Func<T, int> calculateFunc;
private int calculateMultiplier;
private Func<T, T, int> compareFunc;
public DynamicComparer(Func<T, int> calculateFunc, bool reverse = false)
{
if (calculateFunc == null)
{
throw new Exception("Delegate function 'calculateFunc' cannot be null.");
}
this.calculateFunc = calculateFunc;
this.calculateMultiplier = reverse ? -1 : 1;
this.compareFunc = null;
}
public DynamicComparer(Func<T, T, int> compareFunc)
{
if (calculateFunc == null)
{
throw new Exception("Delegate function 'compareFunc' cannot be null.");
}
this.calculateFunc = null;
this.compareFunc = compareFunc;
}
public int Compare(T x, T y)
{
if (calculateFunc != null)
{
return (calculateFunc(x) - calculateFunc(y)) * this.calculateMultiplier;
}
if (compareFunc != null)
{
return compareFunc(x, y);
}
throw new Exception("Compare not possible because neither a Compare or a Calculate function was specified.");
}
}
You'll also need the Func delegates if you're using .NET 2.0 (found on Replacing Func with delegates C#):
public delegate TResult Func<T, TResult>(T t);
public delegate TResult Func<T, U, TResult>(T t, U u);
Usage:
myList.Sort(new DynamicComparer<MyClass>(x => x.MyIntProperty) // Ascending
myList.Sort(new DynamicComparer<MyClass>(x => x.MyIntProperty, true) // Descending
Some simple unit testing:
[TestClass()]
public class DynamicComparerTU
{
[TestMethod()]
public void SortIntList()
{
// Arrange
dynamic myIntArray = new int[] {
4,
1,
9,
0,
4,
7
};
dynamic myIntList = new List<int>(myIntArray);
// Act
int temp = 0;
for (int write = 0; write <= myIntArray.Length - 1; write++)
{
for (int sort = 0; sort <= myIntArray.Length - 2; sort++)
{
if (myIntArray(sort) > myIntArray(sort + 1))
{
temp = myIntArray(sort + 1);
myIntArray(sort + 1) = myIntArray(sort);
myIntArray(sort) = temp;
}
}
}
myIntList.Sort(new DynamicComparer<int>(x => x));
// Assert
Assert.IsNotNull(myIntList);
Assert.AreEqual(myIntArray.Length, myIntList.Count);
for (int i = 0; i <= myIntArray.Length - 1; i++)
{
Assert.AreEqual(myIntArray(i), myIntList(i));
}
}
[TestMethod()]
public void SortStringListByLength()
{
// Arrange
dynamic myStringArray = new string[] {
"abcd",
"ab",
"abcde",
"a",
"abc"
};
dynamic myStringList = new List<string>(myStringArray);
// Act
myStringList.Sort(new DynamicComparer<string>(x => x.Length));
// Assert
Assert.IsNotNull(myStringList);
Assert.AreEqual(5, myStringList.Count);
Assert.AreEqual("a", myStringList(0));
Assert.AreEqual("ab", myStringList(1));
Assert.AreEqual("abc", myStringList(2));
Assert.AreEqual("abcd", myStringList(3));
Assert.AreEqual("abcde", myStringList(4));
}
[TestMethod()]
public void SortStringListByLengthDescending()
{
// Arrange
dynamic myStringArray = new string[] {
"abcd",
"ab",
"abcde",
"a",
"abc"
};
dynamic myStringList = new List<string>(myStringArray);
// Act
myStringList.Sort(new DynamicComparer<string>(x => x.Length, true));
// Assert
Assert.IsNotNull(myStringList);
Assert.AreEqual(5, myStringList.Count);
Assert.AreEqual("abcde", myStringList(0));
Assert.AreEqual("abcd", myStringList(1));
Assert.AreEqual("abc", myStringList(2));
Assert.AreEqual("ab", myStringList(3));
Assert.AreEqual("a", myStringList(4));
}
}
