Generic Interfaces


Just like classes, interfaces may be generic. In the transition from version 1 of .Net to version 2 of .Net quite a few of the existing interfaces that were non-generic were made generic. For example, consider the generic and non-generic interfaces for comparing two entries (IComparable).

interface IComparable         // Non-generic form of Interface
{
 int CompareTo(object o);
}

interface IComparable<T>      // Generic form of Interface
{
 int CompareTo(T t);
}

The non-generic form of the interface relies upon the base class object to perform comparisons. The generic interface is type-safe and it is the preferred method once generics became available. Another example of a pair of interfaces like this is IComparer.

interface IComparer         // Non-generic form of Interface
{
 int Compare(object x, object y);
}

interface IComparer<T>      // Generic form of Interface
{
 int Compare(T x, T y);
}

Other examples of paired generic/non-generic interfaces are IEqualityComparer, IEnumerable etc. Thus, many new generic interfaces were introduced with version 2. In the .Net documentation, the non-generic version of IComparer is referred to as just IComparer; whereas, the generic version is referred to as IComparer(Of T) (Visual Basic syntax).

The previous versions of the Binary Search Tree used generic constraints and the generic interface IComparable(Of T) to implement key comparisons. This is a great pedagogic device, but it is not the way the .Net Collection Classes operate. There is one more step to consider. Collection classes generally use the IComparer interface shown above to implement key comparisons. There is another class called Comparer which has a property called Default. Comparer implements the IComparer interface. The property Default of Comparer uses RTTI to detect the presence of the IComparable interface. The benefit of doing things this way is that when IComparable is present and the default options are taken, it is detected. However, it is possible to manually specify an IComparer which either overrides default behaviour or implements comparison when no default behaviour is present (i.e. the key type K does not derive from IComparable). To gain practice with generic interfaces, the next example upgrades the BST to use IComparer rather than IComparable with constraints. The end result is a more flexible BST.

// Generic12 - Binary Search Tree
//           - Using IComparer Generic Interface

using System;
using System.Collections.Generic;

public delegate bool Predicate<K, T>(K k, T t);

public class TreeNode<K, T>
{
    public K Key;
    public T Data;
    public TreeNode<K, T> Left;
    public TreeNode<K, T> Right;
    public TreeNode<K, T> Parent;
    public bool IsHeader;

    public TreeNode() { Parent = null; Left = this; Right = this; IsHeader = true; }

    public TreeNode(K k, T t, TreeNode<K, T> p)
    {
        Key = k;
        Data = t;
        Left = null;
        Right = null;
        Parent = p;
        IsHeader = false;
    }
}

class Tree<K, T> : IEnumerable<KeyValuePair<K, T>>
{
    IComparer<K> Comparer;
    TreeNode<K, T> Header;

    TreeNode<K, T> Root
    {
        get
        {
            return Header.Parent;
        }
        set
        {
            Header.Parent = value;
        }
    }

    public TreeEntry<K, T> Begin
    { get { return new TreeEntry<K, T>(Header.Left); } }

    public TreeEntry<K, T> End
    { get { return new TreeEntry<K, T>(Header); } }

    public Tree()
    {
        Comparer = Comparer<K>.Default;
        Header = new TreeNode<K, T>();
    }

    public Tree(IComparer<K> c)
    {
        Comparer = c;
        Header = new TreeNode<K, T>();
    }

