Practicing TDD

Read time: 35 minutes (8865 words)

I have been talking a lot about TDD, it is time to use it to develop an important class.

The TDD Class

This is the first class that will use something called dynamic memory, meaning memory you ask the system for as the program is running. This is a huge advance in your programming skills, because with this concept mastered, you can write code that adapts to the problem, and can us more memory than you can set up at compile time. It is the foundation of most data structures you will need to create.

The TDD Approach

First, remember that we will be writing two different kinds of program components, real code, and test code. This is a new idea, but is really important to grasp!

In this lecture, we will follow three basic rules:

# You cannot write any real code unless it makes a failing test pass.

# You cannot write any more test code than is sufficient to make that test fail. Compilation errors when processing real code are failures.

# You cannot write any more real code than is sufficient to make one failing test pass.

These rules seem ridiculous, they will slow you down, and we are all in a hurry!

That is the point!

Using this approach means one thing that one aspect of your programming is very certainly going to be different. Most of the time, your code works! You will debug less and in the end, you will make progress faster. (Well, you will after you master this technique!)

You will also accumulate a body of tests that can be used to make sure your code does not break when you modify it later on. You will need to add features to that code, and later, after you ahve forgotten everything you knew about the code, your tests will make sure your additions do not mess up your code.

Our TDD Tool

We will use Phil Nash’s catch.hpp tool to build our tests for this lesson.

Assuming the testing framework is in place, we are ready to start development of the Linked List class.

Cycle 1: Starting the Linked List Class

Following the TDD mantra, we write a test we know will fail. This is simple, since we have not written anything yet. Let’s start off by building a new list. By itself, that is not much to test, so we will add one method that will return the number of items in the list. With that method in place, we can test that the number of items in a new list is zero:

tests/test_list.cpp (1)
1
2
3
4
5
6
7
8
#include <catch.hpp>
#include "List.h"

TEST_CASE( "a new list returns a length of zero" ) {
    List list;
    REQUIRE( list.getSize() == 0 );
}

As we would expect, this test fails:

$ make
g++ -c -std=c++11 -MMD -Iincludes tests/test_list.cpp -o tests/test_list.o
tests/test_list.cpp:2:18: fatal error: List.h: No such file or directory
compilation terminated.

We can fix this error by adding the header for the class:

includes/List.h
1
2
3
4
5
6
7
8
9
#pragma once

class List {
    private: 
        int size;
    public:
        int getSize( void );
};

This time, we get a different error. (The compiler complains about a missing reference.) We set up the header, but did not actually add the implementation for the getSize() method. This is called a “red to red” error, and it means we have more work to do to get this test to pass.

Here is the missing implementation code:

lib/List.cpp (1)
1
2
3
4
5
6
#include "List.h"

int List::getSize( void ) {
    return size;
}

$ tests

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tests is a Catch v1.2.1 host application.
run with -? for options

------------------------------------------------------------------------------
 a new list returns a length of zero
------------------------------------------------------------------------------
tests/test_list.cpp:4
..............................................................................

tests/test_list.cpp:6: FAILED:
 REQUIRE( list.getSize() == 0 )
with expansion:
 1988925645 (0x768c98cd) == 0
==============================================================================
test cases: 2 | 1 passed | 1 failed
assertions: 2 | 1 passed | 1 failed

Another “red-to-red” error! The problem here should be apparent. We failed to initialize the size variable. Trying to do this in the header file will generate an error, since C++ is not keen on letting you do that. So, the correct solution is to set up a default constructor where we can do this initialization. We will need that later anyway!

includes/List.h (2)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#pragma once

class List {
    private: 
        int size;
    public:
        List();
        int getSize( void );
};

And the implementation:

lib/List.cpp (3)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include "List.h"

List::List() {
    size = 0;
    list = NULL;
}

int List::getSize( void ) {
    return size;
}

Now we get a passing test! We have completed our first cycle using TDD!

