Homework 4

Due Tuesday, November 20 at 11:59pm via turnin.

1 Testing Functions with Multiple Correct Answers

Our data structure functions have introduced a couple of functions that could return one of several answers: remElt on BSTs has this property, as do the addElt and remMinElt functions on heaps.

Writing test cases for such functions clearly requires more than writing a specific, concrete answer (as you are used to doing). Instead, of writing a concrete answer, you have to write a function that checks whether your answer is correct, and run that function within your test case.

For example, assume you had a function isHeap on binary trees that produces a boolean indicating whether the tree satisfies the requirements of a heap. Assume you had a function makeHeap that takes 5 integers and claims to return some heap containing those integers. You could then write test cases as follows:

  boolean test1(Tester t) {
    t.checkExpect(makeHeap(6,3,9,2,5).isHeap(),true);
  }

In other words, you capture the requirements of a valid answer in a function, then call that function to check whether the function you are testing produces the right answer.

For this part of the assignment, your job is to write functions to test the results of addElt and remMinElt on heaps (which may have duplicate elements), then use these functions to write test cases for addElt and remMinElt. The behavior of these functions (and hence what your tester must confirm) is as follows:

The binary tree returned by each must be a heap.
addElt must retain all elements that were in the original heap, while adding only the new element one time.
remMinElt must retain all elements that were in the original heap other than removing one occurrence of the smallest element.

Here are both a binary tree implementation and an initial correct heap implementation to use in writing your tester. Add whatever methods you need to these file to implement your tester. Provide an Examples class that uses your tester to check that the addElt and remMinElt are behaving properly.

This Java file contains several buggy heap implementations (each of which extends DataHeap so that it easy to swap them in and out).

1.1 Summary of Assignment Goals (from Discussion Board)

At a high level, you are writing test cases to check whether a given implementation of addElt and remMinElt are producing the right answer. We have provided both correct and incorrect versions of these methods, so you can test whether your test cases can distinguish from good and bad implementations.

However, writing these tests is a bit trickier than usual because there is no single correct answer. There are multiple correct answers, so your tests need to be asking "did I get _a_ correct answer" (rather than _the_ correct answer).

This assignment is teaching you how to write tests for "_a_ correct answer". The idea is that you write a function that can detect whether a proposed answer is correct, then you use that function to see whether you are getting correct answers.

Your job here is to write two functions: one takes a heap, and element, and a heap and returns true if the second heap is a valid answer to adding the element to the first heap; the other is similar for remMinElt. (Depending on whether you put this method in the heap classes or the examples class would change the exact set of inputs, but this is the idea).

2 Binary Trees over Any Datatype

Right now, our binary trees and heaps are only for integer data. Instead, we would like to be able to make trees and heaps over any kind of data (realistically, you can only use kinds of data that can be ordered, so you know which element to put at the root of a heap, but we’ll set that aside for the moment).

Modify the binary tree and heap classes to work on data of any type (in other words, the classes/interfaces should take the type as a parameter). Rewrite your existing Examples class to create binary trees and heaps of integers using your parameterized data structures.

There is one subtlety to this: once you make the type a parameter, Java cannot be sure that the type you choose to use will allow the numeric comparison operation in isBigger. You therefore need to tell Java that you will only make heaps with types of data that can be compared. The way you do this is by putting an extends constraint on the type parameter, and using Java’s built-in interface Comparable to require a type whose values can be compared. Integer in Java implements Comparable.

Here is an example of a simple class with generics, Comparable, and an isBigger method. Note that the method that Comparable requires is called compareTo. It returns a positive integer, 0, or negative integer to indicate greater than, equal to, or smaller than, respectively.

  class Pair<T extends Comparable<T>> {
    T one;
    T two;

    Pair(T one, T two) {
      this.one = one;
      this.two = two;
    }

    boolean isBiggerThan(Pair<T> other) {
      if (1<=this.one.compareTo(other.one))
        return true;
      else
        return false;
    }
  }

You can use a similar approach when creating a generic version of the binary tree and heap classes.

1	Testing Functions with Multiple Correct Answers
2	Binary Trees over Any Datatype