1 A Version in Racket
1.1 The Racket Code
1.2 Converting the Racket Design to Java
2 Stage 1: Adding Iteration Methods to Lists
3 Stage 2: Creating a Same Size List Checker
4 Stage 3: Adding the Contains Elt tests to the Checker
5 Stage 4: Improving the Feedback
6 Extra Credit: Add the Is Sorted Check
7 Perspective
8 What to Turn In
9 Grading

Homework 4: Creating a Test Harness

[Starting with this assignment, please create a separate file for each class/interface that you define.]

Writing test cases can be tedious. In some cases, such as tests over very large data or tests of programs that could return one of many possible answers (such as AVL-tree rotation), writing explicit expected answers isn’t even feasible. We need to be able to run such tests in practice though, so what do we do?

Clearly, we need to rethink how we describe expected answers. Rather than write a specific expected answer, we can instead write programs that check various aspects of a correct answer. If a computed answer passes all of these test programs, we consider the test to be successful.

For example, imagine that you want to test a program that sorts a list into increasing order. You could write one program that checks whether the returned list is in sorted order, a second that checks whether the returned list has all of the elements of the original list, and a third that checks whether the two lists have the same size. The test case would then look something like

  boolean SortTest (Tester t) {

    // your input test

    List<Integer> L1 = new ConsList (5, ...)

    // your computed output

    List<Integer> SL = L1.sort;

    boolean allTests = (SL.isSorted() &&

                        SL.sameSize(L1) &&

                        SL.containsEltsOf(L1));

    return t.checkExpect(allTests, true);

  }

This design isn’t ideal for several reasons:

In this assignment, we will start to build a testing harness with these better features. We’ll create tests for sorted lists this week. You will use your testing harness again on another assignment later in the term.

1 A Version in Racket

For those trying to picture what a testing harness looks like, this section sketches out a simple design in Racket. If you want to jump directly to the problems in the next section, feel free to do so. This section does not describe problems or assignment requirements.

1.1 The Racket Code

Here is a straightforward version of the code. The checker is in the last function (sortedListChecker1). The remaining functions define the tests that determine whether a sort function works properly. The andmap function used in hasEltsOf takes a predicate and a list and returns true if the predicate is true of every item in the list. The filter function takes a predicate and a list and returns the list of items from the original list that satisfy the predicate.

  (define (sameSize L1 L2)

    (= (length L1) (length L2)))

  

  (define (hasEltsOf L1 L2)

    (andmap (lambda (elt) (member elt L2)) L1))

  

  (define (allGtEq e L)

    (empty? (filter (lambda (Lelt) (> e Lelt)) L)))

  

  (define (isSorted L)

    (cond [(empty? L) true]

          [(cons? L) (and (allGtEq (first L) (rest L))

                          (isSorted (rest L)))]))

  

  (define (resultSorted L1 L2) (isSorted L2))

  

  (define (sortedListChecker1 Lin Lans)

    (and (sameSize Lin Lans)

         (hasEltsOf Lin Lans)

         (isSorted Lans)))

The sortedListChecker1 function isn’t very general, as it hardcodes the test (remember, our goal is to write a general-purpose testing framework). We first generalize the code by representing the tests as a list (sortedListChecker2), then take the list of tests as a parameter (make-Checker and sortedListChecker3).

  (define (sortedListChecker2 Lin Lans)

    (andmap (lambda (test) (test Lin Lans))

            (list sameSize hasEltsOf resultSorted)))

  

  (define (make-Checker tests)

    (lambda (Lin Lans)

      (andmap (lambda (test) (test Lin Lans))

              tests)))

  

  (define sortedListChecker3

    (make-Checker (list sameSize hasEltsOf resultSorted)))

If you don’t understand how this code is set up, please ask questions before you start working on the Java version. The Java version won’t make sense if you don’t understand what this one is doing.

1.2 Converting the Racket Design to Java

What will we need to do to implement this Racket design in Java?

The following sections break these steps down into stages that will help you test your work incrementally. If you are confident in the course material, you might want to think about how you would break this problem into steps before reading further (it’s a good exercise). You can get partial credit for this assignment by completing the earlier stages, so work from the stages if necessary.

2 Stage 1: Adding Iteration Methods to Lists

Extend your GList (lists via generics) implementation from Homework 3 to satisfy the following interface (a different interface name for your lists is fine, as long as it uses generics):

  interface IGList<T> {

    // returns the size (length) of the list

    int size();

    // determines whether the list contains the given element

    boolean hasElt(T e);

    // returns list of elements for which predicate returns true

    IGList<T> filter(IPred<T> pred);

    // determines whether predicate returns true on all

    //   elements in the list

    boolean andmap(IPred<T> f);

  }

You will need to develop the IPred interface as part of your work. IPred represents a predicate, a function that returns a boolean. Your IPred interface should require a single method called process that consumes an element of the list and returns a boolean. For this assignment, you may assume that you are only testing functions over lists of integers.

3 Stage 2: Creating a SameSize List Checker

In this stage, we will create enough of a testing harness to check whether two lists have the same size. We need to define a checker that takes a list of tests as input, and set up the methods to execute that list of tests.

4 Stage 3: Adding the ContainsElt tests to the Checker

Create a class ContainsAllElts that implements IListTest and whose run method returns true if the second list contains all of the elements of the first list. Use the andmap function that you added to the list classes in Stage 1. Extend your Examples class (including tests) accordingly.

5 Stage 4: Improving the Feedback

Now, we want to extend the testing framework to report the status of each individual test in the list. Edit your framework to print out the result of each test. Do this by adding a toString method to each test, and printing the corresponding string prefixed with either "PASSED" or "FAILED" as appropriate. Figuring out where to put this code is part of the point of the question. Please add a comment to the point where you did this extension to help us find your solution.

6 Extra Credit: Add the IsSorted Check

We have not yet added the check that the returned list is sorted. For extra credit, extend your framework with this ListTest as well.

7 Perspective

We’ve made a lot of headway towards a testing harness in this assignment. Ideally, we would abstract this harness to work over any kind of data (not just lists of integers). We would also want to generate random test data (to help us test at scale). We will return to these and other issues in the coming weeks.

8 What to Turn In

Submit .java files containing the final versions of all classes, interfaces, and examples developed for this assignment. Do not submit the .class files. Submit a separate file for each class/interface (standard for Java) or a single file containing all classes and interfaces.

9 Grading

You will get more points for complete solutions to some stages than partial solutions to all stages.