Tuesday, June 24, 2008

Controlling your sorts under List<T> - the old fashioned sort

NOTE: This article uses C# 3.0 syntax (VS 2008) if you would like to learn more about it's syntax please see here.

Why would I post something about List<>.Sort() I hear you ask, because isn't everyone using LINQ yet? Well for those who have legacy code in Comparer classes who do not wish to use LINQ, and besides everyone is blogging about LINQ right? :) Also as this post is device centric, both LINQ to SQL and LINQ to Entities are not supported on CF 3.5 so we have few options.

Which brings me to sorting a generic arraylist class. You can use Array.Sort(T) which uses the quicksort algorithm.

Usually you have to write a comparer class for each sort type. For example, if you wanted to sort a collection of customers by country, you would normally have a comparer class named something like CustomersCountryComparer. Or if you wanted to sort by city for example; you'd have a comparer named something like CustomersCityComparer. In the *old days*, I emphasize old days as they are not really old days but pre .NET 2.0 and generics the way we would write a comparer was slightly different to how we write them today. We historically would derive from CollectionBase and implement a sort method which would provide the sort operations with a sort direction ASC or DESC, easy.

But now we're all using generics, right! or should be at least for many reasons. Generic collections offer many benefits one of which is we no longer have to write an implementation of CollectionBase to hold our objects. Instead today we use List<> (generic ArrayList). Which exposes a sort method.

Here is the list of sort overloads as of .NET 3.5:

Name Description
Sort()()() Sorts the elements in the entire List<(Of <(T>)>) using the default comparer.
Sort(Comparison<(Of <(T>)>)) Sorts the elements in the entire List<(Of <(T>)>) using the specified System..::.Comparison<(Of <(T>)>).
Sort(IComparer<(Of <(T>)>)) Sorts the elements in the entire List<(Of <(T>)>) using the specified comparer.
Sort(Int32, Int32, IComparer<(Of <(T>)>)) Sorts the elements in a range of elements in List<(Of <(T>)>) using the specified comparer.

This is all fine and dandy, but often requirements state that they want to sort ascending or descending. How do you do this with the overloads defined above? You can't, the information has to be passed to the comparer, so when the List invokes Sort, comparer tells it which direction to sort to.

This post will show an example on how to achieve this.

The following code example shows a typical object which might be returned in a generic collection:
public class CustomerInfo
{
public int CustomerId
{
get;
set;
}

public string Name
{
get;
set;
}

public string AddressLine1
{
get;
set;
}

public string AddressLine2
{
get;
set;
}

public string AddressLine3
{
get;
set;
}

public string City
{
get;
set;
}

public string County
{
get;
set;
}

public string PostalCode
{
get;
set;
}

public string Country
{
get;
set;
}
}
Note the above is C# 3.0 syntax. Nothing too complex here. Suppose we now have a collection of Customers defined in a List:
List<CustomerInfo> customers;
This list could have been returned from a data layer in Country order ascending. But what if the user now wants to see the list of customers in City order descending. Do you go back to the SQL Server and get a new collection of objects based on the new query or do you manipulate the current set of data and display this to your user? The fastest way would always be to manipulate the data you already have rather than go back to the database. So this is where the Comparer class comes into the equation.

Before using our own comparer that we will pass to the Sort method of the List<> class, what happens if we call the default Sort method without passing over a IComparable instance?

We get an error whats what, we get a "Failed to compare two elements in the array." InvalidOperationException:

The code I used is as follows:

List<CustomerInfo> customers = new List<CustomerInfo>
{
new CustomerInfo
{CustomerId = 1, Name = "Joe", City = "London"},
new CustomerInfo
{CustomerId = 2, Name = "Pete", City = "Paris"},
new CustomerInfo
{CustomerId = 3, Name = "John", City = "New York"},
new CustomerInfo
{CustomerId = 4, Name = "Pete", City = "London"},
new CustomerInfo
{CustomerId = 5, Name = "Paul", City = "Dublin"},
new CustomerInfo
{CustomerId = 6, Name = "Steve", City = "Exeter"},
new CustomerInfo
{CustomerId = 7, Name = "Clare", City = "Norwich"}
};

