15

我正在构建一个通用Tree<T>类，它支持子树的继承。但是我遇到了一些问题。你能帮帮我吗？

描述

让我们定义Tree类和BlueTree类，其中BlueTree extends Tree.

让我们定义Leaf类和RedLeaf类，其中RedLeaf extends Leaf. 它们被用作树包含的“数据”。

ATree<Leaf>表示树的类型Tree，它的“数据”是类型Leaf。

对于继承（这不是正确的 Java 继承）：

  • aTree<Leaf>可以有子类型
    • Tree<Leaf>, Tree<RedLeaf>,BlueTree<Leaf>和BlueTree<RedLeaf>.

.

  • aTree<RedLeaf>可以有子类型
    • Tree<RedLeaf>, 和BlueTree<RedLeaf>,
    • 但不是 Tree<Leaf>，或BlueTree<Leaf>。

.

  • aBlueTree<Leaf>可以有子类型
    • BlueTree<Leaf>, 和BlueTree<RedLeaf>,
    • 但不是 Tree<Leaf>，或Tree<RedLeaf>。

.

  • aBlueTree<RedLeaf>可以有子类型
    • BlueTree<RedLeaf>,
    • 但不是 Tree<Leaf>,Tree<RedLeaf>或BlueTree<Leaf>.

*这里，“孩子”是指树的树枝/树叶。

（有点复杂，这就是我分开行的原因。）

编码

（如果你有解决方案，你可能不需要阅读下面我尝试的详细说明。如果你想一起找出解决方案，我的代码可能会给你一些想法 - 或者，它可能会使他们感到困惑。）

初审：（最简单的）

// This is the focus of this question, the class signature
public class Tree<T> {
    // some fields, but they are not important in this question
    private Tree<? super T> mParent;
    private T mData;
    private ArrayList<Tree<? extends T>> mChildren;

    // This is the focus of this question, the addChild() method signature
    public void addChild(final Tree<? extends T> subTree) {
        // add the subTree to mChildren
    }
}

该类结构满足描述中的大部分要求。除了，它允许

class BlueTree<T> extends Tree<T> { }
class Leaf { }
class RedLeaf extends Leaf { }

Tree<Leaf> tree_leaf = new Tree<Leaf>();
BlueTree<Leaf> blueTree_leaf = new BlueTree<Leaf>();

blueTree_leaf.addChild(tree_leaf);    // should be forbidden

违反

  • aBlueTree<Leaf> 不能有子类型Tree<Leaf>。

问题在于，在 中BlueTree<Leaf>，它的addChild()方法签名仍然是

public void addChild(final Tree<? extends Leaf> subTree) {
     // add the subTree to mChildren
}

理想的情况是，BlueTree<Leaf>.addChild()方法签名（在继承时自动）更改为

public void addChild(final BlueTree<? extends Leaf> subTree) {
     // add the subTree to mChildren
}

（请注意，此方法不能通过继承覆盖上述方法，因为参数类型不同。）

有一种解决方法。RuntimeException我们可以添加一个类继承检查，并针对这种情况抛出：

public void addChild(final Tree<? extends Leaf> subTree) {
    if (this.getClass().isAssignableFrom(subTree.getClass()))
        throw new RuntimeException("The parameter is of invalid class.");
    // add the subTree to mChildren
}

但是让它成为编译时错误比运行时错误要好得多。我想在编译时强制执行此行为。

二审

第一个试用结构中的问题是，Tree方法addChild()中的参数类型不是泛型类型参数。因此它不会在继承时更新。这一次，让我们也尝试将其设为泛型类型参数。

首先，定义通用Tree类。

public class Tree<T> {
    private Tree<? super T> mParent;
    private T mData;
    private ArrayList<Tree<? extends T>> mChildren;

    /*package*/ void addChild(final Tree<? extends T> subTree) {
        // add the subTree to mChildren
    }
}

然后TreeManagerwhich 管理一个Tree对象。

public final class TreeManager<NodeType extends Tree<? super DataType>, DataType> {
    private NodeType mTree;

