The rest of the problem is here: https://www.cs.princeton.edu/courses/archive/fa

Question

The rest of the problem is here:

https://www.cs.princeton.edu/courses/archive/fall16/cos226/assignments/autocomplete.html

Write an immutable data type Term. java that represents an auto complete 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). public class Tern lmplements Comparable {//Initializes a term with the given query string and weight. public Term(String Query, long weight)//Compares two terms in descending order by weight public static Comparator byReverseweightOrder()//compares the two terms in lexicographic order hut using only the first r characters of each query. public static Comparator byprefixorder (int r)//Compares the two terms in lexicographic order by query public int compareto (Term that)//Returns a string representation of this tern in the following format://the weight, followed by a tab, followed by the query, public String toString()//unit testing (required) public static void main(String[] arga)} The string comparison functions should take time proportional to the number of characters needed to resolve the comparison.

Explanation / Answer

//AutocompleteGUI .java

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.introcs.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;

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

  

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<String> 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
private final int DEF_COLUMNS = 45;
  
// an example of one of the longest strings in the database
private final String suggListLen =
"<b>Harry Potter and the Deathly Hallows: Part 1 (2010)</b>";
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 < N; i++) {
String line = in.readLine();
if (line == null) {
System.err.println("Could not read line " + (i+1) + " of " + filename);
System.exit(1);
}
int tab = line.indexOf(' ');
if (tab == -1) {
System.err.println("No tab character in line " + (i+1) + " of " + filename);
System.exit(1);
}
long weight = Long.parseLong(line.substring(0, tab).trim());
String query = line.substring(tab + 1);
terms[i] = new Term(query, weight);
}
}
catch (Exception e) {
System.err.println("Could not read or parse input file " + filename);
e.printStackTrace();
System.exit(1);
}

// Create the autocomplete object
auto = new Autocomplete(terms);

GroupLayout layout = new GroupLayout(this);
this.setLayout(layout);
  
// create the search text, and allow the user to interact with it
searchText = new JTextField(DEF_COLUMNS);
searchText.setMaximumSize(new Dimension(
searchText.getMaximumSize().width,
searchText.getPreferredSize().height));
searchText.getInputMap().put(
KeyStroke.getKeyStroke("UP"), "none");
searchText.getInputMap().put(
KeyStroke.getKeyStroke("DOWN"), "none");
searchText.addFocusListener(
new FocusListener() {
@Override
public void focusGained(FocusEvent e) {
int pos = searchText.getText().length();
searchText.setCaretPosition(pos);
}
public void focusLost(FocusEvent e) { }
});
  
// create the search text box
JPanel searchTextPanel = new JPanel();
searchTextPanel.add(searchText);
searchTextPanel.setBorder(
BorderFactory.createEmptyBorder(0, 0, 0, 0));
searchTextPanel.setLayout(new GridLayout(1, 1));
  
// create the drop-down menu items
int fontsize = 13;
int cellHeight = 20;
  
// suggestions = new JList<String>(results);
suggestions = new JList(results);
suggestions.setBorder(BorderFactory.createLineBorder(Color.BLACK, 1));
suggestions.setVisible(false);
suggestions.setSelectionMode(ListSelectionModel.SINGLE_SELECTION);
suggestions.setMaximumSize(new Dimension(
searchText.getMaximumSize().width,
suggestions.getPreferredSize().height));
  
// Set to make equal to the width of the textfield
suggestions.setPrototypeCellValue(suggListLen);   
suggestions.setFont(
suggestions.getFont().deriveFont(Font.PLAIN, fontsize));
suggestions.setFixedCellHeight(cellHeight);
  
// add arrow-key interactivity to the drop-down menu items
Action makeSelection = new AbstractAction() {
// for serializable classes
private static final long serialVersionUID = 1L;
public void actionPerformed(ActionEvent e) {
if (!suggestions.isSelectionEmpty()) {
String selection =
(String) suggestions.getSelectedValue();
if (displayWeights)
selection = selection.substring(
0, selection.indexOf("<td width="));
selection = selection.replaceAll("\<.*?>", "");
searchText.setText(selection);
getSuggestions(selection);
}
searchOnline(searchText.getText());
}
};
Action moveSelectionUp = new AbstractAction() {
// for serializable classes
private static final long serialVersionUID = 1L;
@Override
public void actionPerformed(ActionEvent e) {
if (suggestions.getSelectedIndex() >= 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)
);
}

private void updateListSize()
{
int rows = k;
if (suggestions.getModel().getSize() < k) {
rows = suggestions.getModel().getSize();
}
  
int suggWidth = searchText.getPreferredSize().width;
int suggPanelWidth = suggestionsPanel.getPreferredSize().width;
int suggHeight = rows*suggestions.getFixedCellHeight();
  
suggestions.setPreferredSize(new Dimension(suggWidth, suggHeight));
suggestionsPanel.setPreferredSize(new Dimension(suggPanelWidth, suggHeight + extraMargin));
suggestionsPanel.setMaximumSize(new Dimension(suggPanelWidth, suggHeight + extraMargin));

//redraw the suggestion panel
suggestionsPanel.setVisible(false);
suggestionsPanel.setVisible(true);
}

