Delegates and Visitors

The GoF visitor pattern is useful but awkward. The usual c++ or Java-y versions typically involve some kind of visitor interface which your visitor must subclass. Java somewhat mitigates this with anonymous classes, but not fully. In C#, if we’re clever with the use of delegates, we can make tasks like tree traversal look about as simple as iteration.

Let’s start with a simple tree class:

class Node {
    Node[] children;
}

We’ll implement a depth-first search using the visitor pattern. Using delegates, we can eliminate the need for an additional class:

class Node {
    public Node[] children;

    public delegate void VisitorDelegate(Node currentNode);
    public void Traverse(VisitorDelegate visitor)
    {
        foreach(Node n in children)
        {
            Traverse(n);
        }
        visitor(this);
    }
}

This is a pretty simple recursion, and really isn’t anything special. The way delegates are typically used, there is still an additional method required for the delegate to be called. But with C# 2.0, we have the opportunity to use anonymous delegates. This is where we can write some really slick code:

void TestTraversal()
{
    Node root = GenerateTestTree();

    int nodeCount = 0;
    root.Traverse(delegate(Node n)
    {
        nodeCount++;
    });
}

The really cool thing about this is that, since anonymous delegates can act as closures, our visitor can pull in the nodeCount from the surrounding environment. This makes for a very succinct version of the visitor pattern.

Technorati Tags: c#, programming