Overview

This is all done in Java.

There are two independent parts to this assignment. In part 1, you will add some key functionality to a word completion program, where a user starts to type and the program makes suggestions for completion. In part 2, you will use recursion to work with files and folders on your computer.

For both parts, you are expected to practice good coding, with careful use of Java statements, thoughtful variable names, and documentation and testing where needed.

As a warning, the problems you are solving in this assignment are more technical than some of the earlier methods you have been asked to write. The problems themselves depend on understanding properties of String and File and Scanner. So take the time to carefully read the assignment well before the due date, keeping the big picture of the problems you are asked to solve while studying the details, and ask for clarification as needed.

Part 1: Binary Search

In this part, you will complete a program that autocompletes city names by searching through a global list of cities. To complete the program, you will write a method to read in a file of cities using a Scanner and also write your own variant of binary search which searches for cities that match some partial city prefix. This search is similar to the binary search we saw in recitation, but now only a partial match between strings is needed to find an item.

As an example of how this program will work, if the user were to type: "Sal"

and the program knew about a city: "Salt Lake City, UT"

it would be able to suggest "Salt Lake City, UT" as a completion, since "Sal" matches the start of "Salt Lake City, UT".

This is similar to autocomplete techniques used in a variety of applications, although commercial ones tend to use more sophisticated techniques that weight the popularity of the word to help pick the best suggestion for completion.

Getting Started

Make an a5 package and download and add these three files: Completer.java (Links to an external site.), CompleterApp.java (Links to an external site.), and cities.txt (Links to an external site.). You will not modify the CompleterApp.java file and the cities.txt is used as a list of city names.

Requirements

Completer.java contains a partial program with ample documentation. Your task is to make this program work by completing the missing methods as documented. The first method (readCitiesFile) reads the city data from a file and stores it in a String array. Then, you will write a modified binary search (binarySearchForKey) that searches all of the city data for a search string input by the user. You should consider a city a match if the city starts exactly with the search string. Some more details about the methods you should write in the Completer.java file are given below.

readCitiesFile: Implement the method as described in its Javadoc. Refer to the lecture on reading files and using Scanner (Links to an external site.) as a starting point. Open the cities.txt file to see what the file structure actually looks like - it starts with a number on the first line specifying how many cities are in the file, followed by a city per line. If you use a Scanner to read the first line containing the number, that String can be converted to an integer with Integer.parseInt(String). Then, read the rest of the file and store each line in an array.

As a further warning, the file of city names has some cities with accent characters. On different systems, those can read differently, or cause failures. You can specify the style of character encoding when you open a File with a Scanner. Please use

Scanner scan = new Scanner(cities, "utf-8");

when using the Scanner to read a file.

binarySearchForKey: Implement the method as described in its Javadoc. You should start with the example binary search from lecture, and then modify it to use the appropriate equality and comparison operators instead of ==, >, and <. Recall that this binary search should work for String objects and should count a partial match as equals. The String method fullString.startsWith(startString) can be used to compare startString with the beginning of the fullString. Then the compareTo method you used in an earlier assignment can be used to see if one String is bigger or smaller than another.

You may find that debugging your code is made more complicated as it is used by the CompleterApp program. You may want to make some simple tests in main as you start to check the behavior of your methods - but remove those tests in main before submitting.

Running the Program

The Completer file has a main method that makes a new CompleterApp object and runs it. The CompleterApp uses the methods you wrote to perform the matching operation. A blank window should appear, and if you type in the window, your text will appear and then any suggested city match, or "no match" if the start text does not match any known city. Type in lower case, as the city text is converted to lower case.

The code that creates the new CompleterApp has some options. The first argument is the path to the cities text file. The second argument is a string of "binary" or "sequential" that specifies which search approach is used. The final argument is a boolean that specifies whether an artificially large array (the cities array duplicated 2000 times) should be used (for true) or the normal cities array (for false) -- this exaggerates the differences between sequential and binary search.

Play with the program a bit. Experiment with the search style and the large array option. Try matching cities that start with "a" and cities that start with "z" for the big array and the different search styles.

Discussion

Add a block comment at the bottom of the Completer.java file that discusses how you experimented with the application and what you observed of the behavior. Discuss the performance behavior under different conditions and your thoughts that might explain this observed behavior. A few sentences is adequate here.

Testing

Add a JUnit test file for Completer.java. Write tests in that program to test the two methods you wrote. You may find it useful to test with a smaller file than cities.txt. You can try this sample.txt (Links to an external site.) file with five names in it as a basis for your tests. Follow the basic pattern of an @Test method that tests some specific thing about one method, with several test methods to cover different cases for each method. You do not need to test for thrown exceptions in the unit tests.

Since you will be testing one method that throws an exception, your code that calls that method is required to be surrounded by a try-catch. If you add a throws declaration to your test method (similar to what the readCitiesFile method does), then the JUnit test will fail and report that error.