Submit Java source code for the classes AnagramTree and Anagrammer together in o
ID: 3834283 • Letter: S
Question
Submit Java source code for the classes AnagramTree and Anagrammer together in one .java file. Do not submit source code for the class Words. If you have tested your program on a short input file, and have a short list of anagrams from that file, then you may include both in comments at the end of your .java file.
Here’s how to write the program. You must use the Java class Words to read words from a text file. Java source code for Words is available below. You don’t have to write it yourself. You don’t even have to know how it works internally. All you need to know is that it acts like an iterator, and that it has the following public methods.
public Words(String path)
Constructor. Initialize an instance of Words that reads words from a text file whose name is path. Throw an IllegalArgumentException if the file doesn’t exist, or if it can’t be read for some reason.
public boolean hasNext()
Test if there is a word waiting to be read from the text file.
public String next()
Read the next word from the text file, convert all its letters to lower case, and return it as a String. It isn’t null, it isn’t empty, and it contains only lower case letters.
You must write a class called AnagramTree that represents an anagram tree. It must have the following members. To simplify grading, you must use the same names as are shown here.
private class TreeNode
(5 points.) A node in the AnagramTree. It must have four private slots and a private constructor. The slot summary points to an array of 26 byte’s; it’s the key. The slot words points to a linear singly linked list of WordNode’s; it’s the value. The slotsleft and right point to TreeNode’s, or to null; they’re subtrees.
private class WordNode
(5 points.) A node that contains a word. It must have two private slots and a private constructor. The slot word must point to a String that represents the word. The slot next must point to a WordNode, or to null; it’s the next node in a singly linked linear list.
public AnagramTree()
(5 points.) Constructor. Initialize an empty instance of AnagramTree. It must have a head node.
public void add(String word)
(20 points.) Add word to the anagram tree, as described in the previous section. This String isn’t null, it isn’t empty, and it has only lower case letters. You must use compareSummaries to control the search through the tree. You must use the tree’s head node to avoid a special case when you add word to an empty tree.
public void anagrams()
(10 points.) Traverse the anagram tree, visiting each of its TreeNode’s exactly once. You must skip the tree’s head node. Every time you visit a TreeNode, you must print all the words from its linked list of WordNode’s, separated by blanks. However, if the linked list has only one node, then you must ignore it.
private int compareSummaries(byte[] left, byte[] right)
(10 points.) Here left and right are summaries: arrays of 26 byte’s. Compare left to right using the K-and-R algorithm. If left is less than right, then return an int less than 0. If left equals right, then return 0. If left is greater than right, then return an int greater than 0.
private byte[] stringToSummary(String word)
(10 points.) Return a summary for word. This String isn’t null, it isn’t empty, and it has only lower case letters. The summary must be represented as an array of 26 byte’s. If c is a character from word, then you must use the Java expression (c 'a') to compute c’s index in that array. You must not use if’s or switch’es to compute c’s index.
You must also write a class called Anagrammer. It’s the driver, and it must have only a main method.
public static void main(String[] args)
(5 points.) Make an instance of Words that reads words from a text file. Make an empty AnagramTree. Read all the words from the text file and add them to the tree. Finally, traverse the tree to print all its anagrams.
Finally, here are some hints, notes, and threats.
Your AnagramTree class must have two nested classes: TreeNode and WordNode. Do not try to use only one nested class, because that won’t work.
You may add as many private variables to the class AnagramTree as you want. However, you must not use a private variable when a local variable would work instead.
You may write as many private helper methods as you want. You must write at least one helper for the method anagrams.
Your anagram tree must use a head node. You may design the head node however you want. However, recall that the head node’s key must appear nowhere else in the tree.
You must represent summaries as arrays of 26 byte’s. Do not use arrays of int’s, because that would take more memory. Recall that byte is Java’s smallest integer type: it can hold integers from 128 to 127. We assume that no word will have more than 127 appearances of the same letter, but you don’t have to check for this.
Source code for Words
You must submit Java source code for the classes AnagramTree and Anagrammer together in one .java file. Do not submit source code for the class Words. If you have tested your program on a short input file, and have a short list of anagrams from that file, then you may include both in comments at the end of your .java file.