使用继承构建通用树

Question

我正在构建一个泛型Tree<T>类,它支持子树的继承.但我遇到了一些问题.请你帮帮我吗？

描述

让我们定义Tree类和BlueTree类,在哪里BlueTree extends Tree.

让我们定义Leaf类和RedLeaf类,在哪里RedLeaf extends Leaf.它们被用作树所包含的"数据".

A Tree<Leaf>表示类型的树Tree,其"数据"是类型Leaf.

对于继承(这不是适当的Java继承):

• 一个Tree<Leaf>可以有孩子的类型
  • Tree<Leaf>,Tree<RedLeaf>,BlueTree<Leaf>,和BlueTree<RedLeaf>.

.

• 一个Tree<RedLeaf>可以有孩子的类型
  • Tree<RedLeaf>,和BlueTree<RedLeaf>,
  • 但不是 Tree<Leaf>,或BlueTree<Leaf>.

.

• 一个BlueTree<Leaf>可以有孩子的类型
  • BlueTree<Leaf>,和BlueTree<RedLeaf>,
  • 但不是 Tree<Leaf>,或Tree<RedLeaf>.

.

• 一个BlueTree<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

违反了

• 一个BlueTree<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
    }
}

然后TreeManager管理一个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()内部时存在编译错误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(以下评论)

基于第一次试验,只允许mChildren通过addChild()(和其他isAssignableFrom()检查方法)进行修改,因此即使允许用户继承Tree和覆盖addChild()也不会破坏树的完整性.

/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.");
    }
}

你怎么看？

Answer 1

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