On Wed, 14 Jan 2009 16:30:36 -0800, Aaron Brady wrote: > Hi, this is a continuation of something that comes up now and again > about reverse lookups on dictionaries, as well as a follow-up to my > pursuit of a Relation class from earlier.
[...] > What's the best way to construct this class? Or, do you have an > argument that it could not be simpler than using a relational db? > Brainstorming, not flamestorming. Here's a lightweight solution that uses lazy calculation of the reverse dict. It makes a number of assumptions: - both keys and values will be hashable and unique; - the dict won't be so large that calculating the reverse dictionary will be time consuming; - modifications to instance.reverse are undefined. Usage: >>> d = ReverseDict(x=2, y=3, z=4) >>> d['x'] 2 >>> d.reverse[2] 'x' >>> d['a'] = 0 >>> d.reverse[0] 'a' def make_dirty(func): from functools import wraps @wraps(func) def f(self, *args, **kwargs): self._dirty = True return func(self, *args, **kwargs) return f # only tested a little bit class ReverseDict(dict): def __init__(self, *args, **kwargs): super(ReverseDict, self).__init__(*args, **kwargs) self._dirty = True @make_dirty def clear(): super(ReverseDict, self).clear() @make_dirty def __setitem__(self, key, value): super(ReverseDict, self).__setitem__(key, value) @make_dirty def __delitem__(self, key): super(ReverseDict, self).__delitem__() @make_dirty def pop(self, key, *arg): return super(ReverseDict, self).pop(key, *arg) @make_dirty def popitem(self): return super(ReverseDict, self).popitem() @make_dirty def setdefault(self, key, value=None): return super(ReverseDict, self).setdefault(key, value) @make_dirty def update(self, other): return super(ReverseDict, self).update(other) @property def reverse(self): if self._dirty: # Modify this to support repeated and non-hashable values. self._reverse = dict((value, key) for (key, value) in self.iteritems()) self._dirty = False return self._reverse An even more lightweight solution is to give up O(1) for the reverse lookup: # untested class ReversableDict(dict): def lookupvalue(self, value): for k,v in self.iteritems(): if v == value: return k raise ValueError('value not found') def lookupallvalues(self, value): results = [] for k,v in self.iteritems(): if v == value: results.append(k) return results -- Steven -- http://mail.python.org/mailman/listinfo/python-list