How would you test a data structure?

[Steve Luke]

I have to come up with a specific data structure to hold subscriptions for a messaging queue. I couldn't find pre made collections that fit the bill for a variety of reasons, so I decided to roll my own. I thought about it for a while and as a base structure it wouldn't be much different than a hierarchy tree with some special rules for inserting and removing. So my basic structure was going to be something like this:

class TopicTree {
    private static class TopicLevel {
        private final Map<String, TopicLevel> children = //...;
        private final ist<TopicListeners> listeners = //...;

        protected Map<...> getChildren() { return children; }
        protected List<...> getListeners() { return listeners; }
    }

    private final TopicLevel root = new TopicLevel();

    private TopicLevel createTopicLevel() { return new TopicLevel(); } 

    public void subscribe(Topic topic, TopicListener listener) { /* logic */ }
    public boolean hasSubscription(Topic topic) { /* logic */ }
    public List<TopicListeners> getSubscriptions(Topic topic) { /* logic */ }
    public void unsubscribe(Topic topic) { /* logic */ }
}

And maybe other supporting methods. Basically, any Topic would look something like "/root/some/levels/then/a/node" with each portion (in this example delineated by "/") would be translated to a TopicLevel and could have a subscription for it (plus a few wildcards so you can subscribe to many topics at once).

My problem is, I have no idea how to write unit tests for it. I could write tests that put things into the tree (subscribe), then pulls them out (getSubscriptions) and assert that I get what I expect. But then I am testing both the put and get functions in a single test, and a failure could mean a failure in either unit, and just as bad, success could mean a failure in one being hidden by a failure in the other creating a false success. I also thought I might be able to separate the putting from the getting by first putting some things into the tree, then iterating over it, building a representation of what it is holding (a List, or Map or something) and comparing with expectations, but that requires knowledge of the inner-workings (i.e. I would have to get at the root, then iterate recursively through all the children map - the root, the inner class, and the map holding the children all what I would consider implementation details) and so would break if the implementation changes (not to mention I would have to be careful not to require some sort of dependency on returned order).

So how would you (or better, how should I) write tests for this? Or should I consider a different design?

[Tim Cooke]

I would be happy enough with a bunch of tests that do a combination of put and query operations to verify the expected behaviour of of interface. So having tests that call both 'subscribe' and 'getSubscriptions' then do some (one) assertion(s) I think is fine. The problem, as you mention, with doing anything more invasive is that you're now coupling your tests to the implementation.

As a general comment I would suggest that even the name TopicTree is too revealing of the internal structure of the class. Consider extracting an interface and naming it something more generic. Perhaps something like:

public class BalancedTreeTopicStore implements TopicStore {
  // implementation here
}

[Steve Luke]

Okay, Thanks Tim. I think that is the approach I will take - pairing subscribe()s with getSubscriptions().