The goal of this lab is to introduce you to automated testing, and to think about testing the correctness of a simple data structure. You'll see:

• what a header file is, and how it separates declaration from implementation
• how to write tests using a simple testing framework
• how to test the semantics of a simple data type
• what a Makefile looks like (even if you can't write one yourself yet)

To fetch the skeleton for this assignment run:

$ git clone git@github.swarthmore.edu:cs35-f15/lab2-<your-username>.git

A skeleton version the program will appear in the lab2-<your-username> directory when you run this. This is a solo lab.

For anything beyond the simplest programs, manual testing—by typing in the inputs and looking at the results that come back—is tedious and quickly becomes impractical. Every time a change is made, the manual inputs need to be re-tested, and it’s easy to make a typo that derails the entire testing effort, forcing the tester to redo work. For these reasons, as software gets more complicated, it becomes necessary to test it automatically.

There are a number of strategies for automated testing with all kinds of names and tradeoffs – “integration testing”, “unit testing”, “end-to-end testing”, and more. A discussion of the full spread of testing strategies is beyond the scope of CS35, so we will keep things straightforward in this course. We’ll use an open-source library called UnitTest++ that lets us check for simple properties and reports which tests failed in a summary report.

If you want to see the whole range of checks provided by UnitTest++, you can visit the Documentation. For this assignment, you will only need two check forms: CHECK_EQUAL and CHECK, along with the TEST form that organizes related checks together. There are examples of using TEST and CHECK_EQUAL in the starter files, and we summarize their use here.

• TEST(name) {
    // code and checks...
  }
      

  TEST groups together some normal C++ code and check statements. Any failures get reported together (along with the given name of the TEST block) when the tests are run. For example:

  TEST(numbers) {
    CHECK_EQUAL(1, 1);
    int x = 5 * 5 * 5;
    CHECK_EQUAL(125, x);
    CHECK_EQUAL(25 * 4, x);
  }
      

  A testing file can have any number of TEST blocks in it, which is useful for grouping related checks.

• CHECK(boolean_expr);
    

  The CHECK form evaluates the boolean_expr and tests whether or not it is “true”. Note the scare quotes around true – in C++, any nonzero value counts as true, and 0 counts as false. For example:

  TEST(check) {
    CHECK(1); // passes
    CHECK(-1); // passes
    CHECK(0); // fails
    CHECK(true && (true || false)); // passes
  }
      

• CHECK_EQUAL(expected, actual);
    

  The CHECK_EQUAL form evaluates the expected and actual expressions to values, and then compares them with ==. If that test succeeds, the test passes, otherwise it fails. The framework will report the first expression as the “expected” value and the second as the “actual” value, so it’s a good idea to stick to that convention in your tests. For example:

  TEST(check_equal) {
    CHECK_EQUAL(1, 3); // reports "Expected 1, got 3"
    CHECK(2, 2); // passes
    CHECK(5 * 5, 24); // reports "Expected 25, got 24"
  }
  

A set is a simple data type that holds an unordered collection of elements. In this assignment, we'll just be talking about sets of ints. We can use sets by creating empty sets with the Set constructor (we’ll talk more about constructors in lecture; for now treat Set just like a function that constructs an object, as in Python or Java).

Set s = Set();

We can add integers to the set with the add method:

s.add(37);
s.add(63);

We can check for their presence using the member method:

s.member(37); // returns true
s.member(63); // returns true
s.member(52); // returns false

We can get their size using the size method:

s.size(); // returns 2

We can remove elements using the remove method:

s.remove(37); // removes 37
s.member(37); // returns false now
s.member(63); // returns true still
s.size(); // is 1 now

Finally, sets support intersection and union via intersect_with and union_with:

Set s1 = Set();
s1.add(37);
s1.add(63);
Set s2 = Set();
s2.add(5);
s2.add(63);
s1.union_with(s2);
// now s1 contains 37, 5, and 63 (s2 is unchanged)
Set s3 = Set();
s3.add(5);
s1.intersect_with(s3);
// now s1 contains only 5 (s3 is unchanged)

A summary of this behavior is included in the header file sets.h. That file looks like:

class Set {
public:
  Set();
  ~Set();

  void add(int element);
  void remove(int element);
  bool member(int element);
  int size();

  void intersect_with(Set &other);
  void union_with(Set &other);

private:
  struct SetRep;
  SetRep* setrep;
};

This describes the Set datatype (implemented as a class), but doesn't contain any function bodies for the methods that are declared, like add or member. Those have all been defined for you, but not visible to you, in the files in implementations/.

Recall from lab that the files in implementations/ are called object files, and they are compiled versions of .cpp files. They were generated by running the compiler with the -c option:

> clang++ -c set1.cpp

which builds the object file for later use. Some other call to the compiler will use the object file to provide some definitions that are declared elsewhere (like in a header file). In the case of this assignment, the test_set.cpp file expects some definitions that match what's in the header file. The Makefile links the tests against each particular incorrect implementation, each of which produces a runnable file (a binary) that produces the test results when executed.

Don’t worry if these build details don’t make complete sense to you yet; we’re providing instructions on how to run everything. Mainly I’m describing all this to start to help you develop some intuition by example for how the build process of larger C++ projects work.

The starter lab repository contains a number of implementations of sets, one of which is correct, with the others intentionally broken. Your task for this lab is to write a suite of tests where:

1. All the tests pass on the correct implementation
2. Some test fails on each incorrect implementation

Further, we will provide short descriptions of how the set implementations are broken, but we won't tell you which implementation is broken in which way (and we won't tell you which one is the correct one!). Along with your submission, you will submit a file matches.txt that matches each set implementation number with the description of its behavior, including which implementation is the correct one. Your file should look like (assuming set3 is correct, set2 is no_negatives, etc):

