Создайте общее дерево с наследованием

Я создаю общий Tree<T> класс, который поддерживает наследование поддеревьев. Но я столкнулся с некоторыми проблемами. Не могли бы вы помочь мне?

Описание

Определить класс Tree и класс BlueTree, где BlueTree extends Tree.

Определите класс Leaf и класс RedLeaf, где RedLeaf extends Leaf. Они используются как "данные", которые содержат деревья.

A Tree<Leaf> означает дерево типа Tree, а его "данные" имеют тип Leaf.

Для наследования (это не правильное наследование Java):

• a Tree<Leaf> может иметь дочерний тип
  • Tree<Leaf>, Tree<RedLeaf>, BlueTree<Leaf> и BlueTree<RedLeaf>.

.

• a Tree<RedLeaf> может иметь дочерний тип
  • Tree<RedLeaf> и BlueTree<RedLeaf>,
  • , но не Tree<Leaf>, или BlueTree<Leaf>.

.

• a BlueTree<Leaf> может иметь дочерний тип
  • BlueTree<Leaf> и BlueTree<RedLeaf>,
  • , но не Tree<Leaf>, или Tree<RedLeaf>.

.

• a 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

который нарушает

• a 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 изменять 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.");
    }
}

Как вы думаете?

Ответы

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
}

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