Fill in the class FileAvl.java such that it indexes the words contained in a text file. The constructor of the FileAvl object should take in the file name as a parameter. It will then go through the input file line by line. For each line, it extracts each word, and inserts that word along with its line number into an AVL tree. Each element of the AVL tree should contain a unique word and a java.util.LinkedList of line numbers where that word occurs.

To implement this AVL tree, use the AvlTree code from the textbook as a starting point. Ive included this code in the project workspace. Ive also included the UnderflowException class which is needed for AvlTree to compile.

Add the following functionality to the AvlTree class by modifying the file:

Make sure the elements in the AvlTree are pairs of a word and a linked list storing line numbers. The relative order of elements in the data structure should depend on the word only. To do this I recommend adding a LinkedList object to the existing AVLNode class. You will also need to edit the add method insert method to take both a word and a line number. In this particular case its also not necessary for AVLTree to be generic, so you may remove generics and make the class simply an AvlTree of String objects.

You are allowed to remove extraneous methods from AVLTree.

Give the following functionality to your FileAvl class:

Write the method public void indexWord(String word, int line) that adds an occurrence of the word word in line line to the AvlTree instance of the FileAvl object. If a word already exists in the AVL Tree, simply add the new line number to the existing node. If a word appears on the same line twice, it should only have one entry in the list for that line. You may assume that word and line are valid inputs to the function.

Write the method public List getLinesForWord(String word) that looks up a word and returns a list of lines in which it occurs for a given FileAVL object. If the word does not exist in the AvlTree, return an empty list.

Write the method public void printIndex() the prints out each unique word that is stored in the AvlTree along with a list of line numbers in which that word appears, in alphabetical order. The output format should be as given below. Any deviation from the prescribed format may result in point deductions.

: , , , ........

Finally, in the file Problem2.java, write a main method to create an instance of your FileAVL class and use it to index the words contained in a text file (provided to the program as a command line argument). Ignore case in the input text (insert everything as lower case). Do NOT remove punctuation. You must split the line into words by whitespace using the String class split method (for example, data structures is fun should be four words: {"data", "structures", "is", "fun"}). When indexing has finished, the program should call the printIndex method to display a list of unique words in the text file and the line numbers in which that word occurs.

Ive provided a very simple file called test.txt that you can use to test your program. Ive also provided a file called output.txt which contains the correct output for the program on the test.txt file. Ive also provided a much larger test file called frank.txt. For the larger test file I will not be providing sample output.