[Checkins] SVN: Sandbox/faassen/iface/src/iface/mapping. * improved implementation of Map

[Martijn Faassen]

Log message for revision 107755:
  * improved implementation of Map
  
  * we started to write doctests and code for MultiMap, but we haven't
    tested it yet so doesn't work properly.
  

Changed:
  U   Sandbox/faassen/iface/src/iface/mapping.py
  U   Sandbox/faassen/iface/src/iface/mapping.txt

-=-
Modified: Sandbox/faassen/iface/src/iface/mapping.py
===================================================================
--- Sandbox/faassen/iface/src/iface/mapping.py	2010-01-06 21:44:23 UTC (rev 107754)
+++ Sandbox/faassen/iface/src/iface/mapping.py	2010-01-06 22:55:47 UTC (rev 107755)
@@ -24,6 +24,12 @@
         return "<MapKey: %r>" % self.key
 
 class Map(dict):
+
+    # sometimes we want to look up things exactly in the underlying
+    # dictionary
+    exact_getitem = dict.__getitem__
+    exact_get = dict.get
+    
     def __getitem__(self, key):
         for mapkey in key._parent_mapkeys:
             try:
@@ -32,4 +38,40 @@
                 pass
         raise KeyError(key)
 
+    def get(self, key, default=None):
+        try:
+            return self[key]
+        except KeyError:
+            return default
 
+class MultiMap(object):
+    def __init__(self):
+        self._by_arity = {}
+        
+    def __setitem__(self, key, value):
+        arity = len(key)
+        key = (arity,) + tuple(key)
+        map = self._by_arity
+        for k in key[:-1]:
+           submap = map.get(k)
+           if submap is None:
+               submap = map[k] = Map()
+           map = submap
+        map[key[-1]] = value
+                    
+    def __delitem__(self, key, value):
+        arity = len(key)
+        key = (arity,) + tuple(key)
+        map = self._by_arity
+        for k in key[:-1]:
+            map = dict(map)[k]
+        del map[key[-1]]
+    
+    def __getitem__(self, key, value):
+        arity = len(key)
+        key = (arity,) + tuple(key)
+        map = self._by_arity
+        for k in key[:-1]:
+            map = map[k]
+        return map[key[-1]]
+

Modified: Sandbox/faassen/iface/src/iface/mapping.txt
===================================================================
--- Sandbox/faassen/iface/src/iface/mapping.txt	2010-01-06 21:44:23 UTC (rev 107754)
+++ Sandbox/faassen/iface/src/iface/mapping.txt	2010-01-06 22:55:47 UTC (rev 107755)
@@ -1,6 +1,9 @@
 A mapping with acyclic directed graph key
 =========================================
 
+Map
+---
+
 A normal mapping (dictionary) in Python has keys that are completely
 independent from each other. If you look up a particular key, either that
 key is present in the mapping or not at all.
@@ -72,6 +75,9 @@
     ...
   KeyError: <MapKey: 'a'>
 
+Looking up ancestors
+~~~~~~~~~~~~~~~~~~~~
+
 Now for the special behavor. Since ``d`` does have ``b`` as an
 ancestor, we can look it up, finding the value for B::
 
@@ -89,6 +95,11 @@
   >>> map[d]
   u'Value for B'
 
+We can also use ``.get``::
+
+  >>> map.get(d)
+  u'Value for B'
+
 When we take out the value for ``b`` we get the value for ``c`` when we
 look up ``d``::
   
@@ -103,6 +114,63 @@
   >>> map[d]
   u'Value for D'
 
+We remove ``d`` again so that we find the value for c again when we
+look up ``d``::
+
+  >>> del map[d]
+  >>> map[d]
+  u'Value for C'
+
+Sometimes it is useful to look up the key as if the map *is* a real
+dictionary, without the ancestor lookup behavior to kick in. We have
+two methods for this, the equivalent of the normal ``dictionary[]``
+(__getitem__) lookup, and the equivalent of the normal
+``dictionary.get`` lookup, named ``exact_getitem`` and ``exact_get``::
+
+  >>> map.exact_getitem(d)
+  Traceback (most recent call last):
+   ...
+  KeyError: <MapKey: 'd'>
+
+  >>> print map.exact_get(d)
+  None
+
+  >>> map.exact_getitem(c)
+  u'Value for C'
+ 
+  >>> map.exact_get(c)
+  u'Value for C'
+
+
+MultiMap
+--------
+
+A MultiMap is a map that takes sequences of MapKey objects as its
+key. We call such a sequence of MapKeys a MultiMapKey.
+
+When looking up a MultiMapKey in a MultiMap, it is compared
+component-wise to the MultiMapKeys registered in the MultiMap.  Each
+of the components of a MultiMapKey found must be either equal to or a
+parent of the corresponding component of the MultiMapKey being looked
+up.  If more than one MultiMapKey could be found by a lookup, the one
+whose first component matches most specifically wins, the other
+components being considered as subordinate comparison criteria, in
+order.
+
+We define gamma, which has parent beta, which has parent alpha::
+
+  >>> alpha = MapKey('alpha')
+  >>> beta = MapKey('beta', [alpha])
+  >>> gamma = MapKey('gamma', [beta])
+
+We define three, which has parent two, which has parent one::
+
+  >>> one = MapKey('one')
+  >>> two = MapKey('two', [one])
+  >>> three = MapKey('three', [two])
+
+Now we create a MultiMap
+
 next: multi lookup. What is the behavior of zope.interface? Do earlier
 entries in the lookup list always weigh more heavily than the second
 one? We need backtracking in case we don't find anything for the next