Cycle 2: Creating Nodes for the List

The whole point in building a linked list is to create a place to store data that can grow as we need more room. We will store the data in objects we create from another class. By tradition, this one is called the Node class.

To keep this example simple, our first node class will store a simple integer. However, to create the linked list, each node will need to hold a pointer to another node, creating the link in our linked list.

To test this new node, we will build a test similar to the one we set up for the list. This time, we will set the data value to zero, and initialize our link to NULL which means “points to nothing”“

Here is the first test for our node class:

tests/test_node.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <catch.hpp>
#include "node.h"

TEST_CASE( "a new node has data set to zero and a NULL nest pointer" ) {
    Node node;
    REQUIRE( node.getData() == 0 );
    REQUIRE( node.getNext() == NULL );
}

TEST_CASE( "setting private data works" ) {

Note

From here on, we will not show the failing tests. Trust me, they failed!

Here is the specification of our node class:

includes/Node.h
1
2
3
4
5
6
7
8
#pragma once

class Node {
    private: 
        int data;
        Node * Next;
    public:
        // constructors

And the implementation file:

lib/Node.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "Node.h"
#include <iostream>

/// constructors
Node::Node() {
    this->Next = NULL;
    this->data = 0;
}

/// accessors
int Node::getData( void ) {
    /// return data iten from this node
    return this->data;
}

Node * Node::getNext( void ) {
    /// return pointer to next node
    return this->Next;
}

/// mutators
void Node::setData( int item ) {
    /// update data item
    this->data = item;
}

void Node::setNext( Node * ptr ) {
    /// update pointer to next node
    this->Next = ptr;
}




Here is out test run now:

$ tests
===============================================================================
All tests passed (4 assertions in 3 test cases)

Not bad! We have two cycles completed, and we have a total of four passing tests (counting the sanity check we did initially!)

However, we do not have any nodes hooked into our list yet, so we need to begin actually building the list!

Cycle 3: Accessing Node Private Attributes

Since we made the attributes of our Node objects private, we will need to add methods to set and get those attributes. Here are the tests we will need for these additions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <catch.hpp>
#include "node.h"

TEST_CASE( "setting private data works" ) {
    Node node;
    node.setData( 5 );
    REQUIRE( node.getData() == 5 );
    Node * ptr = &node;
    node.setNext( ptr );
    REQUIRE( node.getNext()->getData() == 5 );
}

There are a few interesting point to make about this code. The data access routines will be pretty simple, and standard get and set methods are all we need. For the Next attribute, the test is a bit trickier. What is going on here is fairly easy to understand. We are making the Next attribute point back to the node it is part of. That makes a loop and if we ask what data item is in the “next” node, we should see the value in the current node. Look closely at the way the access is set up and make sure you can follow it:

  • Node * ptr sets up a pointer variable
  • = &node` sets that pointer to the address of the node object.
  • node.setNext( ptr ) sets the Next attribute so it points back to this node
  • node.getNext() retrieves a pointer to a Node.
  • ->getData() follows the pointer, and asks for the data attribute in that object
  • Finally, we check to make sure we see our own value, the one we set earlier.

Phew! But the test works, and that is what is important!

Adding these methods is pretty simple. Here are the new prototypes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#pragma once

class Node {
    private: 
        int data;
        Node * Next;
    public:
        // constructors
        Node();

        // accessors
        int getData( void );
        Node * getNext( void );

        // mutators
        void setData( int item );
        void setNext( Node * ptr );
};

And here is the code to make these methods work:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "Node.h"
#include <iostream>

/// constructors
Node::Node() {
    this->Next = NULL;
    this->data = 0;
}

/// accessors
int Node::getData( void ) {
    /// return data iten from this node
    return this->data;
}

Node * Node::getNext( void ) {
    /// return pointer to next node
    return this->Next;
}

/// mutators
void Node::setData( int item ) {
    /// update data item
    this->data = item;
}

void Node::setNext( Node * ptr ) {
    /// update pointer to next node
    this->Next = ptr;
}




Cycle 4: Adding a Node to the List Front

We will start off adding items to our list by building a method that will add a node to the front of the list. At this point in the development, we need to get serious about thinking through what might be going on when we call this new method. For instance, the list is either going to be empty, or there will already be nodes hooked into the list. We must deal with both cases. Also, we need to make sure that our list accurately tracks the number of nodes it is managing as new nodes are added! Let’s create a test that checks to see that the size of the list grows as we add a node:

tests/test_list.cpp (3)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include <catch.hpp>
#include "List.h"

TEST_CASE( "adding an item increases the size by one" ) {
    List list;
    int size = list.getSize();
    list.addItem( 5 );
    REQUIRE( list.getSize() == size + 1 );
}

Note that we set up a routine that adds a new item, not a new node. When you build a data container like this, you should hide the details about how the container is actually working from the user. That way, if needed, you can change the entire implementation of your container with out changing the interface to that container! (We might need to change its name, though, if it is no longer a list!)

To make this test pass, we need to create the addItem() method. This method will need to do several things:

  • Create a Node object
  • Save the data item in it
  • Hook the new Node object into the list
  • hook what whatever was in the list previously to the end of this new node

That last step is critical, We need to check to see if there is something already in the list, and hang on to it while we add this new node to the list. We can tel is anything is in the list by checking the list management object. Wait! We have not added an attribute to that object to hold the list of nodes!

1
2
3
    public:
        // mutators
        void addItem( int item );

And the required implementation code:

1
2
3
4
5
6
7
8
void List::addItem( int item ) {
    /// add new item to the list in front
    Node * n = new Node;            // create new node
    n->setData( item );             // save the item
    n->setNext( this->list );       // node point to old list
    this->list = n;                 // list points to new node
    this->size += 1;                // increase list size
}

In this code, we create a new Node object using dynamic memory. The new operator asks the operating system for a chunk of memory big enough to hold the object, and gets back the address of that memory chunk. We will initialize that new (unnamed) object, then hook it to the front of the list. By copying the old list attribute from the List object into the Next attribute in the new object we attach any old list to this node. That is exactly what we want if this list is to become the new first item.

Cycle 5: Walking the List

Now that we have a way to add items to the front of the list, we are in a position to “walk” the list, visiting each node in order. We can print this list our and read it, but to test the new method, we need to do something different.

C++ has a string “sstream” class we can use to construct a string as we walk the list. We can then print this new string out, or compare it to what we want to prove it contains.

Here is a test to make sure the list holds the required data:

1
2
3
4
5
6
7
8
TEST_CASE( "creating a list produces right list" ) {
    List list;
    list.addItem( 1 );
    list.addItem( 2 );
    list.addItem( 3 );
    list.addItem( 4 );
    REQUIRE( list.toString() == "4 3 2 1 " );
}

Here is the new code we need to add to the list class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
string List::toString( void ) {
    /// returns a space separated string with list contents
    stringstream ss;
    Node * ptr = list;
    while( ptr != NULL ) {
        ss << ptr->getData() << " ";
        ptr = ptr->getNext();
    }
    return ss.str();
}

Note that the string we produce using this toString() method will be the nodes in reverse. There will also be a trailing space at the end of the string generated.

Wrapping Up

At this point we have a basic linked list class that we can use as a basis for our simulator. Of course, we need to alter the list to make it hold the vehicles we will be simulating. That is easy to do, but requires copying this List class and changing the data type of the data item. That is simple enough to do, but it raises an interesting point.

What if we want to build a bunch of linked lists, each holding a different data type? Do we have to copy and edit this class a bunch of times?

Actually, no!

We can use a feature of C++ called templates to create a generic linked list class that we can use to create all of the special lists we need. This is not formally part of this course, but here is what it will look like:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include <iostream>
using namespace std;

template<class T>
class Node {
    public:
        T data;
        Node<T> * next;
        Node<T>(const T& d):data(d), next() {}
        Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}
    private:
        Node<T>& operator=(const Node<T>&);
};

template<class T>
class LinkedList {
public:

    Node<T> * head;
    Node<T> * tail;

    LinkedList(const LinkedList& LL);
    LinkedList& operator=(LinkedList byValList);
    LinkedList(): head(NULL), tail(NULL) {}
    LinkedList(Node<T> * newNode) : head(newNode), tail(newNode) {}
    ~LinkedList();

    static LinkedList<int> sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2);

    void insertToTail(T val);
    void insertToHead(T val);
    void print();
    void printBackwards();
};

template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& LL) : head(NULL), tail(NULL) {
    const Node<T> * curr = LL.head;

    if (!head && curr) {
        head = new Node<T>(curr->data);
        tail = head;
        curr = curr->next;
    }

    while (curr) {
        Node<T> * newNode = new Node<T>(curr->data);
        tail->next = newNode;
        tail = newNode;
        curr = curr->next;
    }
}

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList) {
    std::swap(head, byValList.head);
    return *this;
}

template<class T>
LinkedList<T>::~LinkedList() {
    Node<T> * curr = head;
    while (head) {
        head = head->next;
        delete curr;
        curr = head;
    }
}

template<class T>
void LinkedList<T>::insertToTail(T val) {
    Node<T> * newNode = new Node<T>(val);
    if (tail == NULL) {
        newNode->next = tail;
        tail = newNode;
        head = newNode;
        return;
    }
    tail->next = newNode;
    tail = tail->next;
}

template<class T>
void LinkedList<T>::insertToHead(T val) {
    Node<T> * newNode = new Node<T>(val);
    newNode->next = head;
    head = newNode;
    if (head->next == NULL)
        tail = newNode;
}

template<class T>
void LinkedList<T>::print() {
    Node<T> * curr = head;
    while (curr) {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL"<<endl;
}

template<class T>
void LinkedList<T>::printBackwards() {
    Node<T> * curr;
    LinkedList ReversedList(new Node<T>(head->data));
    curr = head->next;
    while (curr) {
        ReversedList.insertToHead(curr->data);
        curr = curr->next;
    }

    curr = ReversedList.head;
    while (curr) {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL\n";
}

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2) {
    Node<T>* curr1 = LL1.head;
    Node<T>* curr2 = LL2.head;

    LinkedList<int> ResultList;

    int newData;
    int carry = 0;

    while (curr1 && curr2) {
        newData = (curr1->data + curr2->data + carry) % 10;
        carry = (curr1->data + curr2->data + carry) / 10;
        ResultList.insertToTail(newData);

        curr1 = curr1->next;
        curr2 = curr2->next;
    }

    while (curr1 || curr2) {
        if (carry) {
            if (curr1)
                ResultList.insertToTail(curr1->data + carry);
            if (curr2)
                ResultList.insertToTail(curr2->data + carry);
            carry = 0;
            continue;
        }
        if (curr1) {
            ResultList.insertToTail(curr1->data);
            curr1 = curr1->next;
        }
        if (curr2) {
            ResultList.insertToTail(curr2->data + carry);
            curr2 = curr2->next;

        }


    }

    return ResultList;
}

int main()
{
    LinkedList<int> LL1(new Node<int>(7));
    LL1.insertToTail(1);
    LL1.insertToTail(6);
    LL1.insertToTail(5);
    LL1.insertToTail(4);

    LinkedList<int> LL2(new Node<int>(5));
    LL2.insertToTail(9);
    LL2.insertToTail(2);

    LinkedList<int> LL = LL1.sumLists(LL1, LL2);
    LL.print();
    LL2.print();
    LL = LL2;
    LL.print();
    LL2.print();

    return 0;
}