Build A Generic Tree With Inheritance

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>.

* Здесь, "ребенок" означает ветви/листья дерева.

(немного сложнее, поэтому я отделить строки.)

Код

(Если у вас есть решение, вы не можете прочитать подробную иллюстрацию моих попыток ниже . Если вы хотите узнать решение вместе, мой код может дать вам некоторые идеи - или, может перепутать их)

Первый Trial:. (простой один)

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

(Обратите внимание, что этот метод не может переопределить вышеуказанный метод путем наследования, поскольку p Типы араметров различаются.)

Существует обходное решение. Мы можем добавить проверку наследования классов, и бросить 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, как показано выше.

Третий Trial

Чтобы исправить ошибку компиляции во втором испытании, я попытался изменить класс подписи (даже больше). Теперь 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 (для comment below)

основе в первой Trial, только позволяют 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

Как я вижу, идеального решения этой проблемы не существует. Это в основном из-за стирания типа. В статье 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) во время компиляции. Добавление вашего теста времени выполнения будет работать, поэтому сделанное вами редактирование выполнит эту работу.

Answer 2

Я думаю, что вам нужно следующее

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 
} 

Answer 3

пытались ли вы такой код?

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