    public TreeManager(Class<NodeType> ClassNodeType) {
        try {
            mTree = ClassNodeType.newInstance();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void managerAddChild(final NodeType subTree) {
        mTree.addChild(subTree);
        // compile error: The method addChild(Tree<? extends capture#1-of ? super DataType>)
        //                in the type Tree<capture#1-of ? super DataType>
        //                is not applicable for the arguments (NodeType)
    }

    // for testing
    public static void main(String[] args) {
        @SuppressWarnings("unchecked")
        TreeManager<Tree    <Leaf>   , Leaf>    tm_TreeLeaf_Leaf           = new TreeManager<Tree    <Leaf>,    Leaf>   ((Class<Tree    <Leaf>>)    new Tree    <Leaf>   ().getClass());
        TreeManager<Tree    <RedLeaf>, RedLeaf> tm_TreeRedLeaf_RedLeaf     = new TreeManager<Tree    <RedLeaf>, RedLeaf>((Class<Tree    <RedLeaf>>) new Tree    <RedLeaf>().getClass());
        TreeManager<BlueTree<Leaf>   , Leaf>    tm_BlueTreeLeaf_Leaf       = new TreeManager<BlueTree<Leaf>,    Leaf>   ((Class<BlueTree<Leaf>>)    new BlueTree<Leaf>   ().getClass());
        TreeManager<BlueTree<RedLeaf>, RedLeaf> tm_BlueTreeRedLeaf_RedLeaf = new TreeManager<BlueTree<RedLeaf>, RedLeaf>((Class<BlueTree<RedLeaf>>) new BlueTree<RedLeaf>().getClass());

        System.out.println(tm_TreeLeaf_Leaf          .mTree.getClass());    // class Tree
        System.out.println(tm_TreeRedLeaf_RedLeaf    .mTree.getClass());    // class Tree
        System.out.println(tm_BlueTreeLeaf_Leaf      .mTree.getClass());    // class BlueTree
        System.out.println(tm_BlueTreeRedLeaf_RedLeaf.mTree.getClass());    // class BlueTree

        @SuppressWarnings("unchecked")
        TreeManager<Tree    <Leaf>   , RedLeaf> tm_TreeLeaf_RedLeaf     = new TreeManager<Tree    <Leaf>,    RedLeaf>((Class<Tree    <Leaf>>)    new Tree    <Leaf>   ().getClass());
        TreeManager<BlueTree<Leaf>   , RedLeaf> tm_BlueTreeLeaf_RedLeaf = new TreeManager<BlueTree<Leaf>,    RedLeaf>((Class<BlueTree<Leaf>>)    new BlueTree<Leaf>   ().getClass());

        System.out.println(tm_TreeLeaf_RedLeaf       .mTree.getClass());    // class Tree
        System.out.println(tm_BlueTreeLeaf_RedLeaf   .mTree.getClass());    // class BlueTree

        // the following two have compile errors, which is good and expected.
        TreeManager<Tree    <RedLeaf>, Leaf>    tm_TreeRedLeaf_Leaf     = new TreeManager<Tree    <RedLeaf>, Leaf>   ((Class<Tree    <RedLeaf>>) new Tree    <RedLeaf>().getClass());
        TreeManager<BlueTree<RedLeaf>, Leaf>    tm_BlueTreeRedLeaf_Leaf = new TreeManager<BlueTree<RedLeaf>, Leaf>   ((Class<BlueTree<RedLeaf>>) new BlueTree<RedLeaf>().getClass());
    }
}

TreeManager初始化没有问题；行虽然有点长。它也符合描述中的规则。

但是，调用Tree.addChild()inside时会出现编译错误TreeManager，如上图所示。

第三次审判

为了修复第二次试用中的编译错误，我尝试更改类签名（更长）。现在mTree.addChild(subTree);编译没有问题。

// T is not used in the class. T is act as a reference in the signature only
public class TreeManager3<T, NodeType extends Tree<T>, DataType extends T> {
    private NodeType mTree;

    public TreeManager3(Class<NodeType> ClassNodeType) {
        try {
            mTree = ClassNodeType.newInstance();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void managerAddChild(final NodeType subTree) {
        mTree.addChild(subTree);    // compile-error is gone
    }
}

我已经用与第二次试验非常相似的代码对其进行了测试。就像第二次试验一样，它没有任何问题。（甚至更长。）

（您可以跳过下面的代码块，因为它只是在逻辑上重复。）

public static void main(String[] args) {
    @SuppressWarnings("unchecked")
    TreeManager3<Leaf   , Tree    <Leaf>   , Leaf>    tm_TreeLeaf_Leaf           = new TreeManager3<Leaf   , Tree    <Leaf>,    Leaf>   ((Class<Tree    <Leaf>>)    new Tree    <Leaf>   ().getClass());
    TreeManager3<RedLeaf, Tree    <RedLeaf>, RedLeaf> tm_TreeRedLeaf_RedLeaf     = new TreeManager3<RedLeaf, Tree    <RedLeaf>, RedLeaf>((Class<Tree    <RedLeaf>>) new Tree    <RedLeaf>().getClass());
    TreeManager3<Leaf   , BlueTree<Leaf>   , Leaf>    tm_BlueTreeLeaf_Leaf       = new TreeManager3<Leaf   , BlueTree<Leaf>,    Leaf>   ((Class<BlueTree<Leaf>>)    new BlueTree<Leaf>   ().getClass());
    TreeManager3<RedLeaf, BlueTree<RedLeaf>, RedLeaf> tm_BlueTreeRedLeaf_RedLeaf = new TreeManager3<RedLeaf, BlueTree<RedLeaf>, RedLeaf>((Class<BlueTree<RedLeaf>>) new BlueTree<RedLeaf>().getClass());

    System.out.println(tm_TreeLeaf_Leaf          .mTree.getClass());    // class Tree
    System.out.println(tm_TreeRedLeaf_RedLeaf    .mTree.getClass());    // class Tree
    System.out.println(tm_BlueTreeLeaf_Leaf      .mTree.getClass());    // class BlueTree
    System.out.println(tm_BlueTreeRedLeaf_RedLeaf.mTree.getClass());    // class BlueTree

    @SuppressWarnings("unchecked")
    TreeManager3<Leaf   , Tree    <Leaf>   , RedLeaf> tm_TreeLeaf_RedLeaf     = new TreeManager3<Leaf   , Tree    <Leaf>,    RedLeaf>((Class<Tree    <Leaf>>)    new Tree    <Leaf>   ().getClass());
    TreeManager3<Leaf   , BlueTree<Leaf>   , RedLeaf> tm_BlueTreeLeaf_RedLeaf = new TreeManager3<Leaf   , BlueTree<Leaf>,    RedLeaf>((Class<BlueTree<Leaf>>)    new BlueTree<Leaf>   ().getClass());

    System.out.println(tm_TreeLeaf_RedLeaf       .mTree.getClass());    // class Tree
    System.out.println(tm_BlueTreeLeaf_RedLeaf   .mTree.getClass());    // class BlueTree

    // the following two have compile errors, which is good and expected.
    TreeManager3<RedLeaf, Tree    <RedLeaf>, Leaf>    tm_TreeRedLeaf_Leaf     = new TreeManager3<RedLeaf, Tree    <RedLeaf>, Leaf>   ((Class<Tree    <RedLeaf>>) new Tree    <RedLeaf>().getClass());
    TreeManager3<RedLeaf, BlueTree<RedLeaf>, Leaf>    tm_BlueTreeRedLeaf_Leaf = new TreeManager3<RedLeaf, BlueTree<RedLeaf>, Leaf>   ((Class<BlueTree<RedLeaf>>) new BlueTree<RedLeaf>().getClass());
}

但是，当我尝试调用时出现问题TreeManager3.managerAddChild()。

tm_TreeLeaf_Leaf.managerAddChild(new Tree<Leaf>());
tm_TreeLeaf_Leaf.managerAddChild(new Tree<RedLeaf>());      // compile error: managerAddChild(Tree<RedLeaf>) cannot cast to managerAddChild(Tree<Leaf>)
tm_TreeLeaf_Leaf.managerAddChild(new BlueTree<Leaf>());
tm_TreeLeaf_Leaf.managerAddChild(new BlueTree<RedLeaf>());  // compile error: managerAddChild(BlueTree<RedLeaf>) cannot cast to managerAddChild(BlueTree<Leaf>)

这是可以理解的。TreeManager3.managerAddChild(NodeType)表示并且参数类型TreeManager3.managerAddChild(Tree<T>)中没有通配符，和初审一样。Tree<? extends T>Tree.addChild(final Tree<? extends T> subTree)

请求您的帮助...

我已经没有想法了。为了解决这个问题，我是否走错了方向？我花了很多时间输入这个问题，并尽我最大的努力使其更具可读性、更易于理解和遵循。我不得不说抱歉，它仍然很长而且很冗长。但是，如果您知道路，请您帮忙，或者请给我您的任何想法？非常感谢您的每一个输入。非常感谢！

编辑＃1（下面的评论）

基于First Trial，只允许mChildren通过addChild()（以及其他带有isAssignableFrom()检查的方法）进行修改，因此即使允许用户继承Tree和覆盖addChild()也不会破坏 Tree 的完整性。

/developer/util/Tree.java

package developer.util;

import java.util.ArrayList;

public class Tree<T> {

    private Tree<? super T> mParent;
    private final ArrayList<Tree<? extends T>> mChildren = new ArrayList<Tree<? extends T>>();

    public int getChildCount() { return mChildren.size(); }
    public Tree<? extends T> getLastChild() { return mChildren.get(getChildCount()-1); }

    public void addChild(final Tree<? extends T> subTree) {
        if (this.getClass().isAssignableFrom(subTree.getClass()) == false)
            throw new RuntimeException("The child (subTree) must be a sub-class of this Tree.");

        subTree.mParent = this;
        mChildren.add(subTree);
    }
}

/user/pkg/BinaryTree.java

package user.pkg;

import developer.util.Tree;

public class BinaryTree<T> extends Tree<T> {
    @Override
    public void addChild(final Tree<? extends T> subTree) {
        if (getChildCount() < 2) {
            super.addChild(subTree);
        }
    }
}

/Main.java

import user.pkg.BinaryTree;
import developer.util.Tree;

public class Main {

    public static void main(String[] args) {
        Tree<Integer> treeOfInt = new Tree<Integer>();
        BinaryTree<Integer> btreeOfInt = new BinaryTree<Integer>();

        treeOfInt.addChild(btreeOfInt);
        System.out.println(treeOfInt.getLastChild().getClass());
        // class user.pkg.BinaryTree

        try {
            btreeOfInt.addChild(treeOfInt);
        } catch (Exception e) {
            System.out.println(e);
            // java.lang.RuntimeException: The child (subTree) must be a sub-class of this Tree.
        }

        System.out.println("done.");
    }
}

你怎么看？

4

3 回答 3

1

在我看来，这个问题没有完美的解决方案。这基本上是由于类型擦除。Erasure of Generic Methods文章解释了你的函数addChild(final Tree<? extends Leaf> subTree)将成为一个addChild(final Tree subTree)函数。所以，即使你能以某种方式拥有一个通用参数<TreeType extends Tree<? extends Leaf>> addChild(final TreeType subTree)（不是有效的语法！），它也会addChild(final Tree subTree)在编译时被删除。不过，添加运行时测试将起作用，因此您所做的编辑将完成这项工作。

于 2013-10-21T22:30:49.177 回答
0

我认为您需要的是以下内容

class Tree<LT extends Leaf>{
//have your generic add/delete/traverse methods here.
}

class BlueTree<LT extends Leaf> extends Tree<LT>{
//have your blue tree specific add/delete/traverse methods here.
}

class Leaf {
//have basic data members here
}
class BlueLeaf extends Leaf{
//have blue leaf specific data members here
}
于 2014-07-28T15:02:31.820 回答
0

你试过这样的代码吗？

package trees;                                                                                                          

import java.util.ArrayList;                                                                                             

public class Trees {                                                                                                    

    public static void main(String... args) {                                                                           
        Tree<Leaf, Tree<? extends Leaf, ?>> tree_leaf = new Tree<>();                                                   
        BlueTree<Leaf, BlueTree<? extends Leaf, ?>> blueTree_leaf = new BlueTree<>();                                   
        Tree<RedLeaf, Tree<? extends RedLeaf, ?>> tree_redLeaf = new Tree<>();                                          
        BlueTree<RedLeaf, BlueTree<? extends RedLeaf, ?>> blueTree_redLeaf = new BlueTree<>();                          
        //1                                                                                                             
        tree_leaf.addChild(tree_leaf);                                                                                  
        tree_leaf.addChild(tree_redLeaf);                                                                               
        tree_leaf.addChild(blueTree_leaf);                                                                              
        tree_leaf.addChild(blueTree_redLeaf);                                                                           
        //2                                                                                                             
        tree_redLeaf.addChild(tree_redLeaf);                                                                            
        tree_redLeaf.addChild(blueTree_redLeaf);                                                                        
        tree_redLeaf.addChild(tree_leaf);//compile error                                                                
        tree_redLeaf.addChild(blueTree_leaf);//compile error                                                            
        //3                                                                                                             
        blueTree_leaf.addChild(blueTree_leaf);                                                                          
        blueTree_leaf.addChild(blueTree_redLeaf);                                                                       
        blueTree_leaf.addChild(tree_leaf);//compile error                                                               
        blueTree_leaf.addChild(tree_redLeaf);//compile error                                                            
        //4                                                                                                             
        blueTree_redLeaf.addChild(blueTree_redLeaf);                                                                    
        blueTree_redLeaf.addChild(tree_leaf);//compile error                                                            
        blueTree_redLeaf.addChild(tree_redLeaf);//compile error                                                         
        blueTree_redLeaf.addChild(blueTree_leaf);//compile error                                                        

    }                                                                                                                   
}                                                                                                                       

class Tree<Data ,Children extends Tree<? extends Data, ?>> {                                                            

    //important in this question                                                                                        
    private Tree<? super Data, ? super Children> mParent;                                                               
    private Data mData;                                                                                                 
    private ArrayList<Children> mChildren;                                                                              

    // This is the focus of this question, the addChild() method signature                                              
    public void addChild(final Children subTree) {                                                                      
        // add the subTree to mChildren                                                                                 
    }                                                                                                                   

}                                                                                                                       


class BlueTree<Data, Children extends BlueTree<? extends Data, ?>> extends Tree<Data, Children> {                       
}                                                                                                                       

class Leaf {                                                                                                            
}                                                                                                                       

class RedLeaf extends Leaf {                                                                                            
}
于 2014-09-12T20:49:35.827 回答