Searching over a templated tree

Question

So I have 2 interfaces:

A node that can have children

public interface INode
{
    IEnumeration<INode> Children { get; }
    void AddChild(INode node);
}

And a derived "Data Node" that can have data associated with it

public interface IDataNode<DataType> : INode
{
    DataType Data;
    IDataNode<DataType> FindNode(DataType dt);
}

Keep in mind that each node in the tree could have a different data type associated with it as its Data (because the INode.AddChild function just takes the base INode)

Here is the implementation of the IDataNode interface:

internal class DataNode<DataType> : IDataNode<DataType>
{
    List<INode> m_Children;

    DataNode(DataType dt)
    {
        Data = dt;
    }

    public IEnumerable<INode> Children
    {
        get { return m_Children; }
    }

    public void AddChild(INode node)
    {
        if (null == m_Children)
            m_Children = new List<INode>();

        m_Children.Add(node);
    }   

    public DataType Data { get; private set; }

Question is how do I implement the FindNode function without knowing what kinds of DataType I will encounter in the tree?

    public IDataNode<DataType> FindNode(DataType dt)
    {
        throw new NotImplementedException();    
    }
}

As you can imagine something like this will not work out

    public IDataNode<DataType> FindNode(DataType dt)
    {
        IDataNode<DataType> result = null;

        foreach (var child in Children)
        {
            if (child is IDataNode<DataType>)
            {
                var datachild = child as IDataNode<DataType>;

                if (datachild.Data.Equals(dt))
                {
                    result = child as IDataNode<DataType>;
                    break;
                }
            }
            else 
            {
                 // What??
            }

            // Need to recursively call FindNode on the child
            // but can't because it could have a different
            // DataType associated with it. Can't call FindNode 
            // on child because it is of type INode and not IDataNode
            result = child.FindNode(dt); // can't do this!

            if (null != result)
                break;
       }

       return result; 
    }

Is my only option to do this when I know what kinds of DataType a particular tree I use will have? Maybe I am going about this in the wrong way, so any tips are appreciated. Thanks!

Answer 1

Use a Generic Function:

public IDataNode<DataType> FindNode<DataType>(DataType dt)
{
    IDataNode<DataType> result = null;

    foreach (var child in Children)
    {
        if (child is IDataNode<DataType>)
        {
            var datachild = child as IDataNode<DataType>;

            if (datachild.Data.Equals(dt))
            {
                result = child as IDataNode<DataType>;
                break;
            }
        }
        else 
        {
             // it's not a DataType You're looking for, so ignore it!
        }
   }

   return result; 
}

Then you call it like this:

var resultsStr = tree.FindNode<string>("Hello");
var resultsInt = tree.FindNode<int>(5);
var resultsCust = tree.FindNode<MyCustomClass>(new MyCustomClass("something"));

Answer 2

First of all, you need to put the FindNode method in INode. Otherwise, you cannot find a node of some type DataType... before having found a node of type DataType. Even if you have a reference to an object that you know is a DataNode<X>, this won't help you if someone tells you to find a DataNode<Y>.

There are now two roads you may take: if you want DataNode to be templated, then you need to know all possible types of data in the tree at compile time. If you know that, you can use a generic DataNode. If there's a chance that you may want to find a node with data of some type that will only become known to you at runtime (e.g. from the return value of some method that you do not control) then you cannot use generics.

I will illustrate the generic solution below.

public interface INode
{
    IEnumerable<INode> Children { get; }
    IDataNode<DataType> FindNode<DataType>(DataType value);
    void AddChild(INode node);
}

public interface IDataNode<DataType> : INode
{
    DataType Data { get; }
}

INode.FindNode could be implemented like this:

public IDataNode<DataType> FindNode<DataType> (DataType value) {
    // If we are searching for ourselves, return this
    var self = this as IDataNode<DataType>;
    if (self != null && self.Data.Equals(value)) {
        return self;
    }

    // Otherwise:
    // 1. For each of our children, call FindNode on it. This will
    //    find the target node if it is our child, since each child
    //    will check if it is the node we look for, like we did above.
    // 2. If our child is not the one we are looking for, FindNode will
    //    continue looking into its own children (depth-first search).
    // 3. Return the first descendant that comes back and is not null.
    //    If no node is found, FirstOrDefault means we will return null.
    return this.children.Select(c => c.FindNode(value))
                        .FirstOrDefault(found => found != null);
}

I have to say that the above recursive implementation with LINQ tries perhaps to be too clever and is maybe not very easy to understand. It could always be written with foreach, to make it more clear.