Chapter 17 Exercise Set 0: Chapter Review

We’ll begin with the setup we have been using since Chapter 13 Exercise Set 1: Introducing Make. You should know where to put things by now, so here are the files to get started.

Makefile:

CC=g++
STD=c++11

build/%.o: src/%.cpp
	@mkdir -p build
	@$(CC) -MM -MT $@ $< > build/$*.d
	$(CC) -c -o $@ $< -std=$(STD)

build/test_lists: build/LinkedList.o build/test_lists.o
	$(CC) -o $@ $^ -std=$(STD)

-include build/*.d

.PHONY: test clean

test: build/test_lists
	./build/test_lists

clean:
	rm -rf build

test_lists.cpp:

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include <doctest.h>
#include <string>
#include "LinkedList.h"
using namespace std;

TEST_CASE("Test can create and render List Nodes") {
    Node* node1 = new Node;
    CHECK(node1->cargo == 0);
}

LinkedList.h:

using namespace std;

struct Node {
    int cargo;
    Node* next;

    // constructors
    Node();
    Node(int);
    Node(int, Node*);
};

LinkedList.cpp:

#include "LinkedList.h"
using namespace std;

Node::Node()
{
    cargo = 0;
    next = nullptr;
}

Node::Node(int cargo)
{
    this->cargo = cargo;
    next = nullptr;
}

Node::Node(int cargo, Node* next)
{
    this->cargo = cargo;
    this->next = next;
}

Add each of the following test cases one at a time to test_lists.cpp and then make the tests pass before adding the next.

1. Create and render list nodes.

   TEST_CASE("Test can create and render List Nodes") {
       Node* node1 = new Node;
       CHECK(node1->cargo == 0);
       Node* node2 = new Node(42);
       CHECK(node2->cargo == 42);
       CHECK(node1->to_string() == "0");
       CHECK(node2->to_string() == "42");
   }
   

2. Link them together.

   TEST_CASE("Test can link nodes together") {
       Node* node1 = new Node(1);
       Node* node2 = new Node(2, node1);
       Node* node3 = new Node(3, node2);
       CHECK(node2->next == node1);
       CHECK(node3->next == node2);
       CHECK(node3->next->next == node1);
   }
   

3. Render a list as a string.

   TEST_CASE("Test can display linked nodes") {
       Node* node1 = new Node(1);
       Node* node2 = new Node(2, node1);
       Node* node3 = new Node(3, node2);
       CHECK(render_list(node3) == "3, 2, 1");
   }
   

4. Render a list backward.

   TEST_CASE("Test can display linked nodes backwards") {
       Node* node1 = new Node(1);
       Node* node2 = new Node(2, node1);
       Node* node3 = new Node(3, node2);
       Node* node4 = new Node(4, node3);
       CHECK(render_list(node4) == "4, 3, 2, 1");
       CHECK(render_list_backward(node4) == "1, 2, 3, 4");
   }
   

5. Now make it “pretty” by putting parenthesis around it.

   TEST_CASE("Test can display linked nodes with parenthesis") {
       Node* node1 = new Node(1);
       Node* node2 = new Node(2, node1);
       Node* node3 = new Node(3, node2);
       Node* node4 = new Node(4, node3);
       CHECK(render_pretty(node4, &render_list) == "(4, 3, 2, 1)");
       CHECK(render_pretty(node4, &render_list_backward) == "(1, 2, 3, 4)");
   }
   

6. Add your own test case for the function remove_second discussed in Modifying linked lists, being careful not to leak memory!

7. Test that you can create a LinkedList object, add elements to the front of it, and render it.

   TEST_CASE("Test can create empty linked list") {
       LinkedList list;
       CHECK(list.to_string() == "Empty list");
       list.insert_in_front(5);
       CHECK(list.to_string() == "5");
       list.insert_in_front(42);
       CHECK(list.to_string() == "42 -> 5");
       list.insert_in_front(9);
       CHECK(list.to_string() == "9 -> 42 -> 5");
   }
   

8. Add tests for a remove_from_front member function and make them pass.