Instructions
Requirements and Specifications
Source Code
// Your class. Notice how it has no generics.
import java.io.File;
import java.util.Scanner;
// This is because we use generics when we have no idea what kind of data we are getting
// Here we know we are getting two pieces of data: a string and a line number
public class IndexTree {
// This is your root
// again, your root does not use generics because you know your nodes
// hold strings, an int, and a list of integers
private IndexNode root;
// Make your constructor
public IndexTree() {
root = null;
}
// It doesn't need to do anything
// complete the methods below
// this is your wrapper method
// it takes in two pieces of data rather than one
// call your recursive add method
public void add(String word, int lineNumber) {
word = word.toLowerCase();
root = add(root, word, lineNumber);
}
// your recursive method for add
// Think about how this is slightly different the the regular add method
// When you add the word to the index, if it already exists,
// you want to add it to the IndexNode that already exists
// otherwise make a new indexNode
private IndexNode add(IndexNode root, String word, int lineNumber) {
if (root == null) {
root = new IndexNode(word, lineNumber);
} else if (word.compareToIgnoreCase(root.word) < 0) {
root.left = add(root.left, word, lineNumber);
} else if (word.compareToIgnoreCase(root.word) > 0) {
root.right = add(root.right, word, lineNumber);
} else if (!root.list.contains(lineNumber)) {
root.list.add(lineNumber);
}
return root;
}
// returns true if the word is in the index
public boolean contains(String word) {
word = word.toLowerCase();
IndexNode current = root;
while (current != null) {
if (word.compareToIgnoreCase(current.word) < 0) {
current = current.left;
} else if (word.compareToIgnoreCase(current.word) > 0) {
current = current.right;
} else {
return true;
}
}
return false;
}
// call your recursive method
// use book as guide
public void delete(String word) {
ord = word.toLowerCase();
root = delete(root, word);
}
// your recursive case
// remove the word and all the entries for the word
// This should be no different than the regular technique.
private IndexNode delete(IndexNode root, String word) {
if (root == null) {
return root;
}
if (word.compareToIgnoreCase(root.word) < 0) {
root.left = delete(root.left, word);
} else if (word.compareToIgnoreCase(root.word) > 0) {
root.right = delete(root.right, word);
} else if (root.left != null && root.right != null) {
IndexNode minNode = findMinimum(root.right);
root.list = minNode.list;
root.word = minNode.word;
root.occurences = minNode.occurences;
root.right = getSuccessor(root.right);
} else {
root = (root.left != null) ? root.left : root.right;
}
return root;
}
private IndexNode findMinimum(IndexNode current) {
if (current != null) {
while (current.left != null) {
current = current.left;
}
}
return current;
}
private IndexNode getSuccessor(IndexNode current) {
if (current == null) {
return current;
}
if (current.left != null) {
current.left = getSuccessor(current.left);
return current;
}
return current.right;
}
// prints all the words in the index in inorder order
// To successfully print it out
// this should print out each word followed by the number of occurrences and the list of all occurrences
// each word and its data gets its own line
public void printIndex() {
printIndex(root);
}
private void printIndex(IndexNode current) {
if (current == null) {
return;
}
printIndex(current.left);
System.out.println(current.toString());
printIndex(current.right);
}
public static void main(String[] args) throws Exception {
IndexTree index = new IndexTree();
// add all the words to the tree
Scanner inFile = new Scanner(new File("shakespeare.txt"));
int lineNumber = 1;
while (inFile.hasNextLine()) {
// Remove punctuations on words
Scanner sc = new Scanner(inFile.nextLine().replaceAll("[^\\p{L} ]", ""));
while (sc.hasNext()) {
index.add(sc.next(), lineNumber);
}
lineNumber++;
}
inFile.close();
// print out the index
index.printIndex();
System.out.println();
// test removing a word from the index
Scanner in = new Scanner(System.in);
while (true) {
System.out.println("Menu");
System.out.println("1 - Print words");
System.out.println("2 - Delete word");
System.out.println("3 - Search word");
System.out.println("0 - Quit");
System.out.print("Option: ");
String option = in.nextLine();
if (option.equals("1")) {
index.printIndex();
} else if (option.equals("2")) {
System.out.print("Enter a word to remove: ");
index.delete(in.nextLine());
} else if (option.equals("3")) {
System.out.print("Enter a word to search: ");
System.out.println(index.contains(in.nextLine()));
} else if (option.equals("0")) {
break;
}
}
}
}