To understand generics, it is worth looking in detail at the problem for which they are designed to solve.

Suppose that you needed to model a first-in, first-out structure such as a queue. You could create a class such as the following:

class Queue
{
    private const int DEFAULTQUEUESIZE = 100;
    private int[] data;
    private int head = 0, tail = 0;
    private int numElements = 0;
    public Queue()
    {
        this.data = new int[DEFAULTQUEUESIZE];
    }
    public Queue(int size)
    {
        if (size > 0)
        {
            this.data = new int[size];
        }
        else
        {
            throw new ArgumentOutOfRangeException("size", "Must be greater than zero");
        }
    }
    public void Enqueue(int item)
    {
        if (this.numElements == this.data.Length)
        {
            throw new Exception("Queue full");
        }
        this.data[this.head] = item;
        this.head++;
        this.head %= this.data.Length;
        this.numElements++;
    }
    public int Dequeue()
    {
        if (this.numElements == 0)
        {
            throw new Exception("Queue empty");
        }
        int queueItem = this.data[this.tail];
        this.tail++;
        this.tail %= this.data.Length;
        this.numElements--;
        return queueItem;
    }
}

This class uses an array to provide a circular buffer for holding the data. The size of this array is specified by the constructor. An application uses the Enqueue method to add an item to the queue and the Dequeue method to pull an item off the queue. The private head and tail fields keep track of where to insert an item into the array and where to retrieve an item from the array. The numElements field indicates how many items are in the array. The Enqueue and Dequeue methods use these fields to determine where to store or retrieve an item from and perform some rudimentary error checking. An application can create a Queue object and call these methods, as shown in the code example that follows. Notice that the items are dequeued in the same order in which they are enqueued:

Queue queue = new Queue(); // Create a new Queue
queue.Enqueue(100);
queue.Enqueue(-25);
queue.Enqueue(33);
Console.WriteLine("{0}", queue.Dequeue());  // Displays 100
Console.WriteLine("{0}", queue.Dequeue());  // Displays -25
Console.WriteLine("{0}", queue.Dequeue());  // Displays 33

Now, the Queue class works well for queues of ints, but what if you want to create queues of strings, or floats, or even queues of more complex types such as Circle (see Chapter 7), or Horse, or Whale (see Chapter 12)? The problem is that the way in which the Queue class is implemented restricts it to items of type int, and if you try to enqueue a Horse, you will get a compile-time error.

Queue queue = new Queue();
Horse myHorse = new Horse();
queue.Enqueue(myHorse); // Compile-time error: Cannot convert from Horse to int

One way around this restriction is to specify that the array in the Queue class contains items of type object, update the constructors, and modify the Enqueue and Dequeue methods to take an object parameter and return an object, such as in the following:

class Queue
{
    ...
    private object[] data;
    ...
    public Queue()
    {
        this.data = new object[DEFAULTQUEUESIZE];
    }
    public Queue(int size)
    {
        ...
        this.data = new object[size];
        ...
    }
    public void Enqueue(object item)
    {
        ...
    }
    public object Dequeue()
   {
        ...
        object queueItem = this.data[this.tail];
        ...
        return queueItem;
    }
}

