4

在 C# 中,我有一个侵入式树结构,如下所示:

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

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

可以添加到树中的各种对象继承自NodeContainer取决于它们是否可以具有子级。

通过创建Container一个内部类,这意味着它可以访问私有成员Node来管理容器的子列表。

这一切都很好。但是现在我希望使它成为通用的,这样我就可以在保持类型安全的同时重用它——基本上将所有的树功能移动到 Node 之上的一个泛型类和另一个在 Node 和 Container 之间。这是我正在尝试做的粗略设计:

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在我自己的库中使用并小心谨慎),我仍然无法找出不会遇到相同问题(和错误)的设计。

(我不认为我必须这样做,只是把它拼出来:我不是试图“修复”编译错误,我也不是在寻找一个简单的树实现。这是一个容器设计问题。)

所以现在我有点难过。有没有人对如何设计这个东西有更好的想法?

编辑:一定要看看这个答案,这是设计的另一个尝试,它试图使用扩展方法来避免将类“注入”到继承层次结构中的问题(但不幸的是不能完全工作)。

4

6 回答 6

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>
{
}
于 2010-10-02T14:34:28.670 回答
0

我的解决方案如下所示:

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;
    }
}

HTH。

注意:其他验证,例如 ParentNode != null 子节点;节点属于它被添加到的同一个父节点等。此示例中未实现。

于 2010-10-02T13:49:38.503 回答
0

一种选择是通过不直接公开 Node 对象,将客户端与树的实际结构完全隔离:

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;
    }
}

树现在可以包含任何类型的数据对象,而不必从特殊类型继承或包含任何控制树结构的属性。树结构全部由 Tree 类在内部处理,所有 Tree 操作由 Tree 类提供。现在客户端与实现细节完全隔离。客户所看到的只是他们的数据对象。如果您仍然希望能够从节点提供导航,您可以在节点界面中提供返回到 Tree 的链接,然后提供使用 Tree 方法来实现导航的扩展方法。

于 2010-10-02T17:09:33.353 回答
0

(不要这样做 - 将其保留以帮助防止其他人也意外放弃扩展;))

这有帮助吗?

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限制为 a 。NodeGenericNode

于 2010-10-02T14:51:09.957 回答
0

我以为我有一个可行的解决方案,但它并不完全有效:

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

虽然只为 Container 公开方法的扩展方法方法不能正常工作,但像这样构造 GenericNode 类具有 Container 和 Node 可以是同一个类的好特性——让最终用户可以选择在可以有孩子的树,或允许所有类型有孩子的树。

(同样由于某种原因,扩展方法没有出现在 VC# 2008 SP1 的 IntelliSense 中,尽管它在 2010 年出现了。)

仍在寻找更好的解决方案...

于 2010-10-02T16:10:17.060 回答
0

只需修复您的泛型类型参数名称,并记住将泛型类型参数添加到继承的 GenericNode。

IE。

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; }
    }
}

编译就好了。

于 2010-10-03T18:07:08.357 回答