What test to do next

Section 9.3 What test to do next

An important question is: How do we pick what test to write next. In general there are two guiding ideas:

The test should be teaching us something new about our code.
The test should be close enough to where we are right now, that we could implement it with a few steps.

For your next test choose a test that is doable and that helps you evolve your code.

Subsection 9.3.1 Test 2 insert at the root

Our next test is predictable enough, we need to have an insert method that will add something to the root the first time it’s called (and that’s all we care about for now). So let’s do that:

@Test
public void insertAtRootOnEmptyTree() {
  BSTree<Integer> tree = BSTree.empty();
  tree.insert(5);
  assertEquals((Integer) 5, tree.getRoot());
}

So we create our tree as before, we insert some number in, and then expect to find that number at the root. For some technical reason I had to cast the 5 into an Integer so that the compiler isn’t confused about the various assertEquals methods, try to remove the cast and you’ll see what I mean.

There’s something that bothers me with this code though. I expect the root to have some sort of "node" which contains the value, and possibly left and right children. But right now my method returns just the value stored at the node. Should my tests care about that node class that I use to hold my tree together? Should my users?

This is a tricky balance that you often run into when testing implementations of standard data structures: At the end of the day we want our users to interact with our tree via a certain set of methods that we provide them, what we often refer to as an abstract data type (ADT). So methods like insert, remove, isEmpty etc. We don’t want them to think about the internals.

But we are now trying to build those internals, and we want our tests to drive that process. And that can’t happen unless we verify things along the way. After all, we could implement a class that offers those methods without using a tree (e.g. an array-list that keeps its elements in sorted order would work, albeit slower).

When test-driving the internals of your implementation of an ADT, you must expose in your tests those internals. This can be accomplished by using package-private methods, as opposed to the public methods of the ADT.

So what that means is that our getRoot method should return a BSTreeNode instance. We’ll need do that change then but first we need to change our test, as (Integer) 5 is no longer the right thing to compare to. It sounds like I should be able to create a node with 5 as its value. I’m thinking something as simple as BSTreeNode.node(5) would do it, for now. So our test will change to:

@Test
public void insertAtRootOnEmptyTree() {
  BSTree<Integer> tree = BSTree.empty();
  tree.insert(5);
  assertEquals(BSTreeNode.node(5), tree.getRoot());
}

This will force me to create the BSTreeNode class, then the node static method, then to change the return type of getRoot to return BSTreeNode<T>. Oh hm that means I need to also use a generic for BSTreeNode, duh! But it’s all somewhat straightforward:

class BSTreeNode<T> {
    static <T> BSTreeNode<T> node(T value) {
        return new BSTreeNode<>(value);
    }

    private BSTreeNode(T value) {}
}

Note that I made the class package-private, as it is really meant to only be used by our tests.

At this point I have a test that compiles but fails. It fails for two reasons, the first of them being that my getRoot method still doesn’t do anything useful, and neither does my insert method. The second reason is that we haven’t implemented equality between nodes, we’ll do that afterwards.

Now let’s think about what needs to happen. I could make my getRoot method return BSTreeNode.node(5), but then my first test will break. The fact that I have tests that expect differing return values from getRoot is what will force us to implement it. This technique has a name:

Triangulation: In order for your tests to force you to write a proper implementation of a method, make different test that expect different behavior from that method. Then a dummy implementation will no longer pass both tests.

OK so it’s time for the real work. How do we know what we need to return from getRoot? That’s easy, it’s what they gave us in insert. We need to remember the input to one method of the class in another method of the class. This is exactly what the fields of an object are for. So we need a field, I guess I will call it just root? And getRoot simply returns it, and insert sets it:

public class BSTree<T> {
  private BSTreeNode<T> root;

  ...

  BSTreeNode<T> getRoot() { return root; }

  void insert(T element) {
      root = BSTreeNode.node(element);
  }
}

At this point our tests fail with an obscure message about two nodes not being equal to each other, and all I can tell about those nodes at the moment is that they have different "ids", so they are different objects in memory.

But I think I want to treat my nodes as value objects, i.e. they should be equal if their contents are equal. We learned earlier how to implement that, by providing equals and hashCode implementations. Hm but how should I implement those? Right now all I know about the nodes is that I have a node method I can use to create a node, and it takes in a value entry, but I didn’t even create a field for it yet. I wasn’t forced to by my tests. Well let’s do that, I will change my assertion in the test to this:

