Created
September 18, 2013 02:17
-
-
Save BenLangmead/6603619 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"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": {} | |
} | |
] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment