Implementing a Stack using Test-Driven Development

Question

I am doing my first steps with TDD. The problem is (as probably with everyone starting with TDD), I never know very well what kind of unit tests to do when I start working in my projects.

Let's assume I want to write a Stack class with the following methods(I choose it as it's an easy example):

Stack<T>
 - Push(element : T)
 - Pop() : T
 - Peek() : T
 - Count : int
 - IsEmpty : boolean

How would you approch this? I never understood if the idea is to test a few corner cases for each method of the Stack class or start by doing a few "use cases" with the class, like adding 10 elements and removing them. What is the idea? To make code that uses the Stack as close as possible to what I'll use in my real code? Or just make simple "add one element" unit tests where I test if IsEmpty and Count were changed by adding that element?

How am I supposed to start with this?

EDIT

Here's my rough tests' implementation:

    [TestMethod]
    public void PushTests() {
        StackZ<string> stackz = new StackZ<string>();

        for (int i = 0; i < 5; ++i) {
            int oldSize = stackz.Size;
            stackz.Push(i.ToString());
            int newSize = stackz.Size;
            Assert.AreEqual(oldSize + 1, newSize);
            Assert.IsFalse(stackz.IsEmpty);
        }
    }

    [TestMethod, ExpectedException(typeof(InvalidOperationException))]
    public void PeekTestsWhenEmpty() {
        StackZ<double> stackz = new StackZ<double>();
        stackz.Peek();
    }

    [TestMethod]
    public void PeekTestsWhenNotEmpty() {
        StackZ<int> stackz = new StackZ<int>();
        stackz.Push(5);

        int firstPeekValue = stackz.Peek();

        for (int i = 0; i < 5; ++i) {
            Assert.AreEqual(stackz.Peek(), firstPeekValue);
        }
    }

    [TestMethod, ExpectedException(typeof(InvalidOperationException))]
    public void PopTestsWhenEmpty() {
        StackZ<float> stackz = new StackZ<float>();
        stackz.Pop();
    }

    [TestMethod]
    public void PopTestsWhenNotEmpty() {
        StackZ<int> stackz = new StackZ<int>();

        for (int i = 0; i < 5; ++i) {
            stackz.Push(i);
        }

        for (int i = 4; i >= 0; ++i) {
            int oldSize = stackz.Size;
            int popValue = stackz.Pop();
            Assert.AreEqual(popValue, i);
            int newSize = stackz.Size;
            Assert.AreEqual(oldSize, newSize + 1);
        }

        Assert.IsTrue(stackz.IsEmpty);
    }

Any corrections/ideas about it? Thanks

Answer 1

I would start like this:

• create() - IsEmpty() == true -> OK
• 2x push() - count() == 2 -> OK
• peek() - T == expected (last pushed) -> OK (peek assumes seek is a typo)
• 2x pop() - count() == 0 && isEmppty -> OK

Answer 2

Start by testing the basic principles of your API.

Test on zero elements.

• Test that it's empty.
• Count is zero.
• Pop fails.

Test on one element:

• Call Push.
• Test that it's not empty.
• Test that count is 1.
• Test that Pop returns the element.
• Test that it's now empty.
• Test that count is now 0.

Test on >1 elements:

• Now Push 2 and test count is two.
• Pop 2 and make sure they come in LIFO order.
• Check the emptiness and counts.

Each of these would be at least one test case.

