Question

SELF-CHECK

1. Why did the first version of method search that passed the first test itemNotFirstElementInSingleElementArray contain 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.

Reference

Rather 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.¹)

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 itemNotFirstElementInSingleElementArray because 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 (index < x.length) { 
        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 if statements 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 0is the same as for the other elements. So we can remove the first statement and start the loop at 0 instead 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 whilewith 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)); 

Answer 1

Why did the first version of method search that passed the first test itemNotFirstElementInSingleElementArray contain only the statement return −1?

   The first version of search method has return as -1 since the first test case is The target element is not in the list / Element is not in the list and to satisfy the case i.e. when element not in the list. The java ArraySearch method returns -1 when the element that we intended to search is not found in the array we search.
  
   What would be the minimal code for a method findLargest that passed this test?
   public class ArraySearch {
  
public static int findLargest(int[] y) {
//Check if length is 1 then return index 0 as the only element will be the largest in the array
if(y.length == 1) {
return 0;
}
return -1;
}
}

--------------
package com.HomeworkLib1;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class ArraySearchTest {
  
@Test
public void testFindLargestOneElement() {
ArraySearch arraySearch = new ArraySearch();
int[] y = {10};
assertEquals(0, arraySearch.findLargest(y));
}
  
}
The minimum code required is
1. Check the length of the array using the length property of the array
2. if it is equal to 1 then return 0 as index
3. else return -1