{
 "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": {}
  }
 ]
}