Как сделать навязчивый класс деревьев в универсальных универсальных дженерах?

Question

В C # У меня есть навязчивый Структура дерева, которая выглядит так:

public abstract class Node
{
    Container parent;
    Node nextNode;
    Node previousNode;

    public abstract class Container : Node
    {
        Node firstChild;
        Node lastChild;
    }
}

Различные объекты, которые могут быть добавлены к дереву, наследующуюся от Node или Container В зависимости от того, могут ли они иметь детей или нет.

При составлении Container Внутренний класс означает, что он может получить доступ к частным членам в Node Для управления список детей контейнера.

Это все хорошо и хорошо. Но теперь я хочу сделать его универсальным, чтобы я мог повторно использовать его, поддерживая безопасность типа - в основном перемещая все функциональные возможности дерева на общий класс выше узла, а другой между узлом и контейнером. Вот грубый дизайн того, что я пытаюсь сделать:

public abstract class GenericNode<Node, Container>
    where Node : GenericNode<Node, Container>
    where Container : GenericNode<Node, Container>.GenericContainer
{
    Container parent;
    Node nextNode;
    Node previousNode;

    public abstract class GenericContainer : Node
    {
        Node firstChild;
        Node lastChild;
    }
}

Который, конечно, не работает, потому что вы не можете сделать GenericContainer наследовать от Node (Ошибка компилятора CS0689.). Даже если я бросаю требование внутреннего класса (скажем, используя internal И просто осторожность в моей собственной библиотеке) я до сих пор не могу понять дизайн, который не работает в той же проблеме (и ошибках).

(Я не думал, что мне придется, но просто разобрать это: Я не пытаюсь «исправить» ошибку компиляции, И не ищите простую реализацию дерева. Это вопрос дизайна контейнера.)

И так теперь я немного озадачен. У кого-нибудь есть лучшие идеи о том, как разработать эту вещь?

Редактировать: Обязательно посмотрите на Этот ответ, что еще один удар по дизайну, что пытается использовать методы расширения, чтобы избежать проблемы «вводящего» класса в иерархии наследования (но, к сожалению, не полностью работает).

Answer 1

Следуя подходу метода расширения, что, если вы определяете ограничение наследования (между узлом и контейнером) на интерфейсе вместо этого, и украсить классы контейнеров с интерфейсом.

{
    MyNode n = new MyNode();
    var c = new MyNode.MyContainer();
    c.AddChild(n);

    MySubNode s = new MySubNode();
    c.AddChild(s);

    OtherNode o = new OtherNode();
    o.AddChild(o);

    //compiler doesn't allow this, as you'd expect:
    //c.AddChild(o);
}        

public interface IContainer<TContainerType, TNodeType>
    where TNodeType : GenericNode<TContainerType, TNodeType>
    where TContainerType : TNodeType, IContainer<TContainerType, TNodeType>
{
}

public static class ContainerExtensions
{
    public static void AddChild<TContainerType, TNodeType>(this IContainer<TContainerType, TNodeType> self, TNodeType node)
        where TNodeType : GenericNode<TContainerType, TNodeType>
        where TContainerType : TNodeType, IContainer<TContainerType, TNodeType>
    {
        GenericNode<TContainerType, TNodeType>.AddChild(self as TContainerType, node);
    }
}

public class GenericNode<TContainerType, TNodeType>
    where TNodeType : GenericNode<TContainerType, TNodeType>
    where TContainerType : GenericNode<TContainerType, TNodeType>
{
    TContainerType parent;
    TNodeType nextNode;
    TNodeType previousNode;

    // Only used by Container
    TNodeType firstChild;
    TNodeType secondChild;

    internal static void AddChild(TContainerType container, TNodeType node)
    {
        container.firstChild = node;
        node.parent = container;
    }
}

public class MyNode : GenericNode<MyContainer, MyNode>
{        
}

public class MyContainer : MyNode, IContainer<MyContainer, MyNode>
{
}

public class MySubNode : MyNode
{
}

public class OtherNode : GenericNode<OtherNode, OtherNode>, IContainer<OtherNode, OtherNode>
{
}

Answer 2

Мое решение выглядит как:

public class Tree<T> : ITree<T> where T : INode{
    public T RootNode { get; private set; }
    public Tree(T rootNode){
        RootNode = rootNode;
    }
}

public interface ITree<T> where T : INode{
    T RootNode { get; }
}

public interface INode{
    INode Parent { get; }
    List<INode> Children { get; }
}

internal class Node : INode{
    public INode Parent { get; private set; }
    public List<INode> Children { get; private set; }
    public Node( INode parent, List<INode> children = new List<INode>()){
        Parent = parent;
        Children = children;
    }
}

Хет

Примечание. Дополнительные проверки, такие как Parentnode! = NULL для детских узлов; Узел принадлежит одному и тому же родителю, к которому он добавляется и т. Д. Не реализован в этом образце.

