Mercurial > public > think_complexity

comparison ch3ex4.py @ 14:bc2c07a059be

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Completing Ch 3.3, exercise 4.2.
author Brian Neal <bgneal@gmail.com>
date Mon, 10 Dec 2012 19:58:03 -0600
parents be7f2cd15faf
children
comparison
equal deleted inserted replaced
13:be7f2cd15faf 14:bc2c07a059be
59 def get(self, k): 59 def get(self, k):
60 """Finds the right LinearMap for key (k) and looks up (k) in it.""" 60 """Finds the right LinearMap for key (k) and looks up (k) in it."""
61 m = self.find_map(k) 61 m = self.find_map(k)
62 return m.get(k) 62 return m.get(k)
63 63
64 def iteritems(self):
65 """Generator function to yield items in the map."""
66 for lm in self.maps:
67 for t in lm.items:
68 yield t
69
64 70
65 class HashMap(object): 71 class HashMap(object):
66 """An implementation of a hashtable using a BetterMap 72 """An implementation of a hashtable using a BetterMap
67 that grows so that the number of items never exceeds the number 73 that grows so that the number of items never exceeds the number
68 of LinearMaps. 74 of LinearMaps.
90 96
91 def resize(self): 97 def resize(self):
92 """Makes a new map, twice as big, and rehashes the items.""" 98 """Makes a new map, twice as big, and rehashes the items."""
93 new_maps = BetterMap(self.num * 2) 99 new_maps = BetterMap(self.num * 2)
94 100
95 for m in self.maps.maps: 101 for k, v in self.maps.iteritems():
96 for k, v in m.items: 102 new_maps.add(k, v)
97 new_maps.add(k, v)
98 103
99 self.maps = new_maps 104 self.maps = new_maps
100 105
101 106
102 def main(script): 107 def main(script):