Nick Polyak’s Software Blog

Code Location

The code for this blog post can be downloaded from
TreeTestsCode.zip.

Introduction

CodeProject

I continue a series of blog posts about implementing WPF
concepts outside of WPF.

This post talks about generic Tree structures in C#. The relationship with WPF will become
clearer once we start talking about Routed Events outside of WPF (hopefully in the next post).

In his great LINQ TO VISUAL TREE
and LINQ to Tree – A Generic Technique for Querying Tree-like Structures articles, Colin Eberhardt talks about queries various
Tree
structures using LINQ. In order to fit the Tree structure into his framework the user of the code should either build an
adaptor satisfying ILinqToTree interface for the tree nodes, or generate such adaptor and the corresponding
LINQ functions using VisualStudion T4 templates.

Here I am defining a Tree structure without resorting to adapter interface
and using delegates instead. This
makes it more generic and makes it possible to apply the concept to a very wide class of objects without T4 template
generation.

What is a Tree?

A Tree is a set of objects called the Tree Nodes.
From any Tree Node one should be able to find its unique parent
Tree Node
(if it exists) or its collection of child Tree Nodes (if they exist). The above
Tree definition allows to find all the Tree Nodes
of a Tree recursively, the following information is given:

• A Tree Node to start navigation.
• A function that for any Tree Node
  returns its parent Tree Node or null
  (if it has no parent).
• A function that for any Tree Node returns a collection of its children
  (it might be null or empty collection if no such children exist).

Translating the above into C# (or any other object oriented language that allows delegates or lambdas) we can write that
the Tree can be defined by one Tree Node
object or a generic type TreeNode and two delegates:

Func<TreeNode, TreeNode> ToParentFunction

and

Func<TreeNode, IEnumerable<TreeNode>> ToChildrenFunction

Note, also, that for navigating up the Tree only ToParentFunction is
required while for navigating down the Tree – only ToChildrenFuncion.

The Tree API

Based on the discussion above I created a generic API for navigating up and down the Tree
using C# extension functions.
The API is located within NP.Paradigms.TreeUtils static class under NP.Paradigms project.
The available functions are very similar to those from Colin Eberhardt’s articles, the difference is that one extra
argument is required – the function for navigation up or down a Tree:

/// Returns a collection of all ancestors of a node.
public static IEnumerable<NodeType> Ancestors<NodeType>
(
this NodeType node,
Func<NodeType, NodeType> toParentFunction
)

/// Returns the node itself and all its ancestors a part of a collection.
public static IEnumerable<NodeType> Ancestors<NodeType>
(
this NodeType node,
Func<NodeType, NodeType> toParentFunction
)

/// returns itself and all its descendants as part of a collection
/// of TreeChildInfo object that contain the node itself and the 
/// distance from to original node (called Level). 
/// Original node passed as an agument to this function 
/// has its level specified by the level argument (the default is 0)
/// its children will have Level property set to 1, grandchildren - to 2 etc.
public static IEnumerable<TreeChildInfo<NodeType>> SelfAndDescendantsWithLevelInfo<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction,
int level = 0
)

/// Returns the descendants nodes with level info (just like SelfAndDescendantsWithLevelInfo)
/// only within the original node itself. 
public static IEnumerable<TreeChildInfo<NodeType>> DescendantsWithLevelInfo<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

/// Returns the original node and its descendants as part of a collection
public static IEnumerable<NodeType> SelfAndDescendants<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

/// Returns the descendants of an original node as a collection
public static IEnumerable<NodeType> Descendants<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)
{
return node.DescendantsWithLevelInfo(toChildrenFunction).Select((treeChildInfo) => treeChildInfo.TheNode);
}

