Wednesday, April 13, 2011

Reusable Tree Operations for the .NET Framework

An earlier article of mine describes how a common ITreeNode<T> interface can facilitate reusable tree operations thanks to the introduction of extension methods. That article discusses reusable tree operations with respect to domain-models. Trees, however, are a ubiquitous data structure and also occur throughout the .NET Framework, as discussed in [Eberhardt 2010]. Ideally, the .NET Framework would include an ITreeNode<T> interface that's consistently implemented within the Framework, but this is not so. [Eberhardt 2010] describes a way to provide tree operations to those Framework types by means of the adapter pattern and code generation. His approach, however, has drawbacks. Wrapping a node instance every time it is navigated is likely to impact performance, and relying on code generation complicates maintenance. Upon looking into the matter for myself, I came up with an approach that suffers neither of these drawbacks.

Before continuing onto my solution, I want to note what tree operations, specifically, should be available. Leveraging the functionality already provided by LINQ to Objects reduces this list considerably. For example, instead of numerous methods that deal with ancestors, such as IsAncestorOf and FindAncestorOfType<T>, a single Ancestors method can be provided with LINQ to Objects taking care of the rest.
//item.IsAncestorOf( newParent )
newParent.Ancestors().Contains( item )

//tvi = this.FindAncestorOfType<TreeViewItem>();
tvi = this.Ancestors().OfType<TreeViewItem>().First();
LINQ to XML sets a good example by borrowing its "axis methods" — that query ancestors, siblings, descendants — from XPath. [Eberhardt 2010] does an excellent job of describing these.

Now I will show my solution for adapting .NET Framework tree types in order to make common tree operations available on them. The code that I will be discussing is available as part of Qnomad's CoreHelpers library. To create my solution, I applied a variation of the adapter pattern. Instead of instantiating a wrapper for every tree node, there's just one wrapper per adapted tree type, e.g. DependencyObject. The library also includes a singleton of this sort for the ITreeNode<T> type discussed in my earlier article. The tree operations, then, use the singletons to navigate the hierarchy. The various pieces of this puzzle are outlined below.
  • internal static class TreeOperations: Contains an implementation for each tree operation. Each method signature is of the form:
    internal static IEnumerable<T> Operation<T>( T startNode, ITreeNodeAdapter<T> adapter )
  • internal interface ITreeNodeAdapter<T>
    bool HasSubItems( T treeNode );
    IEnumerable<T> GetSubItems( T treeNode );
    T GetParent( T treeNode );
  • Next come the implementations of ITreeNodeAdapter<T>. The library contains these two:
    • internal class WpfTreeNodeAdapter : ITreeNodeAdapter<DependencyObject>
    • internal class ITreeNodeAdapterImpl<T> : ITreeNodeAdapter<ITreeNode<T>>
You've undoubtedly noticed that everything so far has been declared as internal. The public methods are all on the corresponding "Extensions" classes. The library's WpfExtentions class, for example, contains this method:
  public static IEnumerable<DependencyObject> Ancestors( this DependencyObject startNode )
return TreeOperations.Ancestors( startNode, WpfTreeNodeAdapter.Instance );
Well, that pretty much wraps it up. So now you see a better way for exposing common tree operations on .NET Framework tree types.