import java.util.*;

public class SpellChecker
{
	protected TreeSet<String> dictionarySet,
                                  documentSet;


	/**
 	 *  Initializes this SpellChecker object.
 	 *
 	 */ 
	public SpellChecker()
	{
        	dictionarySet = new TreeSet<String>();
        	documentSet = new TreeSet<String>();
 	} // default constructor

   
	/**
 	 *  Inserts a specified word into the dictionary set of words.
 	 *  The worstTime(n) is O(log n), where n is the number of words in the
 	 *  dictionary set of words.
 	 *
 	 *  @param word - the word to be inserted into the dictionary set of words.
 	 *
 	 */
	public void addToDictionarySet (String word)
	{
        	dictionarySet.add (word);
	} // method addToDictionarySet


	/**
 	 *  Inserts all of the words in a specified line into the document set of words.
 	 *  The worstTime(m) is O(log m), where m is the number of (unique) words
 	 *  in the document set of words.
 	 *
 	 *  @param line - the line whose words are added to the document set of 
 	 *                 words.
 	 *
 	 */
	public void addToDocumentSet (String line)
	{
        	final String DELIMITERS = " \'\"\n\r\t;:.,!?()";

        	StringTokenizer tokens = new StringTokenizer (line, DELIMITERS);

        	String word;

        	while (tokens.hasMoreTokens())
        	{
	            	word = tokens.nextToken().toLowerCase();
        	    	documentSet.add (word);
        	} // while line has more tokens
	} // method addToDocumentSet	


	/**
 	 *  Determines all words that are in the document set but not in the 
 	 *  dictionary set.
 	 *  The worstTime(m, n) is O(m log n), where m is the number of words
 	 *  in the document set, and n is the number of words in the dictionary set.
 	 *
 	 *  @return a LinkedList consisting of all the words in the document set that
 	 *                are not in the dictionary set.
 	 *
 	 */
	public LinkedList<String> compare()
	{
        	LinkedList<String> misspelled = new LinkedList<String>();
        
        	for (String word : documentSet)        
            		if (!dictionarySet.contains (word))
                		misspelled.add (word);
            	return misspelled;
	} // method compare

} // class SpellChecker