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 1 3
arrows 1 3
awry 1 26
ay 1 9
bare 1 17
be 3 1, 8
bear 3 13, 18, 21
bodkin 1 17
bourn 1 20
. . .
NOTE: 'be' must occur several times on the same line – do not repeat a line number
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:
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
//now 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
}
}
output bst
}