Unit-Test korrekte Datenstruktur Erstellung

Question

Wie würde man prüfen, ob Datenstruktur richtig gebaut? Ich bin eine Art modifizierte radix Baum Implementierung und mich gefragt, wie Sie überprüfen, ob Ihre Datenstruktur korrekt aufbaut.

einen Baum von TreeNode {String, Int} Knoten in Betracht. Sie wollen immer neues Kind bis zum tiefstenen Knoten Wert gleich 0 ist, wie in folgendem Beispiel anfügen:

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

Die Frage ist, wie man Unit-Test, wenn Baumstruktur baut, wie Sie wollen? TreeNode hat nur eine Methode, die insert würde.

Meine Idee war so weit TreeVisitor zu schreiben, die durch Baum gehen würde und jeden Knoten in String konvertieren. Baum aus obigem Beispiel könnte wie folgt aussehen:

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

Algorithmus wohl wissend, dass Baum aufbaut, kann ich solche Zeichenfolge manuell erstellen, wenn ich Ahnung, welche Elemente ich einfügen. My Unit-Test wie folgt aus (mit demselben Beispiel) aussehen würde.

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

Ich habe das Gefühl, es ist nicht beste Ansatz. Zum Anfang des, sobald Besucher ändern, werden alle Tests fehlschlagen (einfach ausgedrückt Änderung [ ] ( )). Außerdem ermöglicht dieser Ansatz mir ziemlich kleine Bäume zu testen (so groß wie ich kann manuell berechnen). Wie würden Sie testen Größere?

Allgemeine Frage ist, wie Tests schreiben Überprüfung, ob Datenstruktur korrekt aufbaut ?

Ich nehme an, ich könnte ganz Test Idee falsch bekommen, wie ich aus Dutzend Tutorials frisch bin, wo die Menschen testen, ob .sum (a, b) wie :-)

erwartet funktioniert

Answer 1

Das ist sieht aus wie ein Fall von Test-Driven Design in Aktion. Eine Schnittstelle mit nur einer ‚Einfügen‘ Methode ist nicht überprüfbar, weil es auch nicht verwendbar ist. Der Aufbau eines Baumes, ohne sehen zu können, oder mit irgendetwas zu tun, der Baum Sie gebaut hat man nicht überall.

heraus, wie Sie Kunden wollen den Baum (Zugriffsmethoden, Besucher-Schnittstelle, oder was auch immer) zuzugreifen. Dann testen Sie es durch sie.

Wenn es interne Komplexität man nicht so leicht an durch die öffentliche Schnittstelle bekommen (das heißt der Baum ist mehr wie ein Java TreeMap als die Art des Baumes Sie in einem TreeView setzen) können Sie verwenden:

• Behauptungen und Invarianten
• so etwas wie ein ausgesetzt debugVerifyTree Verfahren.
• Brute-Force: insert 36542 pseudo-zufällige Elemente, ein Coverage-Tool verwenden, um zu überprüfen, dass alle Fälle abdeckt
.

Unabhängig davon, welche Art und Weise kann jedes Mal, wenn Sie einen Test schreiben, stellen Sie sicher, fragen Sie die Frage ‚wird jeder Kunde dieses Codes vorsichtig, wenn dieser Test fehlschlägt?‘. Wenn nicht, löschen Sie es.

Answer 2

Vielleicht können Sie die Implementierung von ersetzen TreeNode in dem Unit-Test mit Ihrer eigenen Unterklasse, die Methoden, die Sie den aktuellen Satz von Kindern rekursiv untersuchen lassen aussetzt. Diese Verfahren würden Ergänzungen der TreeNode Implementierung Unit-Tests zu unterstützen und würde seine bestehende Funktionalität nicht ersetzen, so dass Sie würde immer noch einen gültigen Test haben.

Answer 3

Was ich in der Regel am Ende tun wird, um die Werte oder Namen zu machen, das die Sache, die Sie testen. So im Fall eines Baumes, könnte der Name die Tiefe und das Kind Index anzuzeigen.

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

Jetzt kann ich mich vorstellen, einen ziemlich großen Baum zu testen. Wenn die Tiefe der Rekursion ein Problem ist, dann könnte man die rekursive Verfahren unter Verwendung eines Stapels statt auszupacken.

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