import java.util.Arrays;

public class Autocomplete {
    private final Term[] terms;

    // Initializes the data structure from the given array of terms.
    // O(N log N)
    public Autocomplete(Term[] terms) {
        if (terms == null)
            throw new java.lang.NullPointerException("terms cannot be null.");

        for (int i = 0; i < terms.length; i++)
            if (terms[i] == null)
                throw new java.lang.NullPointerException("Any item in terms cannot be null.");

        Arrays.sort(terms, Term.byLexicographicOrder());
        this.terms = terms;
    }

    // Returns all terms that start with the given prefix, in descending order of weight.
    // O(log N + M log M)
    public Term[] allMatches(String prefix) {
        if (prefix == null)
            throw new java.lang.NullPointerException("prefix cannot be null.");

        int matchesCount = numberOfMatches(prefix);
	if (matchesCount == 0) return new Term[0];
        Term[] matches = new Term[matchesCount];
        Term key = new Term(prefix, 0);
        int first = RangeBinarySearch.firstIndexOf(this.terms, key, Term.byPrefixOrder(prefix.length()));
        for (int i = 0; i < matchesCount; i++)
            matches[i] = this.terms[i + first];

        Arrays.sort(matches, Term.byReverseWeightOrder());
        return matches;
    }


    // Returns the number of terms that start with the given prefix.
    // O(log N)
    public int numberOfMatches(String prefix) {
        if (prefix == null)
            throw new java.lang.NullPointerException("prefix cannot be null.");

        Term key = new Term(prefix, 0L);
        int first = RangeBinarySearch.firstIndexOf(this.terms, key, Term.byPrefixOrder(prefix.length()));
        int last = RangeBinarySearch.lastIndexOf(this.terms, key, Term.byPrefixOrder(prefix.length()));
	if (first == -1 && last == -1) return 0;
        return last - first + 1;
    }

}