1 Example: A Sorted List Checker in Racket
2 Implementing the Test Harness for Heaps in Java
2.1 Create a Simple Heap Checker
2.2 Extend the Set of Tests
2.3 Improve the Feedback
3 Perspective
4 What to Turn In

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) &&


    return t.checkExpect(allTests, true);


This design isn’t ideal for several reasons:

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))



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

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.