import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;

public class Driver {
public static void main(String[] args) throws FileNotFoundException {
// Once you complete the TODO code, your code should pass the tests.
if (LinkedList.testClass()) {
System.err.println("Code passes all tests. You should still make sure that the reported accuracy is 80.138%.\n" +
"Otherwise there may be an error in your predictAuthor method.\n");
}
else {
System.err.println("Please fix code and try again.");
return;
}

// Process the input
Scanner sc = new Scanner(new File("input.txt"));
int phraseCount = Integer.valueOf(sc.nextLine());
Phrase[] phrases = new Phrase[phraseCount];
for (int i = 0; i < phraseCount; i++) {
String line = sc.nextLine();
String[] tokens = line.split("\t");
phrases[i] = new Phrase(Integer.valueOf(tokens[0]),tokens[1],Integer.valueOf(tokens[2]));
}
sc.close();

// Build the phrase matcher
long startTime = System.currentTimeMillis();
PhraseMatcher phraseMatcher = new PhraseMatcher(4);
for (int i = 0; i < phraseCount; i++) {
phraseMatcher.insertNgramsFromPhrase(phrases[i]);
}
phraseMatcher.scaleWeightsByLength();

// Assess the accuracy of the system
int correct = 0;
for (int i = 0; i < phraseCount; i++) {
int bestMatch = phraseMatcher.predictAuthor(phrases[i]);
if (bestMatch == phrases[i].getAuthor()) correct++;
}
System.out.printf("System accuracy: %.3f%%%n", 100.0*correct/phraseCount);

System.out.println("Elapsed time: " +(System.currentTimeMillis() - startTime));

}
}

/**
* A spooky phrase object
*/
class Phrase {
private int id;
private int author; // 0 for Edgar Allen Poe, 1 for H.P. Lovecraft, and 3 for Mary W. Shelly
private String text; // The text of the phrase

public Phrase(int id, String text, int author) {
this.id = id;
this.text = text;
this.author = author;
}

/*
* Getter Methods
*/
public int getId() { return id; }
public int getAuthor() { return author; }
public String getText() { return text; }
}

/**
* The PhraseMatcher stores phrases for the purpose of finding similar phrases
*/
class PhraseMatcher {
private static final int LOG_CHARSET_SIZE = 5;
private final int N;
private LinkedList[] ngrams;
private int[] mappings = new int[127];

PhraseMatcher(int n) {
this.N = n;

int ndx = 0;
char[] punct = " !.\"',".toCharArray();
for (char c : punct) {
mappings[c] = ndx++;
}
for (int c = 'a'; c <= 'z'; c++) {
mappings[c] = ndx++;
}

ngrams = new LinkedList[1<<(LOG_CHARSET_SIZE*N)];
}

/**
* Add n-grams for a phrase to the appropriate linked list
*
* Extra credit: You can speed up the process of obtaining the mapping of the
* substring to an index in the ngram array, by more than a factor of N. Note
* that this is a small component of the overall running time, so you may or
* may not see a speed up in the elapsed time measure.
*
* @param phrase the phrase to add
*/
void insertNgramsFromPhrase(Phrase phrase) {
for (int i = 0; i < phrase.getText().length() - N + 1; i++) {
int index = 0;
for (int j = i; j < i+N; j++) {
index = index * 32 + mappings[phrase.getText().charAt(j)];
}
if (ngrams[index] == null) ngrams[index] = new LinkedList();
ngrams[index].addNode(phrase, 1);
}
}

/**
* Scale the weights in the ngram lists by dividing them by the length of the lists
*/
public void scaleWeightsByLength() {
for (LinkedList list: ngrams) {
if (list != null) {
list.scaleWeights();
}
}
}

/**
* Use a k-nearest neighbor approach to predict the author of the attached phrase
*
* Extra credit: You can speed up the process of obtaining the mapping of the
* substring to an index in the ngram array, by more than a factor of N. Note
* that this is a small component of the overall running time, so you may or
* may not see a speed up in the elapsed time measure.
*
* @param phrase the phrase to match
* @return the id corresponding to the predicted author
*/
int predictAuthor(Phrase phrase) {
LinkedList matchList = null;

for (int i = 0; i < phrase.getText().length() - N + 1; i++) {
int index = 0;
for (int j = i; j < i+N; j++) {
index = index * 32 + mappings[phrase.getText().charAt(j)];
}
if (matchList == null) matchList = new LinkedList(ngrams[index]);
else matchList.merge(ngrams[index]);
}

return matchList.getTopAuthor(phrase);
}
}

class LinkedList {
static int K_OF_K_NEAREST_NEIGHBORS = 27;
Node first;
int length;

public LinkedList() {}

/**
* Create a copy of the parameter list, by creating new nodes with the same
* contents of the nodes in the input list. While you should create new Node
* objects, you should not create new Phrase objects
*
* Note that this should run in time that is linear in the length of the input list.
*
* @param that the input list
*/
public LinkedList(LinkedList that) {
// TODO: Implement this method
if(that != null) {
Node tmp = that.first;
LinkedList lst = new LinkedList();
while (tmp != null) {
lst.addNode(tmp.phrase, tmp.weight);
tmp = tmp.next;
}
Node t = lst.first;
while (t != null){
addNode(t.phrase, t.weight);
t = t.next;
}
}
}

/**
* Replace all of the weights in the nodes with their weight divided
* by the length of the list
*/
public void scaleWeights() {
//TODO: Implement this method
Node tmp = first;

while (tmp != null){
tmp.weight /= (double) length;
tmp = tmp.next;
}
}

Build an implementation of a weighted graph ADT. Use it to compute...