/******************************************
* The three classes below implement a *
* "Trie" structure in java. My favorite *
* application of this structure is a *
* streaming keyword replacer where a *
* keywords can be compared one character *
* at a time as a stream is read. Enjoy! *
******************************************/
/**************
* LookupTree *
**************/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Method;
import java.util.Iterator;
/**
* A collection of LookupTreeNodes that represents a list of words
* layed out in such a way that incremental lookup by letter is convenient.
*/
public class LookupTree
{
private LookupTreeNode mRootNode = new LookupTreeNode();
public void addWord(String word)
{
LookupTreeNode nodeIter = mRootNode, tempIter = null;
char currentChar = (char)0;
for(int i = 0; i < word.length(); i++)
{
currentChar = word.charAt(i);
if( (tempIter = nodeIter.getNodeForLetter(currentChar)) == null )
{
nodeIter = nodeIter.addLetter( currentChar, false );
}
else
{
nodeIter = tempIter;
}
}
if( nodeIter.getIsWord() )
{
System.out.println( "Word: " + word + " already exists in table" );
}
else
{
nodeIter.setIsWord(true);
}
}
/**
* Given a file containing a list or words seperated by newlines fill up the
* tree with those words.
* @param fileName The name of the file to read words from.
*/
public void loadWordsFromFile(String fileName)
{
String tempStr = null;
File inFile = null;
BufferedReader br = null;
try
{
inFile = new File(fileName);
br = new BufferedReader(
new InputStreamReader(
new FileInputStream(inFile)));
}
catch(FileNotFoundException fe)
{
System.out.println( fe.toString() );
return;
}
try
{
while( (tempStr = br.readLine()) != null )
{
this.addWord( tempStr );
}
}
catch(IOException ioe)
{
System.out.println( ioe.toString() );
}
}
/**
* Given String return true if the word is in the tree, false otherwise.
* @param word The word to check the existence of.
* @returns boolean true if the word is in the tree, false otherwise.
*/
public boolean wordExists( String word )
{
LookupTreeNode nodeIter = mRootNode;
boolean returnVal = false;
char currentChar = (char)0;
for( int i = 0; i < word.length(); i++)
{
currentChar = word.charAt(i);
nodeIter = nodeIter.getNodeForLetter(currentChar);
if( nodeIter == null )
{
break;
}
}
if( nodeIter != null && nodeIter.getIsWord() )
{
returnVal = true;
}
return returnVal;
}
/**
* Walk the table and perform an action on each word. Order is not guaranteed.
* @param node The node to start from.
* @param currWord The starting String, used for recursion
* @param action A method in the form void action(String arg) to be performed on each string found
*/
private void walkTable(LookupTreeNode node, String currWord, Method action)
{
Iterator iter = node.getLetterIterator();
LookupTreeNode nextNode = null;
Object [] arg = new Object[1];
StringBuffer currentWord = new StringBuffer(currWord);
currentWord.setLength( currWord.length() + 1 );
char currentChar = (char)0;
while( iter.hasNext() )
{
currentChar = ((Character)(iter.next())).charValue();
currentWord.setCharAt(currWord.length(), currentChar);
nextNode = node.getNodeForLetter( currentChar );
if( nextNode.getIsWord() )
{
arg[0] = currentWord.toString();
if( action != null && this.validateActionMethod( action ) )
{
try
{
action.invoke( this, arg );
}
catch( Exception e )
{
System.out.println( "Error while trying to execute method: " + action.toString() +
": " + e.toString() );
}
}
else
{
System.out.println( "Action method null or invalid" );
}
}
this.walkTable( nextNode, currentWord.toString(), action );
}
}
/**
* Make sure that the method passed as action to the walker is of the right format.
*/
private boolean validateActionMethod( Method action )
{
Class [] params = action.getParameterTypes();
boolean returnVal = true;
try
{
if( params.length != 1 || !params[0].equals(Class.forName("java.lang.String")) )
{
returnVal = false;
}
}
catch( Exception e )
{
System.out.println( "Invalid class for parameter found" );
returnVal = false;
}
return returnVal;
}
/**
* Walk the tree and print each word
*/
public void printTable()
{
try
{
this.walkTable( mRootNode, new String(), this.getActionMethodFromName( "printWord" ) );
}
catch(Exception e)
{
System.out.println( e.toString() );
}
}
protected void printWord( String arg )
{
System.out.println( arg );
}
/**
* utility for retrieving the Method object from the method name from *this* class
*/
private Method getActionMethodFromName( String funcName )
{
Method returnMethod = null;
try
{
Class [] params = { new String().getClass() };
returnMethod = this.getClass().getDeclaredMethod( funcName, params );
}
catch( Exception e )
{
System.out.println( "Warning - returning null method: " + e.toString() );
}
return returnMethod;
}
/**
* Return an iterator that can be used to incrementally (letter by letter)
* check if a word exists in the list.
*/
public LookupTreeIterator getIterator()
{
return new LookupTreeIterator(mRootNode);
}
/**
* Return an iterator that can be used to incrementally (letter by letter)
* check if a word exists in the list.
*/
public boolean isRootChar( char c)
{
return mRootNode.containsLetter( c );
}
public static void main( String [] args )
{
try
{
LookupTree LT = new LookupTree();
LT.loadWordsFromFile("dictionary.txt");
LT.printTable();
BufferedReader stdReader = new BufferedReader(
new InputStreamReader( System.in ));
String tempStr = null;
while(true)
{
System.out.print("Enter a word to lookup, or \"quit\" to quit: ");
tempStr = stdReader.readLine();
if(tempStr.equals("quit") )
{
break;
}
else
{
System.out.println( LT.wordExists( tempStr ) );
}
}
}
catch(Exception e)
{
e.printStackTrace();
System.out.println( e.toString() );
}
}
}
/******************
* LookupTreeNode *
******************/
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
/**
* Represents one node of a tree class that makes
* incremental word-lookup easy.
*/
public class LookupTreeNode
{
//true when the word ending with the letter that is this
//TreeNode's key is a complete word.
private boolean isWord = false;
private HashMap letterMap = new HashMap();
public LookupTreeNode() {}
/**
* Returns an iterator over the set of keys in this Node.
* The set of keys is the set of letters represented at this
* level of the tree.
* @returns Iterator The keySet iterator
*/
public Iterator getLetterIterator()
{
return letterMap.keySet().iterator();
}
/**
* Returns the Set of keys int his Node. The keys represent
* the letters represented at this level of the tree.
* returns Set The set of letters in this Node.
*/
public Set getLetterSet()
{
return letterMap.keySet();
}
/**
* Returns the Set of keys int his Node. The keys represent
* the letters represented at this level of the tree.
* returns Set The set of letters in this Node.
*/
public boolean containsLetter( char c )
{
return letterMap.containsKey(new Character(c));
}
/**
* Adds a new letter at this level, and returns the corresponding
* Node that is created.
* @param c The letter to be added
* @param isword If true, the isWord flag will be set for true in the returned Node,
* indicating that the added letter completed a word.
* @returns LookupTreeNode The added node.
*/
public LookupTreeNode addLetter(char c, boolean isword)
{
LookupTreeNode newNode = new LookupTreeNode();
letterMap.put(new Character(c), newNode);
return newNode;
}
public boolean getIsWord() { return this.isWord; }
public void setIsWord( boolean isword ) { isWord = isword; }
/**
* See if this node contains some letter c. If it does, return the letter's
* corresponding node.
* @param c The letter to look up
* @returns LookupTreeNode the Node corresponding to the letter c, or null
*/
public LookupTreeNode getNodeForLetter(char c)
{
return (LookupTreeNode)letterMap.get(new Character(c));
}
}
/**********************
* LookupTreeIterator *
**********************/
import java.util.Set;
/**
* The iterator class. Maintains state and can be reset.
*/
public class LookupTreeIterator
{
private final int BUFFER_SIZE = 1024;
private LookupTreeNode mInitialTreeNode = null;
private LookupTreeNode mCurrentTreeNode = null;
private Set mCurrentNodeKeys = null;
private char [] mCurrentWord = null;
private int mCurrentWordCount = 0;
private boolean mValidState = true;
private boolean mIsWord = false;
/**
* Start at node rootNode, initialize word buffer, set initial node for reset later.
*/
public LookupTreeIterator( LookupTreeNode rootNode )
{
mCurrentTreeNode = mInitialTreeNode = rootNode;
mCurrentNodeKeys = mCurrentTreeNode.getLetterSet();
mCurrentWord = new char [ BUFFER_SIZE ];
mCurrentWordCount = 0;
}
/**
* See if the character c exists at the iterator's current location in the tree.
*/
public boolean tryCharacter( char c )
{
boolean returnVal = false;
mCurrentWord[ mCurrentWordCount++ ] = c;
if( mCurrentNodeKeys.contains( new Character(c) ) )
{
returnVal = true;
gotoNextNode(c);
}
else
{
mValidState = false;
mIsWord = false;
}
return returnVal;
}
/**
* Iterate to the next letter, only called if that letter exists.
*/
private void gotoNextNode( char c )
{
mCurrentTreeNode = mCurrentTreeNode.getNodeForLetter(c);
mCurrentNodeKeys = mCurrentTreeNode.getLetterSet();
mIsWord = mCurrentTreeNode.getIsWord();
}
/**
* Get the current buffer containing all looked up letters, including any that didn't exist.
*/
public String getCurrentBuffer()
{
//MJM return mCurrentWord.toString();
return new String( mCurrentWord, 0, mCurrentWordCount );
}
/**
* Is the word currently held in the buffer a complete word in the tree?
*/
public boolean isWord()
{
return mIsWord;
}
/**
* Is the iterator currently in a valid state? i.e. did the last letter checked exist,
* meaning that what is currently in the buffer can be traced in through the tree?
*/
public boolean isValid()
{
return mValidState;
}
/**
* Reset the iterator
*/
public void reset()
{
mCurrentTreeNode = mInitialTreeNode;
mCurrentNodeKeys = mCurrentTreeNode.getLetterSet();
mCurrentWordCount = 0;
mValidState = true;
}
}
