Homework 3 (Advanced): Creating a Test Harness

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

This assignment uses Java’s built-in List classes. If you don’t already know them, this example shows the basics of creating lists, adding elements, and iterating over lists with a for loop. The LinkedList documentation gives a full list of available methods. If you prefer to use ArrayLists (or some other variant), that is fine. However, I want you to use the collection-class iterators (like the for construct in the linked example) to iterate over the list, rather than a hand-crafted for loop over indices into the list.

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 heap operations 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 that addElt was working propertly on AVL trees. You could write programs to test whether the output is a BST, whether it is balanced, whether it contains the new element, and whether it retained all the elements of the original AVL tree. Your test case would then look something like

  boolean AVLAddTest (Tester t) {
    // your input test
    AVLTree AT = ... // some expression to make an AVL tree
    // your computed output
    AVLTree ATout = AT.addElt(5);
    boolean allTests = (ATout.isBST() &&
                        ATout.isBalanced() &&
                        ATout.hasElt(5) &&
                        ATout.containsEltsOf(AT));
    return t.checkExpect(allTests, true);
  }

This design isn’t ideal for several reasons:

We have to manually construct the allTests answer every time. An better testing framework would have us call some function with a computed answer and a list of tests (ie, functions) to run on that computed answer.
If allTests is false, we have no idea which tests failed. A better framework would report which tests failed, which suggests returning a list of failed tests rather than a boolean.
This design assumes that all of the testing methods are built into the data classes (ie, AVL Trees have isBST, isBalanced, etc). This conflates testing with the programs we want to run. (Not to mention, by definition you should not have an object of the AVL tree class that fails the isBST or isBalanced checks). A better framework would define these testing functions externally so as not to clutter up the classes. This suggests that we should define the testing functions as methods that consume the AVL trees to test.

In this assignment, you will build a testing harness with these better features. We’ll create tests for heaps this week. You may use your testing harness again on another assignment later in the term.

1 Example: A Sorted List Checker in Racket

For those trying to picture what a testing harness looks like, this section sketches out a simple design of a sorted list checker 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.

Here is a first 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.

2 Implementing the Test Harness for Heaps in Java

Building your test harness will require several classes and objects:

The test functions are passed as arguments to the checker, so you will need a class for tests. The class for a test needs fields for the arguments to the test (in this case, two heaps).
We can’t have top-level functions in Java, so each checker must be an object with a method used to execute the test.
We need some data structure to hold the set of tests comprising a checker and that lets us iterate over the tests (to apply each to the given input and output). Lists are ideally suited for this.

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.

You do not need to implement heaps yourself for this assignment. Here are both a binary tree implementation and an initial correct heap implementation to use in writing your tester. This Java file contains several buggy heap implementations (each of which extends DataHeap so that it easy to swap them in and out).

2.1 Create a Simple Heap Checker

Create enough of a testing harness to check whether two heaps have the same number of elements. You’ll need to define a checker that takes a list of tests as input, and set up the methods to execute that list of tests.

Create an interface IHeapTest that requires a run method that consumes two heaps of integers as arguments and returns a boolean.
Create a class sameSize that implements IHeapTest and whose run method returns true if the two input heaps have the same size.
Create a class Checker with one field that holds a list of IHeapTest.
Add a Checker object to your Examples class that has a list containing just the SameSize test. Make sure your code compiles at this point.
Now add a run method to Checker that consumes two heaps (representing the input to and output from the heap function you are testing) and returns a boolean indicating whether all of the tests pass when given those two heaps.
Add some test cases on your SameSize checker.

2.2 Extend the Set of Tests

Next, create additional IHeapTest objects as needed to fully test addElt on heaps. Extend your Examples class (including tests) accordingly.

2.3 Improve 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.

3 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 heaps of integers). We would also want to generate random test data (to help us test at scale).

4 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.

1	Example: A Sorted List Checker in Racket
2	Implementing the Test Harness for Heaps in Java
3	Perspective
4	What to Turn In