Unit testing the internal state of a data structure

Question

I have the task of creating implementations for a large number of metric data structures (namely quadtree and kd tree ). I have about four of these implementations, but the way I am currently testing is, in my absence of a better word, good.

I need a clean way to check the insertion and deletion of data from these tree / trie structures so that I can test the internal structures of the nodes (checking parents, children, ordering, etc.). These implementations follow separate proofs of correctness and runtime analysis, so I need to make sure that not only the node is inserted correctly (which means you can retrieve it from the tree later), but also in a very “correct” position in the tree.

"Unit testing" seems like the wrong way around this, however, since the goal, if I'm not mistaken, is to check the structure or frontend of the API. I saw many questions related to unit testing that ask the question: “How to access the private field in unit test” or “how to check non-returning public methods return values”, and the answer is usually “not 't - and I agree this answer.

And so I do not leave those who want to help with blurry strokes, the interface that implements my trees is the following (based on the interface map of the java collection):

public interface SpatialMap<K, V> extends Iterable<SpatialMap.Entry<K, V>> { // Query Operations /** * Returns the number of key-value mappings in this map. If the map contains more than * <tt>Integer.MAX_VALUE</tt> elements, returns <tt>Integer.MAX_VALUE</tt>. * * @return The number of key-value mappings in this map. */ int size(); /** * Returns <tt>true</tt> if this map contains no key-value mappings. * * @return <tt>true</tt> if this map contains no key-value mappings. */ boolean isEmpty(); /** * Returns <tt>true</tt> if this map contains a mapping for the specified key. * * @param key * The key whose presence in this map is to be tested. * @return <tt>true</tt> if this map contains a mapping for the specified key. */ boolean containsKey(K key); /** * Returns the value to which the specified key is mapped, or {@code null} if this map contains * no mapping for the key. * * <p>A return value of {@code null} does not <i>necessarily</i> indicate that the map contains * no mapping for the key; it also possible that the map explicitly maps the key to * {@code null}. The {@link #containsKey containsKey} operation may be used to distinguish these * two cases. * * @see #put(Comparable, Comparable, Object) * * @param key * The key whose associated value is to be returned. * @return The value to which the specified key is mapped, or {@code null} if this map contains * no mapping for the key. */ V get(K key); // Modification Operations /** * Associates the specified value with the specified key in this map. If the map previously * contained a mapping for the key, the old value is replaced. * * @param key * The key with which the specified value is to be associated. * @param data * The value to be associated with the specified key. * @return The previous value associated with the key, or <tt>null</tt> if there was no mapping * for the key. (A <tt>null</tt> return can also indicate that the map previously * associated <tt>null</tt> with <tt>key</tt>.) */ V put(K key, V data); /** * Removes the mapping for the specified key from this map if present. * * @param key * The key whose mapping is to be removed from the map. * @return The previous value associated with the key, or <tt>null</tt> if there was no mapping * for the key. (A <tt>null</tt> return can also indicate that the map previously * associated <tt>null</tt> with <tt>key</tt>.) */ V remove(K key); // Bulk Operations /** * Removes all of the mappings from this map. The map will be empty after this call returns. */ void clear(); } 

This makes it difficult to test only using public methods, since I need certain data (child / parent pointers) that are not accessible from the public interface. In addition, in trie structures (PR Quadtree, PRKDTree, MX options, etc.) there are nodes that are separate from the data, so creating an open method that returns “node” will also abstract too far to get the right ones data.

What type of testing method (or technique that I can use with JUnit, and don't feel like I'm destroying beautiful cognitive boundaries) I'm looking for?

Answer 1

There are times when sometimes you really need to check the internal state of the structure. In this case, I would gain access to the internal variables using reflection. There are several JUnit add-ons (PrivateAccessor http://junit-addons.sourceforge.net/junitx/util/PrivateAccessor.html ) that make this easier.

The trade-off is that your test will be more fragile, because if the internal state changes, your test may break. But if you need confidence in the correctness of your internal state, sometimes you need to do this.

Answer 2

One of the methods that I used in this situation is to protect these internal fields and create a subclass for testing. Through this subclass, you can open any state needed to test the white box.

Answer 3

If you put the interface and its implementation (s) separately in a dedicated package and create internal state methods for this implementation with package protection , your tests can access them and possibly test them, and the rest of your system cannot.

This is not good for unit testing "purists", but usually, as I do, when I do not want to open the guts of my class for the rest of the system, but I still want to make statements about its internal behavior.