I have a package of code which is suppose to tell me where to allocate elements. When I add a new element it may require repositioning of existing elements to keep my ‘tree’ in a format that promises a log-n search. Ultimately when I hand it a current system and new elements to add I should get a list of where to add new elements, and when/where old elements were moved to.
I want to test that the set returned is valid, but I’m not certain how to. I can easily test if the elements are placed in valid locations, ie locations that won’t break assumptions about my ‘tree’, but this doesn’t ensure that I did the minimal and most efficent movement of elements. However, I can’t think of how to check the moves are efficent without essentially rewriting a large part of the package just to test it’s results.
Since I wrote the package I know some implementation specific details. I know that A will be moved to B because I know exactly what logic was used to decide the move, but this is implementation specific. There are cases where I hae multuple equally valid choices and I pick one way when I could pick another. Is it ‘right’ to do this sort of functional testing by utilizing my understanding of the algorithm to specify specifially what should have moved where? if not how else would I write the test to have any idea that i’m not making the most inefficent, but valid, moves possible?
It sounds like you’re looking to make sure that:
- Your interface is valid
- Your implementation is efficient
- You’re not regressing
Valid interface
Write tests which verify that, for each interface method, the result is a valid one, and leave it at that. If you’re expecting a valid list of locations as an output from a function, check that’s what you’re getting back. If you’re expecting certain inputs to cause exceptions or raise errors, test that. Etc…
Efficient Implementation
You must have some sort of measure of efficiency which you’re using to make sure that your solutions are, indeed, the most efficient possible. Sounds like “number of moves”, in your case.
So, manually create some inputs, for which you manually check that the number of moves is optimal. Then, run the inputs through your algorithm, and check that the number of moves it produces exactly your expectations (maybe also check that the solution is valid, for sanity’s sake). If the number is higher, something is wrong with your algorithm; if the number is lower, something is wrong with your hand-math 😉
Ie, provide a list of inputs and an appropriate, expected measurement of efficiency.
Design the inputs to stress corner cases for any general solution to your problem – inputs for which it’s particularly difficult to come up with efficient solutions, or for which your algorithm might break (and continue executing infinitely, for example).
Regression
Generate/find/obtain a set of real-life reflecting inputs for your algorithm.
Run the algorithm against the inputs.
Record and store valid measurements for the results (measurements from the Efficient Implementation section, and others which are likely not to be dependent on your specific algorithm.
Write tests which make sure that each run of your algorithm on the real data, produces valid results, which exactly match the measurements of know, stable, previous runs.
It sounds like your tests need to cover two things:
- The API of your package – how the outside world will use it
- Internal details of your package – making sure that the current implementation works correctly
So I would write tests in both areas, and divide them up so that their purpose is clear. For example, separate classes, namespaces or packages. If you change the implementation, the first set of tests should be unaffected, ensuring your API is unbroken.