Построить родовое дерево с наследованием
Я строю общий Tree<T> класс, который поддерживает наследование поддеревьев. Но я столкнулся с некоторыми проблемами. Не могли бы вы помочь мне?
Описание
Давайте определим Tree класс и BlueTree класс, где BlueTree extends Tree,
Давайте определим Leaf класс и RedLeaf класс, где RedLeaf extends Leaf, Они используются в качестве "данных", которые содержат деревья.
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) в первом испытании.
Прошу помощи...
У меня уже кончились идеи. Я шел в неправильном направлении, чтобы решить эту проблему? Я потратил много времени, набирая этот вопрос, и изо всех сил старался сделать его более читабельным, понятным и понятным. Я должен сказать, извините, что это все еще очень долго и многословно. Но не могли бы вы помочь, если вы знаете способ, или, пожалуйста, дайте мне какие-нибудь идеи, которые у вас есть? Каждый ваш вклад высоко ценится. Большое спасибо!
Edit # 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.");
}
}
Как вы думаете?
3 ответа
На мой взгляд, не существует идеального решения этой проблемы. Это в основном из-за стирания типа. Статья 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) во время компиляции. Добавление вашего теста во время выполнения будет работать, так что внесенные вами изменения будут работать.
Ты пробовал такой код?
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 {
}
Я думаю, что вам нужно следующее
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
}