Data Structures and Algorithms

Lab 1: Testing

Due on Sunday, January 31st at 11:59 PM. This is an individual lab. You are to complete this lab on your own, although you may discuss the lab concepts with your classmates. Remember the Academic Integrity Policy: do not show your code to anyone outside of the course staff and do not look at anyone else’s code for this lab. If you need help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

This lab will focus on automated testing. In this lab, you will learn about:

• Abstraction: you’ll interact with a C++ data structure through its header file (without access to its implementation)
• Testing: you’ll write a series of tests for the data structure using a simple testing framework
• Makefiles: although you won’t be writing one, we’ll see how a Makefile can be used to build and run your code

You can begin by cloning your code repository at git@github.swarthmore.edu:cs35-s16/lab01-<your-username>. Recall that Lab 0 gave instructions for cloning Git repositories from the Swarthmore GitHub.

Testing Your Programs

The process of writing a program can be broken into a few steps:

1. Figure out what you want (e.g. read your lab assignment)
2. Plan how you will teach the computer to solve your problem (i.e. design an algorithm)
3. Write your program as source code
4. Test your program to make sure that it works correctly
5. Repeat the above steps whenever you find bugs or other mistakes

This lab focuses on step 4 above. You should always run your program to make sure that it works correctly in a variety of situations. This requires running your program several times and inspecting the output, which can be exhausting. If you change your program to fix a bug, your change might introduce a new bug. Ideally, you would test every different scenario you could imagine every time you change your program, but that would be tedious and time-consuming.

Conveniently, computer programming is a good solution for tedious, time-consuming tasks. Instead of testing our program manually, we’ll write a tiny program to test our code for us. There are many different forms of testing for software in general; the approach we will use here is called unit testing. We’ll be using an open-source library called UnitTest++ to write our tests.

UnitTest++

In general, unit testing libraries are specific to an environment or language. UnitTest++ is a library which simplifies the process of unit testing in C++. Although UnitTest++ provides a variety of testing operations (which are documented here), we only require a few of them.

• The TEST macro is used to create a single test.

    TEST(my_test) {
        // code and checks go here
    }
  

  Here, my_test is a name you can give the test. The code appearing inside of the braces can be anything you like, but it should be written to check some property of the code you’re testing. We generally want to make tests as simple as possible: each test only tries to check one way in which our code might be used.

• The CHECK_EQUAL macro is used to make sure two values are equal. It takes two arguments: the value we expect and the actual value. For instance:

    TEST(sum_positives) {
        int result = sum(4,5); // imagine a sum function which adds two numbers
        CHECK_EQUAL(9, result); // if result is not 9, the unit testing framework will observe the error
    }
  

  In the above, the first line of code within the test is normal C++ code: it calculates the result of a call to a function named sum and stores it in an int variable named result. The second line verifies that result is equal to 9; if it is not, then UnitTest++ will complain that this test failed and will include the value for result. Make sure you give the arguments in the right order! The CHECK_EQUAL macro requires that the first argument be the value that you expect to get; otherwise, it will produce incorrect error messages.

• The CHECK macro is used to verify a condition. It takes a single argument and fails if that argument is not “true”. (Note: in C++, “true” is not a distinct value like it is in Python or Java; any non-zero value is true and any zero value is false.) For instance:

    TEST(sum_negatives) {
        int result = sum(-1,-2); // again, assume a sum function exists
        CHECK(result < 0); // if the result is not negative, the unit testing framework will complain
    }
  

  The CHECK macro is similar to CHECK_EQUAL: it ensures that a condition holds. CHECK_EQUAL can’t be used as often as CHECK can (since CHECK can address any condition while CHECK_EQUAL can only verify equality), but CHECK_EQUAL produces more precise error messages.

Sets

A set is a simple data type similar to a list. Both sets and lists can hold multiple values. However, lists and sets differ in that:

• Sets are unordered. While each element in a list has a position (or index), elements in a set just exist in the set. That is, $\{1,2,3\}$ and $\{3,1,2\}$ are the same set. (Mathematical convention is to use braces – $\{$ and $\}$ – to represent sets.)
• Elements in a set are unique. A list may contain the same element twice at different positions; a set may only contain a given element once. That is, if we add the element $2$ to the set $\{1,2\}$, we get the same set $\{1,2\}$.

In this lab, you will work with a set interface defined in the header file set.h. You should look at that file. It contains documentation describing the behavior of the Set class. The set.h file is a header file: it contains the interface describing how the class can be used but not the implementation describing what it does. This is important: it means we can write code using the Set without having to think about how it works.

The remainder of this section gives an example of how the Set class might be used.

First, we can create a Set object by declaring a variable of that type.

Set s;

This syntax is a little different from Python or Java and has different meaning: the Set we are creating now will be destroyed at the end of the current function, just like other local variables. It’s important to note that this calls the constructor of the Set class on s, so it’s ready to be used.

Now that we have an empty set, let’s add some numbers to our set now using the add method.

s.add(4);
s.add(6);
s.add(8);

We can determine whether a number is in our set by using the contains method.

s.contains(4); // returns true
s.contains(5); // returns false
s.contains(6); // returns true

We can also determine the number of elements in our set using the size method.

s.size(); // returns 3 (because the set contains 4, 6, and 8)

Now let’s remove a number using the remove method.

s.remove(4); // the set now contains just 6 and 8
s.size(); // so this call will return 2
s.contains(4); // and this call will return false
s.contains(6); // but this call still returns true

Nothing is wrong with adding an existing element or removing an absent one; they just don’t do anything.

s.remove(4); // we already removed 4, so this does nothing
s.remove(9); // s never contained 9, so this does nothing as well
s.add(6); // s already contains 6, so this also has no effect

Of course, we can create more than one set.

Set s2;
s2.add(1);
s2.add(3);

The Set class also has methods to allow two sets to be used together. For instance, add_all will add all of the elements from another set.

s2.add_all(s);
s2.contains(6); // returns true: s2 now contains 6 because s did
s2.contains(4); // returns false: s2 still doesn't contain 4 because s didn't
s.contains(1); // returns false: s wasn't changed and still only contains 6 and 8

We can also use remove_all to remove all of the elements from another set.

s.remove_all(s2); // since s2 contains 1, 3, 6, and 8, all of those would be removed (if they exist)
s.size(); // so now s should be empty; this call returns 0

At the end of this function, the s and s2 objects will be destroyed because they were statically allocated. We will cover during lecture precisely what this means.

Your Assignment

The implementations directory of your Git repository for this lab contains many implementations of the interface given in set.h. Each implementation is stored as an object file (e.g. set04.o). One of these implementations is correct; the rest are intentionally broken in a variety of ways. We will give you descriptions of the different set implementations (but we won’t tell you which description goes with which .o file). Your job will be as follows:

• Write a series of tests for the set interface in the file test_set.cpp. Since every implementation uses the same interface, you can use this one set of tests for every implementation. You must write the tests so that the correct implementation passes every test that you write but that each incorrect implementation fails at least one test. (Some implementations will fail on numerous tests; that’s okay.)
• Once you have written your tests, identify each implementation by pairing its .o file with one of the descriptions below.

Setting Up

Remember from the last lab that your assignment will be submitted by updating the contents of your repository on the Swarthmore GitHub. To get started, you need to clone that repository into your home directory on the CS network:

git clone git@github.swarthmore.edu:cs35-s16/lab01-<your-username>.git

Your initial repository includes a Makefile which you will use to build your code. The first time you run make, it will perform a series of operations that you won’t have to perform again. Go ahead and run make now to get that out of the way.

Testing the Sets

You will write your tests into the file test_set.cpp. Once you have done so, you can compile that file, link it with one of the set implementations, and then run the resulting program. Ordinarily, this could look something like the following:

