import java.util.*;


/**
 * CSE 373 Prof. Martin Dickey<br>
 * Assignment 1 
 * 
 * AnagramChecker
 * check whether two words are anagrams of each other
 * or if a word has any anagrams in a dictionary of words
 */
public class AnagramChecker implements IAnagramChecker {
	
	/** Determine whether one word is an anagram of the other.
	 * Non-alphanumeric characters are ignored.  The check is
	 * case-insensitive.
	 * @param word1 any non-null string.
	 * @param word2 any non-null string.
	 * @return true iff the second word is an anagram of the first.
	 */
	public boolean isAnagram(String word1, String word2) {
		
		//convert both word1 and word2 to lower case strings and screen off non-alphanumeric characters
		String word11 = normalize(word1);
		String word22 = normalize(word2);
		
    	// If lengths are different, can't possibly be anagrams
    	// If two strings are the same strings ignoring cases and non-alphanumeric characters, they are not anagrams
    	if (( word11.length() != word22.length() ) || ( word11.equals( word22 )))
    		return false;
    		
		HashMap counter = new HashMap();

		//currently deal with word1LowerCase and word2LowerCase
    	// Stores the occurrences of characters in the first string in a hashmap.
    	for ( int i = 0 ; i < word11.length() ; i++ ){
      		Character ch = new Character(word11.charAt(i));
      		Integer count = (Integer) counter.get( ch );
      		if ( count == null )
        		counter.put( ch, new Integer(1));
      		else{        
        		counter.put( ch, new Integer( count.intValue() + 1 ));
      		}
    	}
        
    	// Subtracts the occurrences of characters in the second string in a hashmap.
    	// If any occurrence of characters become negative, 
    	// this means there were more of this character in the second string,
    	// therefore is not an anagram.
    	for ( int i = 0 ; i < word22.length() ; i++ ){
      		Character ch = new Character(word22.charAt(i));
      		Integer count = (Integer) counter.get( ch );
      
      		if ( count == null  || count.intValue() == 0 )
        		return false;
      		else{        
        		counter.put( ch, new Integer( count.intValue() - 1 ));
      		}
    	}
    
    	// If program reached this point, it passed all the tests.
    	return true;   
	}
	
	
	/** Find all anagrams (if any) of a given word in a dictionary
	 * (list) of words.
	 * @param dictionary a non-null list of strings.
	 * @param word a non-null string.
	 * @return a list of all words from the dictionary which are
	 * anagrams of the given word, using the same criteria as
	 * in method isAnagram.  The returned list may be empty but
	 * not null.
	 */
	public List findAnagrams(List dictionary, String word) {
		List anagramList = new ArrayList();   
        
    	Iterator iter = dictionary.iterator();    
    	while( iter.hasNext() ){
       		String s = (String) iter.next(); 
      		
      		if ( isAnagram( word, s ) )
      			anagramList.add( s );
      	}
      	
      	return anagramList;      
    
	}
	
	
	/** Strip non-alphanumeric characters from a string, and convert to
	 * all lower-case.
	 * @param word a non-null string
	 * @return a string containing, in the same order as the original,
	 * all and only the alphanumeric characters, lowercase.
	 */
	private String normalize(String word) {
	    return word.toLowerCase().replaceAll("[^a-z0-9]", "");
	}

}