Autocomplete
Implementing a comparable data type for efficient autocomplete.1
Autocomplete is a feature of many modern applications that automatically helps the user complete an input query based on a list of predicted terms. We can implement predictive autocomplete in three steps: sorting the terms by query string; binary searching to find all query strings that start with a given prefix; and sorting the matching terms by relevance.
Autocomplete
- Sep 30
- Welcome to CSE 143
- BJP 8
- Oct 1
- SectionObjects
- Oct 2
- Comparable
- BJP 9.5, 10.2
- Describe the relationships between client vs. implementer and interface vs. class.
- Define methods that accept instances of the same class as parameters.
- Define classes that implement public interfaces such as
Comparable
.
Specification
Implement a Term
class that represents an autocomplete term—a query string and an associated integer weight. Each instance of the Term
class can be compared against other instances of the Term
class in two different ways.
- Compare query by lexicographic order so that terms appear in dictionary order.
- Compare weight by descending order so that the most heavily-weighted terms appear first.
Term(String query, int weight)
- Constructs a term with the given non-null
query
string andweight
. int compareTo(Term other)
- Compares to another term in lexicographic order by query and ignoring case.
int compareToByReverseWeight(Term other)
- Compares to another term in descending order by weight.
String query()
- Returns this term’s query.
int weight()
- Returns this term’s weight.
String toString()
- Returns this term’s query.
Run, Check, Mark
The Run button will run the main
method in the Term
class. Modify the main
method to test different combinations and print the results to check that they match your expectations.
The Check button will display a link to open the Java visualizer for stepping through the main
method.
The Mark button will run a suite of automated tests to check that the program meets the specification.
Web app
To launch the web app, Open Terminal
javac Server.java && java Server cities.tsv; rm *.class
Then, open the Network
When you’re done, return to the terminal and enter the key combination Ctrl
C
to close the server.
Grading
Mark the program to submit it for grading. In addition to the automated tests, the final submission will also undergo code review for internal correctness on comments, variable names, indentation, and code quality.
- Commenting errors
- Class header missing or doesn’t describe both student and program.
- Blind copying of text from assignment writeup.
- Readability errors
- Lines over 100 characters long.
- Not following Java naming conventions..
- One-letter or nondescriptive field names.
- Method or constructor does not have a blank line before it.
- Class design errors
- Extra public methods or constructors not in the specification.
- Not including either public or private for a method declaration.
Kevin Wayne. 2016. Autocomplete-Me. In Nifty Assignments 2016. http://nifty.stanford.edu/2016/wayne-autocomplete-me/ ↩