In [1]:

    

class TrieMap(object):
    """ Trie implementation of a map.  Associating keys (strings or other
        sequence type) with values.  Values can be any type. """
    
    def __init__(self, kvs):
        self.root = {}
        # For each key (string)/value pair
        for (k, v) in kvs: self.add(k, v)
    
    def add(self, k, v):
        """ Add a key-value pair """
        cur = self.root
        for c in k: # for each character in the string
            if c not in cur:
                cur[c] = {} # if not there, make new edge on character c
            cur = cur[c]
        cur['value'] = v # at the end of the path, add the value
    
    def query(self, k):
        """ Given key, return associated value or None """
        cur = self.root
        for c in k:
            if c not in cur:
                return None # key wasn't in the trie
            cur = cur[c]
        # get value, or None if there's no value associated with this node
        return cur.get('value')


    

In [2]:

    

mp = TrieMap([("hello", "value 1"), ("there", 2), ("the", "value 3")])


    

In [3]:

    

mp.query("hello")


    

    
Out[3]:





'value 1'

In [4]:

    

mp.query("hello there") # returns None


    

In [5]:

    

mp.query("there")


    

    
Out[5]:





2

In [6]:

    

mp.query("ther") # returns None


    

In [7]:

    

mp.query("the")


    

    
Out[7]:





'value 3'

In [8]:

    

mp.query("") # returns None


    

In [8]: