public abstract class TreeNodeBase<T> : ITreeNode<T> where T : class, ITreeNode<T>
Introduction
I wanted to create an abstract base class for an existing tree class. This seemed like a quick copy and paste job but turned out to be not as simple as I first thought.
The base class had to be able to do all of the basic tree handling such as Add Child Nodes, Get the Root of the Tree, Get the Parent of the current Node, etc. The
concrete class had to be able to extend and use the base class tree functionality, and I didn't want any casting. I wanted a base class that implemented all of the standard functionality of a
tree as opposed to a set of interfaces.
Background
After copying the existing class to form the basis of the abstract base class, I quickly cut out the code that was specific to the concrete class,
thus leaving the basic tree code. I quickly turned this into a generic class of
T
and then this is when the fun started.
I started to hit a few problems at this stage, so thought I would check out CodeProject. I quickly found some other articles, but they did not fulfill
all of my criteria. They were typically a wrapper class for the node, so the concrete class was not aware of the tree.
Getting Started
After a couple of false starts I thought I would try something that I wasn't sure was possible using
Generics.
I decided to have the concrete class inherit from a generic class of itself. It seemed to compile OK, so I thought I would continue down this path and see where it took me.
So the start of my Generic tree looked like this:
public abstract class TreeNodeBase<T>
public class SpecialTreeNode : TreeNodeBase<SpecialTreeNode>
OK, time to put some meat on the bone. I added in properties for the list of
child nodes and the parent node plus a name of the current node.
Things looked good. I continued, and implemented properties for IsLeaf
and IsRoot
and still looking good.
So my base class now looked something like this:
public abstract class TreeNodeBase<T>
{
protected TreeNodeBase(string name)
{
Name = name;
ChildNodes = new List<T>();
}
public string Name
{
get;
private set;
}
public T Parent
{
get;
set;
}
public List<T> ChildNodes
{
get;
private set;
}
public bool IsLeaf
{
get { return ChildNodes.Count == 0; }
}
public bool IsRoot
{
get { return Parent == null; }
}
}
Problem 1: this
I went to add a method to add a child node to the current node, but quickly found my first problem. I couldn't set the new child node's
parent
to this
because it could not cast this
to type T
.
public void AddChild(T child)
{
child.Parent = this; ChildNodes.Add(child);
}
public void AddChildren(IEnumerable<T> children)
{
foreach (T child in children)
AddChild(child);
}
This was resolved by getting this
from a property implemented in the concrete class.
In the base class:
protected abstract T MySelf
{
get;
}
The implementation in the concrete class:
protected override SpecialTreeNode MySelf
{
get { return this; }
}
So now wherever the base class need this
, I could use MySelf
.
public void AddChild(T child)
{
child.Parent = MySelf;
ChildNodes.Add(child);
}
Problem 2: what is T
I went to implement the next method which was to get the root node from the current node,
but the Parent
node is of type T
and type T
has an unknown implementation in the base class.
public T GetRootNode()
{
if (Parent == null)
return MySelf;
return Parent.GetRootNode(); }
To solve this problem was to basically solve the puzzle. I implemented a generic interface for the properties and methods the base class need to know about.
The nice bit is that the base class implements the interface which allows the base class to know about itself (if you know what I mean).
The interface
public interface ITreeNode<T>
{
T Parent { get; set; }
bool IsLeaf { get; }
bool IsRoot { get; }
T GetRootNode();
string GetFullyQualifiedName();
}
The base class declaration now looks like this:
public abstract class TreeNodeBase<T> : ITreeNode<T> where T : class, ITreeNode<T>
which allowed me to complete the base class methods. It now looked like this:
public abstract class TreeNodeBase<T> : ITreeNode<T> where T : class, ITreeNode<T>
{
protected TreeNodeBase(string name)
{
Name = name;
ChildNodes = new List<T>();
}
public string Name
{
get;
private set;
}
public T Parent
{
get;
set;
}
public List<T> ChildNodes
{
get;
private set;
}
protected abstract T MySelf
{
get;
}
public bool IsLeaf
{
get { return ChildNodes.Count == 0; }
}
public bool IsRoot
{
get { return Parent == null; }
}
public List<T> GetLeafNodes()
{
return ChildNodes.Where(x => x.IsLeaf).ToList();
}
public List<T> GetNonLeafNodes()
{
return ChildNodes.Where(x => !x.IsLeaf).ToList();
}
public T GetRootNode()
{
if (Parent == null)
return MySelf;
return Parent.GetRootNode();
}
public string GetFullyQualifiedName()
{
if (Parent == null)
return Name;
return string.Format("{0}.{1}", Parent.GetFullyQualifiedName(), Name);
}
public void AddChild(T child)
{
child.Parent = MySelf;
ChildNodes.Add(child);
}
public void AddChildren(IEnumerable<T> children)
{
foreach (T child in children)
AddChild(child);
}
}
The only thing that I am not entirely happy with is that the parent has a public setter due to the interface.
Concrete class specialisation
To prove that it fulfills all of my original criteria, I had to add some specialisation to my concrete class and see that I could truly leverage the base class from it.
So I added a property called IsSpecial
and a couple of methods to get the
special nodes (i.e., child nodes where IsSpecial
is true),
and another method to get the special leaf nodes. This would prove that it new about the
tree and could make use of the base class properties.
public class SpecialTreeNode : TreeNodeBase<SpecialTreeNode>
{
public SpecialTreeNode(string name)
: base(name)
{
}
protected override SpecialTreeNode MySelf
{
get { return this; }
}
public bool IsSpecial
{
get;
set;
}
public List<SpecialTreeNode> GetSpecialNodes()
{
return ChildNodes.Where(x => x.IsSpecial).ToList();
}
public List<SpecialTreeNode> GetSpecialLeafNodes()
{
return ChildNodes.Where(x => x.IsSpecial && x.IsLeaf).ToList();
}
public List<SpecialTreeNode> GetSpecialNonLeafNodes()
{
return ChildNodes.Where(x => x.IsSpecial && !x.IsLeaf).ToList();
}
}
Using the code
To use the base class, simply create a concrete class and inherit from the
TreeNoderBase
class where the generic type is your concrete class.
public class SpecialTreeNode : TreeNodeBase<SpecialTreeNode>
You should now have a fully functioning tree that you can begin to specialise. (From above) I implemented the
SpecialTreeNode
class and performed a few tests to see
that it all checked out.
You can see the tests in the source code, but here are the results:
Points of interest
I like that the class inherits from a generic class of itself. I also like that base class relies on the generic interface to know about itself so that
it can implement the interface. It is all very circular but quite pretty in the end.
History
- v1.0 12 March 2012: Initial release.