{ "metadata": { "name": "CG_TrieMap" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "code", "collapsed": false, "input": [ "class TrieMap(object):\n", " \"\"\" Trie implementation of a map. Associating keys (strings or other\n", " sequence type) with values. Values can be any type. \"\"\"\n", " \n", " def __init__(self, kvs):\n", " self.root = {}\n", " # For each key (string)/value pair\n", " for (k, v) in kvs: self.add(k, v)\n", " \n", " def add(self, k, v):\n", " \"\"\" Add a key-value pair \"\"\"\n", " cur = self.root\n", " for c in k: # for each character in the string\n", " if c not in cur:\n", " cur[c] = {} # if not there, make new edge on character c\n", " cur = cur[c]\n", " cur['value'] = v # at the end of the path, add the value\n", " \n", " def query(self, k):\n", " \"\"\" Given key, return associated value or None \"\"\"\n", " cur = self.root\n", " for c in k:\n", " if c not in cur:\n", " return None # key wasn't in the trie\n", " cur = cur[c]\n", " # get value, or None if there's no value associated with this node\n", " return cur.get('value')" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "code", "collapsed": false, "input": [ "mp = TrieMap([(\"hello\", \"value 1\"), (\"there\", 2), (\"the\", \"value 3\")])" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [ "mp.query(\"hello\")" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "pyout", "prompt_number": 3, "text": [ "'value 1'" ] } ], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [ "mp.query(\"hello there\") # returns None" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 4 }, { "cell_type": "code", "collapsed": false, "input": [ "mp.query(\"there\")" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "pyout", "prompt_number": 5, "text": [ "2" ] } ], "prompt_number": 5 }, { "cell_type": "code", "collapsed": false, "input": [ "mp.query(\"ther\") # returns None" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 6 }, { "cell_type": "code", "collapsed": false, "input": [ "mp.query(\"the\")" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "pyout", "prompt_number": 7, "text": [ "'value 3'" ] } ], "prompt_number": 7 }, { "cell_type": "code", "collapsed": false, "input": [ "mp.query(\"\") # returns None" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 8 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 8 } ], "metadata": {} } ] }