Autocomplete

Implementing a comparable data type for efficient autocomplete.¹

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

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.

1. Compare query by lexicographic order so that terms appear in dictionary order.
2. 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 and weight.

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 , paste the following command, and press Enter.

javac Server.java && java Server cities.tsv; rm *.class

Then, open the Network dropdown and select host 0.0.0.0:8000.

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.