Read the Expectations on Homework and the Homework Tips.
You should organize your solution for this and all remaining labs and homeworks as a Java project (each interface and class definition go into a separate file). If you are using DrJava, refer to the documentation on the project facility.
Writing test cases for such methods 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 method that checks whether your answer meets the requirements of a correct answer and run that method within your test case. In other words, rather than checking whether you got the correct answer, you have to check whether you got a correct answer. This assignment is teaching you how to write tests for situations when you need "a correct answer".
Your job here is to write two methods, the first of which is addEltTester(). addEltTester() takes a heap, an integer, and a binary tree (in that order) and returns true if the binary tree is a valid result of adding the given integer to the first Heap. In other words, you want to fill in
boolean addEltTester(IHeap hOrig, int elt, IBinTree hAdded) {
...code to compare hOrig and hAdded around the addition of elt as appropriate...
}
You can use this to test a given addElt() implementation by writing a test such as
@Test
public void test1(){
assertTrue(addEltTester(myHeap,5,myHeap.addElt(5)));
}
Or, you can provide the binary tree "manually", as in
@Test
public void test2(){
assertTrue(addEltTester(myHeap,5,myBinTree));
}
where myHeap and myBinTree are data that you defined. Note that every heap is also a binary tree, so you can use addElt() to generate binary trees from heaps.
Also provide remMinEltTester, which is similar (but tests remMinElt). For this, fill in
boolean remMinEltTester(IHeap hOrig, IBinTree hRemoved) {
...code to compare hOrig and hRemoved as appropriate...
}
addElt() or remMinElt() (respectively) on the original heap. A valid result is defined by the following conditions: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.
addElt() or remMinElt() on a heap does not modify the heap (this lets you reuse the same heap data in multiple test cases).
For this assignment, heaps may have duplicate elements.
HeapChecker.
You do not need to implement addElt() or remMinElt(). We are giving them to you, along with the other heap operations. Here are both a binary tree implementation and an initial correct heap implementation to use in writing your tester. You are getting both files because we build heaps as subclasses of binary trees.
If you need additional methods on Heaps or BinTrees, modify the classes in these files as needed with your additional methods. Do not change the names of the classes, any of the existing methods, or make your own subclasses (that will break the auto-tester). Just edit these classes and/or interfaces by adding your own additional methods.
DO NOT call addElt() in addEltTester() or remMinElt() in remMinEltTester()!!! Doing so undermines the purpose of this assignment.
test1 above). Limit yourself to no more than six (6) tests for each of the methods. Your job is to check as well as you can within 6 tests whether or not each method functions the way it should.
Note that since your method is in the HeapChecker class, your Examples class will need a HeapChecker object. This means your test cases will look like the following:
class Examples {
Examples(){}
HeapChecker HT = new HeapChecker();
...
@Test
public void test3(){
assertTrue(HT.addEltTester(myHeap, 5, myBinTree));
}
}
where myHeap and myBinTree are data defined in your Examples class.
Put differently, assume you wanted to add 8 to the following heap:
4 / 5Imagine that the addElt code you were using returned
8 / \ 4 5(which is wrong because it isn't a heap [with min elts on top]). Then your addEltTester would return false, because the produced heap is not a valid answer when adding 8 to the original heap. A good set of test cases, then, will cover different elements to add to different configurations of heaps, looking for ways in which addElt/remMinElt might go wrong.
If you want to see whether your tester is detecting bad implementations of the Heap operations, you can use this Java file (put it in your directory). It contains several incorrect heap implementations (each a separate class that extends DataHeap). You can build a broken heap doing something like
IHeap badHeap =
new TestHeap2(3, new TestHeap2(4, new MTHeap(),
new MTHeap()),
new MTHeap());
(which replaces DataHeap with TestHeap2 when creating the example). If you now used badHeap as an input to your addEltTester, some tests should fail where they would have passed had you made the same example with DataHeap.
The tests in your final Examples class should just be written using DataHeap, not these broken implementations. The broken implementations are just to help you in checking your work. Either delete or comment out any tests that used the TestHeap classes before you submit.
Submit (via InstructAssist) a single zip file (not tar, rar, 7zip, etc) containing all of your .java files that contain your classes, interfaces, and examples for this assignment. The name of the project in InstructAssist is Homework 4. Do not submit the .class files.
We will be looking for code that correctly implements addEltTester and remMinEltTester.