"""
 Programming Pearls Column 2 Exercise 1
 
 Find all of the anagrams of an input word in a dictionary. Do this in two
 ways: One where you are not allowed to preprocess the dictionary, and the
 other where you are.

 Preprocessing the dictionary in this case is a waste of time, because we only
 allow one search term per program invocation, and so there aren't any
 subsequent requests to 'buy back' the time we spent on the preprocessing.

 Lookups of the anagram lists in the preprocessed case could be made constant
 time by using a hash function that maps all anagrams to a single (quasi)
 unique integer i, and storing the list of these anagrams in index i of an
 enormous array (2^sizeof(int) indices). We could then look up the anagrams by
 the array at the number produced by the signature. We wouldn't even need to do
 any scaling for negative numbers since Python allows array indices to be
 negative.
"""
# Author: Michael DiBernardo (mikedebo@gmail.com)
# Copyright Michael DiBernardo 2008

def sign(word):
    """
    Produce a signature for a word such that all anagrams of this word will
    share the same signature.
    """
    word = word.lower()
    chars = [word[i] for i in xrange(len(word))]
    chars.sort()
    return ''.join(chars)

def no_preprocess_and_find(search_word, word_list):
    """
    Find all anagrams of the given search word without preprocessing the
    dictionary.
    """
    search_word_sig = sign(search_word)
    anagrams = (word for word in word_list if sign(word) == search_word_sig)
    return anagrams

def preprocess_and_find(search_word, word_list):
    """
    Find all anagrams of the given search word by first preprocessing the
    dictionary.
    """
    anagram_dict = dict()
    for word in word_list:
        word_sig = sign(word)
        try:
            anagram_dict[word_sig].append(word)
        except KeyError:
            anagram_dict[word_sig] = [word]

    try:
        return anagram_dict[sign(search_word)]
    except KeyError:
        return []

def main(argv):
    """
    Driver for exercise.
    """
    if len(argv) != 3:
        print "Usage: anagrams_of_word search_word dictionary_file\n"
        exit(-1)
    search_word = argv[1].strip()
    dictionary_filename = argv[2]
    methods = [no_preprocess_and_find, preprocess_and_find]
    for search_method in methods:
        print "Using method: %s" % search_method.func_name
        dictionary_handle = open(dictionary_filename)
        word_list = (word.strip() for word in dictionary_handle)
        anagrams = search_method(search_word, word_list)
        for anagram_word in anagrams:
            print "%s " % anagram_word

if __name__ == "__main__":
    import sys
    main(sys.argv)