Write a .java class called AnagramTree that represents an anagram tree. It must
ID: 3834610 • Letter: W
Question
Write a .java 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.
Submit Java source code for the classes AnagramTree and Anagrammer together in one .java file. 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.
Explanation / Answer
import java.io.FileReader; // Read Unicode chars from a file.
import java.io.IOException; // In case there's IO trouble.
// WORDS. Iterator. Read words, represented as STRINGs, from a text file. Each
// word is the longest possible contiguous series of alphabetic ASCII CHARs.
class Words
{
private int ch; // Last CHAR from READER, as an INT.
private FileReader reader; // Read CHARs from here.
private StringBuilder word; // Last word read from READER.
// Constructor. Initialize an instance of WORDS, so it reads words from a file
// whose pathname is PATH. Throw an exception if we cannot open PATH.
public Words(String path)
{
try
{
reader = new FileReader(path);
ch = reader.read();
}
catch (IOException ignore)
{
throw new IllegalArgumentException("Cannot open '" + path + "'.");
}
}
// HAS NEXT. Try to read a WORD from READER, converting it to lower case as we
// go. Test if we were successful.
public boolean hasNext()
{
word = new StringBuilder();
while (ch > 0 && ! isAlphabetic((char) ch))
{
read();
}
while (ch > 0 && isAlphabetic((char) ch))
{
word.append(toLower((char) ch));
read();
}
return word.length() > 0;
}
// IS ALPHABETIC. Test if CH is an ASCII letter.
private boolean isAlphabetic(char ch)
{
return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z';
}
// NEXT. If HAS NEXT is true, then return a WORD read from READER as a STRING.
// Otherwise, return an undefined STRING.
public String next()
{
return word.toString();
}
// READ. Read the next CHAR from READER. Set CH to the CHAR, represented as an
// INT. If there are no more CHARs to be read from READER, then set CH to -1.
private void read()
{
try
{
ch = reader.read();
}
catch (IOException ignore)
{
ch = -1;
}
}
// TO LOWER. Return the lower case ASCII letter which corresponds to the ASCII
// letter CH.
private char toLower(char ch)
{
if ('a' <= ch && ch <= 'z')
{
return ch;
}
else
{
return (char) (ch - 'A' + 'a');
}
}
// MAIN. For testing. Open a text file whose pathname is the 0th argument from
// the command line. Read words from the file, and print them one per line.
public static void main(String [] args)
{
Words words = new Words(args[0]);
while (words.hasNext())
{
System.out.println("'" + words.next() + "'");
}
}
}
class AnagramTree
{
private class TreeNode
{
private byte[] summary;
private WordNode words ;
private TreeNode left;
private TreeNode right;
private TreeNode(WordNode words)
{
this.summary = summary;
this.words = words;
left = null;
right = null;
}
}
private class WordNode
{
private String word;
private WordNode next;
private WordNode(String word, WordNode next)
{
this.word = word;
this.next = next;
}
}
private TreeNode head;
public AnagramTree()
{
head = new TreeNode(null);
}
public void add(String word)
{
TreeNode temp = head;
WordNode wordnode = new WordNode(word, null);
TreeNode new_tree_node = new TreeNode(wordnode);
while(temp != null)
{
if(temp.left == null && (compareSummaries(new_tree_node.summary, temp.summary) <= 0))
{
temp.left = new_tree_node;
}
else
{
temp = temp.left;
}
if(temp.right == null && (compareSummaries(new_tree_node.summary, temp.summary) >= 0))
{
temp.right = new_tree_node;
}
else
{
temp = temp.right;
}
}
}
public void anagrams()
{
TreeNode temp = head;
while(temp != null)
{
if(temp.words.next != null)
{
printInOrder_anagrams(temp);
System.out.print(" ");
}
}
}
private void printInOrder_anagrams(TreeNode currNode)
{
if(currNode == null)
{
return;
}
printInOrder_anagrams(currNode.left);
System.out.print(currNode.words.next + " ");
printInOrder_anagrams(currNode.right);
}
private int compareSummaries(byte[] left, byte[] right)
{
for(int i = 0; i < 26; i++)
{
System.out.print(left[i]);
if(left[i] != right[i])
{
System.out.print(left[i]);
return left[i] - right[i];
}
}
return 0;
}
private byte[] stringToSummary(String word)
{
byte[] summary = new byte[26];
for(int i = 0; i < word.length(); i++)
{
int index = word.charAt(i) - 'a';
summary[index] += 1;
System.out.print(summary[index]);
}
return summary;
}
}
class Anagrammer
{
public static void main(String[] args)
{
Words words = new Words(args[0]);
AnagramTree tree = new AnagramTree();
while (words.hasNext())
{
tree.add(words.next());
}
tree.anagrams();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.