# http://en.wikipedia.org/wiki/Trie
# arbre de préfixes

class Trie:
    def __init__(self, letter=""): # au début, l'arbre est vide
        self.branches = {}
        self.letter = letter
        self.is_word_end = False

    def __getitem__(self, letter): # permet d'accéder à une valeur 
        return self.branches.get(letter, None)

    def isWordEnd(self): # est-ce la fin d'un mot ?
        return self.is_word_end

    def setWordEnd(self, value=True): # dire que c'est la fin d'un mot
        self.is_word_end = value

    def getLetter(self): # lire une lettre
        return self.letter

    def addBranch(self, branch): # ajouter une branche à l'arbre
        self.branches[branch.getLetter()] = branch

    def makeTrie(self, liste_mots):
        # crée un trie à partir d'une liste de mots
        for un_mot in liste_mots:
            noeud = self                # on se place au début de l'arbre
            mot = un_mot.rstrip()
            if len(mot)>1:
                for lettre in mot:      # lit les lettres du mot une à une
                    if not noeud[lettre]: 
                        noeud.addBranch(Trie(lettre))   # on crée une nouvelle branche
                    noeud = noeud[lettre]   # on avance dans l'arbre
                noeud.setWordEnd()          # on met une marque de fin de mot
        return self

    def inTrie(self, mot):
        # mot est-il dans le Trie ?
        noeud = self
        for lettre in mot:
            if noeud[lettre] != None :
                noeud = noeud[lettre]
            else:
                return False
        else:
            if noeud.isWordEnd() :
                return True
            else:
                return False