How to unit test internals (organization) of a data structure?

views:

answers:

+2 Q:

How to unit test internals (organization) of a data structure?

I've started working on a little ruby project that will have sample implementations of a number of different data structures and algorithms. Right now it's just for me to refresh on stuff I haven't done for a while, but I'm hoping to have it set up kind of like Ruby Koans, with a bunch of unit tests written for the data structures but the implementations empty (with full implementations in another branch). It could then be used as a nice learning tool or code kata.

However, I'm having trouble coming up with a good way to write the tests. I can't just test the public behavior as that won't necessarily tell me about the implementation, and that's kind of important here. For example, the public interfaces of a normal BST and a Red-Black tree would be the same, but the RB Tree has very specific data organization requirements. How would I test that?

+2 A:

Not sure what you are up to, but if you want to provide common interfaces for various data structures which can then be implemented and/or specialized further in various ways, I don't see how you could write tests for any concrete implementation which does not yet exist.

You can write tests for the common interface to ensure that all implementations fulfill the contract specified by that interface. E.g. all implementations of a sorted tree should order their elements properly etc. As a side note, this wouldn't actually be a unit test but rather functionality / acceptance test.

For red-black trees, you could write a suite of additional (optional) tests though, to verify that the tree is reordered properly after inserts & deletes. This can and should be tested via the public interface nevertheless. E.g. add a series of elements to the tree in a way that would make the tree unbalanced without reordering, then check the tree structure to ensure that it got reordered properly.

Péter Török 2010-04-05 14:14:58

How to publicly expose the internal structure is what I'm not sure about. At least not without making the actual tree nodes publicly accessible, and I'd rather not do that (though that might be OK for my purposes)

Herms 2010-04-05 14:51:34

@Herms I assume that an interface for any collection is not full without methods to access the individual elements. For trees, this would include querying and traversing the children of a node, getting the path to a specific node etc.

Péter Török 2010-04-05 15:08:35

I was mostly thinking of the "interface" to be that of a standard Map-like collection. Though maybe that's not the right way to look at it.

Herms 2010-04-05 15:17:15

@Herms Ah, I see. You are right, a map needs a much narrower interface. I was sort of viewing the question from the tree's other end :-) You could still define a subinterface for tree based maps, which would allow traversal of the map structure. Or an entirely different Tree interface, then have the tree based maps implement both Map and Tree.

Péter Török 2010-04-05 17:39:32

Well, this is ruby, so there aren't really Interfaces as much as "Methods I deign to implement". But yea, thinking about it as a tree object instead of a collection object that happens to use a tree does suggest more methods I could add, which would make testing the tree bits easier.

Herms 2010-04-05 17:41:42

Testing the actual implementation of a class is generally a bad idea. You're much better of testing the contract for each method in the class.

Think about it: if the public interface is the same, wouldn't the unit tests be the same, regardless of the implementation?

A good example of unit tests for data structures (in Java) is the Google Collections framework. It has about 35,000 of them. Note that none of them test the internal implementation: instead they verify the contract for each method and class.

Frederik 2010-04-05 14:23:57

Unit testing is about testing the actual implementation of a class, and it is a very good idea according to lots of people including myself. (However, the tests in question here are not unit tests per definition.)

Péter Török 2010-04-05 14:31:43

Generally I see unit tests as testing the expected behavior of a class, but shouldn't assume anything about the actual implementation (so the class can be refactored or a different algorithm chosen as long as the outwardly visible behavior is still correct). The problem here though is that the internal behavior is part of the contract if you're talking about a specific algorithm, which is what I'm doing here.

Herms 2010-04-05 14:53:18

ansaurus

tags:

views:

answers:

How to unit test internals (organization) of a data structure?

related questions