-
Notifications
You must be signed in to change notification settings - Fork 0
/
Autocomplete.java
116 lines (96 loc) · 3.73 KB
/
Autocomplete.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.util.Arrays;
/*Created: Sunday, October 8th, 2017 @8:01 p.m.
*Author: Scott McKay
*Co-Others: Travis Wheeler (Unit Testing)
*Purpose of Class: Driver class for Auto-Complete.
*
*Collaborators: None
*/
public class Autocomplete
{
private Term[] terms;
//Initializes the data structure from the given array of items.
public Autocomplete(Term[] terms)
{
this.terms = terms;
}
//Returns all terms that start with the given prefix, in descending order of weight
public Term[] allMatches(String prefix)
{
Term query = new Term(prefix, 0);
int firstIndex = BinarySearchDeluxe.firstIndexOf(terms, query, Term.byPrefixOrder(query.getQuery().length()));
int lastIndex = BinarySearchDeluxe.lastIndexOf(terms, query, Term.byPrefixOrder(query.getQuery().length()));
//If there are no suggestions.
if (firstIndex == -1)
{
Term[] noSuggestions = new Term[1];
noSuggestions[0] = new Term("No Suggestions", 0);
return noSuggestions;
}
else
{
//Add one to the end to ensure array size does not equal zero.
int arraySize = (lastIndex - firstIndex) + 1;
Term[] suggestions = new Term[arraySize];
//Copy suggestions to new array, 'suggestions'
for (int index = 0; index < arraySize; index++)
{
suggestions[index] = terms[firstIndex];
firstIndex++;
}
Arrays.sort(suggestions, Term.byReverseWeightOrder());
return suggestions;
}
}
//Returns the number of terms that start with the given prefix.
public int numberOfMatches(String prefix)
{
Term query = new Term(prefix, 0);
int firstIndex = BinarySearchDeluxe.firstIndexOf(terms, query, Term.byPrefixOrder(query.getQuery().length()));
int lastIndex = BinarySearchDeluxe.lastIndexOf(terms, query, Term.byPrefixOrder(query.getQuery().length()));
if (firstIndex == -1)
{
return 0;
}
else
{
return lastIndex - firstIndex;
}
}
public static void main(String[] args)
{
StdOut.println("Autocomplete: v0.3.0");
StdOut.println("Author: Scott McKay");
StdOut.println("Course: Data Structures [Section 00]");
StdOut.println("Type '-q' to exit program");
//Read in the terms from a file
String filename = args[0];
In in = new In(filename);
int N = in.readInt();
Term[] terms = new Term[N];
for (int index = 0; index < N; index++)
{
long weight = in.readLong(); //Read the next weight
in.readChar(); //Scan past the tab
String query = in.readLine(); //Read the next query
terms[index] = new Term(query, weight);//Construct the term
}
//Read in queries from standard input and print out the top k matching terms
int k = Integer.parseInt(args[1]);
Autocomplete autocomplete = new Autocomplete(terms);
while (StdIn.hasNextLine())
{
String prefix = StdIn.readLine();
if (prefix.contentEquals("-q"))
{
break;
}
Term[] results = autocomplete.allMatches(prefix);
for (int i = 0; i < Math.min(k, results.length); i++)
{
StdOut.println(results[i]);
}
}
StdOut.println("Exit Success");
}
}