Section 1.3. Implement the Collection Interfaces | Visual C# 2005: A Developers Notebook

1.3. Implement the Collection Interfaces

In addition to its generic collection classes, .NET 2.0 also provides a set of generic interfaces that enable you to create type-safe collections that have all the functionality of the earlier, nongeneric .NET 1.x collection types. You'll find these interfaces in the System.Collections.Generic namespace. The namespace also includes a number of related generic interfaces, such as IComparable<T>, which you can use to compare two objects of type T regardless of whether they are part of a collection.

You can create a sorted linked list by having each datatype stored in the list implement the IComparable<T> interface and by having your Node object be responsible for inserting each new Node at the correct (sorted) position in the linked list.

1.3.1. How do I do that?

Integer already implements IComparable; you can easily modify Pilgrim to do so as well. Modify the definition of the Pilgrim class to indicate that it implements the IComparable<T> interface:

public class Pilgrim : IComparable<Pilgrim>

Be sure to implement the CompareTo and the Equals methods that the interface requires. The objects these methods receive will be of type Pilgrim because this is a type-safe interface, not a "standard" interface that would pass in objects:

public int CompareTo(Pilgrim rhs) public bool Equals(Pilgrim rhs)

All you need to do now is change the logic of adding a node. This time, instead of adding to the end of the list, you'll insert the new node into the list where it belongs based on the implementation of the CompareTo method.

Note: You can constrain the datatypes your generic type accepts by using constraints.

For this to work, you must ensure that the datatype held in the node implements IComparable. You accomplish this with a constraint using the keyword where:

public class Node<T> : IComparable<Node<T>> where T:IComparable<T>

This line of code declares a class Node of T that implements IComparable (of Node of T) and that is constrained to hold datatypes that implement IComparable. If you try to have your Node class hold an object that does not implement IComparable, you will receive an error message when you attempt to compile it.

You must be careful to return the new head of the list if the new node is "less than" the current head of the list, as shown in Example 1-3 (Changes from the previous example are highlighted.)

Example 1-3. Implementing generic interfaces

using System; using System.Collections.Generic;     namespace ImplementingGenericInterfaces {    public class Pilgrim : IComparable<Pilgrim>    {       private string name;       public Pilgrim(string name)       {          this.name = name;       }       public override string ToString( )       {          return this.name;       }           // implement the interface       public int CompareTo(Pilgrim rhs)       {          return this.name.CompareTo(rhs.name);       }       public bool Equals(Pilgrim 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 SortedLinkedList<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 SortedLinkedList( )       {       }           // 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;          }       }    }        class Program    {       // entry point       static void Main(string[  ] args)       {          SortedLinkedList<int> mySortedLinkedList = new SortedLinkedList<int>( );          Random rand = new Random( );          Console.Write("Adding: ");          for (int i = 0; i < 10; i++)          {             int nextInt = rand.Next(10);             Console.Write("{0}  ", nextInt);             mySortedLinkedList.Add(nextInt);          }              SortedLinkedList<Pilgrim> pilgrims = new SortedLinkedList<Pilgrim>( );          pilgrims.Add(new Pilgrim("The Knight"));          pilgrims.Add(new Pilgrim("The Miller"));          pilgrims.Add(new Pilgrim("The Reeve"));          pilgrims.Add(new Pilgrim("The Cook"));          pilgrims.Add(new Pilgrim("The Man of Law"));          Console.WriteLine("\nRetrieving collections...");          DisplayList<int>("Integers", mySortedLinkedList);          DisplayList<Pilgrim>("Pilgrims", pilgrims);          //Console.WriteLine("Integers: " + mySortedLinkedList);          //Console.WriteLine("Pilgrims: " + pilgrims);          Console.WriteLine("The fourth integer is " + mySortedLinkedList[3]);          Pilgrim d = pilgrims[2];          Console.WriteLine("The third pilgrim is " + d); //         foreach (Pilgrim p in pilgrims) //         { //            Console.WriteLine("The pilgrim's name is " + p.ToString( )); //         }       }   // end main       private static void DisplayList<T>(string intro, SortedLinkedList<T> theList)          where T : IComparable<T>       {          Console.WriteLine(intro + ": " + theList);       }    }   // end class }      // end namespace

Output:

Adding: 2  8  2  5  1  7  2  8  5  5   Retrieving collections... Integers: 1, 2, 2, 5, 7, 8, 8 Pilgrims: The Cook, The Knight, The Man of Law, The Miller, The Reeve The fourth integer is 5 The third pilgrim is The Man of Law

1.3.2. What just happened?

The Pilgrim class changed just enough to implement the generic IComparable interface. The linked list didn't change at all, but the Node class did undergo some changes to support the sorted list.

First, the Node class was marked to implement IComparable and was constrained to hold only objects that themselves implement IComparable:

public class Node<T> : IComparable<Node<T>> where T:IComparable<T>

Second, Node added a reference to the previous node, in addition to the next node (making this a doubly linked list):

private Node<T> next = null; private Node<T> prev = null;

The Node class must implement CompareTo and Equals. These are simple to implement because the constraint ensures that the data you are comparing also implements IComparable:

public int CompareTo(Node<T> rhs) {    // this works because of the constraint    data.CompareTo(rhs.data);  }

1.3.3. What about . . .

...the IComparable requirement? Why did Pilgrim and Node require IComparable, but the linked list did not?

To understand this, it's important to note that both Pilgrims and Nodes must be compared; linked lists are not compared. Because the linked list is sorted by sorting its nodes, there is no need to compare two linked lists to see which one is "greater" than the other.

...what about passing generic types to a method; can I do that?

Yes, you can pass a generic type to a method, but only if the method is generic. In Example 1-3, you display the contents of the list of integers and the list of pilgrims with the following code:

Console.WriteLine("Integers: " + myLinkedList); Console.WriteLine("Pilgrims: " + pilgrims);

You are free to create a method to take these lists and display them (or manipulate them):

private void DisplayList<T>(string intro, LinkedList<T> theList) where T : IComparable<T> {    Console.WriteLine(intro + ": " + theList); }

When you call the method, you supply the type:

DisplayList<int>("Integers", myLinkedList); DisplayList<Pilgrim>("Pilgrims", pilgrims);

Tip: The compiler is capable of type inference, so you can rewrite the preceding two lines as follows:

DisplayList("Integers", myLinkedList); DisplayList("Pilgrims", pilgrims);

1.3.4. Where can I learn more?

The MSDN Library covers the Generic namespace extensively. Search on Systems.Collections.Generic. Also, see my article on generics on O'Reilly's ONDotnet.com site at http://www.ondotnet.com/pub/a/dotnet/2004/05/17/liberty.html.