Xây dựng một cây chung với thừa kế

Question

Tôi đang xây dựng một lớp chung Tree<T>, hỗ trợ kế thừa các cây con. Nhưng tôi đã gặp phải một số vấn đề. Bạn vui lòng giúp tôi được không?

Mô tả

Hãy xác định các lớp Tree và BlueTree lớp, nơi BlueTree extends Tree.

Hãy xác định lớp Leaf và lớp RedLeaf, trong đó RedLeaf extends Leaf. Chúng được sử dụng như là "dữ liệu" cây chứa.

A Tree<Leaf> có nghĩa là cây thuộc loại Tree và "dữ liệu" của loại này là loại Leaf.

Đối với thừa kế (đây là không thích Java thừa kế):

• một Tree<Leaf> có thể có con của loại
  • Tree<Leaf>, Tree<RedLeaf>, BlueTree<Leaf> và BlueTree<RedLeaf>.

.

• một Tree<RedLeaf> có thể có con của loại
  • Tree<RedLeaf>, và BlueTree<RedLeaf>,
  • nhưng khôngTree<Leaf>, hoặc BlueTree<Leaf>.

.

• một BlueTree<Leaf> có thể có con của loại
  • BlueTree<Leaf> và BlueTree<RedLeaf>,
  • nhưng khôngTree<Leaf>, hoặc Tree<RedLeaf>.

.

• một BlueTree<RedLeaf> có thể có con của loại
  • BlueTree<RedLeaf>,
  • nhưng khôngTree<Leaf>, Tree<RedLeaf>, hoặc BlueTree<Leaf>.

* Ở đây, "con" nghĩa là cành/lá của cây.

(một chút phức tạp, đó là lý do tại sao tôi tách dòng.)

Mã

(Nếu bạn có một giải pháp, bạn có thể không cần phải đọc hình minh họa tiết của những nỗ lực của tôi dưới đây . Nếu bạn muốn tìm ra giải pháp với nhau, mã của tôi có thể cung cấp cho bạn một số ý tưởng - hay, nó có thể nhầm lẫn giữa chúng)

Đầu tiên Trial:. (một trong những đơn giản)

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

Cấu trúc lớp này đáp ứng hầu hết các yêu cầu trong mô tả. Ngoại trừ, nó cho phép

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 

vi phạm

• một BlueTree<Leaf>không có thể có con của loại Tree<Leaf>.

Vấn đề là bởi vì, trong BlueTree<Leaf>, addChild() phương pháp chữ ký của nó vẫn còn là

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

Trường hợp lý tưởng là, chữ ký BlueTree<Leaf>.addChild() phương pháp được thay đổi (tự động, sau khi thừa kế) để

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

(Lưu ý rằng phương pháp này không thể ghi đè phương thức trên bằng cách thừa kế, dưới dạng p các loại tham số khác nhau.)

Có một giải pháp thay thế. Chúng tôi có thể thêm một tấm séc lớp thừa kế, và ném RuntimeException cho trường hợp này:

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 
} 

Nhưng làm cho nó một lỗi thời gian biên dịch là tốt hơn nhiều so với một lỗi thời gian chạy. Tôi muốn thực thi hành vi này lúc biên dịch.

Second Trial

Các vấn đề trong cấu trúc thử nghiệm đầu tiên là, các tham số kiểu Tree trong phương pháp addChild() không phải là một tham số kiểu generic. Do đó nó sẽ không được cập nhật khi thừa kế. Lần này, chúng ta hãy cố gắng biến nó thành một tham số kiểu generic.

Trước hết, hãy xác định lớp học chung 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 
    } 
} 

Sau đó, TreeManager quản lý đối tượng 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 khởi tạo không có vấn đề gì; các dòng hơi dài. Nó cũng phù hợp với các quy tắc trong phần mô tả.

Tuy nhiên, có lỗi biên dịch khi gọi Tree.addChild() bên trong TreeManager, như minh họa ở trên.

Trial Thứ ba

Để khắc phục các biên dịch lỗi trong thử nghiệm thứ hai, tôi đã cố gắng thay đổi chữ ký lớp (thậm chí lâu hơn). Bây giờ mTree.addChild(subTree); biên dịch không có vấn đề gì.

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

Và tôi đã thử nghiệm mã rất giống với thử nghiệm thứ hai. Nó tạo ra mà không có bất kỳ vấn đề, như thử nghiệm thứ hai nào. (Chỉ cần thậm chí lâu hơn.)

(Bạn có thể bỏ qua khối mã dưới đây, vì nó chỉ là một cách logic lặp đi lặp lại.)

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

Tuy nhiên, một vấn đề nảy sinh khi tôi cố gắng gọi 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>) 

Điều này là dễ hiểu. TreeManager3.managerAddChild(NodeType) nghĩa là TreeManager3.managerAddChild(Tree<T>) và không có ký tự đại diện Tree<? extends T> trong loại thông số, như Tree.addChild(final Tree<? extends T> subTree) trong lần dùng thử đầu tiên.

Đang yêu cầu trợ giúp của bạn ...

Tôi đã hết ý tưởng. Tôi đã đi sai hướng để giải quyết vấn đề này? Tôi đã dành rất nhiều thời gian để đánh máy câu hỏi này và cố gắng hết sức để làm cho nó dễ đọc hơn, dễ hiểu và dễ theo dõi hơn. Tôi phải nói xin lỗi vì nó vẫn còn rất dài và dài dòng. Nhưng bạn có thể vui lòng giúp đỡ nếu bạn biết cách, hoặc xin vui lòng cho tôi bất kỳ ý tưởng bạn có? Mỗi đầu vào của bạn được đánh giá cao. Cảm ơn rất nhiều!

---

Chỉnh sửa # 1 (đối với comment below)

Có trụ sở tại Đầu tiên Trial, chỉ cho phép mChildren phải được sửa đổi bởi addChild() (và các phương pháp khác với việc kiểm tra isAssignableFrom()), vì vậy ngay cả cho phép người sử dụng thừa kế của Tree và ghi đè addChild() sẽ không phá vỡ tính toàn vẹn của cây.

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

Bạn nghĩ sao?

Answer 1

Như tôi thấy, không có giải pháp hoàn hảo cho vấn đề này. Điều này về cơ bản là do loại tẩy xoá. Bài viết Erasure of Generic Methods giải thích rằng hàm addChild(final Tree<? extends Leaf> subTree) của bạn sẽ trở thành một hàm addChild(final Tree subTree). Vì vậy, ngay cả khi bạn bằng cách nào đó có thể có một tham số chung <TreeType extends Tree<? extends Leaf>> addChild(final TreeType subTree) (cú pháp không hợp lệ!), Nó sẽ bị xóa thành addChild(final Tree subTree) lúc biên dịch. Tuy nhiên, việc thêm kiểm tra thời gian chạy của bạn sẽ hoạt động, do đó chỉnh sửa bạn đã thực hiện sẽ thực hiện công việc.

Answer 2

Tôi nghĩ rằng những gì bạn cần là những sản phẩm sau

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

cậu thử mã như vậy?

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