使用inheritance构建通用树
我正在构建一个通用的Tree
类,它支持子树的inheritance。 但我遇到了一些问题。 请你帮帮我吗?
描述
让我们定义Tree
类和BlueTree
类,其中BlueTree extends Tree
。
让我们定义Leaf
类和RedLeaf
类,其中RedLeaf extends Leaf
。 它们被用作树包含的“数据”。
Tree
表示Tree类型的Tree
,其“data”是Leaf
类型。
对于inheritance (这不是适当的Javainheritance):
-
Tree
可以有类型的子项-
Tree
,Tree
,BlueTree
和BlueTree
。
-
。
-
Tree
可以有类型的子项-
Tree
和BlueTree
, - 但不是
Tree
或BlueTree
。
-
。
-
BlueTree
可以有类型的子项-
BlueTree
和BlueTree
, - 但不是
Tree
或Tree
。
-
。
-
BlueTree
可以有类型的子项-
BlueTree
, - 但不是
Tree
,Tree
或BlueTree
。
-
*这里,“孩子”是指树的分支/叶子。
(有点复杂,这就是我将线分开的原因。)
代码
(如果你有一个解决方案,你可能不需要阅读下面我的尝试的详细说明。如果你想一起找到解决方案,我的代码可能会给你一些想法 – 或者,它可能会混淆它们。)
初审 :(简单的)
// This is the focus of this question, the class signature public class Tree { // some fields, but they are not important in this question private Tree mParent; private T mData; private ArrayList<Tree> mChildren; // This is the focus of this question, the addChild() method signature public void addChild(final Tree subTree) { // add the subTree to mChildren } }
该类结构满足描述中的大多数要求。 除此之外,它允许
class BlueTree extends Tree { } class Leaf { } class RedLeaf extends Leaf { } Tree tree_leaf = new Tree(); BlueTree blueTree_leaf = new BlueTree(); blueTree_leaf.addChild(tree_leaf); // should be forbidden
违反了
-
BlueTree
不能具有Tree
类型的子项。
问题是因为,在BlueTree
,它的addChild()
方法签名仍然存在
public void addChild(final Tree subTree) { // add the subTree to mChildren }
理想情况是, BlueTree.addChild()
方法签名被更改(在inheritance时自动)
public void addChild(final BlueTree subTree) { // add the subTree to mChildren }
(注意,此方法不能通过inheritance覆盖上述方法,因为参数类型不同。)
有一个解决方法。 我们可以添加一个类inheritance检查,并为这种情况抛出RuntimeException
:
public void addChild(final Tree subTree) { if (this.getClass().isAssignableFrom(subTree.getClass())) throw new RuntimeException("The parameter is of invalid class."); // add the subTree to mChildren }
但是使它成为编译时错误远比运行时错误好。 我想在编译时强制执行此行为。
二审
第一个试验结构中的问题是,方法addChild()
的参数类型Tree
不是generics类型参数。 因此,在inheritance时不会更新。 这一次,让我们尝试使它成为generics类型参数。
首先,定义一般的Tree
类。
public class Tree { private Tree mParent; private T mData; private ArrayList<Tree> mChildren; /*package*/ void addChild(final Tree subTree) { // add the subTree to mChildren } }
然后是管理Tree
对象的TreeManager
。
public final class TreeManager<NodeType extends Tree, DataType> { private NodeType mTree; public TreeManager(Class 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) // in the type Tree // is not applicable for the arguments (NodeType) } // for testing public static void main(String[] args) { @SuppressWarnings("unchecked") TreeManager<Tree , Leaf> tm_TreeLeaf_Leaf = new TreeManager<Tree , Leaf> ((Class<Tree >) new Tree ().getClass()); TreeManager<Tree , RedLeaf> tm_TreeRedLeaf_RedLeaf = new TreeManager<Tree , RedLeaf>((Class<Tree >) new Tree ().getClass()); TreeManager<BlueTree , Leaf> tm_BlueTreeLeaf_Leaf = new TreeManager<BlueTree, Leaf> ((Class<BlueTree>) new BlueTree ().getClass()); TreeManager<BlueTree, RedLeaf> tm_BlueTreeRedLeaf_RedLeaf = new TreeManager<BlueTree, RedLeaf>((Class<BlueTree>) new BlueTree().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 , RedLeaf> tm_TreeLeaf_RedLeaf = new TreeManager<Tree , RedLeaf>((Class<Tree >) new Tree ().getClass()); TreeManager<BlueTree , RedLeaf> tm_BlueTreeLeaf_RedLeaf = new TreeManager<BlueTree, RedLeaf>((Class<BlueTree>) new BlueTree ().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 , Leaf> tm_TreeRedLeaf_Leaf = new TreeManager<Tree , Leaf> ((Class<Tree >) new Tree ().getClass()); TreeManager<BlueTree, Leaf> tm_BlueTreeRedLeaf_Leaf = new TreeManager<BlueTree, Leaf> ((Class<BlueTree>) new BlueTree().getClass()); } }
TreeManager
初始化没有问题; 虽然线条有点长。 它也符合说明中的规则。
但是,在TreeManager
调用Tree.addChild()
时会出现编译错误,如上所示。
第三次审判
为了修复第二次试用中的编译错误,我尝试更改类签名(甚至更长)。 现在是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, DataType extends T> { private NodeType mTree; public TreeManager3(Class 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> tm_TreeLeaf_Leaf = new TreeManager3<Leaf , Tree , Leaf> ((Class<Tree >) new Tree ().getClass()); TreeManager3<RedLeaf, Tree , RedLeaf> tm_TreeRedLeaf_RedLeaf = new TreeManager3<RedLeaf, Tree , RedLeaf>((Class<Tree >) new Tree ().getClass()); TreeManager3<Leaf , BlueTree , Leaf> tm_BlueTreeLeaf_Leaf = new TreeManager3<Leaf , BlueTree, Leaf> ((Class<BlueTree>) new BlueTree ().getClass()); TreeManager3<RedLeaf, BlueTree, RedLeaf> tm_BlueTreeRedLeaf_RedLeaf = new TreeManager3<RedLeaf, BlueTree, RedLeaf>((Class<BlueTree>) new BlueTree().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 , RedLeaf> tm_TreeLeaf_RedLeaf = new TreeManager3<Leaf , Tree , RedLeaf>((Class<Tree >) new Tree ().getClass()); TreeManager3<Leaf , BlueTree , RedLeaf> tm_BlueTreeLeaf_RedLeaf = new TreeManager3<Leaf , BlueTree, RedLeaf>((Class<BlueTree>) new BlueTree ().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 , Leaf> tm_TreeRedLeaf_Leaf = new TreeManager3<RedLeaf, Tree , Leaf> ((Class<Tree >) new Tree ().getClass()); TreeManager3<RedLeaf, BlueTree, Leaf> tm_BlueTreeRedLeaf_Leaf = new TreeManager3<RedLeaf, BlueTree, Leaf> ((Class<BlueTree>) new BlueTree().getClass()); }
但是,当我尝试调用TreeManager3.managerAddChild()
时出现问题。
tm_TreeLeaf_Leaf.managerAddChild(new Tree()); tm_TreeLeaf_Leaf.managerAddChild(new Tree()); // compile error: managerAddChild(Tree) cannot cast to managerAddChild(Tree) tm_TreeLeaf_Leaf.managerAddChild(new BlueTree()); tm_TreeLeaf_Leaf.managerAddChild(new BlueTree()); // compile error: managerAddChild(BlueTree) cannot cast to managerAddChild(BlueTree)
这是可以理解的。 TreeManager3.managerAddChild(NodeType)
表示TreeManager3.managerAddChild(Tree)
并且没有通配符Tree
在参数类型中Tree
,如第一次试验中的Tree.addChild(final Tree subTree)
。
乞求你的帮助……
我已经没有想法了。 我是否朝错误的方向解决这个问题? 我花了很多时间来输入这个问题,并尽最大努力使其更具可读性,更易于理解和遵循。 我不得不说抱歉它仍然很长而且冗长。 但是如果你知道的话,请你帮忙,或者请你给我任何想法? 您的每一个输入都非常感谢。 非常感谢!
编辑#1(以下评论 )
基于第一次试验 ,只允许通过addChild()
(以及使用isAssignableFrom()
检查的其他方法addChild()
修改isAssignableFrom()
,因此即使允许用户inheritanceTree
并覆盖addChild()
也不会破坏树的完整性。
/developer/util/Tree.java
package developer.util; import java.util.ArrayList; public class Tree { private Tree mParent; private final ArrayList<Tree> mChildren = new ArrayList<Tree>(); public int getChildCount() { return mChildren.size(); } public Tree getLastChild() { return mChildren.get(getChildCount()-1); } public void addChild(final Tree 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 extends Tree { @Override public void addChild(final Tree 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 treeOfInt = new Tree(); BinaryTree btreeOfInt = new BinaryTree(); 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."); } }
你怎么看?
在我看来,这个问题没有完美的解决方案。 这基本上是由于类型擦除。 通用方法的擦除文章解释了你的addChild(final Tree extends Leaf> subTree)
函数将成为addChild(final Tree subTree)
函数。 所以,即使你能以某种方式拥有一个通用参数
(无效的语法!)它将在编译时删除addChild(final Tree subTree)
。 添加运行时测试会起作用,因此您所做的编辑将完成工作。
我想你需要的是以下内容
class Tree{ //have your generic add/delete/traverse methods here. } class BlueTree extends Tree { //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 }
你试过这样的代码吗?
package trees; import java.util.ArrayList; public class Trees { public static void main(String... args) { Tree> tree_leaf = new Tree<>(); BlueTree> blueTree_leaf = new BlueTree<>(); Tree> tree_redLeaf = new Tree<>(); BlueTree> 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> { //important in this question private Tree super Data, ? super Children> mParent; private Data mData; private ArrayList 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> extends Tree { } class Leaf { } class RedLeaf extends Leaf { }