Unit Testing Internal State of Data Structure

Question

I have the task of creating implementations for a large number of metric data structures (namely quadtree and k-d tree variants). I've got about four of these implementations down, but the way I am currently testing is not, for my lack of a better word, good.

I need a clean way to test insertion and deletion of data from these tree/trie structures in a way that I can test the internal structures of the nodes (checking parents, children, ordering, etc). These implementations are following separate correctness proofs and runtime analyses, so I need to make sure that not only a node is inserted correctly (meaning, retrievable from the tree later), but also in a very "correct" position in the tree.

"Unit testing" seems like the wrong way to go about this, however, as it's purpose, if I'm not mistaken, is to test a structure or system's external API. I've seen a lot of unit-testing related questions asking "how do I get access to a private field in unit test" or "how do I test a non-public method's return values", and the answer is generally "dont't" - and I agree with this answer.

And so I don't leave anyone willing to help with just vague ramblings, the interface my trees implement is the following (based off the java collection's Map interface):

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's 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 with only the public methods, as I need certain data (children/parent pointers) that is not available from the public interface. Also, in the trie structures (PR Quadtree, PRKDTree, MX variants, etc) have nodes that are separated from data, so creating a public method that returns a "node" will also be abstracted too far to get me the correct data.

What type of testing method (or techniques that I could use with JUnit and not feel like I'm destroying beautiful cognitive boundaries) am I looking for?

Answer 1

There are cases like this where sometimes you really do need to test the internal state of a structure. In this case I would access the internal variables using reflection. There are some JUnit addons (PrivateAccessor http://junit-addons.sourceforge.net/junitx/util/PrivateAccessor.html) that make this easier.

The tradeoff is that your test will be more brittle because if internal state changes, then your test may break. But if you want the confidence that your internal state is correct, sometimes you need to do this.

Answer 2

One method I've used in this type of situation is to make those internal fields protected, and create a subclass for testing. Through that subclass, you can expose whatever state is needed for your white box testing.