Lab Purpose Purpose is to develop a program that uses a binary search tree, circular linked list and hashing. Create a concordance from a text file Your program will read a file of text and produce a concordance from it. For example, output of the program for Hamlet's famous soliloquy by Shakespeare will be: . the file, each line preceded by a line number 1: To be or not to be that is the question 2: Whether tis nobler in the mind to suffer The slings 3: and arrows of outrageous fortune Or to take arms against 4: a sea of troubles And by opposing end them To 5: die to sleep No more and by a sleep to . followed by a concordance, which shows each important word in alphabetical order, with a count of the number of occurrences, and line numbers: word Count Line numbers arms w arrows 3 awry 26 ay 1 bare 1 17 be 3 1, 8 bear 3 13, 18, 21 bodkin 17 bourn 1 20 NOTE: 'be' must occur several times on the same line - do not repeat a line numberThe binary search tree Build a binary search tree of the important words read from the file: to be whether of not that 1S question the Figure I beginning to build the binary search tree All of the file reading and word processing is given to you . a word is defined as consecutive alphabetic characters . spaces, newlines and punctuation characters are used only to mark work boundaries, are not included in the tree . any uppercase letters are converted to lowercase . all of the file reading and word processing is given to you The WordCount class The WordCount class represents all the information for a word in the concordance. So WordCount will be the information stored in the generic bst. You must write this class. Three instance variables, then appropriate methods: public class wordCount implements Comparable protected String word; protected int count; protected CircularList lineNums; . lineNums here will be a reference to a circular linked list of integers, used to store line numbers of occurrence:. use a circular linked list because, with just a single reference it's easy to add at rear, print from the front in order . again, do not add a new item to the list if the word occurs again on the same line. Use hashing to omit common words We will use hashing to omit common, uninteresting words. Hashing will be covered next week, will be added to the lab then. Ignore for now, make the program work for every word. main() is given to you main() does all the file input and output for you, setting the word and linenum to be processed. main() in pseudocode will be something like: main { build then output hash table / /do later while(!eof input file) { sets and outputs word, lineNum / ow process word and lineNum here if(!word found in hash table) { / /do later if (word is found in bst) update in bst else insert into bst 7 output bstHints So you are writing three things: - appropriate methods to implement the WurdCount class - add a method to the CircularList class which returns the last line number in the list. This will be useful when deciding whether to add the current line number to the list of line numbers - appropriate code in main\" to search then either update or insert into the bst. When complete and correct, run the program and save the output as an outputttxt text le, saved in the BlueJ project folder. Use hashing to omit common words We will now use hashing to omit common, uninteresting words from the concordance. The program will first build a hash table by opening and processing a text file containing the common words. Use linear probing to handle collisions. Output the number of collisions that occur when building the hash table. Then output the hash table, counting the number of words in the table. Finally, use fast hashing search to quickly compare each input word from the hamlet input text against the common words. Only put an input word into the bat and therefore the concordance, if hashing does not find it in the common words. As a reminder, here's the main() method in pseudocode: main { build then output hash table / /add now while(leof input file) { sets and outputs word, lineNum / ow process word and lineNum here if (!word found in hash table) { //add now if (word is found in bst) update in bst else insert into bst output butThe HashTable class The HashTable class implements the required hashing functionality. you must complete this class as follows; Just one instance variable, then appropriate methods: public class Hash Table { public static 'Final int MAX = 36; private String hashTab1e; - MAX is the size of the hash table 0 we know from my lecture notes that MAX ideally is "a prime number 10 times" the number of keys 0 however, MAX is deliberately set much smaller here. to test your handling of collisions The constructor method - builds the hash table from the 'common_words.txt' text le 0 use linear probing to handle collisions 0 count the number of collisions while building the hash table 0 a collision is every time a word cannot be put into a hash table slot because it is full 0 output the number of collisions at the end of the method The nd() method - takes a word as a param, returns true if the word is found in the hash table, false otherwise 0 use hashing for fast search, with linear probing to handle collisions l he tobtrlngu method - traverses the hash table to output each word, preceded by a simple word count as shown next o e'gt partial output from toString when printed would be: their now have on m b w M H every Hints So now that some hashing stuff is added, program output should look something like: Number of collisions building the table: ?? their now have on m h w M H every To be or not to he that is the question whether tis nobler in the mind to suffer The slings and arrows of outrageous ortune Or to take arms against a sea of troubles And by opposing and them To 4: 5: ache die to sleep Me More and by a sleep to action against arms 27 ea >4 H ea pa arrows When complete and correct, run the program and save the output as an outputtxt text le, saved in the BlueJ project folder