$ # This next line compiles test_set.cpp into test_set.o
$ c++ -c test_set.cpp
$ # This next line links test_set.o with a set implementation and with UnitTest++
$ c++ -o test_set00 test_set.o implementations/set00.o unittest-cpp/CMakeFiles/UnitTest++.dir/UnitTest++/*.o unittest-cpp/CMakeFiles/UnitTest++.dir/UnitTest++/Posix/*.o
$

That’s rather tedious, of course, so we’ve added rules to the Makefile to help you build your test programs. Instead of the above:

• To compile a program that tests a single implementation, you can run make test_set04. This will create a program test_set04 that you can run with ./test_set04.
• To compile one test program for each implementation, you can run make all. This will create test_set00, test_set01, and so on.

For instance, if I want to run my tests against implementation 6, I could run:

$ make test_set06
c++ -c -o test_set.o test_set.cpp
c++ -o test_set06 test_set.o implementations/set06.o "unittest-cpp/CMakeFiles/UnitTest++.dir/UnitTest++/"/*.o "unittest-cpp/CMakeFiles/UnitTest++.dir/UnitTest++/"/Posix/*.o
$ ./test_set06
Success: 1 tests passed.
Test time: 0.00 seconds.
$

The initial test_set.cpp that you have been provided contains only one test, which creates a set and then destroys it. This is, of course, not very interesting and you have some work to do here. Normally, you would have to invent your own tests to be sure that your code is correct. This involves thinking about behavior your code should (or shouldn’t) have and then writing tests accordingly. This time, however, you will know the behavior of the different implementations; you just don’t know which one is which. So it will be sufficient for you to write tests based on that behavior. Here are descriptions of each of the set implementations you have been provided. Each description is accompanied by a name.

• correct: This is the correct set implementation.
• starts_containing_4: This set contains the number 4 when it is constructed (instead of the new set being empty).
• size_zero: The size of this set is always reported as zero, but every other operation (add, remove, contains, etc.) works just fine.
• has_maximum_size: This set stops working after it reaches a certain size.
• allows_duplicates: This set allows duplicate elements.
• add_destroys_old_elements: Adding an element to this set can cause previously-added elements to be removed.
• add_duplicate_causes_removal: Adding a duplicate element should result in nothing happening; in this implementation, the element is removed from the set entirely.
• no_negatives: This set doesn’t allow negative numbers to be added to it.
• no_remove: This set’s remove method never does anything.
• remove_only_backwards: This set only allows elements to be removed in the opposite order in which they were added. All other removes are ignored.
• remove_always_shrinks: In this set, calling remove changes the size of the set even if the element wasn’t in the set in the first place.
• remove_zeroes_element: In this set, remove replaces the element with a 0 rather than removing it.
• add_all_only_adds_one: In this set, the add_all method only adds one element from its argument.
• add_all_forgets: In this set, calling add_all can result in elements being lost from the set.
• add_all_removes_elements_from_argument: The add_all method of this set changes the argument set, which is supposed to be left alone.
• remove_all_removes_wrong_elements: The remove_all method of this set sometimes removes the wrong elements from the target set.

Identifying the Sets

In addition to writing the tests described above, you will submit a file named matches.txt which will contain a series of matches in the following format:

set00: correct
set01: starts_containing_4
set02: size_zero
set03: has_maximum_size
...

That is, if you believe that set00.o is the correct set implementation, you write a line into the matches.txt file containing the set’s number (e.g. set00) and its name (e.g. correct). Add matches.txt to the same directory in your repository as the test_set.cpp file. If your file is not in this format, you will lose points!

Deliverables

To summarize, you will be submitting two files for this assignment:

• test_set.cpp: A file containing your tests.
• matches.txt: A text file identifying each of the set implementations in the format described above.

Please refer to Lab 0 for the appropriate git commands. Don’t forget to commit, push, and then check the Swarthmore GitHub site to make sure everything turned out okay!