Generic Delegates


Delegates may be generic. The general form of declaring a generic delegate is shown below.

delegate return-type delegate-name<type-parameter-list>(parameter-list);

The type parameter list immediately follows the delegate name.

A Binary Search Tree (BST) as defined in previous examples is an associative array. An associative array is an array where the indices can be of a class type rather than just being of an integer type. Generic delegates may be used as a means of searching an associative array. The form of the generic delegate is shown below.

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

This delegate has type parameters K (the key) and T (the type). It returns a boolean value indicating whether the key and the type satisfy the condition. The next program implements a linear search on an associative array using a delegate of this form. The array is iterated from start to finish and the predicate is called for each entry in the array. When the predicate returns true, the search is halted and the key/value pair that satisfies the predicate is returned. The example is large but it is a realistic use of generic delegates.

// Generic11 - Binary Search Tree
//           - Generic Delegates - XQL

using System;
using System.Collections.Generic;

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

public class TreeNode<K, T> where K : IComparable<K>
{
    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>>
    where K : IComparable<K>
{
    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()
    {
        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 = key.CompareTo(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 = key.CompareTo(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>>
                                where K : IComparable<K>
{
    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 output of the program is as follows.

Found t[3] = S3

A predicate called FindPredicate is coded and this predicate searches for "S3" amongst the entries of the array. Note that "S3" is not of the key type; rather, it is of the data type. A delegate is created and a search is conducted with the following statement.

KeyValuePair<int, string> kvp = t.Find(FindPredicate);

This causes the associative array to be iterated upon and the entry (3,S3) to be located and returned as a KeyValuePair. The KeyValuePair is then printed.

Many other operations like this one may be defined for a BST. For example, a select can be coded in which all entries that satisfy the generic predicate are returned as a subtree (rather than just the first one as above). Alternatively, a search can be coded such that it returns all entries satisfying a predicate using events. Proceeding in this way, a generic based language can be created for dealing with trees (XQL - Extended Query Language).