Searching over a templated tree
- by floatingfrisbee
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??
}
}
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!
