C# 2.0 Generic Tree containing multiple types

Question

I'm having a tricky time in thrashing out how best to approach this particular problem and would really like some guidance from the expert community!

Let's say I have 3 classes

Branch
Twig
Leaf

A Branch can contain a collection of other Branch objects, but can also contain a collection of Twig objects and a collection of Leaf objects.

A Twig can contain a collection of other Twig objects, but can also contain a collection of Leaf objects.

A Leaf object can be considered a base component and contains no collections of any other objects.

Hence, the possible stuctures are

Branch

Branch                Branch                  Branch
|                     |                       |
|_Branch              |_Twig                  |_Leaf
|  |_etc...           |  |_etc...
|                     |
|_Twig                |_Leaf
|  |_etc...
|
|_Leaf

Twig

Twig                  Twig
|                     |
|_Twig                |_Leaf
|  |_etc...
|
|_Leaf

Leaf

Leaf

Given a Branch, I would like to be able to interrogate any descendent Branch, Twig, or Leaf objects and know

1. The ratio that each descendent object contributes to the top object (the ratio is contextual to the parent and child object in each case).

2. If the descendent objects of a particular type contain a particular property value. For example, Check descendent Leaf objects to see if more than 4 have UnderSide property value "Furry"

I would also like to be able to have the options to

3.enumerate through the objects a descendent level at a time i.e. an ordered list of all first children, followed by all second children, etc (the order of objects in each level does not matter).

4. enumerate through the objects breadth-wise i.e. an ordered list of first child, and if first child has children then first child's children, then if that object has children then it's children ....then second child, etc...

My first thought is to use a generic tree and interface polymorphism, but I'm having difficulty in working out the details - Twig and Leaf objects share some common properties but Branch objects are very different. If I was dealing with only one type of object it would be very straightforward! Can this be done in a type-safe manner?

Any help would be greatly appreciated.

Answer 1

This is how I would probably do it:

public interface INodeChild
{
    public INodeParent Parent {get;set;}
    //Any methods/properties common to ALL inheritors
}

public abstract class NodeParent : INodeChild
{
    public INodeParent Parent {get; protected set;}

    public IList<INodeChild> Children {get;set;}
    // This is just breadth-wise since I'm more familiar with that.
    public string ListChildren(int level)
    {
        StringBuilder sb = new StringBuilder();
        foreach(INodeChild item in Children)
        {
            sb.AppendLine(Enumerable.Repeat(" ", level));
            INodeParent itemParent = item as INodeParent;
            if(itemParent != null)
            {
                itemParent.ListChildren(++level);
            }
        }
        return sb.ToString();
    }
    //Any methods/properties common to all parent inheritors (brach/twig/etc)
}

public class Brach : NodeParent
{
    // Any branch only stuff goes here.
}

public class Twig : NodeParent
{
    // Any twig only stuff goes here
}

public class Leaf : INodeChild
{
    // Any leaf only stuff goes here.
}

Answer 2

I would use interfaces to dictate who can hold what:

public interface IBranch { }
public interface ITwig { }

public class Branch : IBranch
{
    List<IBranch> _Kids = new List<IBranch>();
    public List<IBranch> Kids
    {
        get { return _Kids; }
    }
}

public class Twig : ITwig, IBranch
{
    List<ITwig> _Kids;
    public List<ITwig> Kids
    {
        get { return _Kids; }
    }
}

public class Leaf : ITwig, IBranch
{
}

implement ienumerable and make sure you "yield return this" before enumerating children. it would be good to put all common functionality in IBranch, and commonality between leaf and twig in ITwig.

hope this helps!

Answer 3

They do all share the Ratio property though don't they, so you could at the very least have them all implement some IRatio interface...