Answer 3

(Не делайте этого - оставляя его, чтобы помочь кому-либо еще отказаться от аварии;))

Эта помощь?

public abstract class GenericNode<Node, Container>
    where Node : GenericNode<Node, Container>
    where Container : GenericNode<Node, Container>.GenericContainer<Node>
{
    Container parent;
    Node nextNode;
    Node previousNode;

    public abstract class GenericContainer<Branch> where Branch: GenericNode<Node, Container> 
    {
        private Leaf firstChild;
        private Leaf secondChild;
    }
}

Также компилируется в 3.5. Branch ограничен быть Node посредством GenericNode Декларация.

Answer 4

Один вариант - изолировать клиента от фактической структуры дерева полностью, не подвергая объекты узла напрямую:

public interface ITagged<T>
{
    T Tag { get; set; }
}

public sealed class Tree<T>
{
    //All Tree operations are performed here (add nodes, remove nodes, possibly move nodes, etc.)
    //Nodes are only exposed as 'ITagged<T>', such as:
    public ITagged<T> Root { get; private set; }

    public IEnumerable<ITagged<T>> GetChildren(ITagged<T> item)
    {
        //Cast to Container and enumerate...
    }

    //Several other tree operations...

    private class Node : ITagged<T>
    {
        Container parent;
        Node nextNode;
        Node previousNode;

        public T Tag { get; set; }
    }

    private class Container : Node
    {
        Node firstChild;
        Node lastChild;
    }
}

Дерево теперь может содержать любой тип объекта данных, без необходимости спускаться от специального типа или включать любые свойства, контролирующие структуру дерева. Структура дерева все это обрабатывается внутри класса деревьев, и все операции дерева обеспечиваются классом дерева. Теперь клиент полностью изолирован от деталей реализации. Все когда-либо видит клиент, являются их объектами данных. Если вы все еще хотите иметь возможность по-прежнему предоставить навигацию от узлов, вы можете вернуть ссылку на дерево в интерфейсе узла, а затем предоставить методы расширения, которые используют методы дерева для реализации навигации.

Answer 5

Я думал, что у меня было рабочее решение, но он не полностью работает:

public abstract class GenericNode<Node, Container>
    where Node : GenericNode<Node, Container>
    where Container : Node
{
    Container parent;
    Node nextNode;
    Node previousNode;

    // Only used by Container
    Node firstChild;
    Node secondChild;

    public static class ContainerHelpers
    {
        public static void AddChild(Container c, Node n)
        {
            c.firstChild = n; // not a real implementation ;)
            n.parent = c;
        }
    }
}

// EDIT: This does not work correctly! (see example below)
public static class GenericNodeExtensionMethods
{
    public static void AddChild<Node, Container>(this Container c, Node n)
        where Node : GenericNode<Node, Container>
        where Container : Node
    {
        GenericNode<Node, Container>.ContainerHelpers.AddChild(c, n);
    }
}

//
// Example Usage
//

public class MyNode : GenericNode<MyNode, MyContainer>
{
}

public class MyContainer : MyNode
{
}

public class MySubNode : MyNode
{
}

public class OtherNode : GenericNode<OtherNode, OtherNode>
{
}


class Program
{
    static void Main(string[] args)
    {
        MyNode n = new MyNode();
        MyContainer c = new MyContainer();
        c.AddChild(n);

        MySubNode s = new MySubNode();
        //
        // This does not work because it tries to fill the generic in the
        // extension method with <MySubNode, MyContainer>, which does not
        // fulfil the constraint "where Container : Node".
        //
        //c.AddChild(s);

        OtherNode o = new OtherNode();
        o.AddChild(o);
    }
}

В то время как метод расширения метод выставления методов выставления методов только для контейнера не работает правильно, структурирование класса универсального значения, подобное это, имеет приятное свойство, который контейнер и узел могут быть одним и тем же классом - давая конечный пользователь возможность иметь определенный тип в Дерево, которое может иметь детей, или позволяет всем типам иметь детей.

(Кроме того, по какой-то причине метод расширения не появляется в Intellisense в VC # 2008 SP1, хотя он выполняет в 2010 году.)

Все еще ищете лучшее решение ...

Answer 6

Просто исправьте имена параметров Generic-Type и не забудьте добавить параметр универсального типа на унаследованный универсальный.

т.е.

public abstract class GenericNode<TNode, TContainer>
    where TNode : GenericNode<TNode, TContainer>
    where TContainer : GenericNode<TNode, TContainer>.GenericContainer
{
    public TContainer Parent { get; set; }
    public TNode Next { get; set; }
    public TNode Previous { get; set; }

    public abstract class GenericContainer : GenericNode<TNode, TContainer>
    {
        public TNode FirstChild { get; set; }
        public TNode LastChild { get; set; }
    }
}

Компилирует просто хорошо.