Software Development book: Cool subtitle here

To see this in action, we will develop a class that holds a binary search tree of objects of some class. If you are not familiar with binary search trees, I would suggest reading up on them first before going through this section.

So we will start by creating a new test class, in our test folder. And we start with a doNothing test. Perhaps within a new bst package for "binary search tree".

package bst;

import org.junit.Test;

public class BSTreeTest {
    @Test
    public void doNothing() {
    }
}

It may seem silly to start with a doNothing method, but it ensures that we have an execution environment, and that we can run our tests, even if they don’t do much yet.

The other weird thing is perhaps the fact that we started with a test class. Shouldn’t we have created the BSTree class first? No, remember our first law. We cannot write production code until we have a test that fails because we haven’t written that code. And that includes a failure to compile. Our laws tell us that we can’t create this class until we have a test that fails because we haven’t.

Do we really need to do it that way? Honestly not really, the world is not going to end because you created the class first. But this is about becoming familiar with the principles of TDD, so that we don’t take shortcuts when it would matter.

Well that seems like a good start. Many concrete tests, then some more vague ones to remind me what I still need to think through. We’ll be adjusting the list as we go.

So for our first test we need to create an empty tree and verify it has null as its root. That should be easy to write with some wishful thinking:

@Test
public void emptyTreeHasNullNode() {
  BSTree<Integer> tree = BSTree.empty();
  assertNull(tree.getRoot());
}

When I type this out there’s all sorts of red, and technically I should have stopped at each point and eliminated the redness. But I’ll do it at this one point, by creating a new BSTree class, setting a static empty method to call its constructor, then a getRoot method that returns null:

package bst;

public class BSTree<T> {
  static <T> BSTree<T> empty() {
    return new BSTree<>();
  }
  private BSTree() {}

  T getRoot() {
    return null;
  }
}

There’s a number of things worth discussing here. First off, notice that I created a static method called empty() to create the empty tree, it felt right. Consequently I also hid the default constructor by declaring it public.

This static method is also one of the first times we get to see generics up close. So the presence of the<T> part in general tells us that this class or method will be making use of this generic variable that stands for another type, and that could end up being any type without affecting our operation. This is called a generic, and it offers what is often called parametric polymorphism: We write our class and it can work with any type for T. This is great, and really useful for a class like our binary search trees. It would be very tedious if we had to create separate classes with identical implementation for each type of values we want to store. So we would have to instead just use Object everywhere, and cast it to something else on the caller side, not pretty at all. Luckily we no longer need to do that.

Normally you specify the <T> at the class definition line, and don’t really need to declare it as such anywhere else, as when the methods are executed on a particular object, a specific type T has been chosen. But that is not the case for the static methods like empty. Therefore we need this funky syntax where we place <T> before the function name, to indicate that this function depends on generic type T that needs to be specified by the caller, and then uses this same type T in the class it creates. In the line static <T> BSTree<T> empty() the first <T> declares the generic parameter, while the second uses that generic parameter to specify the type for the class parameter. In fact we could have used a different letter like S, then the line static <S> BSTree<S> empty() first declares a generic variable S and then uses that variable S as the T in the class definition for BSTree.

Ok that all was a bit technical, you won’t miss much if it didn’t all make sense on a first read. Just come back to it at a later time.

The next interesting thing is the getRoot method. What is interesting about it is that it does the wrong thing! We know that returning null is not always the right thing. But it is simple and good enough to pass our current test. and this is what our third law of TDD tells us: Don’t write more production code than is needed to pass the currently failing test. If we want our getRoot method to do something smarter, we will need to write some more tests. For now, my current test is passing. The technique we just used is called fake it until you make it.

This red-green-blue cycle is pivotal, and is at the heart of TDD. And it is a cycle that is a few minutes long most of the time, because we keep making small steps.