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: ,

Advertisements

10 thoughts on “Delegates and Visitors

  1. It’s worth noting that List().ForEach implements this pattern too.
    And so do some of the other helpers on List.
    I just wish they were static and accepted anything implementing IEnumerable 😦

  2. Your example appears simple because it only has one type of Node. In the more general case where the visitor pattern is applied there can be subtypes of nodes. Imagine a more complex visitor operation where the visitor needs to handle different node types differently. That’s where double dispatch and the visitor pattern is really needed.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s