CS 70

Phase 1

Now we'll begin our test-driven development process. You'll implementing the IntList Specifications piece by piece.

In this part, we'll get to a point where we can create empty lists, and check that they really are empty.

The Development Process

We've broken the development of our IntList class into six phases. For each phase you implement, there are four steps that you will go through (in Phase 1 we've done some of them for you, see Coding below):

1. Plan

By drawing pictures and making notes, you will sketch out what you want to do. Your notes/picture should take into account any edge cases that you will need to consider.

You will submit your planning to us by uploading a picture, which we will check for completeness. We will not grade the correctness of your planning.

You should complete this step in the way that is most beneficial to you for understanding what you’re being asked to implement.

2. Write Tests

After you plan, but before you start writing any code, you will add new test code to the appropriate section of the intlist-test.cpp file.

Your tests should be designed to investigate whether the implementation is working properly by checking your actual results against expected results. You should specifically test any edge cases that you identified in planning.

We will run your tests against both working and broken implementations of IntList, and you will be graded for both completeness (your coverage of cases) and for correctness (do your tests check the things that they say they’re checking?).

Because other people need to be able to read your tests and understand what they are doing, make sure you write clear code and also provide suitable comments.

3. Implement

Once you’re satisfied with your planning and test writing, you will implement the function(s) for the step you’re on.

As for all coding parts in CS 70, we will grade your implementation for completeness, correctness, style, elegance, and clarity.

4. Test & Fix

After your implementation is written, you should run your tests to see if your code has any bugs. If your implementation doesn’t pass your tests, you should ask yourself whether the problem is with your implementation (i.e., is your IntList not doing what it’s supposed to be doing) or with your tests (e.g., do your tests make incorrect assumptions or break the rules?)

Fixing problems may require changes to more than one of these steps—your planning, your tests, and/or your implementation. You don’t need to upload revised versions of your planning document, but you should correct your tests and implementation as needed.

We won’t directly grade your verification work, but this step will help you make sure that your “writing tests” and “implementation” submissions are of high quality.

There's also one more “unofficial” step…

Consider Adding More Tests

Now that you've written and tested your code, do you have more ideas for ways it could have gone wrong or conditions that should be verified? Did you cause and catch bugs along the way that your tests wouldn't have caught? Can you add a test to your test suite that would reveal this bug?

Improving the quality of your tests might even catch more bugs in your implementation!

Coding

In this part of the assignment the goal is to develop the following parts of the code:

  • The default constructor.
  • The size() function.
  • The empty() function.

Already-Done Parts

We have already done some of the work for you, following the steps above. You'll find that we have

  1. Planned this part for you—the planning image is in the Planning directory, called Phase_1.jpg, and looks like this:

    Planning image for Phase 1

  2. Written a test called emptyListTest() in intlist-test.cpp.

  3. Written the default constructor and size() functions.

When you get started, all the provided code should compile and the tests can be run. They produce output similar to the following:

intlist DOCKER > ./intlist-test
!! Unexpected exception: std::logic_error -- empty isn't implemented (yet)!
FAILURE (after 0 passes): intlist-test.cpp:46:  myList.empty()

Summary of affirmation failures for empty list (default constructor, info funcs)
----
Fails   / Total Issue
1       / 1     intlist-test.cpp:46:    myList.empty()


Summary of affirmation failures for all tests
----
Fails   / Total Issue
1       / 2     [empty list (default constructor, info funcs)]

As is often the case, the most important information is at the top:

!! Unexpected exception: std::logic_error -- empty isn't implemented (yet)!

The test is failing because empty() hasn't been written yet.

Remaining Implementation Work

We haven't finished all the implementation work for you—you will need to write the empty() function (which should be very straightforward).

Testing

Moving on to step four, do the provided tests reveal any bugs in your implementation? If so, fix them!

Helpful Hints

Read the Spec!

You'll want to have the IntList specifications document open in another window or tab so you consult as you work. Do it!

Using the CS 70 Testing Library

There are help pages for both the overall testing process as well as the the CS 70 testing library that you can refer to.

But as a quick reminder,

  • affirm_expected takes two arguments—the actual value your code produces, and an expected value, often a constant—and compares them. If these values aren't identical, the test fails. Example,
    • affirm_expected(myEmptyBarn.size(), 0);
  • affirm takes a boolean expression as its argument. If the value is false, it counts as a test failure. Example,
    • affirm(myCow.happiness() > 7.5);

As a rule of thumb, use affirm_expected whenever you can, because it will give you more information if the test fails. But if somehow you aren't testing against an expected result value but checking some kind of other condition, you'll need to use affirm.

Compiling Code and Building the Executable

We've provided a Makefile for this assignment, so you should just run make (or cs70-make, if you prefer) to build the code. You shouldn't need to edit the Makefile.

Running the Executable

Remember, you can run the tests two ways, by saying either

./intlist-test

or

valgrind --leak-check=full ./intlist-test

Testing the Tests

You may want to confirm that the emptyListTest() really works by deliberately making empty() return the opposite value and seeing if it detects the problem.

IntList's (Private) selfCheck() Function

You'll notice that most of the IntList member functions call a private function called selfCheck() just before they return.

selfCheck() checks invariants—things that should always be true in any IntList object (except inside a member function when it is halfway through being updated).

selfCheck() uses an assert statement, which is a standard part of both C and C++. Like affirm, it takes a boolean expression. If the statement is true, nothing happens (the program keeps running), but if the statement is false, the program crashes with an error message that tells you which assert statement in the program failed.

  • Rabbit speaking

    Fun fact! It's possible to use the compiler option -DNDEBUG to cause assert statements not to run at all, for folks who want to run with maximum speed and minimum safety.

  • LHS Cow speaking

    We don't really need to know that for class, but it is important to only put “sanity checks” in assert statements, not code that does essential productive work.

Using assert to Test Pre- and Post-Conditions

In addition to invariants, functions often have elements that we know should be true when they're done, or should be true when they're called. You can use assert statements to check these things and crash the program if something isn't the way it is supposed to be.

For example—although the default constructor has been written, you could add an assert(empty()); statement to it to check that when a default-constructed IntList is supposed to be created, it really is created. That's something that we know should be true, but checking to make sure that the things we think should be true actually are true can reveal bugs.

For all the development stages in this part, you'll only be working with

  • intlist-test.cpp (adding code)
  • intlist.cpp (adding code)
  • intlist.hpp (refering back to; perhaps adding comments)

There are other files we'll use in later parts, but you don't need to look at them right now.

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)