set1: bad_empty_size
set2: no_negatives
set3: correct
set4: bad_empty_remove
set5: bad_add_removes_sometimes
set6: bad_max_100_elements
... all the way through set16

You will add the tests in the test_sets.cpp file (there is an example to get you started). To run the tests, you can do one of a few things:

• > make test_setN
  

  will run your test suite on the implementation numbered N, so you can test each implementation individually if you want to focus on a single one.

• > make test_all
  

  will run your test suite on all the set implementations, so you can see a summary of all the different results.

For example, the starter file you've been given has tests that pass on all the implementations, so you have some work to do. When we run make test_all at the start, we'll see something like:

# lots of build mumbo-jumbo the first time

mint:lab2$ make test_all

set1
Success: 2 tests passed.
Test time: 0.00 seconds.

set2
Success: 2 tests passed.
Test time: 0.00 seconds.

set3
Success: 2 tests passed.
Test time: 0.00 seconds.

set4
Success: 2 tests passed.
Test time: 0.00 seconds.

set5
Success: 2 tests passed.
Test time: 0.00 seconds.

set6
Success: 2 tests passed.
Test time: 0.00 seconds.

set7
Success: 2 tests passed.
Test time: 0.00 seconds.

set8
Success: 2 tests passed.
Test time: 0.00 seconds.

set9
Success: 2 tests passed.
Test time: 0.00 seconds.

set10
Success: 2 tests passed.
Test time: 0.00 seconds.

set11
Success: 2 tests passed.
Test time: 0.00 seconds.

set12
Success: 2 tests passed.
Test time: 0.00 seconds.

set13
Success: 2 tests passed.
Test time: 0.00 seconds.

set14
Success: 2 tests passed.
Test time: 0.00 seconds.

set15
Success: 2 tests passed.
Test time: 0.00 seconds.

set16
Success: 2 tests passed.
Test time: 0.00 seconds.

As tests start to fail (and you detect bad solutions), you'll start to see output like:

set8
test_set.cpp:55:1: error: Failure in my_test_name: Expected 0 but was 1
FAILURE: 1 out of 15 tests failed (1 failures).
Test time: 0.00 seconds.

Output like this means the test at line 55 failed on the set8 implementation. As long as you're confident your test is correct, this means that your test suite has detected something wrong with the set8 implementation. The test you wrote should give you a clue about what's going on, and you can use that information to fill in which problem set8 has in matches.txt.

Each implementation has a short title that you should use in matches.txt to indicate which implementation number matches which description.

• correct –This implementation is completely correct for all the provided methods.
• no_remove –This implementation has a broken remove method that doesn't remove things from the set.
• empty_remove –This implementation has issues using remove on the empty set.
• no_remove2 –This implementation has a broken remove method that has issues removing things from the set that have been added more than once.
• wrong_remove –This implementation has a broken remove method that sometimes removes the wrong thing.
• size_empty –This implementation has a size method that runs into problems with empty sets.
• member_empty –This implementation has a broken member method that runs into problems with empty sets.
• size_duplicates –This implementation has trouble keeping track of the size of sets with duplicate elements.
• size_changing –This implementation has trouble keeping size up to date across many operations.
• max_capacity –This implementation has a maxiumum capacity beyond which it stops working.
• naturals_only –This implementation has trouble adding integers in a particular range.
• add_removes –This implementation has trouble with adding duplicate items.
• intersect++ –This implementation has trouble keeping track of the size of intersected sets.
• disjoint_union – This implementation got the meaning of “union” wrong.
• right_union – This implementation adds everything it should in a union, but doens't remember everything it should.
• weird_union – This implementation has trouble getting some kinds of unions right.

You should edit only matches.txt and test_set.cpp. Add, commit, and push your changes to Github by 11:59PM on Sunday, September 13.