customers.Sort();
Why didn't it work? It didn't work because CustomerInfo does not implement the IComparable interface. Instead we use a cleaner solution to implementing a IComparable for the colums of interest.

So what we'll do next is write a simple comparer class which we will feed into the arraylist class sort method. The interface that we'll need to implement is the IComparer.

The class looks like the following:public class CustomerCityComparer : IComparer
public class CustomerCityComparer : IComparer
{
private SortBy sortBy;



public CustomerCityComparer(SortBy sortBy)
{
sortBy = sortBy;
}


///
/// Returns one of the following:-
///
/// 1. Less than zero (x is less than y).
/// 2. Zero (x is equal to y).
/// 3. Greater than zero (x is greater than y).
///

public int Compare(CustomerInfo customer1, CustomerInfo customer2)
{
if (sortBy == SortBy.Ascending)
{
return customer1.City.CompareTo(customer2.City);
}
else
{
return customer2.City.CompareTo(customer1.City);
}
}


public SortBy SortBy
{
get
{
return sortBy;
}
set
{
sortBy = value;
}
}
}
Fairly trivial code. We use the CompareTo method because we are comparing string objects and not integers. Notice we have defined a constructor with a passing enum value type named SortBy. This forces the consumer to pass a sort type rather than defaulting to one.

Also note we have created a read/write property named SortBy which allows the consumer to change the sort direction of the comparer without creating a new instance of the object.

I've written a simple bit of code that creates a collection of customers and sorts acending and decending based on the City the customer is based.

This code looks like the following:
internal class Program
{
private static void Main(string[] args)
{
List customers = new List
{
new CustomerInfo
{CustomerId = 1, Name = "Joe", City = "London"},
new CustomerInfo
{CustomerId = 2, Name = "Pete", City = "Paris"},
new CustomerInfo
{CustomerId = 3, Name = "John", City = "New York"},
new CustomerInfo
{CustomerId = 4, Name = "Pete", City = "London"},
new CustomerInfo
{CustomerId = 5, Name = "Paul", City = "Dublin"},
new CustomerInfo
{CustomerId = 6, Name = "Steve", City = "Exeter"},
new CustomerInfo
{CustomerId = 7, Name = "Clare", City = "Norwich"}
};


Console.WriteLine("Before sort");
DisplayCollection(customers);

Console.WriteLine();

CustomerCityComparer cityComparer = new
CustomerCityComparer(SortBy.Ascending);
customers.Sort(cityComparer);

Console.WriteLine("After sort - Ascending");
DisplayCollection(customers);

Console.WriteLine();
cityComparer.SortBy = SortBy.Descending;
customers.Sort(cityComparer);
Console.WriteLine("After sort - Descending");
DisplayCollection(customers);

Console.ReadLine();
}

public static void DisplayCollection(List customers)
{
foreach (CustomerInfo customer in customers)
{
Console.WriteLine(string.Format("Name: {0}, City: {1}",
customer.Name, customer.City));
}

}
The output from the code above looks like the following:
Before sort
Name: Joe, City: London
Name: Pete, City: Paris
Name: John, City: New York
Name: Pete, City: London
Name: Paul, City: Dublin
Name: Steve, City: Exeter
Name: Clare, City: Norwich
After sort - Ascending
Name: Paul, City: Dublin
Name: Steve, City: Exeter
Name: Pete, City: London
Name: Joe, City: London
Name: John, City: New York
Name: Clare, City: Norwich
Name: Pete, City: Paris
After sort - Descending
Name: Pete, City: Paris
Name: Clare, City: Norwich
Name: John, City: New York
Name: Joe, City: London
Name: Pete, City: London
Name: Steve, City: Exeter
Name: Paul, City: Dublin
If we wanted to sort on different fields then we would create another custom comparer.

Of course LINQ to Entities makes this much easier. I will write a simple example on implementing this using LINQ in my next article. - Please note though, LINQ to entities are not supported on devices.

No comments: