"""
The multimap data structure associates multiple values to a key.
In this module the multimap is implemented by a dictionary in which each key is
associated to a container, which can be a list, a dictionary, or a set.
These containers are created, accessed, and extended using the usual array
notation, e.g. m["a"] = 1, m["a"] = 2 creates a container for key "a"
containing 1 and 2. An item within a container can be removed using the
"remove" method.
Requires Python 2.5.
"""
import collections
import sets
class Map(object):
""" Map wraps a dictionary. It is essentially an abstract class from which
specific multimaps are subclassed. """
def __init__(self):
self._dict = {}
def __repr__(self):
return "%s(%s)" % (self.__class__.__name__, repr(self._dict))
__str__ = __repr__
def __getitem__(self, key):
return self._dict[key]
def __setitem__(self, key, value):
self._dict[key] = value
def __delitem__(self, key):
del self._dict[key]
def remove(self, key, value):
del self._dict[key]
def dict(self):
""" Allows access to internal dictionary, if necessary. Caution: multimaps
will break if keys are not associated with proper container."""
return self._dict
class ListMultimap(Map):
""" ListMultimap is based on lists and allows multiple instances of same value. """
def __init__(self):
self._dict = collections.defaultdict(list)
def __setitem__(self, key, value):
self._dict[key].append(value)
def remove(self, key, value):
self._dict[key].remove(value)
class SetMultimap(Map):
""" SetMultimap is based on sets and prevents multiple instances of same value. """
def __init__(self):
self._dict = collections.defaultdict(sets.Set)
def __setitem__(self, key, value):
self._dict[key].add(value)
def remove(self, key, value):
self._dict[key].remove(value)
class DictMultimap(Map):
""" DictMultimap is based on dicts and allows fast tests for membership. """
def __init__(self):
self._dict = collections.defaultdict(dict)
def __setitem__(self, key, value):
self._dict[key][value] = True
def remove(self, key, value):
del self._dict[key][value]
def test():
def test_multimap(m):
print "__________________________________"
print m["a"]
m["a"] = 1
m["a"] = 2
m["a"] = 2
m["a"] = 3
m["a"] = 4
print m
m.remove("a", 4)
print m
print ("a" in m.dict())
print m["a"]
m["a"] = 5
m["b"] = 6
print m
del m["b"]
print m
print (3 in m["a"])
test_multimap(ListMultimap())
test_multimap(SetMultimap())
test_multimap(DictMultimap())
if __name__ == "__main__":
test()
