David's Blog

This post has been moved to: http://blogs.clarience.com/clarience/?p=31

When dealing with tree structures, it’s helpful to be able to visit all nodes. Here’s an extension method that makes traversing tree structures easier (in this case, in preorder, depth-first).

internal static class TreeTraverse
{
    public static IEnumerable<T> PreorderTraverse<T>(this T node, Func<T, IEnumerable<T>> childrenFor)
    {
        yield return node;

        var childNodes = childrenFor(node);
        if (childNodes != null)
        {
            foreach (var childNode in childNodes.SelectMany(n => n.PreorderTraverse(childrenFor)))
            {
                yield return childNode;
            }
        }
    }
}

This extension method allows you to treat any type as the root node of a tree, providing you can define a sensible childrenFor method for it.

Example usage:

var root = new Node
{
    Name = "root",
    Children = new List<Node>()
    {
        new Node
        {
            Name = "root > child A",
            Children = new List<Node>()
            {
                new Node
                {
                    Name = "root > child A > child AA"
                }
            }
        },
        new Node
        {
            Name = "root > child B"
        }
    }
};

foreach (var node in root.PreorderTraverse(n => n.Children))
{
    Console.WriteLine(node.Name);
}

Where Node is defined as:

class Node
{
    public string Name { get; set; }
    public IEnumerable<Node> Children { get; set; }
}

To use PreorderTraverse on an IEnumerable<T> you can combine with SelectMany, as in fact the PreorderTraverse extension method does.

More specifically, lambda expressions… Let’s say you have a method, the body of which will execute based on the value of a flag (myFlag in the example here):

public void MyConditionalMethod(string format, params object[] args)
{
    if (myFlag)
    {
        DoSomething(string.Format(format, args));
    }
}

Ideally, in scenarios where myFlag is false we’d like a call to this method, such as the following, to have limited overhead:

MyConditionalMethod("{0}, {1}", param0, param1);

If param0 and/or param1 are value-types, this call will incur the overhead of boxing regardless of the value of myFlag. Obviously, things get worse as we pass more value-types as parameters.

One approach to addressing this problem is through the use of lambda expressions; the lambda expression is only executed if the flag is set. Here’s a version of MyConditionalMethod modified accordingly:

public void MyConditionalMethod(Func<string> getString)
{
    if (myFlag)
    {
        DoSomething(getString());
    }
}

A call to the modified method looks like this:

MyConditionalMethod(() => string.Format("{0}, {1}", param0, param1));

Here are some rough performance numbers (with compiler optimizations on) to illustrate the potential advantages of this approach:

This technique can be used in tracing or other scenarios where these methods may be called frequently throughout your code and it can have a significant performance benefit in the aggregate.