Continue with the partner you worked with to get set up in IntelliJ, GitHub, and git.
Lots of modern software has some kind of autocomplete feature. Google's autocomplete feature, for example:
During the baseball season, I make heavy use of a site called Baseball HQ. Among many other things, this site allows me to search for specific baseball players by name, with an autocomplete feature to help me. Here, for example, I am provided with a scrollable list of Hernandezes when I enter "hernan":
For this assignment, you are going to implement an autocomplete feature for a dataset consisting of actor's names, much like the Baseball HQ autocomplete. The implementation of this feature will be reasonably interesting, and could be extremely useful in practice in the right context. But for our purposes, the main reason for implementing this system will be to help us practice test-driven development.
For Phase 2 of this assignment, you will not implement the autocomplete feature. Rather, you will develop a set of unit tests intended to ensure that your yet-to-be-implemented autocomplete feature does the right thing. Once you have developed a suitable set of unit tests, you will (in Phase 3) write the autocomplete feature itself. Once all your unit tests pass, you will have reasonable confidence that you have implemented your autocomplete feature correctly.
Before you can write a suite of unit tests, we need to describe the autocomplete feature in appropriate detail. Here's how it goes. When the user enters a search string S, then our program will invoke the getCompletions method on an Autocompleter object using the parameter S. In Java, this would look something like:
After this, the program would do whatever it wanted to do with the list of completions. For example, truncate the list to its first five items and display those in a popup window.
So, what remains is to describe the process by which Autocompleter.getCompletions should identify actors' names that are legal completions of S, and how it should sort those names once they are found. Here's my shot at doing that.
Completions
Given an actor name A = last_name + ", " + first_name, let the corresponding comparison string C = A in lower case and with all spaces removed. For example, if A = "De Niro, Robert", then C = "deniro,robert".
Also, let S' be S in lower case with all spaces removed.
We will consider A to be a completion of S if S' is non-empty and S' is a substring of C. Note that this means that some completion lists will be very long (e.g. when S = "e") and that some will be a little weird (e.g. S = "o, r" for Robert De Niro).
Sorting
Let's sort so the following kinds of matches appear in the following order:
So if S = "avi" then Bette Davis comes before Javier Bardem.
Suppose two names A and B match S' in the same way. If S' matches CA at a smaller string index than CB, then A comes first. If they match at the same string index, then we will order A and B based on the lexicographic order of CA and CB.
For example, suppose S = "dav", A = "Davis, Viola", and B = "Davis, Bette". Then both matches of S' occur at index 0 (in "davis,viola" and "davis,bette"), so we fall back to sorting "davis,viola" and "davis,bette" as ordinary strings, in which case B would come before A.
On the other hand, suppose S = "avi", A = "Davis, Viola", and B = "Rhys-Davies, John"). Then again, S' matches these two names in the same way (i.e. "anywhere else in the last name"), but the match is at index 1 for A and index 6 for B, so A comes before B in our sorted order.
As another example, suppose S = "amy", A = "Adams, Amy", and B = "Ryan, Amy". Then A and B both match in a "beginning of first name" way, so we have to look at the index. S' matches "adams,amy" at index 6, and "ryan,amy" at index 5, so B comes first.
Note that this last example feels a little weird. You might expect that start-of-first-name matches would just get alphabetized by last name or something. And indeed, we could revisit this question in some fictional future version of this specification. But for now, just adhere to the spec as written: the "index of match" is computed within the "comparison string" C as a whole, not within just the matched component of C.
As noted above, your job for this part of the assignment is to implement a thorough collection of unit tests for the non-constructor public methods in Autocompleter. (As it happens, there is only one such method--getCompletions.) How many distinct unit tests you write is up to you. That said, you should strive for a thorough exploration of the testing space, including typical cases and boundary cases of various sorts.
You may not change Autocompleter in any way during Phase 2. In particular, the signatures for the Autocompleter constructor and the getCompletions method should never change during any phase of this project.
Writing tests without yet having the thing-to-be-tested in hand can feel a little weird. For example, it's hard to tell whether your testing code is correct until you have something to test against. But something has to be written first, and the benefits of writing tests first are substantial, so we're taking a strict line on that in this assignment. Don't write the code until you've first written the tests.
To create your AutocompleterTest.java file in IntelliJ:
You may discover that when you first create your test file, there are some compile errors. You can address these problems by clicking on red text, clicking on the resulting red lightbulb, and following your nose from there. Be careful when taking the red lightbulb's advice, though--you might want to write down what decisions you made with the lightbulb, so you can track down any problems that pop up later.
Submit your program by committing and pushing to your GitHub repository and tagging the commit you want graded with a tag named "autocomplete_phase2".
Have fun!