Costruisci un albero generico con ereditarietà

Question

Sto costruendo una classe generica Tree<T>, che supporta l'ereditarietà di sottoalberi. Ma ho riscontrato alcuni problemi. Per favore, per favore, aiutami?

Descrizione

Definiamo la classe e la classe TreeBlueTree, dove BlueTree extends Tree.

Definiamo la classe Leaf e la classe RedLeaf, dove RedLeaf extends Leaf. Sono usati come "dati" che contengono gli alberi.

A Tree<Leaf> indica un albero di tipo Tree ei suoi "dati" sono di tipo Leaf.

Per eredità (questo è non corretta eredità Java):

• un Tree<Leaf> può avere bambino di tipo
  • Tree<Leaf>, Tree<RedLeaf>, BlueTree<Leaf> e BlueTree<RedLeaf>.

.

• un Tree<RedLeaf> può avere bambino di tipo
  • Tree<RedLeaf>, e BlueTree<RedLeaf>,
  • ma nonTree<Leaf> o BlueTree<Leaf>.

.

• un BlueTree<Leaf> può avere bambino di tipo
  • BlueTree<Leaf>, e BlueTree<RedLeaf>,
  • ma nonTree<Leaf> o Tree<RedLeaf>.

.

• un BlueTree<RedLeaf> può avere bambino di tipo
  • BlueTree<RedLeaf>,
  • ma nonTree<Leaf>, Tree<RedLeaf> o BlueTree<Leaf>.

* Qui, "bambino" si intendono i rami/foglie dell'albero.

(un po 'complicato, è per questo che separare le linee.)

Il codice

(Se si dispone di una soluzione, potrebbe non essere necessario leggere l'illustrazione dettagliata dei miei tentativi di sotto . Se si desidera trovare la soluzione insieme, il mio codice può darvi alcune idee - o, li può confondere)

primo processo:. (la semplice)

012.

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

Questa struttura di classe soddisfa la maggior parte dei requisiti della descrizione. Tranne, permette

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 

che viola

• un BlueTree<Leaf>non può avere bambino di tipo Tree<Leaf>.

Il problema è perché, in BlueTree<Leaf>, il suo metodo firma addChild() è ancora

public void addChild(final Tree<? extends Leaf> subTree) { 
    // add the subTree to mChildren 
} 

Il caso ideale è, la firma BlueTree<Leaf>.addChild() metodo viene cambiato (automaticamente, su eredità) per

public void addChild(final BlueTree<? extends Leaf> subTree) { 
    // add the subTree to mChildren 
} 

(notare che questo metodo non può sovrascrivere il metodo precedente per ereditarietà, come la p tipi di arametro differiscono)

C'è una soluzione alternativa. Possiamo aggiungere un controllo di ereditarietà di classe, e gettare RuntimeException per questo caso:

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 
} 

Ma rendendolo un errore di compilazione è molto meglio di un errore di run-time. Mi piacerebbe applicare questo comportamento in fase di compilazione.

secondo processo

Il problema nella prima struttura di prova è, il tipo di parametro Tree nel metodo addChild() non è un parametro di tipo generico. Quindi non sarà aggiornato sull'ereditarietà. Questa volta, proviamo a renderlo anche un parametro di tipo generico.

In primo luogo, definire la classe generale 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 
    } 
} 

Poi il TreeManager che gestisce un oggetto 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()); 
    } 
} 

Le TreeManager inizializza senza problemi; le linee sono un po 'lunghe però. È conforme anche alle regole nella descrizione.

Tuttavia, è presente un errore di compilazione quando si chiama Tree.addChild() all'interno di TreeManager, come illustrato sopra.

terza prova

Per risolvere il compilazione errore nella seconda prova, ho provato a cambiare la firma della classe (a anche più a lungo). Ora mTree.addChild(subTree); compila senza problemi.

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

E l'ho provato con codice molto simile alla seconda prova. Crea senza problemi, come fa il secondo processo. (Basta anche di più.)

(Potete saltare il blocco di codice qui sotto, in quanto è solo logico ripetendo.)

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()); 
} 

Tuttavia, sorge un problema quando provo a chiamare 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>) 

Questo è comprensibile. TreeManager3.managerAddChild(NodeType) significa TreeManager3.managerAddChild(Tree<T>) e non è presente alcun jolly Tree<? extends T> nel tipo di parametro, ad esempio Tree.addChild(final Tree<? extends T> subTree) nella prima prova.

Supplicare per il vostro aiuto ...

ho già a corto di idee. Stavo andando nella direzione sbagliata per risolvere questo problema? Ho passato molto tempo a scrivere questa domanda e ho provato il mio massimo sforzo per renderlo più leggibile, più facile da capire e da seguire. Devo dire scusa che è ancora molto lungo e prolisso. Ma potresti aiutarmi se conosci la strada, o per favore dammi qualche idea che hai? Ogni tuo input è molto apprezzato. Molte grazie!

---

Modifica # 1 (per la comment below)

sede nel primo processo, consentire solo mChildren essere modificato da addChild() (e altri metodi con l'assegno isAssignableFrom()), quindi, anche permettendo l'eredità utente di Tree e l'override di addChild() non interromperà l'integrità dell'albero.

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

Cosa ne pensi?

Answer 1

Come vedo, non esiste una soluzione perfetta a questo problema. Questo è fondamentalmente dovuto alla cancellazione del tipo. L'articolo Erasure of Generic Methods spiega che la tua funzione addChild(final Tree<? extends Leaf> subTree) diventerà una funzione addChild(final Tree subTree). Quindi, anche se si potesse in qualche modo avere un parametro generico <TreeType extends Tree<? extends Leaf>> addChild(final TreeType subTree) (sintassi non valida!) Esso verrebbe cancellato a addChild(final Tree subTree) in fase di compilazione. L'aggiunta del test di runtime funzionerà comunque, quindi la modifica apportata farà il lavoro.

Answer 2

Penso che quello che vi serve è il seguente

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

Hai provato tale codice?

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