criação estrutura de dados adequada teste de unidade

Question

Como seria um teste se a estrutura de dados construída corretamente? Estou implementando tipo de árvore patricia modificado, e se perguntando como é que você verifique se a sua estrutura de dados acumula-se corretamente.

Considere uma árvore de nós TreeNode {String, Int}. Você sempre quer anexar nova criança a mais profunda nó de valor igual a 0, como no seguinte exemplo:

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

A pergunta é, como teste de unidade se estrutura da árvore se acumula como você queria? TreeNode tem apenas um método, que seria insert.

A minha ideia até agora era escrever TreeVisitor que andaria através da árvore e converter cada nó para string. Árvore do exemplo acima, poderia ser assim:

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

Sabendo algoritmo que constrói árvore, eu posso criar tais corda manualmente se tenho idéia do que elementos que eu estou inserindo. Meu teste de unidade ficaria assim (usando mesmo exemplo).

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

Tive a sensação de que não é melhor abordagem. Para iniciar de, assim que mudanças visitante, todos os testes falhará ([ ] mudança simplesmente colocar a ( )). Além disso, esta abordagem permite-me para testar muito pequenas árvores (tão grande quanto eu posso calcular manualmente). Como você testar maiores?

pergunta geral é, como escrever testes verificar se a estrutura de dados acumula-se corretamente ?

Eu suponho que eu poderia estar recebendo toda testes ideia errada, como eu sou fresco de dezenas de tutoriais em teste as pessoas se .sum (a, b) funciona como esperado :-)

Answer 1

Este é parece um caso de Test Driven Design, em ação. Uma interface com apenas um método de 'inserção' não pode ser testada, porque é também inutilizável. A construção de uma árvore, sem ser capaz de ver, ou fazer qualquer coisa com, a árvore que você construiu não leva a lugar nenhum.

Exercite-se como você deseja que os clientes para acessar a árvore (métodos de acesso, interface de visitante, ou qualquer outro). Em seguida, testá-lo através deles.

Se houver complexidade interna que você não pode facilmente chegar a através da interface pública (ou seja, a árvore é mais como um TreeMap Java do que o tipo de árvore que você colocar em um TreeView), você pode usar:

• afirmações e invariantes
• algo como uma exposição debugVerifyTree método.
• força bruta:. Inserção itens 36542 pseudo-aleatórios, use uma ferramenta de cobertura para verificar que cobre todos os casos

Seja como for, a qualquer momento você escrever um teste, certifique-se de fazer a pergunta 'Será que algum cliente deste cuidado de código se este teste falhar?'. Se não, excluí-lo.

Answer 2

Talvez você pode substituir a implementação de TreeNode no teste de unidade com sua própria subclasse que expõe métodos para deixá-lo inspecionar o conjunto atual de crianças de forma recursiva. Estes métodos seriam adições ao TreeNode implementação para o teste de unidade ajuda e não substituiria a sua funcionalidade existente, então você ainda tem um teste válido.

Answer 3

O que eu geralmente acabam fazendo é os valores ou nomes indicativos da coisa que você está testando. Assim, no caso de uma árvore, o nome pode indicar a profundidade eo índice criança.

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

Agora que eu poderia imaginar testando uma árvore bastante grande. Se a profundidade da recursividade é um problema, então você pode desembrulhar o método recursivo com o uso de uma pilha vez.

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