Write a program to implement autocomplete for a given set of n terms, where a term is a query string and an associated non-negative weight. That is, given a prefix, find all queries that start with the given prefix, in descending order of weight.

Autocomplete is pervasive in modern applications. As the user types, the program predicts the complete query (typically a word or phrase) that the user intends to type. Autocomplete is most effective when there are a limited number of likely queries. For example, the Internet Movie Database uses it to display the names of movies as the user types; search engines use it to display suggestions as the user enters web search queries; cell phones use it to speed up text input.

The application predicts how likely it is that the user is typing each query and presents to the user a list of the top-matching queries, in descending order of weight. These weights are determined by historical data, such as box office revenue for movies, frequencies of search queries from other Google users, or the typing history of a cell phone user. For the purposes of this assignment, you will have access to a set of all possible queries and associated weights (and these queries and weights will not change).

The performance of autocomplete functionality is critical in many systems. For example, consider a search engine which runs an autocomplete application on a server farm. According to one study, the application has only about 50ms to return a list of suggestions for it to be useful to the user. Moreover, in principle, it must perform this computation for every keystroke typed into the search bar and for every user!

You will implement autocomplete by 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 weight.

Part 1: term. Write an immutable data type Term.java that represents an autocomplete term—a query string and an associated integer weight. You must implement the following API, which supports comparing terms by three different orders: lexicographic order by query string (the natural order); in descending order by weight (an alternate order); and lexicographic order by query string but using only the first r characters (a family of alternate orderings). The last order may seem a bit odd, but you will use it in Part 3 to find all query strings that start with a given prefix (of length r). The finished code for term.java is below - if you notice anything off, FIX IT, otherwise, keep it the same.

import edu.princeton.cs.algs4.StdOut;
import java.util.Comparator;

public class Term implements Comparable<Term> {

    private String Query;
    private long Weight;

    // Initializes a term with the given query string and weight.
    public Term(String query, long weight)
    {
        if (query == null)
        {
            throw new IllegalArgumentException("query cannot be null");
        }
        else if (weight < 0)
        {
            throw new IllegalArgumentException("weight cannot be negative");
        }

        Query = query;
        Weight = weight;
    }

    // Compares the two terms in descending order by weight.
    public static Comparator<Term> byReverseWeightOrder()
    {
        return new Comparator<Term>() {
            @Override
            public int compare(Term t1, Term t2)
            {
                return Long.compare(t2.Weight, t1.Weight); //swapped
            }
        };
    }

    // Compares the two terms in lexicographic order,
    // but using only the first r characters of each query.
    public static Comparator<Term> byPrefixOrder(int r)
    {
        if (r < 0)
        {
            throw new IllegalArgumentException("r cannot be negative");
        }

        return new Comparator<Term>() {
            @Override
            public int compare(Term t1, Term t2) 
            {
                String t1SubString;
                String t2SubString;

                //if statements prevent out of bounds error if prefix r > string length
                if (r <= t1.Query.length()) {
                    t1SubString = t1.Query.substring(0, r);
                } else {
                    t1SubString = t1.Query;
                }
                if (r <= t2.Query.length()) {
                    t2SubString = t2.Query.substring(0, r);
                } else {
                    t2SubString = t2.Query;
                }

                //String t1SubString = t1.Query.substring(0, r); //changed from (0, r + 1)
                //String t2SubString = t2.Query.substring(0, r); //changed from (0, r + 1)
                return t1SubString.compareTo(t2SubString);
            }
        };
    }

    // Compares the two terms in lexicographic order by query.
    public int compareTo(Term that)
    {
        return (this.Query).compareTo(that.Query);
    }

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

    // unit testing (required)
    public static void main(String[] args)
    {
        Term t1 = new Term("bleh bleh", 12345);
        Term t2 = new Term("word", 41238);
        StdOut.println(t1.toString());
        StdOut.println(t2.toString());

        StdOut.println(t1.compareTo(t2));
        StdOut.println(t2.compareTo(t1));

        StdOut.println(byReverseWeightOrder());
        StdOut.println(byPrefixOrder(3));
    }

}

Corner cases.  Throw an IllegalArgumentException in the constructor if either query is null or weight is negative. Throw an IllegalArgumentException in byPrefixOrder() if r is negative.

Unit testing.  Your main() method must call each public constructor and method directly and help verify that they work as prescribed (e.g., by printing results to standard output).

Performance requirements.  The string comparison functions must take time proportional to the number of characters needed to resolve the comparison.

Part 2: binary search. When binary searching a sorted array that contains more than one key equal to the search key, the client may want to know the index of either the first or the last such key. The finished code for this part is also below - if you notice anything off, FIX IT, otherwise, keep it the same.

import edu.princeton.cs.algs4.StdOut;

import java.util.Comparator;

public class BinarySearchDeluxe {

    // Returns the index of the first key in the sorted array a[]
    // that is equal to the search key, or -1 if no such key.
    public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
        //edge cases
        if (a == null) {
            throw new IllegalArgumentException("Array can not be null");
        } else if (key == null) {
            throw new IllegalArgumentException("Key can not be null");
        } else if (comparator == null) {
            throw new IllegalArgumentException("Comparator can not be null");
        }


        int low = 0;
        int high = a.length - 1;
        int returnInt = -1; //this variable is updated in the event a key is found, -1 represents key is not in array
        //standard binary search
        while (low <= high) {
            int mid = low + (high - low) / 2; //avoids integer overflow
            //for comparator, number will be negative if first element is lesser than second
            //0 if equal, and positive if first element is greater than second
            if (comparator.compare(key, a[mid]) < 0) {
                high = mid - 1; //check left half
            } else if (comparator.compare(key, a[mid]) > 0) {
               low = mid + 1; //check right half
            } else {
                //even if we find our key, we want to check anything before it for the first instance of that key
                returnInt = mid;
                high = mid - 1;
            }
        }
        return returnInt;
    }

    // Returns the index of the last key in the sorted array a[]
    // that is equal to the search key, or -1 if no such key.
    public static <Key> int lastIndexOf(Key[] a, Key key, Comparator<Key> comparator) {
        //edge cases
        if (a == null) {
            throw new IllegalArgumentException("Array can not be null");
        } else if (key == null) {
            throw new IllegalArgumentException("Key can not be null");
        } else if (comparator == null) {
            throw new IllegalArgumentException("Comparator can not be null");
        }


        int low = 0;
        int high = a.length - 1;
        int returnInt = -1; //this variable is updated in the event a key is found, -1 represents key is not in array
        //standard binary search
        while (low <= high) {
            int mid = low + (high - low) / 2; //avoids integer overflow
            //for comparator, number will be negative if first element is lesser than second
            //0 if equal, and positive if first element is greater than second
            if (comparator.compare(key, a[mid]) < 0) {
                high = mid - 1; //check left half
            } else if (comparator.compare(key, a[mid]) > 0) {
                low = mid + 1; //check right half
            } else {
                //even if we find our key, we want to check anything after it for the last instance of that key
                returnInt = mid;
                low = mid + 1;
            }
        }
        return returnInt;
    }

    // unit testing (required)
    public static void main(String[] args) {
        String[] a = { "A", "A", "A", "A", "A", "A", "Z", "Z", "Z", "Z"};
        Comparator<String> comparator = String.CASE_INSENSITIVE_ORDER;
        int indexFirst = BinarySearchDeluxe.firstIndexOf(a, "Z", comparator);
        int indexLast = BinarySearchDeluxe.lastIndexOf(a, "A", comparator);
        //StdOut.println(indexFirst);
        //StdOut.println(indexLast);

        Term term1 = new Term("AAA", 0);
        Term term2 = new Term("AAA", 1);
        Term term3 = new Term("AAAB", 2);
        Term term4 = new Term("AAB", 3);
        Term term5 = new Term("AAB", 4);
        Term term6 = new Term("AAB", 5);
        Term term7 = new Term("AAC", 6);
        Term term8 = new Term("AAD", 7);
        Term term9 = new Term("AAE", 8);
        Term term10 = new Term("AAF", 9);

        Term[] termList = {term1, term2, term3, term4, term5, term6, term7, term8, term9, term10};
        Comparator<Term> comparatorReverse = Term.byReverseWeightOrder();
        Comparator<Term> comparatorP2 = Term.byPrefixOrder(2);
        Comparator<Term> comparatorP5 = Term.byPrefixOrder(5);
        Comparator<Term> comparatorP11 = Term.byPrefixOrder(11);

        

        int indexTermFirst = BinarySearchDeluxe.firstIndexOf(termList, term1, comparatorP2);
        int indexTermLast = BinarySearchDeluxe.lastIndexOf(termList, term1, comparatorP2);
        StdOut.println(indexTermFirst);
        StdOut.println(indexTermLast);

    }
}

Corner cases.  Throw an IllegalArgumentException if any argument to either firstIndexOf() or lastIndexOf() is null.

Preconditions.  Assume that the argument array is in sorted order (with respect to the supplied comparator).

Unit testing.  Your main() method must call each public method directly and help verify that they work as prescribed (e.g., by printing results to standard output).

Performance requirements.  The firstIndexOf() and lastIndexOf() methods must make at most 1+⌈log2n⌉
 compares in the worst case, where n is the length of the array. In this context, a compare is one call to comparator.compare().

Part 3: autocomplete. This is the part you need to generate yourself, implementing the other two parts of course. In this part, you will implement a data type that provides autocomplete functionality for a given set of string and weights, using Term and BinarySearchDeluxe. To do so, sort the terms in lexicographic order; use binary search to find the all query strings that start with a given prefix; and sort the matching terms in descending order by weight. Organize your program by creating an immutable data type Autocomplete with the following API:

public class Autocomplete {

    // Initializes the data structure from the given array of terms.
    public Autocomplete(Term[] terms)

    // Returns all terms that start with the given prefix,
    // in descending order of weight.
    public Term[] allMatches(String prefix)

    // Returns the number of terms that start with the given prefix.
    public int numberOfMatches(String prefix)

    // unit testing (required)
    public static void main(String[] args)

}
Corner cases.  Throw an IllegalArgumentException in the constructor if either its argument array is null or any entry is null. Throw an IllegalArgumentException in allMatches() and numberOfMatches() if its argument is null.

Unit testing.  Your main() method call each public constructor and method directly and help verify that they work as prescribed (e.g., by printing results to standard output).

Performance requirements.  Your implementation must achieve each of the following worst-case performance requirements:

The constructor must make O(nlogn)
 compares where n is the number of terms.
The allMatches() method must make O(mlogm+logn)
 compares, where m is the number of matching terms.
The numberOfMatches() method must make O(logn)
 compares.
In this context, a compare is one call to any of the compare() or compareTo() methods defined in Term.
Input format. We provide a number of sample input files for testing. Each file consists of an integer n followed by n pairs of query strings and non-negative weights. There is one pair per line, with the weight and string separated by a tab. A weight can be any integer between 0 and 263 − 1. A query string can be any sequence of Unicode characters, including spaces (but not newlines).