Homework 3 (Standard)
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 binary tree. 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 a function to test the results of addElt and remMinElt on heaps (which may have duplicate elements). These operations need to behave as follows:
Each must return 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).
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.