/// Returns the anscestors of the current node (starting from the Root node) 
/// and the current node's descendants. Level specifies the 
/// distance from the Root Node (top node)
public static IEnumerable<TreeChildInfo<NodeType>> AncestorsAndDescendants<NodeType>
(
this NodeType node,
Func<NodeType, NodeType> toParentFunction,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

/// returns all the nodes of the tree except for the
/// original node itself, its descendents and ancestors (the top node is still returned
/// even thought it is an ascestor).
public static IEnumerable<TreeChildInfo<NodeType>> AllButAncestorsAndDescendants<NodeType>
(
this NodeType node, 
Func<NodeType, NodeType> toParentFunction,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

The last two functions AncestorsAndDescendants and AllButDescendantsAndAncestors
do not have analogues in Colin Eberhardt’s articles but are still pretty useful sometimes.

Non-Visual Tree Usage Example

The usage example can be found under project TreeTests (do not forget to make this project
a start up project within the solution).

In the Main function of this project (located within Program.cs file,
we build a tree out of TestTreeNode objects. Each TestTreeNode object
contains a Parent property specifying the parent of the node, Children
collection specifying the children of the node and NodeInfo property – which is
simply a string that should uniquely identify the node. Function AddChild(string childNodeInfo)
fascilitates building the tree. It adds a child node setting its NodeInfo property to the
passed string parameter and setting its Parent property to the current node.

Here is how we build the tree:

#region Start building tree out of TestTreeNodes objects
TestTreeNode topNode = new TestTreeNode { NodeInfo = "TopNode" };

TestTreeNode level2Node1 = topNode.AddChild("Level2Node_1");
TestTreeNode level2Node2 = topNode.AddChild("Level2Node_2");

TestTreeNode level3Node1 = level2Node1.AddChild("Level3Node_1");
TestTreeNode level3Node2 = level2Node1.AddChild("Level3Node_2");

TestTreeNode level3Node3 = level2Node2.AddChild("Level3Node_3");
TestTreeNode level3Node4 = level2Node2.AddChild("Level3Node_4");
#endregion End tree building

The functions to go up and down the tree are specified in the following way:

// to parent function
Func<TestTreeNode, TestTreeNode> toParentFn =
(treeNode) => treeNode.Parent;

// to children function
Func<TestTreeNode, IEnumerable<TestTreeNode>> toChildrenFn =
(treeNode) => treeNode.Children;

Finally we print anscestors and descendents of the nodes:

Console.WriteLine("Print ancestors of node level3Node3");

foreach (var treeNode in level3Node3.Ancestors(toParentFn))
Console.WriteLine("\t" + treeNode.NodeInfo);

Console.WriteLine("\n");

Console.WriteLine("Print self and ancestors of node level3Node3");
foreach (var treeNode in level3Node3.SelfAndAncestors(toParentFn))
Console.WriteLine("\t" + treeNode.NodeInfo);

Console.WriteLine("\nPrint whole tree");

foreach (var treeNodeInfo in topNode.SelfAndDescendantsWithLevelInfo(toChildrenFn))
{
// shift the string by the level number plus 1 tabs
string tabs = new string('\t', treeNodeInfo.Level + 1);

Console.WriteLine(tabs + treeNodeInfo.TheNode.NodeInfo);
}

Here are the printed results:

Print ancestors of node level3Node3
Level2Node_2
TopNode

Print self and ancestors of node level3Node3
Level3Node_3
Level2Node_2
TopNode

Print whole tree
TopNode
Level2Node_1
Level3Node_1
Level3Node_2
Level2Node_2
Level3Node_3
Level3Node_4

Note, that when we print the top node of the tree and its descendents (the last print out)
we shift the descendents to the right by placing Tab characters in front of the strings.
The number of those tab characters equals to the Level property of the
corresponding TreeNodeInfo object so that the farther the nodes are
from the top node, the farther to the right they will appear.

WPF Visual and Logical Trees Usage Examples

WPF VisualTreeHelper and LogicalTreeHelper classes can furnish us
with delegates to go up and down visual and logical trees correspondingly. Project
NP.Paradigms.Windows contains VisualTreeUtils and LogicalTreeUtils
static classes providing LINQ functions for Visual an Logical trees correspondingly. They are
simply wrappers around NP.Paradigms.TreeUtils class described above.

VisualTreeHelper operates on objects of FrameworkElement class. Because of this,
all the VisualTreeUtils functions operate on FrameworkElement objects.
Here is how we define the ToParentFunction and ToChildFunction for the
VisualTreeUtils class:

static Func<FrameworkElement, FrameworkElement> toParentFunction =
(obj) => VisualTreeHelper.GetParent(obj) as FrameworkElement;

static Func<FrameworkElement, IEnumerable<FrameworkElement>> toChildrenFunction =
(parentObj) =>
{
int childCount = VisualTreeHelper.GetChildrenCount(parentObj);

List<FrameworkElement> result = new List<FrameworkElement>();
for (int i = 0; i < childCount; i++)
{
result.Add(VisualTreeHelper.GetChild(parentObj, i) as FrameworkElement);
}

return result;
};

The extension method of VisualTreeUtility class are self explanotary and
correspond to the TreeUtils class methods one to one except that they start
with prefix Visual to avoid the name clashes.

When it come to LogicalTreeHelper, some of the children, that it returns
might not be of FrameworkElement type. If fact contents of the Buttons or
of TextBlock or other objects can be simply strings. Because of that we define all of our
extension methods on plain objects. Here is how the ToParentFunction and ToChildFunction
are defined for the logical tree:

static Func<object, object> toParentFunction =
(obj) =>
{
if ( !(obj is DependencyObject) )
{
return null;
}

return LogicalTreeHelper.GetParent(obj as DependencyObject);
};

static Func<object, IEnumerable<object>> toChildrenFunction =
(parentObj) =>
{
if (!(parentObj is DependencyObject))
{
return null;
}

return LogicalTreeHelper.GetChildren(parentObj as DependencyObject).Cast<object>();
};

The extension methods of the LogicalTreeUtils class are also self explanotary and have
preffix Logical to avoid the name clashes.

The usage example for VisualTreeHelper and LogicalTreeHelper methods
is located under VisualTreeTests project. The function MainWindow_Loaded
gets the tree nodes for the visual and logical trees of ElementToDisplay grid that
contains a TextBlock and a Button. The collections of tree nodes
are converted into collections of TreeNodeDisplayer objects that transform the
tree nodes into indented strings: FrameworkElements are displayed by their type name
in parentheses followed by name and other objects are simply converted to strings using
ToString() method. The indentation is related to their level within the tree
(how far they are from the root node of the tree). The visual and logical trees are displayed
under the ElementToDisplay: