def find_compound_words(words):
    """ trie + BFS + pruning
    Advantages of trie:
    1. Predictable O(k) lookup time where k is the size of the key.
    2. We can easily get all prefixes of a given word.
    Drawbacks of tries:
    1. Space-consuming, it is a trade-off between time-complexity and space\
    complexity. We can use radix-tree to get optimized space, but in \
    practice, it doesn't have a reasonable improvement and it takes more\
    time than trie.
    """
    compound_words = set([])
    trie = Trie()
    queue = collections.deque()
    prefixes_dict = {}
    for word in words:
        prefixes = trie.has_prefixes(word)
        for prefix in prefixes:
            queue.append((word, word[len(prefix) :]))
        trie.insert(word)
    while queue:
        word, suffix = queue.popleft()
        # pruning
        if word in compound_words:
            continue
        # find a compund word
        if suffix in trie:
            compound_words.add(word)
        else:
            prefixes = trie.has_prefixes(suffix)
            for prefix in prefixes:
                queue.append((word, suffix[len(prefix) :]))
    return compound_words

def getCommonPrefix(fileSet, trieNode, separator='-_'):
    debug = False
    # debug = ('killswitch engage - temple from the within.mp3' in fileSet)
    root = Trie('$$')
    for f in fileSet:
        root.insert(list(trieNode.children[f].key))
    prefixList = []
    def dfs(trieNode, curStr=''):
        if debug:
            print curStr, trieNode.num_successors, int(0.8*len(fileSet))
        if (trieNode.num_successors >= int(0.8*len(fileSet)) and trieNode.num_successors > 1) or trieNode.num_successors >= 3:
            res = False
            for k in trieNode.children:
                res = (dfs(trieNode.children[k], curStr+k) or res)
            if res:
                return True
            elif trieNode.key in separator:
                prefixList.append((curStr, trieNode.num_successors))
                return True
            else:
                return False
        else:
            return False
    dfs(root)
    # if len(prefixList) > 0:
    #     print prefixList, "->\n", '\n\t'.join(fileSet)
    return prefixList

def test_contatins():
    """Test contains responds with true for a word that has been inserted."""
    from trie import Trie
    t = Trie()
    t.insert("cat")
    result = t.contains("cat")
    assert result is True

def test_contains_on_shorter():
    """Test contains returns false on non-inserted longer word."""
    from trie import Trie
    trie = Trie()
    token = 'pig'
    trie.insert(token)
    assert trie.contains('piglet') is False

    def to_dict(self):
        state = self.state.to_dict(True)
        nstate = {}
        for s in state:
            t = Trie(STATEDB_DIR, state[s][STORAGE_INDEX])
            o = [0] * ACCT_RLP_LENGTH
            o[NONCE_INDEX] = decode_int(state[s][NONCE_INDEX])
            o[BALANCE_INDEX] = decode_int(state[s][BALANCE_INDEX])
            o[CODE_INDEX] = state[s][CODE_INDEX]
            td = t.to_dict(True)
            o[STORAGE_INDEX] = {decode_int(k): decode_int(td[k]) for k in td}
            nstate[s.encode('hex')] = o

        return {
            "number": self.number,
            "prevhash": self.prevhash,
            "uncles_root": self.uncles_root,
            "coinbase": self.coinbase,
            "state": nstate,
            "transactions_root": self.transactions_root,
            "difficulty": self.difficulty,
            "timestamp": self.timestamp,
            "extradata": self.extradata,
            "nonce": self.nonce
        }

def find_top_k_with_trie(k = 10):
    """
    Too slow and large memory consuming.
    
    time consuming:  147.656000137
    (164, 'mh')
    (164, 'sq')
    (165, 'bi')
    (165, 'mo')
    (167, 'im')
    (168, 'ux')
    (169, 'br')
    (169, 'gj')
    (170, 'ij')
    (171, 'qd')
    """
    result = []
    t = Trie()
    # trie
    with open(TDATA) as f:
        for line in f:
            t.insert(line.strip())
    
    # heapq
    for n in t.ipreorder(t.root):
        if len(result) < k:
            heapq.heappush(result, n)
        else:
            heapq.heappushpop(result, n)
            
    return result

def test_contains_given_string_one_string_():
    """Test that a given string is in the list."""
    from trie import Trie
    trie = Trie()
    token = 'pig'
    trie.insert(token)
    assert trie.contains(token)

def test_contains_on_partial():
    """Test contains returns false on partial match."""
    from trie import Trie
    trie = Trie()
    token = 'piglet'
    trie.insert(token)
    assert trie.contains('pig') is False

def test_contatins_false():
    """Test contains responds with false for a word that is not inserted."""
    from trie import Trie
    t = Trie()
    t.insert("cat")
    result = t.contains("dog")
    assert result is False

def test_insert_one_token():
    """Test when token is inserted into the trie correctly."""
    from trie import Trie
    trie = Trie()
    token = 'pig'
    trie.insert(token)
    assert trie.container == {'p': {'i': {'g': {'$': '$'}}}}

 def test_finds_nodes(self):
     t1, t2, t3, t4 = Trie(), Trie(), Trie(), Trie()
     t1.children['b'] = t2
     t2.children['a'] = t3
     t3.children['r'] = t4
     trie = t1.find('bar')
     assert trie == t4

def car_trie():
    """Filled trie."""
    from trie import Trie
    t = Trie()
    for word in WORDS:
        t.insert(word)
    return t

def create_data_structure(filepath):
    """Open file and load wordlist into Trie ds"""
    ds = Trie()
    with open(filepath, 'r') as fp:
        for word in fp:
            ds.add_word(word.rstrip())
    return ds

class DictionaryTest(unittest.TestCase):
    def setUp(self):
        self.unigrams = Trie()
        self.unigrams['a'] = 200
        self.unigrams['hi'] = 130
        self.unigrams['hello'] = 120
        self.unigrams['there'] = 140
        self.unigrams['how'] = 150
        self.unigrams['are'] = 80
        self.unigrams['you'] = 200
        self.unigrams['your'] = 100

        self.ngrams = Trie()
        self.ngrams[['hello','there']] = 20
        self.ngrams[['hello','you']] = 25
        self.ngrams[['how','are','you']] = 80
        self.ngrams[['you','are','there']] = 30
        self.ngrams[['are','you','there']] = 60

        self.bindict = BinaryDictionary()
        self.bindict.encode_unigrams(self.unigrams)
        self.bindict.encode_ngrams(self.ngrams)

    def test_trie_weight(self):
        self.assertEqual(self.unigrams['hello'], 120)
        self.assertEqual(self.ngrams[['hello','there']], 20)

    def test_trie_key_error(self):
        with self.assertRaises(KeyError):
            self.ngrams['hello']

    def test_trie_unigram_predict(self):
        self.assertTrue('e' in map(itemgetter(0), self.unigrams.get_predictions(['h'])))
        self.assertEquals('l', self.unigrams.get_predictions(list('he'))[0][0])
        self.assertEquals(len(self.unigrams.get_predictions(list('hello'))), 0)

    def test_trie_ngram_predict(self):
        self.assertTrue('there' in map(itemgetter(0), self.ngrams.get_predictions(['hello'])))
        self.assertTrue('you' in map(itemgetter(0), self.ngrams.get_predictions(['how','are'])))

    def test_bindict_exists(self):
        self.assertTrue(self.bindict.exists('hello'))
        self.assertTrue(not self.bindict.exists('hellos'))
        self.assertTrue(not self.bindict.exists('h'))
        self.assertTrue(self.bindict.exists('a'))

    def test_bindict_ngram_predict(self):
        self.assertTrue('there' in map(itemgetter(0), self.bindict.get_predictions(['hello'])))
        self.assertTrue('you' in map(itemgetter(0), self.bindict.get_predictions(['how','are'])))

    def test_correct(self):
        self.assertTrue('you' in self.bindict.get_corrections('yuu').keys())
        self.assertTrue('your' in self.bindict.get_corrections('yuur').keys())

    def test_completions(self):
        self.assertTrue('you' in self.bindict.get_completions('yo', 1))
        self.assertFalse('your' in self.bindict.get_completions('yo', 1))
        self.assertTrue('your' in self.bindict.get_completions('yo', 2))
        self.assertFalse('yo' in self.bindict.get_completions('y', 1))

def trie_dictionary(dictionary):
    trie = Trie()
    
    for key in dictionary.keys():
        #print key
        trie.add(key, dictionary[key])
        
    return trie

def test_traversal_no_words():
    """Test traversal on trie with no words."""
    from trie import Trie
    word_list = []
    trie = Trie()
    for word in trie.traversal(start=trie.container):
        word_list.append(word)
    assert word_list == []

def readDict():
  #get words from /usr/share/dict/words
  f = open('/usr/share/dict/words', 'r')
  words = Trie()
  #load words into trie
  for word in f.read().split('\n'):
	words.insert(word)
  return words

def test_overlapping_words():
    from trie import Trie
    new_trie = Trie()
    new_trie.insert('words')
    new_trie.insert('trie')
    new_trie.insert('trip')
    assert new_trie.root == {'w': {'o': {'r': {'d': {'s': {'$': '$'}}}}},
                             't': {'r': {'i': {'e': {'$': '$'}, 'p': {'$': '$'}}}}}

def test_2_trie():
    """Test that we can insert two words into the Trie."""
    from trie import Trie
    new_trie = Trie()
    new_trie.insert('words')
    new_trie.insert('trie')
    assert new_trie.root == {'w': {'o': {'r': {'d': {'s': {'$': '$'}}}}},
                             't': {'r': {'i': {'e': {'$': '$'}}}}}

    def test_search_7(self):
        trie = Trie()
        key = "tea"
        trie.insert( key )

        matches = trie.search( "pea", 1 )
        self.assertEqual(len(matches), 1)
        self.assertTrue(key in matches)