    public T this[K Key]
    {
        set
        {
            if (Root == null)
            {
                Root = new TreeNode<K, T>(Key, value, Header);
                Header.Left = Header.Right = Root;
            }
            else
            {
                TreeNode<K, T> Search = Root;
                for (; ; )
                {
                    int Compare = Comparer.Compare(Key,Search.Key);

                    if (Compare == 0) // Item Exists
                    { Search.Data = value; break; }

                    else if (Compare < 0)
                    {
                        if (Search.Left != null)
                            Search = Search.Left;
                        else
                        {
                            Search.Left = new TreeNode<K, T>(Key, value, Search);
                            if (Header.Left == Search) Header.Left = Search.Left;
                            break;
                        }
                    }

                    else
                    {
                        if (Search.Right != null)
                            Search = Search.Right;
                        else
                        {
                            Search.Right = new TreeNode<K, T>(Key, value, Search);
                            if (Header.Right == Search) Header.Right = Search.Right;
                            break;
                        }
                    }
                }
            }
        }
        get
        {
            if (Root == null)
                throw new EntryNotFoundException();
            else
            {
                TreeNode<K, T> Search = Root;

                do
                {
                    int Result = Comparer.Compare(Key,Search.Key);

                    if (Result < 0) Search = Search.Left;

                    else if (Result > 0) Search = Search.Right;

                    else break;

                } while (Search != null);

                if (Search == null)
                    throw new EntryNotFoundException();
                else
                    return Search.Data;
            }
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    { return new TreeEntry<K, T>(Header); }

    IEnumerator<KeyValuePair<K, T>> IEnumerable<KeyValuePair<K, T>>.GetEnumerator()
    { return new TreeEntry<K, T>(Header); }

    public KeyValuePair<K, T> Find(Predicate<K, T> Predicate)
    {
        TreeEntry<K, T> i = Begin;
        TreeEntry<K, T> e = End;
        while (i != e && !Predicate(i.Key, i.Value)) i.MoveNext();
        if (i != e) return new KeyValuePair<K, T>(i.Node.Key, i.Node.Data);
        else throw new EntryNotFoundException();
    }
}

public class EntryNotFoundException : Exception
{
    static String message = "The requested entry could not be located in the specified collection.";

    public EntryNotFoundException() : base(message) { }
}

public struct TreeEntry<K, T> : IEnumerator<KeyValuePair<K, T>>
{
    public TreeEntry(TreeNode<K, T> N) { Node = N; }

    public K Key
    {
        get
        {
            return Node.Key;
        }
    }

    public T Value
    {
        get
        {
            return Node.Data;
        }
    }

    public bool IsEnd { get { return Node.IsHeader; } }

    public bool MoveNext()
    {
        if (Node.IsHeader)
            Node = Node.Left;
        else
        {
            if (Node.Right != null)
            {
                Node = Node.Right;
                while (Node.Left != null) Node = Node.Left;
            }
            else
            {
                TreeNode<K, T> y = Node.Parent;

                if (y.IsHeader)
                    Node = y;
                else
                {
                    while (Node == y.Right) { Node = y; y = y.Parent; }
                    Node = y;
                }
            }
        }
        return Node.IsHeader ? false : true;
    }

    public void Reset()
    {
        while (!MoveNext()) ;
    }

    object System.Collections.IEnumerator.Current
    { get { return new KeyValuePair<K, T>(Node.Key, Node.Data); } }

    KeyValuePair<K, T> IEnumerator<KeyValuePair<K, T>>.Current
    { get { return new KeyValuePair<K, T>(Node.Key, Node.Data); } }

    public static bool operator ==(TreeEntry<K, T> x, TreeEntry<K, T> y) { return x.Node == y.Node; }
    public static bool operator !=(TreeEntry<K, T> x, TreeEntry<K, T> y) { return x.Node != y.Node; }


    public override string ToString()
    {
        return "(" + Key.ToString() + "," + Value.ToString() + ")";
    }

    public void Dispose() { }

    public TreeNode<K, T> Node;
}

class Program
{
    static bool FindPredicate(int i, string s)
    {
        return s == "S3";
    }

    static void Main()
    {
        Tree<int, string> t = new Tree<int, string>();

        for (int i = 0; i < 10; i++)
            t[i] = "S" + i.ToString();

        KeyValuePair<int, string> KVP = t.Find(FindPredicate);
        Console.WriteLine("Found t[{0}] = {1}", KVP.Key, KVP.Value);
    }
}

The class Tree<K,T> now has the field Comparer which is an object of class IComparer<K>. The generic constraints have been removed. The default constructor uses the class Comparer to default the comparison mechanism as shown below.

public Tree()
{
    Comparer = Comparer<K>.Default;
    Header = new TreeNode<K, T>();
}

If K derives from IComparable<K>, the Default property of Comparer will detect this using RTTI. To add flexability, another constructor has been added and it is shown below.

public Tree(IComparer<K> C)
{
    Comparer = C;
    Header = new TreeNode<K, T>();
}

This constructor manually supplies the comparer. It can be used in two ways:

  1. to override the IComparable<K> interface for K or
  2. to supply a comparer when K does not derive from IComparable<K>.

Understanding IComparable<T> and IComparer<T> is crucial to being able to use collection classes in .Net.