// see getSuggestions for documentation
public void update() {
getSuggestions(searchText.getText());
}

public void getSuggestions(String text) {
  
// don't search for suggestions if there is no input
if (text.equals("")) {
suggestions.setListData(new String[0]);
suggestions.clearSelection();
suggestions.setVisible(false);
scrollPane.setVisible(false);
}
else {
int textLen = text.length();

// get all matching terms
Term[] allResults = auto.allMatches(text);
if (allResults == null) {
throw new NullPointerException("allMatches() is null");
}

results = new String[Math.min(k, allResults.length)];
if (Math.min(k, allResults.length) > 0) {
for (int i = 0; i < results.length; i++) {

// A bit of a hack to get the Term's query string
// and weight from toString()
String next = allResults[i].toString();
if (allResults[i] == null) {
throw new NullPointerException("allMatches() "
+ "returned an array with a null entry");
}
int tab = next.indexOf(' ');
if (tab < 0) {
throw new RuntimeException("allMatches() returned"
+ " an array with an entry without a tab:"
+ " '" + next + "'");
}
String weight = next.substring(0, tab).trim();
String query = next.substring(tab);

// truncate length if needed
if (query.length() > suggListLen.length())
query = query.substring(0, suggListLen.length());

// create the table HTML
results[i] = "<html><table width=""
+ searchText.getPreferredSize().width + "">"
+ "<tr><td align=left>"
+ query.substring(0, textLen + 1)
+ "<b>" + query.substring(textLen + 1) + "</b>";
if (displayWeights) {
results[i] += "<td width="10%" align=right>"
+ "<font size=-1><span id="weight" "
+ "style="float:right;color:gray">"
+ weight + "</font>";
}
results[i] += "</table></html>";
}
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("<td width="));
}
selection = selection.replaceAll("\<.*?>", "");
selection = selection.replaceAll("^[ ]+|[ ]+$", "");
return selection;
}
else {
return getSearchText();
}
}
public String getSearchText() {
return searchText.getText();
}
}

private void searchOnline(String s) {

// create the URL
URI searchAddress = null;
try {
URI tempAddress = new URI(SEARCH_URL + URLEncoder.encode(s.trim(), "UTF-8"));
searchAddress = new URI(tempAddress.toASCIIString()); // Hack to handle Unicode
}
catch (URISyntaxException e2) {
e2.printStackTrace();
return;
}
catch (UnsupportedEncodingException e) {
e.printStackTrace();
return;
}

// open the URL in the browser
try {
Desktop.getDesktop().browse(searchAddress);
}
catch (IOException e1) {
e1.printStackTrace();
}
}

public static void main(String[] args) {
final String filename = args[0];
final int k = Integer.parseInt(args[1]);
SwingUtilities.invokeLater(
new Runnable() {
public void run() {
new AutocompleteGUI(filename, k).setVisible(true);
}
});
}
}

===========================================================================

//BinarySearchDeluxe.java

import java.util.Comparator;

public class BinarySearchDeluxe
{

// Return the index of the first key that equals the search key, return-1 if no such key.
public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator)
{
if (a.length <= 0)//check for invalid length
{
return -1;
}
int min = 0;
int max = a.length - 1;
int middle;
while (min <= max)
{

middle = (max - min) / 2 + min;
if (comparator.compare(key, a[middle]) > 0)//passed key is greater than key in
{ //the middle position
min = middle + 1;
}
else if (comparator.compare(key, a[middle]) < 0)//passed key is less than key in
{ //the middle position
max = middle - 1;
}
else //passed key is equal to the key in
{ //the middle position
  
if (middle == 0)//check for the first position of the array
{
return middle;
}
else if (comparator.compare(key, a[middle - 1]) > 0)//check if position a[middle--] is also
//greater than the passed key
{
return middle;
}
else //the previous position is also equal or greater than the passed key
{
max = middle - 1;//set max to middle-- and go through the checks again
}//end inner if else loop
}//end outer if else loop
}//end while

return -1;
}//end firstIndexOf()

// Return the index of the last key that equals the search key, return -1 if no such key.
public static <Key> int lastIndexOf(Key[] a, Key key,
Comparator<Key> comparator)
{
if (a.length <= 0)//check for invalid length
{
return -1;
}
int length = a.length - 1;
int min = 0;
int max = length;
int middle;
while (min <= max)
{
middle = (max - min) / 2 + min;
if (comparator.compare(key, a[middle]) > 0)//passed key is greater than key in
{ //the middle position
min = middle + 1;
}
else if (comparator.compare(key, a[middle]) < 0)//passed key is less than key in
{ //the middle position
max = middle - 1;
}
else //passed key is equal to the key in
{ //the middle position
  
if (middle == length) //is this the last pos in the array?
{   
return middle;
}
else if (comparator.compare(key, a[middle + 1]) < 0)//is the pos next position greater than the key?
{
return middle;
}
else //the next position is also equal or less than
{
min = middle + 1; //set min for another run through to check the next higher position
}//end inner if else loop
}//end outer if else loop
}//end while
return -1;
}//end lastIndexOf()
}//end class

=========================================================================

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.