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":
1. The autocomplete task
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:
- S' matches at the beginning of the last name
- S' matches at the beginning of the first name
- S' matches anywhere else in the last name
- S' matches anywhere else in the first name
- S' matches C across the comma boundary between the last name and the first name
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.
2. Required for phase 2
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.
3. Notes about IntelliJ
To create your AutocompleterTest.java file in IntelliJ:
- Get my Autocompleter code into your project. You can do that by first cloning my cs257_2018 project: https://github.com/ondich/cs257_2018.git. Then, copy the Autocompleter.java file from my repository into your repository and change its "package edu.carleton.jondich" line to use your package string.
- Open your copy of Autocomplete in IntelliJ.
- Click on the word Autocompleter in the class declaration at the top of Autocompleter.java. IntelliJ should show you a little yellow lightbulb. Click on that and select "Create Test" and then use the wizard that pops up.
- In the wizard, under "Testing library:", select JUnit5 (or whatever is the highest number of JUnit offered to you). Click the "Fix" button if JUnit5 isn't yet available. Leave the "Superclass" blank. Use your package ID for the "Destination package". Check the "setUp" and "tearDown" checkboxes, and at least one of the methods in "Generate test methods for". That way, you'll be given the proper syntax for the setUp, tearDown, and generic unit test methods in the automatically generated code.
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.
4. General advice
- For this simple exercise, go ahead and include the actors.txt file in your Autocomplete project.
- I recommend adding an Autocompleter instance variable to your AutocompleterTest class.
You can initialize this instance variable inside your setUp method:
autocompleter = new Autocompleter("actors.txt");or something like that. This way, your test methods will have an Autocompleter object to use for testing purposes, and you don't have to scatter repeated code throughout your test methods.
- Lots of small tests is usually better than a few complicated tests.
- Learn the order in which methods get called when you run JUnit tests in IntelliJ. You can do this by putting print statements inside the various methods, or by using breakpoints (which we'll look at on Monday if not today).
5. Handing it in
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!