How is unit test an internal (organization) data structure?

Question

I started working on a small ruby ​​project that will have examples of implementations of a number of different data structures and algorithms. Right now, I'm just updating on things that I haven't been doing for a while, but I hope it is set up like Ruby Koans, with a bunch of unit tests written for data structures, but the implementation is empty (with full implementations in another branch) . It can then be used as a good learning tool or kata code.

However, I am having problems with a good way to write tests. I can’t just check on social behavior, as this will not necessarily tell me about this implementation and what is important here. For example, the common interfaces of a regular BST and a Red-Black tree will be the same, but the RB tree has very specific data organization requirements. How can I check this?

Answer 1

I'm not sure what you need, but if you want to provide common interfaces for various data structures that can then be implemented and / or specialized in different ways, I don’t see how you could write tests for any specific one that does not exist yet.

You can write tests for a common interface to ensure that all implementations conform to the contract specified by that interface. For instance. all implementations of a sorted tree must properly order their elements, etc. As a side note, this will not actually be a unit test, but rather a test / acceptance test.

For red-black trees, you can write a set of additional (optional) tests to make sure that the tree is properly ordered after insertion and deletion. This can and should be tested through an open interface. For instance. add a series of elements to the tree so that the tree is unbalanced without reordering, and then check the tree structure to make sure it is reordered correctly.

Answer 2

Testing the actual implementation of a class is usually a bad idea. You test the contract much better for each method in the class.

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

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