This is java Write a program to implement autocomplete for a given set of N term
ID: 3591118 • Letter: T
Question
This is java
Write a program to implement autocomplete for a given set of N terms, where a term is a query string and an associated nonnegative 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.
In these examples, 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 that 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!
In this assignment, you will implement autocomplete by (1) sorting the terms by query string; (using one of the sorts introduced in lecture), (2) binary searching to find all query strings that start with a given prefix; and (3) sorting the matching terms by weight.
Part 1: autocomplete 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).
Corner cases. The constructor should throw a java.lang.NullPointerException if query is null and a java.lang.IllegalArgumentException if weight is negative. The byPrefixOrder() method should throw a java.lang.IllegalArgumentException if r is negative.
Performance requirements. The string comparison functions should 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. Accordingly, implement the following API:
public class BinarySearchDeluxe { // Returns the index of the first key in a[] that equals the search key, or -1 if no such key. public static int firstIndexOf(Key[] a, Key key, Comparator comparator) // Returns the index of the last key in a[] that equals the search key, or -1 if no such key. public static int lastIndexOf(Key[] a, Key key, Comparator comparator) // unit testing (you should have some Unit Testing here to confirm that your methods work) public static void main(String[] args) }
Corner cases. Each static method should throw a java.lang.NullPointerException if any of its arguments is null. You should assume that the argument array is in sorted order (with respect to the supplied comparator).
Performance requirements. The firstIndexOf() and lastIndexOf() methods should make at most 1 + log2 N 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. 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 sortthe 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) }
Corner cases. The constructor should throw a java.lang.NullPointerException if its argument is null or if any of the entries in its argument array are null. Each method should throw a java.lang.NullPointerException if its argument is null.
Performance requirements.
The constructor should make proportional to N log N compares (or better) in the worst case, where N is the number of terms. (This is the number of compares required to put the terms in lexicographically sorted order)
The allMatches()method should make proportional to log N + M log M compares (or better) in the worst case, where M is the number of matching terms. (log N is the number of compares required for a binary search; M log M is the number of compares required to sort the M matching entries by weight)
The numberOfMatches() method should make proportional to log N compares (or better) in the worst case. (It's calling firstIndexOf and lastIndexOf to get the range, and each is a binary search)
In this context, a compare is one call to any of the compare() or compareTo() methods defined in Term. Any sort must be linearithmic.
CHANGE: You may use Arrays.sort() for this assignment. If you wish to use one of the sorts introduced in lecture (e.g. Insertion.sort() or MergeX.sort()), you may do so. Note that the merge sort implementation is in MergeX.sort; for some reason, Merge.sort doesn't accept Comparators. You may not call any library functions other than those in java.lang, java.util, stdlib.jar, and algs4.jar.
Input format. We provide a number of sample input files for testing. Each file consists of an integer N ( the number of terms) followed by N pairs of query strings and nonnegative 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 2^63 1. A query string can be an arbitrary sequence of Unicode characters, including spaces (but not newlines).
The file wiktionary.txt contains the 10,000 most common words in Project Gutenberg, with weights proportional to their frequencies.
The file cities.txt contains over 90,000 cities, with weights equal to their populations.
Below is a sample client that takes the name of an input file and an integer k as command-line arguments. It reads the data from the file; then it repeatedly reads autocomplete queries from standard input, and prints out the top k matching terms in descending order of weight. This uses your Term and Autocompleteto perform its work. Use it to verify your code (beyond unit tests).
Here are a few sample executions:
Interactive GUI (optional, but fun and no extra work). Download and compile AutocompleteGUI.java. The program takes the name of a file and an integer k as command-line arguments and provides a GUI for the user to enter queries. It presents the top k matching terms in real time. When the user selects a term, the GUI opens up the results from a Google search for that term in a browser.
% more wiktionary.txt 10000 5627187200 the 3395006400 of 2994418400 and 2595609600 to 1742063600 in 1176479700 i 1107331800 that 1007824500 was 879975500 his ... 392323 calves
% more cities.txt 93827 14608512 Shanghai, China 13076300 Buenos Aires, Argentina 12691836 Mumbai, India 12294193 Mexico City, Distrito Federal, Mexico 11624219 Karachi, Pakistan 11174257 stanbul, Turkey 10927986 Delhi, India 10444527 Manila, Philippines 10381222 Moscow, Russia ... 2 Al Khniq, YemenIMDb a beautif All IMDbPro A Beautiful Mind (2001) Russell Crowe, Ed Harris A Beautiful Life (2008) Dana Delany, Debi Mazar A Beautiful Soul (202 randt Deitrick Haddon, Lesley-Ann Brandt AMER See all results for "a beauyt" NAME MACHET Breaking Bad American Hustle Trailer #1 Breaking Bad Machete Kills Trailer #2 "Say My Name" See featured HD Trailers »
Explanation / Answer
import java.io.IOException; import java.io.UnsupportedEncodingException; import java.net.URI; import java.net.URISyntaxException; import java.net.URLEncoder; import java.awt.Color; import java.awt.Font; import java.awt.Container; import java.awt.Dimension; import java.awt.GridLayout; import java.awt.Desktop; import java.awt.event.MouseEvent; import java.awt.event.MouseAdapter; import java.awt.event.FocusEvent; import java.awt.event.FocusListener; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.SwingUtilities; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.JComponent; import javax.swing.JTextField; import javax.swing.JList; import javax.swing.JScrollPane; import javax.swing.JButton; import javax.swing.JCheckBox; import javax.swing.JLabel; import javax.swing.GroupLayout; import javax.swing.BorderFactory; import javax.swing.LayoutStyle; import javax.swing.KeyStroke; import javax.swing.ListSelectionModel; import javax.swing.Action; import javax.swing.AbstractAction; import javax.swing.event.DocumentEvent; import javax.swing.event.DocumentListener; import javax.swing.event.MouseInputAdapter; import edu.princeton.cs.algs4.In; public class AutocompleteGUI extends JFrame { // for serializable classes private static final long serialVersionUID = 1L; private static final int DEF_WIDTH = 850; // width of the GUI window private static final int DEF_HEIGHT = 400; // height of the GUI window // URL prefix for searches private static final String SEARCH_URL = "https://www.google.com/search?q="; // Display top k results private final int k; // Indicates whether to display weights next to query matches private boolean displayWeights = true; /** * Initializes the GUI, and the associated Autocomplete object * @param filename the file to read all the autocomplete data from * @param k the maximum number of suggestions to return */ public AutocompleteGUI(String filename, int k) { this.k = k; setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setTitle("Autocomplete Me"); setPreferredSize(new Dimension(DEF_WIDTH, DEF_HEIGHT)); pack(); setLocationRelativeTo(null); Container content = getContentPane(); GroupLayout layout = new GroupLayout(content); content.setLayout(layout); layout.setAutoCreateGaps(true); layout.setAutoCreateContainerGaps(true); final AutocompletePanel ap = new AutocompletePanel(filename); JLabel textLabel = new JLabel("Search query:"); // Create and add a listener to the Search button JButton searchButton = new JButton("Search Google"); searchButton.addActionListener( new ActionListener() { public void actionPerformed(ActionEvent ae) { searchOnline(ap.getSelectedText()); } }); // Create and add a listener to a "Show weights" checkbox JCheckBox checkbox = new JCheckBox("Show weights", null, displayWeights); checkbox.addActionListener( new ActionListener() { public void actionPerformed(ActionEvent ae) { displayWeights = !displayWeights; ap.update(); } }); // Define the layout of the window layout.setHorizontalGroup( layout.createSequentialGroup() .addGroup(layout.createParallelGroup( GroupLayout.Alignment.TRAILING) .addComponent(textLabel, GroupLayout.PREFERRED_SIZE, GroupLayout.DEFAULT_SIZE, GroupLayout.PREFERRED_SIZE) .addComponent(checkbox, GroupLayout.PREFERRED_SIZE, GroupLayout.DEFAULT_SIZE, GroupLayout.PREFERRED_SIZE)) .addPreferredGap(LayoutStyle.ComponentPlacement.RELATED, GroupLayout.DEFAULT_SIZE, GroupLayout.DEFAULT_SIZE) .addComponent(ap, 0, GroupLayout.DEFAULT_SIZE, DEF_WIDTH) .addComponent(searchButton, GroupLayout.PREFERRED_SIZE, GroupLayout.DEFAULT_SIZE, GroupLayout.DEFAULT_SIZE) ); layout.setVerticalGroup( layout.createSequentialGroup() .addGroup(layout.createParallelGroup( GroupLayout.Alignment.LEADING) .addGroup(layout.createSequentialGroup() .addComponent(textLabel) .addComponent(checkbox)) .addComponent(ap) .addComponent(searchButton)) ); } /** * The panel that interfaces with the Autocomplete object. It consists * of a search bar that text can be entered into, and a drop-down list * of suggestions auto-completing the user's query. * */ private class AutocompletePanel extends JPanel { // for serializable classes private static final long serialVersionUID = 1L; private final JTextField searchText; // the search bar private Autocomplete auto; // the Autocomplete object private String[] results = new String[k]; // an array of matches //// private JList suggestions; // a list of autocomplete matches (Java 7) private JList suggestions; // a list of autocomplete matches (Java 6) private JScrollPane scrollPane; // the scroll bar on the side of the private JPanel suggestionsPanel; // the dropdown menu of suggestions private int extraMargin = 5; // extra room to leave at the bottom of // the suggestion drop-down below the // last suggestion // Note: can't use JList in Java 6 // TODO: change how this is implemented so it is dynamic; // shouldn't have to define a column number. // Keep these next two values in sync! - used to keep the search box // the same width as the drop-down // DEF_COLUMNS should be the number of characters in suggListLen // number of columns in the search text that is kept private final int DEF_COLUMNS = 45; // an example of one of the longest strings in the database private final String suggListLen = "Harry Potter and the Deathly Hallows: Part 1 (2010)"; /** * Creates the Autocomplete object and the search bar and suggestion * drop-down portions of the GUI * @param filename the file the Autocomplete object is constructed from */ public AutocompletePanel(String filename) { super(); // Read in the data Term[] terms = null; try { In in = new In(filename); String line0 = in.readLine(); if (line0 == null) { System.err.println("Could not read line 0 of " + filename); System.exit(1); } int n = Integer.parseInt(line0); terms = new Term[n]; for (int i = 0; i = 0) { suggestions.requestFocusInWindow(); suggestions.setSelectedIndex( suggestions.getSelectedIndex() - 1); } } }; Action moveSelectionDown = new AbstractAction() { // for serializable classes private static final long serialVersionUID = 1L; public void actionPerformed(ActionEvent e) { if (suggestions.getSelectedIndex() != results.length) { suggestions.requestFocusInWindow(); suggestions.setSelectedIndex( suggestions.getSelectedIndex() + 1); } } }; Action moveSelectionUpFocused = new AbstractAction() { // for serializable classes private static final long serialVersionUID = 1L; public void actionPerformed(ActionEvent e) { if (suggestions.getSelectedIndex() == 0) { suggestions.clearSelection(); searchText.requestFocusInWindow(); searchText.setSelectionEnd(0); } else if (suggestions.getSelectedIndex() >= 0) { suggestions.setSelectedIndex( suggestions.getSelectedIndex() - 1); } } }; suggestions.getInputMap(JComponent.WHEN_IN_FOCUSED_WINDOW).put( KeyStroke.getKeyStroke("UP"), "moveSelectionUp"); suggestions.getInputMap(JComponent.WHEN_IN_FOCUSED_WINDOW).put( KeyStroke.getKeyStroke("DOWN"), "moveSelectionDown"); suggestions.getActionMap().put( "moveSelectionUp", moveSelectionUp); suggestions.getActionMap().put( "moveSelectionDown", moveSelectionDown); suggestions.getInputMap(JComponent.WHEN_FOCUSED).put( KeyStroke.getKeyStroke("ENTER"), "makeSelection"); suggestions.getInputMap().put( KeyStroke.getKeyStroke("UP"), "moveSelectionUpFocused"); suggestions.getActionMap().put( "moveSelectionUpFocused", moveSelectionUpFocused); suggestions.getActionMap().put("makeSelection", makeSelection); // Create the suggestion drop-down panel and scroll bar suggestionsPanel = new JPanel(); scrollPane = new JScrollPane(suggestions); scrollPane.setVisible(false); int prefBarWidth = scrollPane.getVerticalScrollBar().getPreferredSize().width; suggestions.setPreferredSize(new Dimension(searchText.getPreferredSize().width, 0)); scrollPane.setAutoscrolls(true); scrollPane.setHorizontalScrollBarPolicy(JScrollPane.HORIZONTAL_SCROLLBAR_NEVER); scrollPane.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED); // resize widths and heights of all components to fit nicely int preferredWidth = searchText.getPreferredSize().width + 2*prefBarWidth; int maxWidth = searchText.getMaximumSize().width + 2*prefBarWidth; int searchBarHeight = searchText.getPreferredSize().height; int suggestionHeight = suggestions.getFixedCellHeight(); int maxSuggestionHeight = DEF_HEIGHT*2; suggestionsPanel.setPreferredSize(new Dimension(preferredWidth, suggestionHeight)); suggestionsPanel.setMaximumSize(new Dimension(maxWidth, maxSuggestionHeight)); suggestionsPanel.setBorder(BorderFactory.createEmptyBorder(0, 0, 0, 0)); suggestionsPanel.add(scrollPane); suggestionsPanel.setLayout(new GridLayout(1, 1)); this.setPreferredSize(new Dimension(preferredWidth, this.getPreferredSize().height)); this.setMaximumSize(new Dimension(preferredWidth, searchBarHeight + maxSuggestionHeight)); searchTextPanel.setPreferredSize(new Dimension(preferredWidth, searchBarHeight)); searchTextPanel.setMaximumSize(new Dimension(maxWidth, searchBarHeight)); searchText.setMaximumSize(new Dimension(maxWidth, searchBarHeight)); // add mouse interactivity with the drop-down menu suggestions.addMouseListener( new MouseAdapter() { @Override public void mouseClicked(MouseEvent mouseEvent) { JList theList = (JList) mouseEvent.getSource(); if (mouseEvent.getClickCount() >= 1) { int index = theList.locationToIndex( mouseEvent.getPoint()); if (index >= 0) { String selection = getSelectedText(); searchText.setText(selection); String text = searchText.getText(); getSuggestions(text); searchOnline(searchText.getText()); } } } @Override public void mouseEntered(MouseEvent mouseEvent) { JList theList = (JList) mouseEvent.getSource(); int index = theList.locationToIndex( mouseEvent.getPoint()); theList.requestFocusInWindow(); theList.setSelectedIndex(index); } @Override public void mouseExited(MouseEvent mouseEvent) { suggestions.clearSelection(); searchText.requestFocusInWindow(); } }); suggestions.addMouseMotionListener( new MouseInputAdapter() { @Override // Google a term when a user clicks on the dropdown menu public void mouseClicked(MouseEvent mouseEvent) { JList theList = (JList) mouseEvent.getSource(); if (mouseEvent.getClickCount() >= 1) { int index = theList.locationToIndex( mouseEvent.getPoint()); if (index >= 0) { String selection = getSelectedText(); searchText.setText(selection); String text = searchText.getText(); getSuggestions(text); searchOnline(searchText.getText()); } } } @Override public void mouseEntered(MouseEvent mouseEvent) { JList theList = (JList) mouseEvent.getSource(); int index = theList.locationToIndex( mouseEvent.getPoint()); theList.requestFocusInWindow(); theList.setSelectedIndex(index); } @Override public void mouseMoved(MouseEvent mouseEvent) { JList theList = (JList) mouseEvent.getSource(); int index = theList.locationToIndex( mouseEvent.getPoint()); theList.requestFocusInWindow(); theList.setSelectedIndex(index); } }); // add a listener that allows updates each time the user types searchText.getDocument().addDocumentListener( new DocumentListener() { public void insertUpdate(DocumentEvent e) { changedUpdate(e); } public void removeUpdate(DocumentEvent e) { changedUpdate(e); } public void changedUpdate(DocumentEvent e) { String text = searchText.getText(); // updates the drop-down menu getSuggestions(text); updateListSize(); } }); // When a user clicks on a suggestion, Google it searchText.addActionListener( new ActionListener() { public void actionPerformed(ActionEvent e) { String selection = getSelectedText(); searchText.setText(selection); getSuggestions(selection); searchOnline(searchText.getText()); } }); // Define the layout of the text box and suggestion dropdown layout.setHorizontalGroup( layout.createSequentialGroup() .addGroup(layout.createParallelGroup( GroupLayout.Alignment.LEADING) .addComponent(searchTextPanel, 0, GroupLayout.DEFAULT_SIZE, GroupLayout.PREFERRED_SIZE) .addComponent(suggestionsPanel, GroupLayout.DEFAULT_SIZE, GroupLayout.DEFAULT_SIZE, GroupLayout.PREFERRED_SIZE)) ); layout.setVerticalGroup( layout.createSequentialGroup() .addComponent(searchTextPanel) .addComponent(suggestionsPanel) ); } /** * Re-populates the drop-down menu with the new suggestions, and * resizes the containing panel vertically */ private void updateListSize() { int rows = k; if (suggestions.getModel().getSize() suggListLen.length()) query = query.substring(0, suggListLen.length()); // create the table HTML results[i] = "" + "" + query.substring(0, textLen + 1) + "" + query.substring(textLen + 1) + ""; if (displayWeights) { results[i] += "" + "" + weight + ""; } results[i] += ""; } suggestions.setListData(results); suggestions.setVisible(true); scrollPane.setVisible(true); } else { // No suggestions suggestions.setListData(new String[0]); suggestions.clearSelection(); suggestions.setVisible(false); scrollPane.setVisible(false); } } } // bring the clicked suggestion up to the Search bar and search it public String getSelectedText() { if (!suggestions.isSelectionEmpty()) { String selection = (String) suggestions.getSelectedValue(); if (displayWeights) { selection = selection.substring(0, selection.indexOf("Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.