Java, Java, Java

One of the most widely used Web browser functions is the search utility. You probably know how it works. You type in a keyword and click on a button, and it returns with a list of Web pages that contain the keyword.

Suppose you were writing a browser in Java. How would you imple- ment this function? Of course, we don’t know yet how to read files or Web pages, and we won’t cover that until Chapter 11. But, for now, we can write a method that will search a string for all occurrences of a given keyword. That’s at least part of the task that the browser’s search engine would have to do.

So we want a method, keywordSearch(), that takes two String pa- rameters, one for the string that’s being searched, and the other repre- senting the keyword. Let’s have the method return a String that lists the number of keyword occurrences, followed by the index of each occur- rence. For example, if we asked this method to find all occurrences of is in “This is a test,” it should return the string “2: 2 5” because there are two occurrences of is, one starting at index 2 and the other at index 5 in the string.

The algorithm for this method will require a loop, because we want to know the location of every occurrence of the keyword in the string. One way to do this would be to use the indexOf() method to search for the location of substrings in the string. If it finds the keyword at index N, it should record that location and then continue searching for more occurrences starting at index N + 1 in the string. It should continue in this way until there are no more occurrences.

,,

 

 

 

 

 

 

 

J

 

SECTION 7.4 • Example: Keyword Search307

As this pseudocode shows, the algorithm uses a while loop with a sentinelImplementation bound. The algorithm terminates when the indexOf() method returns a

1, indicating that there are no more occurrences of the keyword in the

string.

Translating the pseudocode into Java gives us the method shown in Fig- ure 7.8. Note how string concatenation is used to build the resultStr. Each time an occurrence is found, its location (ptr) is concatenated to the right-hand side of the resultStr. When the loop terminates, the number of occurrences (count) is concatenated to the left-hand side of the resultStr.

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

J

Figure 7.8: The keywordSearch() method.

 

Testing and Debugging

What test data should we use for the keywordSearch() method? One What test data do we need?

important consideration in this case is to test that the method works for all possible locations of the keyword within the string. Thus, the method should be tested on strings that contain keyword occurrences at the begin- ning, middle, and end of the string. We should also test the method with a string that doesn’t contain the keyword. Such tests will help verify that the loop will terminate properly in all cases. Given these considerations, Table 7.1 shows the tests that were made. As you can see from these re- sults, the method did produce the expected outcomes. While these tests do not guarantee its correctness, they provide considerable evidence that the algorithm works correctly.

 

TABLE 7.1 Testing the keywordSearch() method.

Test PerformedExpected Result

keywordSearch("this is a test","is")2: 2 5

keywordSearch("able was i ere i saw elba","a")4: 0 6 18 24

keywordSearch("this is a test","taste")0: