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

A Flipdict is a python dict subclass that maintains a one-to-one inverse mapping. Each key maps to a unique value, and each value maps back to that same key. Each instance has a "flip" attribute to access the inverse mapping.

Python, 189 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
_NOTFOUND = object()


class Flipdict(dict):
    """An injective (one-to-one) python dict.  Ensures that each key maps
    to a unique value, and each value maps back to that same key.

    A Flipdict is a dict, implementing the dict API::
        >>> fd = Flipdict({1: 'one', 2: 'two', 3: 'three'})
        >>> fd[1]
        'one'
        >>> fd.setdefault(4, 'four')
        'four'
        >>> fd
        Flipdict({1: 'one', 2: 'two', 3: 'three', 4: 'four'})

    Each Flipdict has a "flip" attribute, its inverse mapping::
        >>> fd is fd.flip.flip
        True
        >>> sorted(fd.flip.items())
        [('four', 4), ('one', 1), ('three', 3), ('two', 2)]

    Just like a dict, remapping a key will erase the old mapping.
    IMPORTANT: Suppose a Flipdict maps key K to value V. Then mapping a
    *new* key to the value V will raise KeyError::
        >>> fd[4444] = 'four'
        Traceback (most recent call last):
        ....
        KeyError: "(key,val) would erase mapping for value 'four'"

    This avoids a subtle situation.  The alternative is to silently erase
    the existing pair (K,V)!  Instead, explicitly use the "flip" attribute
    like a python dict::
        >>> fd.flip['four'] = 4444
        >>> fd
        Flipdict({1: 'one', 2: 'two', 3: 'three', 4444: 'four'})
    """

    def __init__(self, *args, **kw):
        """Cf. dict.__init__

        Examples::
            >>> fd = Flipdict( zip((1, 2, 3), ('one', 'two', 'three')) )
            >>> fd == Flipdict({1: 'one', 2: 'two', 3: 'three'})
            True
            >>> fd == Flipdict(one=1, two=2, three=3).flip
            True

        IMPORTANT: Mapping many keys to the same value will raise KeyError.
        """
        self._flip = dict.__new__(self.__class__)
        setattr(self._flip, "_flip", self)
        for key, val in dict(*args, **kw).iteritems():
            self[key] = val

    @property
    def flip(self):
        """The inverse mapping.

        Examples::
            >>> fd = Flipdict({1: 'one', 2: 'two', 3: 'three'})
            >>> fd.flip['two']
            2
            >>> fd is fd.flip.flip
            True
        """
        return self._flip


    #{ Non-mutating methods that are NOT delegated to the dict superclass.

    def __repr__(self):
        return "%s(%r)" % (self.__class__.__name__, dict(self))

    __str__ = __repr__

    def copy(self):
        return self.__class__(self)

    @classmethod
    def fromkeys(cls, keys, value=None):
        """
        NOTE: This method is mostly useless for a Flipdict, because
        each key must map to a UNIQUE value.
        """
        return cls(dict.fromkeys(keys, value))

    #}


    #{ Mutating methods.  These must keep the inverse mapping in sync!

    def __setitem__(self, key, val):
        """self[key] = val (and self.flip[val] = key)

        Remapping a key will erase the old mapping (just like a dict)::
            >>> fd = Flipdict(one=1, two=2)
            >>> fd['two'] = 22
            >>> fd
            Flipdict({'two': 22, 'one': 1})
            >>> fd.flip
            Flipdict({1: 'one', 22: 'two'})

        Just like a dict, remapping a key will erase the old mapping.
        IMPORTANT: Suppose a Flipdict maps key K to value V. Then mapping a
        *new* key to the value V will raise KeyError::
            >>> fd['twenty-two'] = 22
            Traceback (most recent call last):
            ....
            KeyError: '(key,val) would erase mapping for value 22'

        This avoids a subtle situation.  The alternative is to silently
        erase the existing pair (K,V)!  Instead, explicitly use the "flip"
        attribute like a python dict::
            >>> fd.flip[22] = 'twenty-two'
            >>> sorted(fd.items())
            [('one', 1), ('twenty-two', 22)]
        """
        k = self._flip.get(val, _NOTFOUND)
        if not (k is _NOTFOUND or k==key):
            raise KeyError('(key,val) would erase mapping for value %r' % val)

        v = self.get(key, _NOTFOUND)
        if v is not _NOTFOUND:
            dict.__delitem__(self._flip, v)

        dict.__setitem__(self,       key, val)
        dict.__setitem__(self._flip, val, key)

    def setdefault(self, key, default = None):
        # Copied from python's UserDict.DictMixin code.
        try:
            return self[key]
        except KeyError:
            self[key] = default
            return default

    def update(self, other = None, **kwargs):
        # Copied from python's UserDict.DictMixin code.
        # Make progressively weaker assumptions about "other"
        if other is None:
            pass
        elif hasattr(other, 'iteritems'):  # iteritems saves memory and lookups
            for k, v in other.iteritems():
                self[k] = v
        elif hasattr(other, 'keys'):
            for k in other.keys():
                self[k] = other[k]
        else:
            for k, v in other:
                self[k] = v
        if kwargs:
            self.update(kwargs)

    def __delitem__(self, key):
        val = dict.pop(self, key)
        dict.__delitem__(self._flip, val)

    def pop(self, key, *args):
        val = dict.pop(self, key, *args)
        dict.__delitem__(self._flip, val)
        return val

    def popitem(self):
        key, val = dict.popitem(self)
        dict.__delitem__(self._flip, val)
        return key, val

    def clear(self):
        dict.clear(self)
        dict.clear(self._flip)


