Mercurial > public > think_complexity
comparison ch3ex5.py @ 20:0326803882ad
Finally completing Ch. 3, exercise 5: write a TreeMap that uses a red-black
tree.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Thu, 27 Dec 2012 15:30:49 -0600 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| 19:3c74185c5047 | 20:0326803882ad |
|---|---|
| 1 """Chapter 3, exercise 5. | |
| 2 | |
| 3 "A drawback of hashtables is that the elements have to be hashable, which usually | |
| 4 means they have to be immutable. That's why, in Python, you can use tuples but | |
| 5 not lists as keys in a dictionary. An alternative is to use a tree-based map. | |
| 6 Write an implementation of the map interface called TreeMap that uses | |
| 7 a red-black tree to perform add and get in log time." | |
| 8 | |
| 9 | |
| 10 """ | |
| 11 import redblacktree | |
| 12 | |
| 13 | |
| 14 class TreeMap(object): | |
| 15 """A tree-based map class.""" | |
| 16 | |
| 17 def __init__(self): | |
| 18 self.tree = redblacktree.Tree() | |
| 19 | |
| 20 def get(self, k): | |
| 21 """Looks up the key (k) and returns the corresponding value, or raises | |
| 22 a KeyError if the key is not found. | |
| 23 | |
| 24 """ | |
| 25 return self.tree.find(k) | |
| 26 | |
| 27 def add(self, k, v): | |
| 28 """Adds the key/value pair (k, v) to the tree. If the key already | |
| 29 exists, the value is updated to the new value v. | |
| 30 | |
| 31 Returns True if the pair was inserted, and False if the key already | |
| 32 existed and the tree was updated. | |
| 33 | |
| 34 """ | |
| 35 node, inserted = self.tree.insert(k, v) | |
| 36 if not inserted: | |
| 37 node.value = v | |
| 38 return inserted | |
| 39 | |
| 40 def remove(self, k): | |
| 41 """Removes the mapping with the given key (k). | |
| 42 Raises a KeyError if the mapping was not found. | |
| 43 | |
| 44 """ | |
| 45 result = self.tree.remove(k) | |
| 46 if not result: | |
| 47 raise KeyError | |
| 48 | |
| 49 def __len__(self): | |
| 50 """Returns the number of mappings in the map.""" | |
| 51 return len(self.tree) | |
| 52 | |
| 53 | |
| 54 def main(script): | |
| 55 import string | |
| 56 m = TreeMap() | |
| 57 s = string.ascii_lowercase | |
| 58 | |
| 59 for k, v in enumerate(s): | |
| 60 m.add([k], v) | |
| 61 | |
| 62 for k in range(len(s)): | |
| 63 key = [k] | |
| 64 print key, m.get(key) | |
| 65 m.remove(key) | |
| 66 | |
| 67 assert len(m) == 0 | |
| 68 | |
| 69 if __name__ == '__main__': | |
| 70 import sys | |
| 71 main(*sys.argv) |