Welcome, guest | Sign In | My Account | Store | Cart

Implementation of multimap based on lists, dicts, or sets using Python 2.5 defaultdict.

Python, 105 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
"""  
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()

I wanted to implement multimap so that its notation would be concise, its containers could be varied, and would only allow values to be added to proper containers. I also wanted to leverage off existing Python libraries as much as possible -- specifically collections.defaultdict and sets.Set.

Initially I tried inheriting from defaultdict, but overriding __setitem__ causes a recursion overflow when creating a new key presumably because the creation causes a __setitem__ call with the new empty set and then loops.

1 comment

Gabriel Genellina 14 years, 9 months ago  # | flag

2.5 is rather old by now. In order to ease portability to current (and future) Python versions, it would be best to implement the MutableMapping interfase; see http://docs.python.org/library/collections.html#abcs-abstract-base-classes If you do, you get the other mapping methods for free (you may need to copy part of the ABC implementation for use in Python 2.5)