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?
