Section 9.5. Constraints

9.5. 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 (where T :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.