assertEquals(BSTreeNode.node(5).value, tree.getRoot().value);

Now this should force me to create a value variable. Then I add the field in my node class:

class BSTreeNode<T> {
    T value;

And now my tests will pass! What joy! Hey wait a minute, I never even set that field! My test just compares null to null, that’s not very helpful.

Oh oh right, my tests should have compared the value to 5 directly, and not to the value from my made-up node. And I will keep the old test around for good measure:

assertEquals((Integer) 5, tree.getRoot().value);
assertEquals(BSTreeNode.node(5), tree.getRoot());

So now the first assertion will fail because I’m not setting the value field, but then the second one will fail until I have a working equals method.

So after we fix the BSTreeNode constructor to store the value parameter in the field, we can now implement equals and hashCode thus:

public boolean equals(Object o) {
  if (this == o) return true;
  if (o == null || getClass() != o.getClass()) return false;
  BSTreeNode<?> that = (BSTreeNode<?>) o;
  return Objects.equals(value, that.value);
}

public int hashCode() {
  return Objects.hash(value);
}

Now our test should finally be passing for good reasons. It is time for the blue phase: refactoring and cleanup.

So what is there to clean up? First of all, I no longer need both assertEquals lines, so now that my equals method works I’ll remove the first assertEquals line. But you can leave it there if you like. I would probably rather write a few node-equality tests instead.

The next thing I want to do is change my previous test a bit. I am now feeling a bit uneasy about the use of assertNull. I think I would like it better if I had a static factory method in my BSTree node that returns the "empty node", even if for now that means just returning null. I prefer how that reads. So this is what the first test would say now:

assertEquals(BSTreeNode.empty(), tree.getRoot());

And the empty method would look like this:

static <T> BSTreeNode<T> empty() {
  return null;
}

There are two cases of code duplication that I am not crazy about. One is the presence of the two tree variables in the two methods, both initialized the same way. It’s probably the case that all my tests will need a tree to get them started, and I could do that by creating a field from my class and initializing it in a setup. method. I am not going to do that because it is going to conflict with another feature I want, which is related to the second of my problems: The second test has two instances of the value 5. It is really important that they are both 5, but I don’t like duplicating them. I also don’t like that I only test this with 5 yet. If someone made it so that the insert method ignores its argument and always puts 5 in, the tests would still pass. I want to triangulate by being able to do that test with two different values there. I am going to achieve that by getting a helper method going on in the test. This method will take 5 as the parameter, then create the tree, insert the value and compare. So it will look like so:

@Test
public void insertAtRootOnEmptyTree() {
  assertInsertingOneMakesRootNode(5);
}

private void assertInsertingOneMakesRootNode(int element) {
  BSTree<Integer> tree = BSTree.empty();
  tree.insert(element);
  assertEquals(BSTreeNode.node(element), tree.getRoot());
}

And now I can simply add another case in the test:

@Test
public void insertAtRootOnEmptyTree() {
  assertInsertingOneMakesRootNode(5);
  assertInsertingOneMakesRootNode(7);
}

Next, I think it would be nice if I didn’t have to write BSTreeNode all the time, so I am going to static import the empty() and node() methods from that class. This makes my tests a little bit shorter, and I like it.

Lastly, I’m thinking I would like a helper method to create a tree from an initial list of elements, inserting them one at a time in order. I’m going to use that in assertInsertingOneMakesRootNode, so that would end up looking like this:

private void assertInsertingOneMakesRootNode(int element) {
  BSTree<Integer> tree = treeWith(element);
  assertEquals(node(element), tree.getRoot());
}
...
private BSTree<Integer> treeWith(Integer... elements) {
  BSTree<Integer> tree = BSTree.empty();
  for (Integer element : elements) tree.insert(element);
  return tree;
}

Ok I am starting to like this. But I better stop so that we can move to our next test. Let’s update our list:

~~empty tree with null root~~
~~insert root~~
insert left
insert right
insert left-left
insert left-right
insert right-left
insert right-right
isEmpty
size
contains value
delete value

Prev Top Next