Pseudocode using Java 2
ProfSteven
Instructions.docxRather than writing a complete method and then testing it, test-driven development involves writing the tests and the method in parallel. The sequence is as follows:
· Write a test case for a feature.
· Run the test and observe that it fails, but other tests still pass.
· Make the minimum change necessary to make the test pass.
· Revise the method to remove any duplication between the code and the test.
· Rerun the test to see that it still passes.
We then repeat these steps adding a new feature until all of the requirements for the method have been implemented.
We will use this approach to develop a method to find the first occurrence of a target in an array.
Case Study: Test-Driven Development of ArraySearch.search
Write a program to search an array that performs the same way as Java method ArraySearch.search. This method should return the index of the first occurrence of a target in an array, or −1−1 if the target is not present.
We start by creating a test list like that in the last section and then work through them one at a time. During this process, we may think of additional tests to add to the test list.
Our test list is as follows:
1. The target element is not in the list.
2. The target element is the first element in the list.
3. The target element is the last element in the list.
4. There is more than one occurrence of the target element and we find the first occurrence.
5. The target is somewhere in the middle.
6. The array has only one element.
7. The array has no elements.
We start by creating a stub for the method we want to code:
/**
* Provides a static method search that searches an array
* @author Koffman & Wolfgang
*/
public class ArraySearch {
/**
* Search an array to find the first occurrence of a target
* @param x Array to search
* @param target Target to search for
* @return The subscript of the first occurrence if found:
* otherwise return -1
* @throws NullPointerException if x is null
*/
public static int search(int[] x, int target) {
return Integer.MIN_VALUE;
}
}
Now, we create the first test that combines tests 1 and 6 above. We will screen the test code in gray to distinguish it from the search method code.
/**
* Test for ArraySearch class
* @author Koffman & Wolfgang
*/
public class ArraySearchTest {
@Test
public void itemNotFirstElementInSingleElementArray() {
int[] x = {5};
assertEquals(-1, ArraySearch.search(x, 10));
}
}
And when we run this test, we get the message:
Testcase: itemNotFirstElementInSingleElementArray: FAILED
expected:<-1> but was:<-2147483648>
The minimum change to enable method search to pass the test is
public static int search(int[] x, int target) {
return -1; // target not found
}
Now, we can add a second test to see whether we find the target in the first element (tests 2 and 6 above).
@Test
public void itemFirstElementInSingleElementArray() {
int[] x = new int[]{5};
assertEquals(0, ArraySearch.search(x, 5));
}
As expected, this test fails because the search method returns −1. To make it pass, we modify our search method:
public static int search(int[] x, int target) {
if (x[0] == target) {
return 0; // target found at 0
}
return -1; // target not found
}
Both tests for a single element array now pass. Before moving on, let us see whether we can improve this. The process of improving code without changing its functionality is known as refactoring. Refactoring is an important step in test-driven development. It is also facilitated by TDD since having a working test suite gives you the confidence to make changes. (Kent Beck, a proponent of TDD says that TDD gives courage.1)
The statement:
return 0;
is a place for possible improvement. The value 00 is the index of the target. For a single element array this is obviously 00, but for larger arrays it may be different. Thus, an improved version is
public static int search(int[] x, int target) {
int index = 0;
if (x[index] == target)
return index; // target at 0
return -1; // target not found
}
Now, let us see whether we can find an item that is last in a larger array (test 3 above). We start with a 2-element array:
@Test
public void itemSecondItemInTwoElementArray() {
int[] x = {10, 20};
assertEquals(1, ArraySearch.search(x, 20));
}
The first two tests still pass, but the new test fails. As expected, we get the message:
Testcase: itemSecondItemInTwoElementArray: FAILED
expected:<1> but was:<-1>
The test failed because we did not compare the second array element to the target. We can modify the method to do this as shown next.
public static int search(int[] x, int target) {
int index = 0;
if (x[index] == target)
return index; // target at 0
index = 1;
if (x[index] == target)
return index; // target at 1
return -1; // target not found
}
However, this would result in an ArrayOutOfBoundsException error for test itemNotFirstElementInSingleElementArraybecause there is no second element in the array {5}. If we change the method to first test that there is a second element before comparing it to target, all tests will pass.
public static int search(int[] x, int target) {
int index = 0;
if (x[index] == target)
return index; // target at 0
index = 1;
if (x[index] == target)
return index; // target at 1
}
return -1; // target not found
}
However, what happens if we increase the number of elements beyond 2?
@Test
public void itemLastInMultiElementArray() {
int[] x = new int[]{5, 10, 15};
assertEquals(2, ArraySearch.search(x, 15));
}
This test would fail because the target is not at position 0 or 1. To make it pass, we could continue to add ifstatements to test more elements, but this is a fruitless approach. Instead, we should modify the code so that the value of index advances to the end of the array. We can change the second if to a while and add an increment of index.
public static int search(int[] x, int target) {
int index = 0;
if (x[index] == target)
return index; // target at 0
index = 1;
while (index < x.length) {
if (x[index] == target)
return index; // target at index
index++;
}
return -1; // target not found
}
At this point, we have a method that will pass all of the tests for any size array. We can group all the tests in a single testing method to verify this.
@Test
public void verificationTests() {
int[] x = {5, 12, 15, 4, 8, 12, 7};
// Test for target as first element
assertEquals(0, ArraySearch.search(x, 5));
// Test for target as last element
assertEquals(6, ArraySearch.search(x, 7));
// Test for target not in array
assertEquals(-1, ArraySearch.search(x, -5));
// Test for multiple occurrences of target
assertEquals(1, ArraySearch.search(x, 12));
// Test for target somewhere in middle
assertEquals(3, ArraySearch.search(x, 4));
}
Although it may look like we are done, we are not finished because we also need to check that an empty array will always return −1:
@Test
public void itemNotInEmptyArray() {
int[] x = new int[0];
assertEquals(-1, ArraySearch.search(x, 5));
}
Unfortunately, this test does not pass because of an ArrayIndexOutofboundsException in the first if condition for method search (there is no element x[0] in an empty array). If we look closely at the code for search, we see that the initial test for when index is 0 is the same as for the other elements. So we can remove the first statement and start the loop at 0instead of 1 (another example of refactoring). Our code becomes more compact and this test will also pass. A slight improvement would be to replace the while with a for statement.
public static int search(int[] x, int target) {
int index = 0;
while (index < x.length) {
if (x[index] == target)
return index; // target at index
index++;
}
return -1; // target not found
}
Finally, if we pass a null pointer instead of a reference to an array, a NullPointerException should be thrown (an additional test not in our original list).
@Test(expected = NullPointerException.class)
public void nullValueOfXThrowsException() {
assertEquals(0, ArraySearch.search(null, 5));
}
JUnit in Netbeans
It is fairly easy to create a JUnit test harness in Netbeans. Once you have written class ArraySearch.java, right click on the class name in the Projects view and then select Tools −> Create/Update Tests. A Create Tests window will pop up. Select OK and then a Select JUnit Version window will pop up: select the most recent version of JUnit (currently JUnit 4.x). At this point, a new class will be created (ArraySearchTest.java) that will contain prototype tests for all the public functions in class ArraySearch. You can replace the prototype tests with your own. To execute the tests, right click on class ArraySearchTest.
ASSIGNMENT
EXERCISES FOR SECTION 3.5
SELF-CHECK
1. Why did the first version of method search that passed the first test itemNotFirstElementInSingleElementArraycontain only the statement return −1?
2. Assume the first JUnit test for the findLargest method described in Self-Check exercise 2 in section 3.4 is a test that determines whether the first item in a one element array is the largest. What would be the minimal code for a method findLargest that passed this test?
PROGRAMMING
1. Write the findLargest method described in self-check exercise 2 in section 3.4 using Test-Driven Development.
