#!/usr/bin/env python
""" (slightly modified) Trie data structure"""

class TrieError(Exception):
    pass

class Trie:
    """Trie data structure"""

    def __init__(self):
        self.children = None
        self.final = 0

    def add(self, str):
        """Adds string to the trie"""
        if len(str):
            key = str[0]
	    if not self.children:
	        self.children = {}
            if not key in self.children.keys():
                self.children[key] = Trie()
            self.children[key].add(str[1:])
        else:
	    self.final = 1

    def remove(self, str):
        """Remove str from trie"""
        if not str:
            self.final = 0
            return

        key = str[0]
        if self.children[key]:
            self.children[key].remove(str[1:])
        
	    
    def has(self, str, n=0): # XXX this is a slight modfication from a std trie!
        """Checks if str[0:n] (may not be whole string) is in trie
	
	   returns 0 on no match
	   returns n on a match of length n
	"""
        if len(str):
            key = str[0]
            if self.children and key in self.children.keys():
                return self.children[key].has(str[1:],n+1)
        return self.final*n

    def newhas(self, str, n=0):
        length = len(str)
        return self._has(str, n, length)

    def _has(self, str, n, length):
        if length:
            key = str[0]
            if self.children and key in self.children.keys():
                return self.children[key]._has(str[1:],n+1,length-1)
        return self.final*n

if __name__ == '__main__':
    t = Trie()
    for i in range(10000):
        t.add(str(i*i))
	
    t.add("das ist ein test")

    print t.has("das ist ein test.trallalla")
    print t.has("9")
    print t.has("81 asdasd")
    print t.has("100 asdasda")
    print t.has("42")

    for i in range(100000):
        x=t.has(str(i))