# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1355189807 21600
# Node ID b75bf8bfa2cfe52b980a28901b4df2cc99792505
# Parent  0f98bcb5bd3f8d3d1b5f29ac4ca6d532c5cfa509
Adding author's Map.py as ch3ex4.py to represent the original version before
working on the exercise.

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