C# Generics: Collection Interfaces
Pages: 1, 2, 3, 4, 5, 6, 7
Constraints
There are times when you must ensure
that the elements you add to a generic list meet certain constraints
(e.g., they derive from a given base class, or they implement a
specific interface). In the next example, we implement a simplified
singly linked, sortable list. The list consists of
Nodes, and each Node must be
guaranteed that the types added to it implement
IComparer. You do so with the following statement:
public class Node<T> :
IComparable<Node<T>> where T : IComparable<T>This defines a generic Node that holds a type,
T. Node of T
implements the IComparable<T> interface,
which means that two Nodes of T
can be compared. The Node class is constrained
(whereT:IComparable<T>) to hold only types that
implement the IComparable interface. Thus, you may
substitute any type for T so long as that type
implements IComparable.
Example 9-12 illustrates the complete implementation, with analysis to follow.
Example 9-12. Using constraints
using System;
using System.Collections.Generic;
namespace UsingConstraints
{
public class Employee : IComparable<Employee>
{
private string name;
public Employee(string name)
{
this.name = name;
}
public override string ToString( )
{
return this.name;
}
// implement the interface
public int CompareTo(Employee rhs)
{
return this.name.CompareTo(rhs.name);
}
public bool Equals(Employee rhs)
{
return this.name == rhs.name;
}
}
// node must implement IComparable of Node of T.
// constrain Nodes to only take items that implement Icomparable
// by using the where keyword.
public class Node<T> :
IComparable<Node<T>> where T : IComparable<T>
{
// member fields
private T data;
private Node<T> next = null;
private Node<T> prev = null;
// constructor
public Node(T data)
{
this.data = data;
}
// properties
public T Data { get { return this.data; } }
public Node<T> Next
{
get { return this.next; }
}
public int CompareTo(Node<T> rhs)
{
// this works because of the constraint
return data.CompareTo(rhs.data);
}
public bool Equals(Node<T> rhs)
{
return this.data.Equals(rhs.data);
}
// methods
public Node<T> Add(Node<T> newNode)
{
if (this.CompareTo(newNode) > 0) // goes before me
{
newNode.next = this; // new node points to me
// if I have a previous, set it to point to
// the new node as its next
if (this.prev != null)
{
this.prev.next = newNode;
newNode.prev = this.prev;
}
// set prev in current node to point to new node
this.prev = newNode;
// return the newNode in case it is the new head
return newNode;
}
else // goes after me
{
// if I have a next, pass the new node along for
// comparison
if (this.next != null)
{
this.next.Add(newNode);
}
// I don't have a next so set the new node
// to be my next and set its prev to point to me.
else
{
this.next = newNode;
newNode.prev = this;
}
return this;
}
}
public override string ToString( )
{
string output = data.ToString( );
if (next != null)
{
output += ", " + next.ToString( );
}
return output;
}
} // end class
public class LinkedList<T> where T : IComparable<T>
{
// member fields
private Node<T> headNode = null;
// properties
// indexer
public T this[int index]
{
get
{
int ctr = 0;
Node<T> node = headNode;
while (node != null && ctr <= index)
{
if (ctr == index)
{
return node.Data;
}
else
{
node = node.Next;
}
++ctr;
} // end while
throw new ArgumentOutOfRangeException( );
} // end get
} // end indexer
// constructor
public LinkedList( )
{
}
// methods
public void Add(T data)
{
if (headNode == null)
{
headNode = new Node<T>(data);
}
else
{
headNode = headNode.Add(new Node<T>(data));
}
}
public override string ToString( )
{
if (this.headNode != null)
{
return this.headNode.ToString( );
}
else
{
return string.Empty;
}
}
}
// Test engine
class Test
{
// entry point
static void Main(string[] args)
{
// make an instance, run the method
Test t = new Test( );
t.Run( );
}
public void Run( )
{
LinkedList<int> myLinkedList = new LinkedList<int>( );
Random rand = new Random( );
Console.Write("Adding: ");
for (int i = 0; i < 10; i++)
{
int nextInt = rand.Next(10);
Console.Write("{0} ", nextInt);
myLinkedList.Add(nextInt);
}
LinkedList<Employee> employees = new LinkedList<Employee>( );
employees.Add(new Employee("John"));
employees.Add(new Employee("Paul"));
employees.Add(new Employee("George"));
employees.Add(new Employee("Ringo"));
Console.WriteLine("\nRetrieving collections...");
Console.WriteLine("Integers: " + myLinkedList);
Console.WriteLine("Employees: " + employees);
}
}
}In this example, you begin by declaring a class that can be placed into the linked list:
public class Employee : IComparable<Employee>This declaration indicates that Employee objects
are comparable, and we see that the Employee class
implements the required methods
(CompareTo and Equals). Note
that these methods are type-safe (they know that the parameter passed
to them will be of type Employee). The
LinkedList itself is declared to hold only types
that implement IComparable:
public class LinkedList<T> where T : IComparable<T>so you are guaranteed to be able to sort the list. The
LinkedList holds an object of type
Node. Node also implements
IComparable and requires that the objects it holds
as data themselves implement IComparable:
public class Node<T> :
IComparable<Node<T>> where T : IComparable<T>These constraints make it safe and simple to implement the
CompareTo method of Node
because the Node knows it will be comparing other
Nodes whose data is comparable:
public int CompareTo(Node<T> rhs)
{
// this works because of the constraint
return data.CompareTo(rhs.data);
}Notice that we don't have to test
rhs to see if it implements
IComparable; we've already
constrained Node to hold only data that implements
IComparable.
