Unit test proper data structure creation
java, tdd, tree, unit-testing
Solution
This is looks like a case of Test Driven Design in action. An interface with only an 'insert' method is untestable, because it is also unusable. Building a tree, without being able to see, or do anything with, the tree you have built doesn't get you anywhere.
Work out how you want clients to access the tree (access methods, visitor interface, or whatever). Then test it through them.
If there is internal complexity you can't easily get at through the public interface (i.e. the tree is more like a Java TreeMap than the type of tree you put in a TreeView), you can use:
- assertions and invariants
- something like an exposed debugVerifyTree method.
- brute force: insert 36542 pseudo-random items, use a coverage tool to check that covers all cases.
Whichever way, any time you write a test, make sure you ask the question 'will any client of this code care if this test fails?'. If not, delete it.
Problem
How would one test whether data structure built properly? I'm implementing kind of modified radix tree, and been wondering how do you check if your data structure builds up correctly. Consider a tree of `TreeNode {String, Int}` nodes. You always want to append new child to deepest node of value equal to 0, as in following example: ``` Root, 0 - Child_1, 5 - Child_2, 0 - Child_3, 1 ``` Question is, how to unit test if tree structure builds up as you wished? TreeNode only has one method, which would be `insert`. My idea so far was to write `TreeVisitor` that would walk through tree and convert each node to string. Tree from example above, could look like this: ``` [Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]] ``` Knowing algorithm that builds tree, I can create such string manually if I have idea what elements I'm inserting. My unit test would look like this (using same example). ``` 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)); ``` I got the feeling it's not best approach. To start of, as soon as visitor changes, all tests will fail (simply put change `[ ]` to `( )`). Also, this approach allows me to test pretty small trees (as big as I can compute manually). How would you test bigger ones? General question is, how to write tests checking whether data structure builds up correctly? I assume I might be getting whole testing idea wrong, as I'm fresh from dozen tutorials where people test whether .Sum(a, b) works as expected :-)