Поиск по шаблонному дереву

Question

Итак, у меня есть 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 будет иметь конкретное дерево, которое я использую? Может быть, я поступаю неправильно, поэтому любые советы приветствуются. Спасибо!

Answer 1

Прежде всего, вам необходимо поместить метод FindNode в INode. В противном случае вы не сможете найти узел какого-либо типа DataType ... до того, как найдете узел типа DataType. Даже если у вас есть ссылка на объект, который вы знаете DataNode<X>, это не поможет вам, если кто-то скажет вам найти DataNode<Y>.

Теперь вы можете выбрать две дороги: если вы хотите, чтобы 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, чтобы сделать его более понятным.

Answer 2

Используйте общую функцию:

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"));