For example (roughly outlined in Google's unit test framework for c++):

TEST(StackTest, TestEmpty) {
  Stack s;
  EXPECT_TRUE(s.empty());
  s.push(1);
  EXPECT_FALSE(s.empty());
  s.pop();
  EXPECT_TRUE(s.empty());
}

TEST(StackTest, TestCount) {
  Stack s;
  EXPECT_EQ(0, s.count());
  s.push(1);
  EXPECT_EQ(1, s.count());
  s.push(2);
  EXPECT_EQ(2, s.count());
  s.pop();
  EXPECT_EQ(1, s.count());
  s.pop();
  EXPECT_EQ(0, s.count());
}

TEST(StackTest, TestOneElement) {
  Stack s;
  s.push(1);
  EXPECT_EQ(1, s.pop());
}

TEST(StackTest, TestTwoElementsAreLifo) {
  Stack s;
  s.push(1);
  s.push(2);
  EXPECT_EQ(2, s.pop());
  EXPECT_EQ(1, s.pop());
}

TEST(StackTest, TestEmptyPop) {
  Stack s;
  EXPECT_EQ(NULL, s.pop());
}


TEST(StackTest, TestEmptyOnEmptyPop) {
 Stack s;
  EXPECT_TRUE(s.empty());
  s.pop();
  EXPECT_TRUE(s.empty());
}

TEST(StackTest, TestCountOnEmptyPop) {
  Stack s;
  EXPECT_EQ(0, s.count());
  s.pop();
  EXPECT_EQ(0, s.count());
}

Answer 3

If you write out the requirements for each method in a little more detail, that will give you more hints as to the unit tests you need. You can then code up these tests. If you have an autocomplete IDE, like IDEA, then doing TDD is simple, because it underlines all the bits that you haven't implemented yet.

For example, if the requirement is "pop() on an empty stack throws a NoSuchElementException" then you would start with

@Test(exception=NoSuchElementException.class)
void popOnEmptyStackThrowsException()
{
   Stack s = new Stack();
   s.pop();
}

The IDE will then prompt you what to do about the missing Stack class. One of the options is "create class", so you create the class. Then it asks about the pop method, which you also choose to create. Now, you can implement your pop method, putting in what you need to implement the contract. i.e.

T pop() {
   if (size==0) throw new NoSuchElementException();
}

You continue, iteratively in this fashion until you have implemented tests for all the Stack requirements. As before, the IDE will complain that there is no "size" variable. I'd leave this until you create the test case "a newly created stack is empty", where you can then create the variable, since it's initialization is verified in that test.

Once your method requirements are handled, you can then add some more complex use cases. (Ideally these use cases would be specified as class-level requirements.)

Answer 4

Ideally the tests have to cover all functionalities of the class. They should check whether each operation behaves according to its contract. Theoretically speaking, I see the contract as a mapping between <prev state , params> to <new state , returned value>. Therefore, before designing the tests you should define well the contracts of all operations.

Here are some sample tests for the stack API above:

1) Push should increase the value returned by Count() by 1

2) Pop on an empty stack should throw an exception

3) Pop should reduce the value returned by Count() by 1

4) Pushing x1,x2,...,xn and then popping them must return them in reverse order xn,...,x1

5) Adding elements, validating isEmpty()==false and then popping all and validating isEmpty ()==true

6) Seek() must not change the value returned by Count()

7) Consecutive calls to Seek() must return the same value etc...

Answer 5

If you read the book about the Test-Driven development by Kent Beck, you might have noticed an idea that sounds frequently in the book: you should write tests to what you are curently missing. As long as you do not need something, do not write tests and do not implement it.

While your implementation of the Stack class fits your needs, you do not need to thoroughly implement it. Under the hood, it can even return constants to you or do nothing.

Testing should not become overhead to your development, it should speed up your development instead, supporting you when you do not want to keep everything in your head.

The main advantage of the TDD that it makes you write code that is testable in a small lines of code, because usually you do not want to write 50 lines of code to test a method. You become more concerned with interfaces and ditribution of the functionality among classes, because, once again, you do not want to write 50 lines of code to test a method.

Having said that, I can tell you that is not interesting and probably useful to learn TDD by implementing unit tests to superutil interfaces that are gained through suffering of several generation of developers. You will just not feel anynthing exciting. Just take any class from an application written by you and try to write tests to it. Refactoring them will give you much pleasure.