CG_TrieMap



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]: