The .NET Framework collection classes provide some useful support for sorting and searching, with built-in functions that do sorting and binary searching. The Array class provides the same functionality, but as static functions rather than as member functions.
Sorting an array of integers is as easy as this:
using System; class Test {
public static void Main()
{
int[] arr = {5, 1, 10, 33, 100, 4};
Array.Sort(arr); foreach (int v in arr)
Console.WriteLine(“Element: {0}”, v);
}
}
The preceding code gives the following output:
4
5
10
33
100
This is convenient for the built-in types, but it doesn’t work for classes or structs because the sort routine doesn’t know how to order them.
1. Implementing IComparable
The .NET Framework has some nice ways for a class or struct to specify how to order instances of the class or struct. In the simplest one, the object implements the IComparable interface:
using System;
public class Employee: IComparable {
public Employee(string name, int id)
{
this.name = name;
this.id = id;
}
int IComparable.CompareTo(object obj)
{
Employee emp2 = (Employee) obj;
if (this.id > emp2.id) return(1);
if (this.id < emp2.id)
return(-1);
else
return(0);
}
public override string ToString()
{
return(String.Format(“{0}:{1}”, name, id));
}
string name;
int id;
}
class Test {
public static void Main()
{
Employee[] arr = new Employee[4];
arr[0] = new Employee(“George”, 1);
arr[1] = new Employee(“Fred”, 2);
arr[2] = new Employee(“Tom”, 4);
arr[3] = new Employee(“Bob”, 3);
Array.Sort(arr);
foreach (Employee emp in arr)
Console.WriteLine(“Employee: {0}”, emp);
// Find employee id 2 in the list;
Employee employeeToFind = new Employee(null, 2);
int index = Array.BinarySearch(arr, employeeToFind);
if (index != -1)
Console.WriteLine(“Found: {0}”, arr[index]);
}
}
This program gives you the following output:
Employee: George:1
Employee: Fred:2
Employee: Bob:3
Employee: Tom:4
Found: Fred:2
This sort implementation allows only one sort ordering; you could define the class to sort based on employee ID or based on name, but you have no way to allow the user to choose which sort order they prefer.
This example also uses the BinarySearch() method to find an employee in the list. For this to work, the array (or ArrayList) must be sorted, or the results won’t be correct.
2. Using IComparer
The designers of the .NET Framework have provided the capability to define multiple sort orders. Each sort order is expressed through the IComparer interface, and the appropriate interface is passed to the sort or search function.
The IComparer interface can’t be implemented on Employee, however, because each class can implement an interface only once, which would allow only a single sort order. You need a separate class for each sort order, with the class implementing IComparer. The class will be simple, since all it will do is implement the Compare() function:
using System;
using System.Collections;
class Employee
{
public string name;
}
class SortByNameClass: IComparer {
public int Compare(object obj1, object obj2)
{
Employee emp1 = (Employee) obj1;
Employee emp2 = (Employee) obj2;
return(String.Compare(emp1.name, emp2.name));
}
}
The Compare() member takes two objects as parameters. Since the class should be used for sorting employees only, the object parameters are cast to Employee. The Compare() function built into string is then used for the comparison.
Revise the Employee class as follows. Place the sort-ordering classes inside the Employee class as nested classes.
using System;
using System.Collections;
public class Employee: IComparable
{
public Employee(string name, int id)
{
this.name = name;
this.id = id;
}
int IComparable.CompareTo(object obj)
{
Employee emp2 = (Employee) obj;
if (this.id > emp2.id) return(1);
if (this.id < emp2.id)
return(-1);
else
return(0);
}
public override string ToString()
{
return(name + “:” + id);
}
public class SortByNameClass: IComparer {
public int Compare(object objl, object obj2)
{
Employee empl = (Employee) objl;
Employee emp2 = (Employee) obj2;
return(String.Compare(emp1.name, emp2.name));
}
}
public class SortByIdClass: IComparer {
public int Compare(object obj1, object obj2)
{
Employee emp1 = (Employee) obj1;
Employee emp2 = (Employee) obj2;
return(((IComparable) emp1).CompareTo(obj2));
}
}
string name; int id;
}
class Test {
public static void Main()
{
Employee[] arr = new Employee[4];
arr[0] = new Employee(“George”, 1);
arr[1] = new Employee(“Fred”, 2);
arr[2] = new Employee(“Tom”, 4);
arr[3] = new Employee(“Bob”, 3);
Array.Sort(arr, (IComparer) new Employee.SortByNameClass());
// employees is now sorted by name
foreach (Employee emp in arr)
Console.WriteLine(“Employee: {0}”, emp);
Array.Sort(arr, (IComparer) new Employee.SortByIdClass());
// employees is now sorted by id
foreach (Employee emp in arr)
Console.WriteLine(“Employee: {0}”, emp);
ArrayList arrList = new ArrayList();
arrList.Add(arr[0]);
arrList.Add(arr[1]);
arrList.Add(arr[2]);
arrList.Add(arr[3]);
arrList.Sort((IComparer) new Employee.SortByNameClass());
foreach (Employee emp in arrList)
Console.WriteLine(“Employee: {0}”, emp);
arrList.Sort(); // default is by id
foreach (Employee emp in arrList)
Console.WriteLine(“Employee: {0}”, emp);
}
}
The user can now specify the sort order and switch between the different sort orders as desired. This example shows how the same functions work using the ArrayList class, though Sort() is a member function rather than a static function.
3. IComparer As a Property
Sorting with the Employee class is still a bit cumbersome since the user has to create an instance of the appropriate ordering class and then cast it to IComparer. You can simplify this a bit further by using static properties to do this for the user:
using System;
using System.Collections;
public class Employee: IComparable {
public Employee(string name, int id)
{
this.name = name;
this.id = id;
}
int IComparable.CompareTo(object obj)
{
Employee emp2 = (Employee) obj;
if (this.id > emp2.id) return(1);
if (this.id < emp2.id)
return(-1);
else
return(o);
}
public static IComparer SortByName {
get
{
return((IComparer) new SortByNameClass());
}
}
public static IComparer SortById
{
get
{
return((IComparer) new SortByIdClass());
}
}
public override string ToString()
{
return(name + “:” + id);
}
class SortByNameClass: IComparer {
public int Compare(object obj1, object obj2)
{
Employee emp1 = (Employee) obj1;
Employee emp2 = (Employee) obj2;
return(String.Compare(emp1.name, emp2.name));
}
}
class SortByIdClass: IComparer {
public int Compare(object obj1, object obj2)
{
Employee emp1 = (Employee) obj1;
Employee emp2 = (Employee) obj2;
}
}
string name;
int id;
}
class Test {
public static void Main()
{
Employee[] arr = new Employee[4];
arr[0] = new Employee(“George”, 1);
arr[1] = new Employee(“Fred”, 2);
arr[2] = new Employee(“Tom”, 4);
arr[3] = new Employee(“Bob”, 3);
Array.Sort(arr, Employee.SortByName);
// employees is now sorted by name
foreach (Employee emp in arr)
Console.WriteLine(“Employee: {0}”, emp);
Array.Sort(arr, Employee.SortById);
// employees is now sorted by id
foreach (Employee emp in arr)
Console.WriteLine(“Employee: {0}”, emp);
ArrayList arrList = new ArrayList();
arrList.Add(arr[0]);
arrList.Add(arr[1]);
arrList.Add(arr[2]);
arrList.Add(arr[3]);
arrList.Sort(Employee.SortByName);
foreach (Employee emp in arrList)
Console.WriteLine(“Employee: {0}”, emp);
arrList.Sort(); // default is by id
foreach (Employee emp in arrList)
Console.WriteLine(“Employee: {0}”, emp);
}
}
The static properties SortByName and SortById create an instance of the appropriate sorting class, cast it to IComparer, and return it to the user. This simplifies the user model quite a bit; the SortByName and SortById properties return an IComparer, so it’s obvious they can be used for sorting, and all the user has to do is specify the appropriate ordering property for the IComparer parameter.
4. Overloading Relational Operators
If a class has an ordering that’s expressed in IComparable, it may also make sense to overload the other relational operators. As with == and !=, other operators must be declared as pairs, with < and > being one pair and >= and <= being the other pair. For example:
using System;
public class Employee: IComparable {
public Employee(string name, int id)
{
this.name = name;
this.id = id;
}
int IComparable.CompareTo(object obj)
{
Employee emp2 = (Employee) obj;
if (this.id > emp2.id) return(1);
if (this.id < emp2.id)
return(-1);
else
return(0);
}
public static bool operator <(
Employee emp1,
Employee emp2)
{
IComparable icomp = (IComparable) emp1;
return(icomp.CompareTo (emp2) < 0);
}
public static bool operator >(
Employee emp1,
Employee emp2)
{
IComparable icomp = (IComparable) emp1;
return(icomp.CompareTo (emp2) > 0);
}
public static bool operator <=(
Employee emp1,
Employee emp2)
{
IComparable icomp = (IComparable) emp1;
return(icomp.CompareTo (emp2) <= 0);
}
public static bool operator >=(
Employee emp1,
Employee emp2)
{
IComparable icomp = (IComparable) emp1;
return(icomp.CompareTo (emp2) >= 0);
}
public override string ToString()
{
return(name + “:” + id);
}
string name;
int id;
}
class Test {
public static void Main()
{
Employee george = new Employee(“George”, 1);
Employee fred = new Employee(“Fred”, 2);
Employee tom = new Employee(“Tom”, 4);
Employee bob = new Employee(“Bob”, 3);
Console.WriteLine(“George < Fred: {0}”, george < fred);
Console.WriteLine(“Tom >= Bob: {0}”, tom >= bob);
// Find employee id 2 in the list;
Employee employeeToFind = new Employee(null, 2);
int index = Array.BinarySearch(arr, employeeToFind);
if (index != -1)
Console.WriteLine(“Found: {0}”, arr[index]);
}
}
This example produces the following output:
George < Fred: true
Tom >= Bob: true
5. Generic Comparison
One of the major use cases for generics is collection classes, so it comes as no surprise that the interfaces that have relevance to collections such as IComparable and IComparer have been augmented with a generic version. The nongeneric versions described earlier in this chapter continue to exist, and the new interfaces are in a new namespace called System.Collections.Generic. In addition to strongly typed comparison methods, the new generic interfaces are slightly richer than their nongeneric equivalents, with IComparable<T> having a strongly typed Equals method and IComparer<T> having strongly typed Equals and GetHashCode methods.
Rewriting the first example in this chapter using the generic IComparable<T >, you get the following:
using System;
using System.Collections.Generic;
public class Employee : IComparable<Employee>
{
public Employee(string name, int id)
{
this.name = name;
this.id = id;
}
int IComparable<Employee>.CompareTo(Employee emp2)
{
if (this.id > emp2.id) return (1);
if (this.id < emp2.id)
return (-1);
else
return (0);
}
bool IComparable<Employee>.Equals(Employee emp2)
{
if (emp2 == null)
return false;
return id == emp2.id && name == emp2.name;
}
public override string ToString()
{
return (String.Format(“{0}:{1}”, name, id));
}
string name;
int id;
}
class Test {
public static void Main()
{
Employee[] arr = new Employee[4];
arr[0] = new Employee(“George”, 1);
arr[1] = new Employee(“Fred”, 2);
arr[2] = new Employee(“Tom”, 4);
arr[3] = new Employee(“Bob”, 3);
Array.Sort(arr);
foreach (Employee emp in arr) Console.WriteLine(“Employee: {0}”, emp);
// Find employee id 2 in the list;
Employee employeeToFind = new Employee(null, 2);
int index = Array.BinarySearch(arr, employeeToFind);
if (index != -1)
Console.WriteLine(“Found: {0}”, arr[index]);
}
}
As expected, the output is the same as the nongeneric version, and only the type-safety and speed of the code have been improved. You can also update the second example that used IComparer to use generics instead:
using System;
using System.Collections.Generic;
public class Employee : IComparable<Employee>
{
public Employee(string name, int id)
{
this.name = name;
this.id = id;
}
int IComparable<Employee>.CompareTo(Employee emp2)
{
if (this.id > emp2.id) return (1);
if (this.id < emp2.id)
return (-1);
else
return (0);
}
bool IComparable<Employee>.Equals(Employee emp2)
{
if (emp2 == null) return
false;
return id == emp2.id && name == emp2.name;
}
public override string ToString()
{
return (name + “:” + id);
}
public class SortByNameClass : IComparer<Employee>
{
public int Compare(Employee emp1, Employee emp2)
{
return (String.Compare(emp1.name, emp2.name));
}
public bool Equals(Employee emp1, Employee emp2)
{
return Compare(emp1, emp2) == 0;
}
public int GetHashCode(Employee emp)
{
return emp.name.GetHashCode();
}
}
public class SortByIdClass : IComparer<Employee>
{
public int Compare(Employee emp1, Employee emp2)
{
return (((IComparable<Employee>)emp1).CompareTo(emp2));
}
public bool Equals(Employee emp1, Employee emp2)
{
return Compare(emp1, emp2) == 0;
}
public int GetHashCode(Employee emp)
{
return emp.id.GetHashCode();
}
}
string name;
int id;
}
class Test2 {
public static void Main()
{
Employee[] arr = new Employee[4];
arr[0] = new Employee(“George”, 1);
arr[1] = new Employee(“Fred”, 2);
arr[2] = new Employee(“Tom”, 4);
arr[3] = new Employee(“Bob”, 3);
Array.Sort<Employee>(arr, (IComparer<Employee>)
new Employee.SortByNameClass());
// employees is now sorted by name
foreach (Employee emp in arr)
Console.WriteLine(“Employee: {0}”, emp);
Array.Sort<Employee>(arr, (IComparer<Employee>)
new Employee.SortByIdClass());
// employees is now sorted by id
foreach (Employee emp in arr)
Console.WriteLine(“Employee: {0}”, emp);
List<Employee> list = new List<Employee>();
list.Add(arr[0]);
list.Add(arr[1]);
list.Add(arr[2]);
list.Add(arr[3]);
list.Sort((IComparer<Employee>)new Employee.SortByNameClass());
foreach (Employee emp in list)
Console.WriteLine(“Employee: {0}”, emp);
list.Sort(); // default is by id
foreach (Employee emp in list)
Console.WriteLine(“Employee: {0}”, emp);
}
}
Notice the use of the generic List<T> collection instead of ArrayList, which was used in the corresponding example earlier in this chapter. The previous listing also used the generic Sort method of Array.
As with the first generic example, the output is the same as the nongeneric equivalent. We didn’t reprint the “IComparer As a Property” example here in the interest of paper conservation, but it does accompany the book’s code, which is available in the Downloads section of the Apress Web site (http://www.apress.com).
6. Advanced Use of Hashes
In some situations, it may be desirable to define more than one hash code for a specific object. You could use this, for example, to allow an employee to be searched for based on the employee ID or on the employee name. You can do this by implementing the IHashCodeProvider interface to provide an alternate hash function, and it also requires a matching implementation of IComparer. These new implementations are passed to the constructor of the Hashtable, like so:
using System;
using System.Collections;
public class Employee: IComparable {
public Employee(string name, int id)
{
this.name = name;
this.id = id;
}
int IComparable.CompareTo(object obj)
{
Employee emp2 = (Employee) obj;
if (this.id > emp2.id) return(1);
if (this.id < emp2.id)
return(-1);
else
return(0);
}
public override int GetHashCode()
{
return(id);
}
public static IComparer SortByName
{
get
{
return((IComparer) new SortByNameClass());
}
}
public static IComparer SortById {
get
{
return((IComparer) new SortByIdClass());
}
}
public static IHashCodeProvider HashByName {
get
{
return((IHashCodeProvider) new HashByNameClass());
}
public override string ToString()
{
return(name + “:” + id);
}
class SortByNameClass: IComparer {
public int Compare(object obj1, object obj2)
{
Employee emp1 = (Employee) obj1;
Employee emp2 = (Employee) obj2;
return(String.Compare(emp1.name, emp2.name));
}
}
class SortByIdClass: IComparer {
public int Compare(object obj1, object obj2)
{
Employee emp1 = (Employee) obj1;
Employee emp2 = (Employee) obj2;
return(((IComparable) emp1).CompareTo(obj2));
}
}
class HashByNameClass: IHashCodeProvider {
public int GetHashCode(object obj)
{
Employee emp = (Employee) obj;
return(emp.name.GetHashCode());
}
}
string name;
int id;
}
class Test {
public static void Main()
{
Employee herb = new Employee(“Herb”, 555);
Employee george = new Employee(“George”, 123);
Employee frank = new Employee(“Frank”, 111);
Hashtable employees =
new Hashtable(Employee.HashByName, Employee.SortByName);
employees.Add(herb, “414 Evergreen Terrace”);
employees.Add(george, “2335 Elm Street”);
employees.Add(frank, “18 Pine Bluff Road”);
Employee herbClone = new Employee(“Herb”, 000);
string address = (string) employees[herbClone];
Console.WriteLine(“{0} lives at {1}”, herbClone, address);
}
}
You should use this technique sparingly. It’s often simpler to expose a value, such as the employee name as a property, and allow that to be used as a hash key instead.
Source: Gunnerson Eric, Wienholt Nick (2005), A Programmer’s Introduction to C# 2.0, Apress; 3rd edition.