Remember that you can use the object type to refer to a value or variable of any type. All reference types automatically inherit (either directly or indirectly) from the System.Object class in the Microsoft .NET Framework (in C#, object is an alias for System.Object). Now, because the Enqueue and Dequeue methods manipulate objects, you can operate on queues of Circles, Horses, Whales, or any of the other classes that you have seen in earlier exercises in this book. However, it is important to notice that you have to cast the value returned by the Dequeue method to the appropriate type because the compiler will not perform the conversion from the object type automatically.

Queue queue = new Queue();
Horse myHorse = new Horse();
queue.Enqueue(myHorse); // Now legal – Horse is an object
...
Horse dequeuedHorse =(Horse)queue.Dequeue(); // Need to cast object back to a Horse

If you don’t cast the returned value, you will get the compiler error “Cannot implicitly convert type ‘object’ to ‘Horse.’” This requirement to perform an explicit cast degenerates much of the flexibility afforded by the object type. Furthermore, it is very easy to write code such as this:

Queue queue = new Queue();
Horse myHorse = new Horse();
queue.Enqueue(myHorse);
...
Circle myCircle = (Circle)queue.Dequeue(); // run-time error

Although this code will compile, it is not valid and throws a System.InvalidCastException exception at run time. The error is caused by trying to store a reference to a Horse in a Circle variable when it is dequeued, and the two types are not compatible. This error is not spotted until run time because the compiler does not have enough information to perform this check at compile time. The real type of the object being dequeued becomes apparent only when the code runs.

Another disadvantage of using the object approach to create generalized classes and methods is that it can consume additional memory and processor time if the runtime needs to convert an object to a value type and back again. Consider the following piece of code that manipulates a queue of int values:

Queue queue = new Queue();
int myInt = 99;
queue.Enqueue(myInt);         // box the int to an object
...
myInt = (int)queue.Dequeue(); // unbox the object to an int

The Queue data type expects the items it holds to be objects, and object is a reference type. Enqueueing a value type, such as an int, requires it to be boxed to convert it to a reference type. Similarly, dequeueing into an int requires the item to be unboxed to convert it back to a value type. See the sections Boxing and Unboxing in Chapter 8 for more details. Although boxing and unboxing happen transparently, they add performance overhead because they involve dynamic memory allocations. This overhead is small for each item, but it adds up when a program creates queues of large numbers of value types.

C# provides generics to remove the need for casting, improve type safety, reduce the amount of boxing required, and make it easier to create generalized classes and methods. Generic classes and methods accept type parameters, which specify the types of objects on which they operate. In C#, you indicate that a class is a generic class by providing a type parameter in angle brackets, like this:

class Queue<T>
{
    ...
}

The T in this example acts as a placeholder for a real type at compile time. When you write code to instantiate a generic Queue, you provide the type that should be substituted for T (Circle, Horse, int, and so on). When you define the fields and methods in the class, you use this same placeholder to indicate the type of these items, like this:

class Queue<T>
{
    ...
    private T[] data; // array is of type 'T' where 'T' is the type parameter
    ...
    public Queue()
    {
        this.data = new T[DEFAULTQUEUESIZE]; // use 'T' as the data type
    }
    public Queue(int size)
    {
        ...
        this.data = new T[size];
        ...
    }
    public void Enqueue(T item)  // use 'T' as the type of the method parameter
    {
        ...
    }
    public T Dequeue() // use 'T' as the type of the return value
    {
        ...
        T queueItem = this.data[this.tail];  // the data in the array is of type 'T'
        ...
        return queueItem;
    }
}

The type parameter T can be any legal C# identifier, although the lone character T is commonly used. It is replaced with the type you specify when you create a Queue object. The following examples create a Queue of ints, and a Queue of Horses:

Queue<int> intQueue = new Queue<int>();
Queue<Horse> horseQueue = new Queue<Horse>();

Additionally, the compiler now has enough information to perform strict type-checking when you build the application. You no longer need to cast data when you call the Dequeue method, and the compiler can trap any type mismatch errors early:

intQueue.Enqueue(99);
int myInt = intQueue.Dequeue();     // no casting necessary
Horse myHorse = intQueue.Dequeue(); // compiler error:
                                    // cannot implicitly convert type 'int' to 'Horse'

You should be aware that this substitution of T for a specified type is not simply a textual replacement mechanism. Instead, the compiler performs a complete semantic substitution so that you can specify any valid type for T. Here are more examples:

struct Person
{
    ...
}
...
Queue<int> intQueue = new Queue<int>();
Queue<Person> personQueue = new Queue<Person>();

The first example creates a queue of integers, whereas the second example creates a queue of Person values. The compiler also generates the versions of the Enqueue and Dequeue methods for each queue. For the intQueue queue, these methods look like this:

public void Enqueue(int item);
public int Dequeue();

For the personQueue queue, these methods look like this:

public void Enqueue(Person item);
public Person Dequeue();

Contrast these definitions with those of the object-based version of the Queue class shown in the preceding section. In the methods derived from the generic class, the item parameter to Enqueue is passed as a value type that does not require boxing. Similarly, the value returned by Dequeue is also a value type that does not need to be unboxed. A similar set of methods is generated for the other two queues.

The type parameter does not have to be a simple class or value type. For example, you can create a queue of queues of integers (if you should ever find it necessary), like this:

Queue<Queue<int>> queueQueue = new Queue<Queue<int>>();

A generic class can have multiple type parameters. For example, the generic Dictionary class defined in the System.Collections.Generic namespace in the .NET Framework class library expects two type parameters: one type for keys, and another for the values (this class is described in more detail in Chapter 18).

public class PrintableCollection<T> where T : IPrintable

The System.Collections.Generic namespace in the .NET Framework class library contains a number of generic classes readily available for you. You can also define your own generic classes, which is what you will do in this section. Before you do this, let’s cover a bit of background theory.

The theory of binary trees

In the following exercises, you will define and use a class that represents a binary tree.

A binary tree is a useful data structure that you can use for a variety of operations, including sorting and searching through data very quickly. Volumes have been written on the minutiae of binary trees, but it is not the purpose of this book to cover this topic in detail. Instead, you’ll look at just the pertinent facts. If you are interested in learning more, consult a book such as The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd Edition by Donald E. Knuth (Addison-Wesley Professional, 1998). Despite its age, this is the recognized, seminal work on sort and search algorithms.

A binary tree is a recursive (self-referencing) data structure that can either be empty or contain three elements: a datum, which is typically referred to as the node, and two subtrees, which are themselves binary trees. The two subtrees are conventionally called the left subtree and the right subtree because they are typically depicted to the left and right of the node, respectively. Each left subtree or right subtree is either empty or contains a node and other subtrees. In theory, the whole structure can continue ad infinitum. The following image shows the structure of a small binary tree.

The real power of binary trees becomes evident when you use them for sorting data. If you start with an unordered sequence of objects of the same type, you can construct an ordered binary tree and then walk through the tree to visit each node in an ordered sequence. The algorithm for inserting an item I into an ordered binary tree B is shown here:

If the tree, B, is empty
Then
  Construct a new tree B with the new item I as the node, and empty left and
  right subtrees
Else
  Examine the value of the current node, N, of the tree, B
  If the value of N is greater than that of the new item, I
  Then
    If the left subtree of B is empty
    Then
      Construct a new left subtree of B with the item I as the node, and
      empty left and right subtrees
    Else
      Insert I into the left subtree of B
    End If
  Else
    If the right subtree of B is empty
    Then
      Construct a new right subtree of B with the item I as the node, and
      empty left and right subtrees
    Else
      Insert I into the right subtree of B
    End If
  End If
End If

Notice that this algorithm is recursive, calling itself to insert the item into the left or right subtree depending on how the value of the item compares with the current node in the tree.

Note

The definition of the expression greater than depends on the type of data in the item and node. For numeric data, greater than can be a simple arithmetic comparison, and for text data, it can be a string comparison; however, you must give other forms of data their own means of comparing values. You will learn more about this when you implement a binary tree in the upcoming section Building a binary tree class by using generics.

If you start with an empty binary tree and an unordered sequence of objects, you can iterate through the unordered sequence, inserting each object into the binary tree by using this algorithm, resulting in an ordered tree. The next image shows the steps in the process for constructing a tree from a set of five integers.

After you have built an ordered binary tree, you can display its contents in sequence by visiting each node in turn and printing the value found. The algorithm for achieving this task is also recursive:

If the left subtree is not empty
Then
  Display the contents of the left subtree
End If
Display the value of the node
If the right subtree is not empty
Then
  Display the contents of the right subtree
End If

The following image shows the steps in the process for outputting the tree. Notice that the integers are now displayed in ascending order.

class Circle
{
    public Circle(int initialRadius)
    {
        radius = initialRadius;
    }
    public double Area()
    {
        return Math.PI * radius * radius;
    }
    private double radius;
}

class Circle : System.IComparable
{
   ...
   public int CompareTo(object obj)
   {
     Circle circObj = (Circle)obj; // cast the parameter to its real type
      if (this.Area() == circObj.Area())
          return 0;
     if (this.Area() > circObj.Area())
          return 1;
      return -1;
   }
}

int CompareTo(T other);

class Circle : System.IComparable<Circle>
{
    ...
    public int CompareTo(Circle other)
    {
        if (this.Area() == other.Area())
            return 0;
        if (this.Area() > other.Area())
            return 1;
        return -1;
    }
}

As well as defining generic classes, you can create generic methods.

With a generic method, you can specify the types of the parameters and the return type by using a type parameter in a manner similar to that used when defining a generic class. In this way, you can define generalized methods that are type-safe and avoid the overhead of casting (and boxing, in some cases). Generic methods are frequently used in conjunction with generic classes; you need them for methods that take generic types as parameters or that have a return type that is a generic type.

You define generic methods by using the same type parameter syntax that you use when creating generic classes. (You can also specify constraints.) For example, the generic Swap<T> method in the code that follows swaps the values in its parameters. Because this functionality is useful regardless of the type of data being swapped, it is helpful to define it as a generic method:

static void Swap<T>(ref T first, ref T second)
{
   T temp = first;
   first = second;
   second = temp;
}

You invoke the method by specifying the appropriate type for its type parameter. The following examples show how to invoke the Swap<T> method to swap over two ints and two strings:

int a = 1, b = 2;
Swap<int>(ref a, ref b);
...
string s1 = "Hello", s2 = "World";
Swap<string>(ref s1, ref s2);

Chapter 8 demonstrates that you can use the object type to hold a value or reference of any other type. For example, the following code is completely legal:

string myString = "Hello";
object myObject = myString;

Remember that in inheritance terms, the String class is derived from the Object class, so all strings are objects.

Now, consider the following generic interface and class:

interface IWrapper<T>
{
    void SetData(T data);
    T GetData();
}
class Wrapper<T> : IWrapper<T>
{
    private T storedData;
    void IWrapper<T>.SetData(T data)
    {
        this.storedData = data;
    }
    T IWrapper<T>.GetData()
    {
        return this.storedData;
    }
}

The Wrapper<T> class provides a simple wrapper around a specified type. The IWrapper interface defines the SetData method that the Wrapper<T> class implements to store the data and the GetData method that the Wrapper<T> class implements to retrieve the data. You can create an instance of this class and use it to wrap a string like this:

Wrapper<string> stringWrapper = new Wrapper<string>();
IWrapper<string> storedStringWrapper = stringWrapper;
storedStringWrapper.SetData("Hello");
Console.WriteLine("Stored value is {0}", storedStringWrapper.GetData());

The code creates an instance of the Wrapper<string> type. It references the object through the IWrapper<string> interface to call the SetData method. (The Wrapper<T> type implements its interfaces explicitly, so you must call the methods through an appropriate interface reference.) The code also calls the GetData method through the IWrapper<string> interface. If you run this code, it outputs the message “Stored value is Hello”.

Take a look at the following line of code:

IWrapper<object> storedObjectWrapper = stringWrapper;

This statement is similar to the one that creates the IWrapper<string> reference in the previous code example, the difference being that the type parameter is object rather than string. Is this code legal? Remember that all strings are objects (you can assign a string value to an object reference, as shown earlier), so in theory this statement looks promising. However, if you try it, the statement will fail to compile with the message “Cannot implicitly convert type ‘Wrapper<string>’ to ‘IWrapper<object>’.”

You can try an explicit cast such as this:

IWrapper<object> storedObjectWrapper = (IWrapper<object>)stringWrapper;

This code compiles but will fail at run time with an InvalidCastException exception. The problem is that although all strings are objects, the converse is not true. If this statement were allowed, you could write code like this, which ultimately attempts to store a Circle object in a string field:

IWrapper<object> storedObjectWrapper = (IWrapper<object>)stringWrapper;
Circle myCircle = new Circle();
storedObjectWrapper.SetData(myCircle);

The IWrapper<T> interface is said to be invariant. You cannot assign an IWrapper<A> object to a reference of type IWrapper<B>, even if type A is derived from type B. By default, C# implements this restriction to ensure the type safety of your code.

interface IStoreWrapper<T>
{
    void SetData(T data);
}
interface IRetrieveWrapper<T>
{
    T GetData();
}
class Wrapper<T> : IStoreWrapper<T>, IRetrieveWrapper<T>
{
   private T storedData;
   void IStoreWrapper<T>.SetData(T data)
   {
       this.storedData = data;
   }
   T IRetrieveWrapper<T>.GetData()
   {
       return this.storedData;
   }
}

Wrapper<string> stringWrapper = new Wrapper<string>();
IStoreWrapper<string> storedStringWrapper = stringWrapper;
storedStringWrapper.SetData("Hello");
IRetrieveWrapper<string> retrievedStringWrapper = stringWrapper;
Console.WriteLine("Stored value is {0}", retrievedStringWrapper.GetData());

IRetrieveWrapper<object> retrievedObjectWrapper = stringWrapper;

interface IRetrieveWrapper<out T>
{
    T GetData();
}

// string derives from object, so this is now legal
IRetrieveWrapper<object> retrievedObjectWrapper = stringWrapper;

Wrapper<int> intWrapper = new Wrapper<int>();
IStoreWrapper<int> storedIntWrapper = intWrapper; // this is legal
...
// the following statement is not legal - ints are not objects
IRetrieveWrapper<object> retrievedObjectWrapper = intWrapper;

public interface IComparer<in T>
{
    int Compare(T x, T y);
}

class ObjectComparer : IComparer<Object>
{
    int IComparer<Object>.Compare(Object x, Object y)
    {
        int xHash = x.GetHashCode();
        int yHash = y.GetHashCode();
        if (xHash == yHash)
            return 0;
        if (xHash < yHash)
            return -1;
        return 1;
    }
}

Object x = ...;
Object y = ...;
ObjectComparer objectComparer = new ObjectComparer();
IComparer<Object> objectComparator = objectComparer;
int result = objectComparator.Compare(x, y);

IComparer<String> stringComparator = objectComparer;

public interface IComparer<in T>
{
    int Compare(T x, T y);
}

In this chapter, you learned how to use generics to create type-safe classes. You saw how to instantiate a generic type by specifying a type parameter. You also saw how to implement a generic interface and define a generic method. Finally, you learned how to define covariant and contravariant generic interfaces that can operate with a hierarchy of types.