New Features in C# 2.0—Collection Interfaces: How do I do that?

Microsoft .NET Framework, ASP.NET, Visual C# (CSharp, C Sharp, C-Sharp) Developer Training, Visual Studio

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.

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.

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