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 bytes; its the key. The slot words points to a linear singly linked list of WordNodes; its the value. The slotsleft and right point to TreeNodes, or to null; theyre 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; its 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 isnt null, it isnt empty, and it has only lower case letters. You must use compareSummaries to control the search through the tree. You must use the trees 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 TreeNodes exactly once. You must skip the trees head node. Every time you visit a TreeNode, you must print all the words from its linked list of WordNodes, 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 bytes. 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 isnt null, it isnt empty, and it has only lower case letters. The summary must be represented as an array of 26 bytes. If c is a character from word, then you must use the Java expression (c 'a') to compute cs index in that array. You must not use ifs or switches to compute cs index.

You must also write a class called Anagrammer. Its 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 wont 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 nodes key must appear nowhere else in the tree.

You must represent summaries as arrays of 26 bytes. Do not use arrays of ints, because that would take more memory. Recall that byte is Javas 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 dont 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.