Your input will require some processing before you can sort

To sort you will create a binary search tree where each node contains for data field a class AnaData with two fields: a String which holds a key and a linked list (GList) which holds the anagrams found in the input. The nodes are inserted into the BST using alphabetical order on the keys. The corresponding anagrams are contained in the linked list.

The flow of control in your program goes as follows:

• The names of the input and output files are read from the command line and opened.
• An instance of Bintree is created.
• As each word is read from the input file it is cleaned and a key is created.
• An instance of AnaData is created and the key is stored in it.
• The BST is searched to see of a node already exists with the given key. If one exists its anagram list is searched to see of the current word is already in the list. If it is not in the list it is added to the list. If the key was not in the list a new node is created with a new instance of AnaData holding the new key and with the current word inserted as the first word in the anagram list.
• A traversal of the BST is made checking the anagram lists in each node. If there is more than one word in the list the list is written to the output file
• The files are closed.

Additions to GList.java

You must add a few simple methods to GList.java in order to allow private GNode cursor; which will be a pointer to the current node being visited in the traversal. Then add three methods:

• public void startTraverse() prepares the class to start a new traversal by pointing cursor to the first element of the list (or null) if the list is empty.
• public boolean hasNext() returns whether there are more nodes in the list.
• public T getNext() advances cursor and returns the current node (pointed to by cursor before it is advanced.)

If you prefer you could define an Iterator instead of the above methods.

BinTree

The Bintree class implements (some of) a BST. You need at least public boolean insert(T), public T find(T) and public void traverse() methods. In the traverse method you will call visit() which will be defined in class AnaData.

The class will begin public class Bintree:>.

Visitable

Bintree is constrained to accept only type parameters which implement a visit() method. This requires a VisitableT> interface. Here it is!

public interface VisitableT> { void visit(); int compareTo(T t); } 

AnaData

This class is what is stored in nodes of the BST. It contains three fields: a String field key which stores the key -- a "cleaned" string with its letters alphabetized, a GNode field called list which holds the anagram list corresponding to the key, and a BufferdReader which will be explained later. It will need a public void visit() method, a public int compareTo(AnaData a) and a constructor.

compareTo() and equals() will compare two AnaData objects by comparing key fields.

visit() will perform the actions done during a traversal which sees if an anagram list is found in the list field and if so displays it. If list contains more than one string we have an anagram list -- print it out using the BufferedReader. Since you must use a BufferedReader and do not want to create one each time an AnaData object is created one will be created (once) in the Anagram (main) class and a reference to it is passed to the constructor here.

AnaGram

This is the main class for your program. Here you will open input and output files (you must use a BufferedReader for input and a BufferedWriter for output. You will also call a method to build the tree and one to traverse the tree.

You will need a method to clean the current string and one to create a key. The "clean" array consists entirely of lower case letters (no punctuation, etc.). Cleaning involves converting the string to all lower case (use toLowerCase(()) and convert it to an char array (use toCharArray()). You will read through this char array copying each character to a new array only if it is a letter (use Character.isLetter()). IMPORTANT! The array you are copying to must be the same length as the final cleaned string, i.e. when you copy to the new array that array must become completelhy filled. Then convert the char array to aString (use String.valueOf()). Building the key is the same but the "new" array must be put in alphabetical order (use Arrays.sort()) before converting to a String.

To build the tree: read a string from the input file, clean it and if the cleaned string is not empty build a key. Create an instance of AnaData to hold the key. Search the tree for this instance of Anadata. If found see if the clean string is in the anagram list -- if it isn't add it to the list. If the instance of Anadata is not in the tree add the cleaned string to its anagram list (as the only value in the list) and insert it into the tree.

In this program you will write a generic (i.e. parameterized) class for binary search trees and another for linked lists (you may use and add to GLis T fom class). You will then use these to write a program which reads a text file, finds all of the anagram groups in this file and writes them to an output file. For example, if the input file was: Alas! My pharyngolaryngeal search for meatballs was untameable Batman thought the meatballs were raisable, but the raisable was truely the domain of Rabelais only In truth the parables were laryngopharyngeal, if one could say that. The only cure for laryngopharyngeal, or perhaps only prebasal, altitudinarian and sparable meatballs was to be ambulante. Though a bantam weight and parsable batmen were both antilabor and blastemal. Halt! you maltable scoundrel" cried the baritonal watchman. It seems Rabelais was the only one who knew The output may be: laryngopharyngeal pharyngolaryngeal rabelais raisable blastemal meatballs parsable sprable prebasal parables baritol antilabor bantam batman Internals Anagram.java, BinTree.java, AnaData.java and GList.java and one interface: Visitable java. You may use the GList.java class we wrote in class but you will have to make minor additions to it. For the Bin Tree.java class you will write a parameterized (generic) binary tree. The idea behind finding anagrams is as follows. Suppose you have a list of words: snarf bloof frans ranfs snooker flobo grunk One can first create an associated key for each word by alphabetizing its letters. snarf afnrs bloof bfloo frans afnrs ranfs afnrs snooker eknoors flobo bfloo grunk gknru Next one alpabetizes the list by key snarf afnrs frans afnrs ranfs afnrs bloof bfloo flobo bfloo nooker eknoors grunk gknru And finally the anagram groups can be picked out since they are grouped together. snarf frans ranfs bloof flobo In this program you will write a generic (i.e. parameterized) class for binary search trees and another for linked lists (you may use and add to GLis T fom class). You will then use these to write a program which reads a text file, finds all of the anagram groups in this file and writes them to an output file. For example, if the input file was: Alas! My pharyngolaryngeal search for meatballs was untameable Batman thought the meatballs were raisable, but the raisable was truely the domain of Rabelais only In truth the parables were laryngopharyngeal, if one could say that. The only cure for laryngopharyngeal, or perhaps only prebasal, altitudinarian and sparable meatballs was to be ambulante. Though a bantam weight and parsable batmen were both antilabor and blastemal. Halt! you maltable scoundrel" cried the baritonal watchman. It seems Rabelais was the only one who knew The output may be: laryngopharyngeal pharyngolaryngeal rabelais raisable blastemal meatballs parsable sprable prebasal parables baritol antilabor bantam batman Internals Anagram.java, BinTree.java, AnaData.java and GList.java and one interface: Visitable java. You may use the GList.java class we wrote in class but you will have to make minor additions to it. For the Bin Tree.java class you will write a parameterized (generic) binary tree. The idea behind finding anagrams is as follows. Suppose you have a list of words: snarf bloof frans ranfs snooker flobo grunk One can first create an associated key for each word by alphabetizing its letters. snarf afnrs bloof bfloo frans afnrs ranfs afnrs snooker eknoors flobo bfloo grunk gknru Next one alpabetizes the list by key snarf afnrs frans afnrs ranfs afnrs bloof bfloo flobo bfloo nooker eknoors grunk gknru And finally the anagram groups can be picked out since they are grouped together. snarf frans ranfs bloof flobo