Поиск по шаблонному дереву
Таким образом, у меня есть 2 интерфейса:
Узел, который может иметь детей
public interface INode
{
IEnumeration<INode> Children { get; }
void AddChild(INode node);
}
И полученный "Узел данных", которому можно было связать данные с ним
public interface IDataNode<DataType> : INode
{
DataType Data;
IDataNode<DataType> FindNode(DataType dt);
}
Следует иметь в виду, что каждому узлу в дереве можно было связать различный тип данных с ним как его Данные (потому что INode. Функция AddChild просто берет основной INode),
Вот реализация интерфейса IDataNode:
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; }
Вопрос состоит в том, как я реализую функцию FindNode, не зная, с какими видами DataType я встречусь в дереве?
public IDataNode<DataType> FindNode(DataType dt)
{
throw new NotImplementedException();
}
}
Поскольку можно предположить, что что-то вроде этого не удастся
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;
}
Моя единственная опция состоит в том, чтобы сделать это, когда я знаю, какие виды DataType конкретное дерево, которое я использую, будет иметь? Возможно, я иду об этом неправильным способом, таким образом, любые подсказки ценятся.Спасибо!
2 ответа
Прежде всего, вам нужно поместить метод FindNode в INode . В противном случае вы не сможете найти узел какого-либо типа DataType ... до того, как найдете узел типа DataType . Даже если у вас есть ссылка на объект, который, как вы знаете, является DataNode , это не поможет вам, если кто-то скажет вам найти DataNode .
Теперь вы можете пойти двумя путями: если вы хотите использовать шаблон DataNode , тогда вам нужно знать все возможные типы данных в дереве во время компиляции. Если вы это знаете, вы можете использовать общий DataNode . Если есть вероятность, что вы можете захотеть найти узел с данными какого-либо типа, которые станут известны вам только во время выполнения (например, из возвращаемого значения какого-либо метода, который вы не контролируете), вы не можете использовать дженерики.
Ниже я проиллюстрирую общее решение.
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 может быть реализован следующим образом:
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);
}
Я должен сказать, что приведенная выше рекурсивная реализация с LINQ, возможно, пытается быть слишком умной и может быть не очень простой для понимания. Его всегда можно было написать с помощью foreach , чтобы было понятнее.
Используйте общую функцию:
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;
}
Затем вы вызываете ее следующим образом:
var resultsStr = tree.FindNode<string>("Hello");
var resultsInt = tree.FindNode<int>(5);
var resultsCust = tree.FindNode<MyCustomClass>(new MyCustomClass("something"));