The purpose of this program is to implement logic of autocomplete feature (Google Search, for instance). The code is divided into 3 parts:
Term
- represents single search term with the query and the weight (number of times this query was searched for).BinarySearchDeluxe
- utility class that provides methods for finding the first and the last keys using binary search algorithm.Autocomplete
- given the data and the query (denoted as prefix), this class provides method for searching for terms in the data that happen to start with the given query and returns them array in descending order (by popularity, if you will).
Edit: Here is the data that you can feed into Autcomplete class, in order to test it : ftp://ftp.cs.princeton.edu/pub/cs226/autocomplete/
- If you are using Linux machine, you can pull data with the following command:
wget -r -nH --cut-dirs=2 ftp://ftp.cs.princeton.edu/pub/cs226/autocomplete/file_name
Term.java
import java.util.Comparator;
/**
* Term is an immutable data type that represents an autocomplete term:
* a query string and an associated integer weight
*/
public class Term implements Comparable<Term> {
private final String query;
private final long weight;
/* Rep Invariant
* true
* Abstraction Function
* represents a single query term
* Safety Exposure Argument
* All fields are private, final and immutable.
*/
/**
* Initializes a term with the specified query and the weight. Query should be non-null
* and weight must be non-negative.
* @param query - the query to be searched for
* @param weight - the corresponding weight of the query
* @throws NullPointerException - if query == null
* @throws IllegalArgumentException - if weight < 0
*/
public Term(String query, long weight) {
if (query == null) throw new NullPointerException("query can't be null");
if (weight < 0) throw new IllegalArgumentException("weight must be nonnegative");
this.query = query;
this.weight = weight;
}
/**
* Returns comparator that provides method for comparing terms using their corresponding weights.
* @return -1 if this.weight < that.weight <br/>
* 0 if this.weight == that.weight <br/>
* 1 if this.weight > that.weight <br/>
*/
public static Comparator<Term> byReverseWeightOrder() {
return new ByReverseWeightOrder();
}
/**
* Returns comparator that provides method for comparing terms in lexicographic order using
* only the first r characters of each query. Parameter r should be non-negative.
* @param r - the first r characters.
* @return -1 if first r characters of this are less than the first r characterst of that<br/>
* 0 if first r characters of this are equal to the first r characterst of that<br/>
* 1 if first r characters of this are larger than to the first r characterst of that<br/>
* @throws new IllegalArgumentException - if r < 0
*/
public static Comparator<Term> byPrefixOrder(int r) {
if (r < 0) throw new IllegalArgumentException("r must be nonnegative, but was " + r);
return new ByPrefixOrder(r);
}
/**
* Returns a string representation of this term in the following format:
* the weight, followed by a tab, followed by the query.
*/
public String toString() {
return weight +"\t" + query;
}
/**
* Compares two terms in lexicographic order by query.
* @return -1 if this is (less than) that<br/>
* 0 if this (is the same as) that<br/>
* 1 if this (is larger than) that<br/>
*/
public int compareTo(Term that) {
int cmp = this.query.toLowerCase().compareTo(that.query.toLowerCase());
if (cmp <= -1) return -1;
else if (cmp >= 1) return 1;
else return 0;
}
private static class ByPrefixOrder implements Comparator<Term> {
private final int r;
private ByPrefixOrder(int r) {
this.r = r;
}
@Override
public int compare(Term t1, Term t2) {
int len1 = t1.query.length();
int len2 = t2.query.length();
if (len1 >= r && len2 >= r) {
String s1 = t1.query.toLowerCase().substring(0, r);
String s2 = t2.query.toLowerCase().substring(0, r);
int cmp = s1.compareTo(s2);
if (cmp <= -1) return -1;
else if (cmp >= 1) return 1;
else return 0;
}
else if (len1 < r && len2 >= r) {
String s1 = t1.query.toLowerCase();
String s2 = t2.query.toLowerCase().substring(0, r);
int cmp = s1.compareTo(s2);
if (cmp <= -1) return -1;
else if (cmp >= 1) return 1;
else return 0;
}
else if (len2 < r && len1 >= r) {
String s1 = t1.query.toLowerCase().substring(0, r);
String s2 = t1.query.toLowerCase();
int cmp = s1.compareTo(s2);
if (cmp <= -1) return -1;
else if (cmp >= 1) return 1;
else return 0;
}
else {
String s1 = t1.query.toLowerCase();
String s2 = t2.query.toLowerCase();
int cmp = s1.compareTo(s2);
if (cmp <= -1) return -1;
else if (cmp >= 1) return 1;
else return 0;
}
}
}
private static class ByReverseWeightOrder implements Comparator<Term> {
@Override
public int compare(Term t1, Term t2) {
Long w1 = t1.weight;
Long w2 = t2.weight;
int cmp = w1.compareTo(w2);
if (cmp <= -1) return 1;
else if (cmp >= 1) return -1;
else return 0;
}
}
}
BinarySearchDeluxe.java
import java.util.Comparator;
public class BinarySearchDeluxe {
/**
* Searches the specified array for the specified value using modification of binary
* search algorithm and returns the index of the first key in a[] that equals the search key,
* or -1 if no such key were found..
* The array must be sorted into ascending order according to the specified
* comparator, otherwise the results are undefined.
*
* @param a - the array of keys to be searched
* @param key - the value to be searched for
* @param comparator - the comparator by which array is ordered
* @return - the index of the first key in a[] that equals the search key, -1 if not found
* @throws NullPointerException - if a == null
* @throws NullPointerException - if key == null
* @throws NullPointerException - if comparator == null
*/
public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
if (a == null) throw new NullPointerException("a cannot be null");
if (key == null) throw new NullPointerException("key cannot be null");
if (comparator == null) throw new NullPointerException("comparator cannot be null");
if (a.length == 0) return -1;
if (comparator.compare(a[0], key) == 0) return 0;
int lo = 0;
int hi = a.length;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cmp = comparator.compare(a[mid], key);
if (cmp >= 1) hi = mid - 1;
else if (cmp <= -1) lo = mid + 1;
else if (comparator.compare(a[mid-1], a[mid]) == 0) hi = mid - 1;
else return mid;
}
return -1;
}
/**
* Searches the specified array for the specified value using modification of binary
* search algorithm and returns the index of the last key in a[] that equals the search key,
* or -1 if no such key were found.
* The array must be sorted into ascending order according to the specified
* comparator, otherwise the results are undefined.
*
* @param a - the array of keys to be searched
* @param key - the value to be searched for
* @param comparator - the comparator by which array is ordered
* @return - the index of the last key in a[] that equals the search key, -1 if not found
* @throws NullPointerException - if a == null
* @throws NullPointerException - if key == null
* @throws NullPointerException - if comparator == null
*/
public static <Key> int lastIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
if (a == null) throw new NullPointerException("array of keys cannot be null");
if (key == null) throw new NullPointerException("key cannot be null");
if (comparator == null) throw new NullPointerException("comparator cannot be null");
if (a.length == 0) return -1;
if (comparator.compare(a[a.length-1], key) == 0) return a.length - 1;
int lo = 0;
int hi = a.length;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cmp = comparator.compare(a[mid], key);
if (cmp >= 1) hi = mid - 1;
else if (cmp <= -1) lo = mid + 1;
else if (comparator.compare(a[mid+1], a[mid]) == 0) lo = mid + 1;
else return mid;
}
return -1;
}
}
Autocomplete.java
import java.util.Arrays;
public class Autocomplete {
private final Term[] termsCopy;
private int n;
private Term[] matches; // cache
/*
* Rep Invariant
* n >= 0
* Abstraction Function
* represents set of terms that match the query
* Safety Exposure Argument
* All fields are private. Aliasing is avoided by making defensive copy of terms array
* passed by the client. Term objects residing in the termsCopy are immutable. Matches is shared with the client, but Term objects are immutable.
*/
/**
* Initialized Autocomplete data structure using array of terms. Array should be non-null
* @param terms - the array of terms
* @throws NullPointerException - if terms == null
*/
public Autocomplete(Term[] terms) {
if (terms == null) throw new NullPointerException("terms should be non-null");
termsCopy = new Term[terms.length];
for (int i = 0; i < terms.length; i++) {
termsCopy[i] = terms[i]; // Term is immutable, so OK
}
Arrays.sort(termsCopy);
}
/**
* Return all terms that start with the given prefix, in descending order of weight.
* Prefix should be non-null.
* @param prefix - prefix of the terms to be searched for
* @return - array of terms that match the given prefix in descending order
* @throws NullPointerException - if prefix == null
*/
public Term[] allMatches(String prefix) {
if (prefix == null) throw new NullPointerException("prefix should be non-null");
Term stub = new Term(prefix, 0); // to emulate the term to be searched for
int firstIndex = BinarySearchDeluxe.firstIndexOf(termsCopy, stub, Term.byPrefixOrder(prefix.length()));
int lastIndex = BinarySearchDeluxe.lastIndexOf(termsCopy, stub, Term.byPrefixOrder(prefix.length()));
this.n = lastIndex - firstIndex + 1;
Term[] allMatches = new Term[n];
int j = 0;
for (int i = firstIndex; i <= lastIndex ; i++) {
allMatches[j++] = termsCopy[i];
}
Arrays.sort(allMatches, Term.byReverseWeightOrder());
this.matches = allMatches;
return allMatches;
}
/**
* @return - the number of terms that start with the given prefix.
*/
public int numberOfMatches(String prefix) {
if (matches == null) {
allMatches(prefix);
return matches.length;
}
return n;
}
}
private final Term[] matches
field inAutocomplete
class. It isfinal
, but it is not initialized in the constructor and there is an attempt to change its reference inallMatches
. Please fix theAutocomplete
class, it does not compile in this state. \$\endgroup\$