def makepair(*args, **kw):
    """Returns a pair:  the Flipdict(*args, **kw) and its inverse.

    Example::
        >>> chr2num, num2chr = makepair({'a':1, 'b':2, 'c':3})
        >>> chr2num['z'] = 26
        >>> num2chr.items()
        [(1, 'a'), (2, 'b'), (3, 'c'), (26, 'z')]
    """
    fd = Flipdict(*args, **kw)
    return fd, fd.flip


if __name__=='__main__':
    import doctest
    doctest.testmod(optionflags=doctest.ELLIPSIS)

Hash-maps (such as python dicts) are amazingly useful. In some situations, it is necessary to also maintain an inverse mapping: each key must map to a unique value, and it must be easy to look up which key corresponds to a given value. One example is a phone-book that allows looking up a phone-number by name, and also looking up a name by phone-number. Another example is python's htmlentitydefs module.

Already there are recipes on ASPN such as Recipe 252143 "Invert a dictionary (one-liner)" but these are one-shot computations instead of a data-structure that supports multiple lookups. I was inspired by the Nov-2009 "python bijection" thread on comp.lang.python, and by the pypi package two_way_dict. One complication of these other approaches is a proliferation of new methods to access the inverse mapping. At first this seems necessary: for every method on a python dict, one expects a corresponding method on the inverse mapping. But I realized the inverse mapping could be accessed as a getter-property... and if that inverse mapping was also a Flipdict with its inverse mapping bound to the original ... This simplifies everything.

Flipdict is a python dict subclass. It overrides just those methods that mutate a dict, to ensure the inverse mapping is maintained. It has only one new method/attribute: its flip attribute accesses the inverse mapping. When a Flipdict is changed, it updates (maintains) its inverse mapping. Because the flip attribute is also a Flipdict, with its inverse mapping pointed at the original Flipdict, the situation is symmetric: the flip attribute can be changed and it will update (maintain) the original mapping.

IMPORTANT! With a python dict, one can re-map an existing key to a different value. With a Flipdict, it is necessary to maintain the inverse mapping. In theory, one could re-map an existing by re-mapping its corresponding value. In practice this is very confusing, and instead a Flipdict will raise KeyError in this situation --- instead you can explicitly delete the old (key,value) pair, or explicitly use a dict-like operations on the inverse mapping.

2 comments

Joshua Bronson 14 years, 4 months ago  # | flag

My version of this, which works like the above except with the inverse available as "inv" instead of "flip", is available on PyPI at http://pypi.python.org/pypi/bidict. It also has a few other niceties such as "namedbidict", an "inverted" iterator, support for the unary invert operator (~), and slice syntax to specify the inverse mapping (e.g. mapping[:'val'] = 'key').

Raymond Hettinger 13 years, 6 months ago  # | flag

ISTM that it is almost always better to just keep and update two dictionaries, perhaps with a simple helper function for adding new pairs:

name2number = {}
number2name = {}

def pair(name, number):
    name2number[name] = number
    number2name[number] = name

The two dict approach requires no new classes or learning curve, it avoids namespace conflicts between to the two sides of the bijection, and the lookups make it obvious what is being looked-up and the expected types for the input and output:

 print 'call received from %s' % number2name[x]

I think that is clearer than:

 print 'call received from %s' % name2number.flip[x]

The slice syntax in http://pypi.python.org/pypi/bidict is much clearer in this regard, but it is hard to compete with the simplicity of using two dicts.