Autocomplete engine

Question

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;
    }
}

Answer 1

Bug

numberOfMatches(String) will return a correct result only on the first call. If you call it again with another prefix, it will return the same value, because it will not be recalculated.

Different approaches can be used to fix it. Previous search prefix can be traced and checked, or even a Map of prefix -> nbResults can store already calculated values.

Code Duplication in ByPrefixOrder Comparator

It's a good idea to normalize the output of compateTo method so as it returns in range [-1, 0, 1], but the implementation contains repetitions of same code.

If I understand well the logic, the comparison of term query strings is made only for the substrings of the queries that do not exceed r number of characters. To normalize the input strings, a shortcut method is useful:

private String cutIfLengthGreaterThanR(String termString) {
  final int endIndex = termString.length() > r ? r : termString.length();
  return termString.substring(0, endIndex);
}

This allows to reduce the compareTo method:

@Override
public int compare(Term t1, Term t2) {
  String s1 = cutIfLengthGreaterThanR(t1.query);
  String s2 = cutIfLengthGreaterThanR(t2.query);
  final int cmp = s1.compareToIgnoreCase(s2);
  if (cmp <= -1) {
    return -1;
  }
  else if (cmp >= 1) {
    return 1;
  }
  else {
    return 0;
  }
  // or even a less readable one-liner:
  //  return (cmp == 0) ? 0 : (cmp < 0) ? -1 : 1;
}

If you are using Java 8, there is no need to create a dedicated class for this purpose. Lambdas are helpful:

public static Comparator<Term> byPrefixOrder(int r) {
  if (r < 0) throw new IllegalArgumentException("r must be nonnegative, but was " + r);
  return (t1, t2) -> {
    String s1 = cutIfLengthGreaterThanR(t1.query, r);
    String s2 = cutIfLengthGreaterThanR(t2.query, r);
    final int cmp = s1.compareToIgnoreCase(s2);
    return (cmp == 0) ? 0 : (cmp < 0) ? -1 : 1;
  };
}

private static String cutIfLengthGreaterThanR(String termString, int r) {
  // same code as above
}

Args Validation

It's also a good idea to validate method arguments, but I think that NullPointerException is not really appropriate here. The checks like

if (query == null) ...
if (terms == null) ...

should all throw IllegalArgumentException: it underlines the requirement for non-nullability of the args.

Array Copies

Arrays are copied "manually" in Autocomplete constructor and allMatches.

java.util.Arrays contains a series of copyOf methods that could make the code shorter and less prone to bugs.

BinarySearchDeluxe

Do not use full-word names for generic types. Key can be easily misleading, even for an IDE (for example, my IntelliJ automatically imported java.security.Key, which is very confusing). Use single-letter names for generics: T, E, U...

The two *indexOf methods differ only in conditional branches inside the while loop, but all the other code is redundant. That can be improved. Using Java 8, we can extract the equality condition check and the lo value change function into the signature of the method:

private static <T> int indexOf(T[] a,
                               T key,
                               Comparator<T> comparator,
                               Predicate<Integer> eqTest,
                               IntFunction<Integer> eqLowChangeFunction) {
  // null checks

  if (a.length == 0) return -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 (eqTest.test(mid)) lo = eqLowChangeFunction.apply(mid);
    else return mid;
  }
  return -1;
}

The two public methods become as follows:

public static <T> int firstIndexOf(T[] a, T key, Comparator<T> comparator) {
  return indexOf(a,
                 key,
                 comparator,
                 mid -> comparator.compare(a[mid-1], a[mid]) == 0,
                 mid -> mid - 1);
}

public static <T> int lastIndexOf(T[] a, T key, Comparator<T> comparator) {
  return indexOf(a,
                 key,
                 comparator,
                 mid -> comparator.compare(a[mid+1], a[mid]) == 0,
                 mid -> mid + 1);
}

The quick checks for first or last elements are not extracted here, but still can be.