java - 継承による汎用ツリーの構築

Question

Tree<T>サブツリーの継承をサポートするジェネリッククラスを作成しています。しかし、私はいくつかの問題に遭遇しました。よろしくお願いします。

説明

TreeクラスとクラスをBlueTree定義しましょうBlueTree extends Tree。

LeafクラスとクラスをRedLeaf定義しましょうRedLeaf extends Leaf。これらは、ツリーに含まれる「データ」として使用されます。

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

違反する

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。

3回目のトライアル

2 回目の試行でコンパイルエラーを修正するために、クラスシグネチャを (さらに長く) 変更してみました。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
    }
}

そして、2 回目の試行と非常によく似たコードでテストしました。2 回目の試行と同様に、問題なく作成されます。（さらに長く。）

(以下のコードブロックは単に論理的に繰り返されているため、スキップしてもかまいません。)

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（以下のコメント用）

First Trialに基づいて、（およびチェック付きの他のメソッド）mChildrenによる変更のみを許可するため、ユーザーの継承とオーバーライドを許可しても、ツリーの整合性が損なわれることはありません。addChild()isAssignableFrom()TreeaddChild()

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

どう思いますか？

score 0 · Accepted Answer

必要なのは以下だと思います

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
}

java - 継承による汎用ツリーの構築

説明

コード

あなたの助けを求めています...

編集＃1（以下のコメント用）

3 に答える 3

Related

Reference