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.

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 `dict`

s) 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.

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').

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

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:

I think that is clearer than:

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.