ユニットテストの適切なデータ構造の作成

Question

データ構造が適切に構築されているかどうかをどのようにテストしますか？ある種の修正基数ツリーを実装していますが、データ構造が正しく構築されているかどうかをどのように確認するのか疑問に思っています。

TreeNode {String、Int} ノードのツリーを検討します。 次の例のように、常に0に等しい値の最も深いノードに新しい子を追加します。

Root, 0
- Child_1, 5
- Child_2, 0
   - Child_3, 1

質問は、ツリー構造が希望どおりに構築されているかどうかを単体テストする方法ですか？ TreeNodeには、 insert という1つのメソッドしかありません。

これまでの私のアイデアは、ツリーをたどって各ノードを文字列に変換する TreeVisitor を書くことでした。 上記の例のツリーは次のようになります。

[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]

ツリーを構築するアルゴリズムを知っているので、挿入する要素がわかれば、そのような文字列を手動で作成できます。私の単体テストは次のようになります（同じ例を使用）。

TreeNode root = new TreeNode("Root", 0);
root.insert(new TreeNode("Child_1", 5));
root.insert(new TreeNode("Child_2", 0));
root.insert(new TreeNode("Child_3", 1));
TreeVisitor visitor = new TreeVisitor();
String expected = "[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]";
asssertEquals(expected, visitor.visit(root));

最善のアプローチではないと感じました。まず、訪問者が変わるとすぐにすべてのテストが失敗します（単に [] を（）に変更します）。また、このアプローチにより、非常に小さなツリー（手動で計算できる大きさ）をテストすることができます。大きなものをどのようにテストしますか？

一般的な質問は、データ構造が正しく構築されているかどうかを確認するテストを作成する方法です。

.Sum（a、b）が期待どおりに動作するかどうかをテストする多数のチュートリアルから新鮮だから、テストのアイディア全体が間違っていると思う:-)

Answer 1

これは、動作中のテスト駆動設計の場合のようです。 「挿入」メソッドのみのインターフェースは、使用できないためテストできません。構築したツリーを表示したり、何も操作したりせずにツリーを構築しても、どこにも到達しません。

クライアントがツリーにアクセスする方法（アクセス方法、訪問者インターフェイスなど）を決定します。次に、それらをテストします。

パブリックインターフェイスを介して簡単に取得できない内部の複雑さがある場合（つまり、ツリーはTreeViewに配置するツリーのタイプよりもJava TreeMapに似ています）、次を使用できます。

• アサーションと不変式
• 露出したようなもの debugVerifyTreeメソッド。
• ブルートフォース：36542の擬似ランダムアイテムを挿入し、カバレッジツールを使用してすべてのケースをカバーすることを確認します。

いずれにしても、テストを書くときはいつでも、「このテストが失敗した場合、このコードのクライアントは気にしますか？」という質問を必ずしてください。そうでない場合は、削除します。

Answer 2

おそらく、ユニットテストの TreeNode の実装を、現在の子のセットを再帰的に検査できるメソッドを公開する独自のサブクラスに置き換えることができます。これらのメソッドは、ユニットテストを支援するための TreeNode 実装への追加であり、既存の機能を置き換えることはないため、有効なテストが残っています。

Answer 3

私が通常やっているのは、テスト対象の値または名前を示すことです。そのため、ツリーの場合、名前は深さと子インデックスを示す場合があります。

TreeNode root = new MyTreeNode("0.0", 0);
root.insert(new MyTreeNode("1.0", 5));
root.insert(new MyTreeNode("1.1", 0));
root.insert(new MyTreeNode("2.0", 1));
verify(root, 0, 0);
...
public void verify(TreeNode node, int depth, int index) {
   verifyName(node, depth, index);
   int numChildren = node.getChildCount();
   depth++;
   for (int i = 0; i < numChildren; i++) {
      verify(node.getChildAt(i), depth, i);
   }
}
public void verifyName(TreeNode node, int depth, int index) {
   StringBuilder expectedName = new StringBuilder();
   expectedName.append(depth).append('.').append(index);
   assertEquals("Tree node not in expected place",
                expectedName.toString(), node.getName());
}

今、かなり大きなツリーをテストすることを想像できました。再帰の深さが問題になる場合は、代わりにスタックを使用して再帰メソッドをアンラップできます。

public void verify(TreeNode root) {
   Stack<TreeNode> toBeVerified = new Stack<TreeNode>();
   verifyName(root, 0, 0);
   toBeVerified.push(root);

   while(!toBeVerified.isEmpty()) {
     TreeNode node = toBeVerified.pop();
     int depth = getDepth(node.getName()) + 1;
     int numChildren = node.getChildCount();
     for (int i = 0; i < numChildren; i++) {
        verifyName(node, depth, i);
        toBeVerified.push(node);
     }
   }
}
public int getDepth(String name) {
   return Integer.parseInt(name.substring(0, name.indexOf('.')));
}