bgneal@12: """ Code example from Complexity and Computation, a book about
bgneal@12: exploring complexity science with Python.  Available free from
bgneal@12: 
bgneal@12: http://greenteapress.com/complexity
bgneal@12: 
bgneal@12: Copyright 2011 Allen B. Downey.
bgneal@12: Distributed under the GNU General Public License at gnu.org/licenses/gpl.html.
bgneal@12: """
bgneal@12: 
bgneal@12: import string
bgneal@12: 
bgneal@12: 
bgneal@12: class LinearMap(object):
bgneal@12:     """A simple implementation of a map using a list of tuples
bgneal@12:     where each tuple is a key-value pair."""
bgneal@12: 
bgneal@12:     def __init__(self):
bgneal@12:         self.items = []
bgneal@12: 
bgneal@12:     def add(self, k, v):
bgneal@12:         """Adds a new item that maps from key (k) to value (v).
bgneal@12:         Assumes that they keys are unique."""
bgneal@12:         self.items.append((k, v))
bgneal@12: 
bgneal@12:     def get(self, k):
bgneal@12:         """Looks up the key (k) and returns the corresponding value,
bgneal@12:         or raises KeyError if the key is not found."""
bgneal@12:         for key, val in self.items:
bgneal@12:             if key == k:
bgneal@12:                 return val
bgneal@12:         raise KeyError
bgneal@12: 
bgneal@12: 
bgneal@12: class BetterMap(object):
bgneal@12:     """A faster implementation of a map using a list of LinearMaps
bgneal@12:     and the built-in function hash() to determine which LinearMap
bgneal@12:     to put each key into."""
bgneal@12: 
bgneal@12:     def __init__(self, n=100):
bgneal@12:         """Appends (n) LinearMaps onto (self)."""
bgneal@12:         self.maps = []
bgneal@12:         for i in range(n):
bgneal@12:             self.maps.append(LinearMap())
bgneal@12: 
bgneal@12:     def find_map(self, k):
bgneal@12:         """Finds the right LinearMap for key (k)."""
bgneal@12:         index = hash(k) % len(self.maps)
bgneal@12:         return self.maps[index]
bgneal@12: 
bgneal@12:     def add(self, k, v):
bgneal@12:         """Adds a new item to the appropriate LinearMap for key (k)."""
bgneal@12:         m = self.find_map(k)
bgneal@12:         m.add(k, v)
bgneal@12: 
bgneal@12:     def get(self, k):
bgneal@12:         """Finds the right LinearMap for key (k) and looks up (k) in it."""
bgneal@12:         m = self.find_map(k)
bgneal@12:         return m.get(k)
bgneal@12: 
bgneal@12: 
bgneal@12: class HashMap(object):
bgneal@12:     """An implementation of a hashtable using a BetterMap
bgneal@12:     that grows so that the number of items never exceeds the number
bgneal@12:     of LinearMaps.
bgneal@12: 
bgneal@12:     The amortized cost of add should be O(1) provided that the
bgneal@12:     implementation of sum in resize is linear."""
bgneal@12: 
bgneal@12:     def __init__(self):
bgneal@12:         """Starts with 2 LinearMaps and 0 items."""
bgneal@12:         self.maps = BetterMap(2)
bgneal@12:         self.num = 0
bgneal@12: 
bgneal@12:     def get(self, k):
bgneal@12:         """Looks up the key (k) and returns the corresponding value,
bgneal@12:         or raises KeyError if the key is not found."""
bgneal@12:         return self.maps.get(k)
bgneal@12: 
bgneal@12:     def add(self, k, v):
bgneal@12:         """Resize the map if necessary and adds the new item."""
bgneal@12:         if self.num == len(self.maps.maps):
bgneal@12:             self.resize()
bgneal@12: 
bgneal@12:         self.maps.add(k, v)
bgneal@12:         self.num += 1
bgneal@12: 
bgneal@12:     def resize(self):
bgneal@12:         """Makes a new map, twice as big, and rehashes the items."""
bgneal@12:         new_maps = BetterMap(self.num * 2)
bgneal@12: 
bgneal@12:         for m in self.maps.maps:
bgneal@12:             for k, v in m.items:
bgneal@12:                 new_maps.add(k, v)
bgneal@12: 
bgneal@12:         self.maps = new_maps
bgneal@12: 
bgneal@12: 
bgneal@12: def main(script):
bgneal@12:     m = HashMap()
bgneal@12:     s = string.ascii_lowercase
bgneal@12: 
bgneal@12:     for k, v in enumerate(s):
bgneal@12:         m.add(k, v)
bgneal@12: 
bgneal@12:     for k in range(len(s)):
bgneal@12:         print k, m.get(k)
bgneal@12: 
bgneal@12: 
bgneal@12: if __name__ == '__main__':
bgneal@12:     import sys
bgneal@12:     main(*sys.argv)