Generics - An Example


The example of the previous section is a useful pedagogic device but it is far too simple to illustrate the power of generic classes. A large effort is required to make it to this point in the book, but the rewards are great when generics are finally reached. Real classes with real uses can then be developed.

A Stack

Perhaps the simplest of all data structures is the stack. The stack is a singly-linked list with a last in first out (LIFO) structure. The next example demonstrates using generics with the simplest possible stack class. We begin with a stack node, which is shown below.

class StackNode<T>
{
    public T data;
    public StackNode<T> next;

    public StackNode(T copy,
                     StackNode<T> n)
    { data = copy; next = n; }
}

The class StackNode is a generic class and it holds a single object of class T called data. The only other field is a reference to the next node in the stack. The next reference of the last node in the stack is always null (and the root of the stack is null when the stack is empty). The constructor copies the T and it also sets the next pointer to the specified node. It will be seen later, that the input next node n is always the root node of the stack.

A stack is interesting because it is not just one class that is parameterized, it is two related classes. The other class is Stack<T>, which is shown below.

class Stack<T>
{
    StackNode<T> root;

    public Stack() {root = null;}

    public void Push(T data)
    {
        root = new StackNode<T>(data, root);
    }

    public T Pop()
    {
        if (root != null)
        {
            T result = root.data;
            root = root.next;
            return result;
        }
        else
            throw new InvalidOperationException();
    }
}

The only field is the root node of the stack root. The constructor sets the root node to be null. The operation of pushing an item onto the stack is merely a matter of allocating the node and setting the root node to point to it (remember the constructor of StackNode<T> adjusts the next pointer). Popping an item delinks the root node from the stack and returns its associated value.

Observing the class StackNode<T>, it is interesting to note that if T is a reference, a reference is stored and if T is a value, a value is created and copied. A single copy of the generic code is generated at runtime to accomodate all reference types. In contrast, when value types are used, multiple versions of the generic class are generated.

The main routine of project Generic2 is shown below.

class Program
{
    static void Main()
    {
        Stack<string> ss = new Stack<string>();

        ss.Push("Hello");
        ss.Push("world");

        Console.WriteLine("Popped: {0}", ss.Pop());
        Console.WriteLine("Popped: {0}", ss.Pop());

        Stack<int> si = new Stack<int>();

        si.Push(5);
        si.Push(500);

        Console.WriteLine("Popped: {0}", si.Pop());
        Console.WriteLine("Popped: {0}", si.Pop());
    }
}

A stack containing strings is created and the strings "Hello" and "world" are pushed onto the stack. The strings are then popped from stack and written to the console. Similarly, a stack of integers is created and the integers 5 and 500 are pushed onto the stack. The integers are then popped from the stack and printed.

A commercial stack class would be much larger. For example, it would have a property to hold the number of items in the stack, interfaces to support foreach evaluation, serialization methods and perhaps even a merge sort. However the above program is the correct starting point of a collection class. A collection class is a class that collects and stores items of a given type. Collection classes are generic classes by nature. For example, a binary tree is a collection class. Collections.Net devotes entire volumes to the study of collecton classes.

A Doubly-Linked List with foreach Evaluation

Once a stack has been mastered, it is a good idea to master a doubly-linked list. A doubly linked list is a list which points backwards to previous entries and forwards to subsequent entries.

C# possesses the context sensitive keyword foreach. This keyword is used to enumerate collections. The doubly-linked list will contain the interfaces required to support foreach evaluation. These interfaces are IEnumerable and IEnumerator. The IEnumerable interface is a base interface for the actual doubly linked list class. It contains the single method GetEnumerator, which delivers an enumerator for the list. An enumerator is a class object that is capable of progressing sequentially through the collection.

The double linked list class is circular and contains a header node. A header node is a dummy entry that is both the first and last entry in the list. The header node points forward to the first real entry and backward to the last real entry. The GetEnumerator method returns the header node. The method MoveNext of the enumerator is called at the beginning of the enumeration to position at the beginning of the list. It is continuously called until MoveNext returns false, indicating that the end of the list has been reached.

Below is shown the code of an elementary doubly linked list.

// Generic2A - A Doubly Linked List with foreach Evaluation

using System;
using System.Collections.Generic;

public class ListNode<T>
{
    public T data;
    public ListNode<T> next;
    public ListNode<T> previous;
    public bool IsRoot;


    public ListNode() { IsRoot = true; next = this; previous = this; }

    public ListNode(T copy)
    { data = copy; IsRoot = false; }
}

public class ListEntry<T> : IEnumerator<T>
{
    public ListEntry(ListNode<T> n) { node = n; }

    public T Value
    {
        get
        {
            return node.data;
        }
    }

     public bool MoveNext()
    {
        node = node.next;
        return !node.IsRoot;
    }

    public void Reset()
    {
     { while (!node.IsRoot) node = node.next; }
    }

    object System.Collections.IEnumerator.Current
    { get { return node.data; } }

    T IEnumerator<T>.Current
    { get { return node.data; } }

    public void Dispose() { }

    public ListNode<T> node;
}

public class List<T> : IEnumerable<T>
{
    ListNode<T> root;

    public List() { root = new ListNode<T>(); }

    public void Add(T data)
    {
        ListNode<T> new_node = new ListNode<T>(data);
        if (root.next == root)
        {
            root.previous = new_node;
            root.next = new_node;
            new_node.previous = root;
            new_node.next = root;
        }
        else
        {
            root.previous.next = new_node;
            new_node.previous = root.previous;
            root.previous = new_node;
            new_node.next = root;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    { return new ListEntry<T>(root); }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    { return new ListEntry<T>(root); }
}

class Program
{
    static void Main()
    {
        List<string> ss = new List<string>();

        ss.Add("Hello");
        ss.Add("Cruel");
        ss.Add("World");

        foreach (string s in ss)
            Console.WriteLine("String: {0}", s);
    }
}

The method Add adds strings at the end of the list. This preserves the order of the list. It is also possible to develop an algorithm to add elements to the front of the list.

In Main(), three strings are added to the list then a foreach evaluation is applied to the list. The strings are duly printed out to the console.

There is a generic form of IEnumerable<T> and a simpler non-generic form of IEnumerable (similarly for IEnumerator<T>). Both methods GetEnumerator need to be overridden in the class List. Likewise for the Current property of the enumerator ListEntry.

The above algorithms should be studied until they become familiar. The interfaces IEnumerable and IEnumerator are available in the .Net class library documentation. They too should be studied.